速看！2025 CSP-J2 入門級(jí)復(fù)賽真題解析！
2025 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 第二輪認(rèn)證11月1日進(jìn)行，目前真題曝光。我們對(duì)CSP-J真題進(jìn)行了分析解讀，并擬定標(biāo)程，供大家參考，一起來(lái)看下。拼數(shù)（number）題意給定一個(gè)包含小寫字母和數(shù)字的字符串 s ，要求從小寫字母及數(shù)字的字符串 s 中選出任意多個(gè)數(shù)字 ，并按任意順序?qū)⑺鼈兤唇映梢粋€(gè)正整數(shù)。每個(gè)數(shù)字只能使用一次。求出所有能拼成的正整數(shù)中的最大值。1≤∣s∣≤106 解析把所有的數(shù)字找出來(lái)，放在桶里面倒序輸出，或者倒序排個(gè)序輸出都可以。標(biāo)程座位（seat）題意考場(chǎng)共有 n 行 m 列座位，共 n×m 名考生?？忌凑粘煽?jī)由高到低，以“蛇形”順序分配座位。蛇形分配的規(guī)則是：先從第1列第1行向下到第 ??n 行，然后轉(zhuǎn)向第2列第 n 行向上到第1行，再轉(zhuǎn)向第3列第1行向下到第 n 行，以此類推。給定考場(chǎng)的行數(shù) n、列數(shù) m 和所有考生的成績(jī) a1,a2,?,an×m (其中 a1 是小R的成績(jī))，要求確定小R的座位所在的列數(shù) c 和行數(shù)r。解析把數(shù)據(jù)排個(gè)序，找到a[1]所在的位次，然后將位次-1分別對(duì)行數(shù)相除和求余，除出來(lái)的就是列數(shù)，求余出來(lái)的就是行數(shù)，不過(guò)行數(shù)要根據(jù)列數(shù)的奇偶性正序或者倒序。標(biāo)程異或和（xor）題意給定一個(gè)長(zhǎng)度為 n 的非負(fù)整數(shù)序列a1,a2,?,an 和一個(gè)非負(fù)整數(shù) k。定義一個(gè)區(qū)間[l,r] 的權(quán)值為該區(qū)間內(nèi)所有元素的二進(jìn)制按位異或和。目標(biāo)是選擇序列中盡可能多的不相交的區(qū)間，使得每個(gè)區(qū)間的權(quán)值都等于 k。1≤n≤5×105 0≤k, ai<220解析貪心，對(duì)于每個(gè)i來(lái)說(shuō)，只要能夠找到前面某一個(gè)數(shù)，使得這段區(qū)間異或和是k那么就肯定選，不然往后拖的話不會(huì)讓答案更優(yōu)。于是先求出前綴異或和s，對(duì)于每個(gè)s[i]， 看能不能找到上一個(gè)出現(xiàn)的s[i]的位置last，可以就說(shuō)明last+1到i構(gòu)成了一個(gè)區(qū)間，維護(hù)最后一次的右端點(diǎn)right，只要last>=right就說(shuō)明形成一個(gè)新區(qū)間，線性掃一遍就可以了，O(n)標(biāo)程解法一多邊形（polygon）題意有 n 根小木棍，長(zhǎng)度分別為a1,a2,?,an。從這 n 根木棍中選出 m 根 (m≥3)，它們能拼成一個(gè)多邊形當(dāng)且僅當(dāng)所有選出木棍的長(zhǎng)度之和大于最長(zhǎng)木棍長(zhǎng)度的兩倍。 要求計(jì)算出有多少種選擇小木棍的方案，使得選出的小木棍能夠拼成一個(gè)多邊形，答案對(duì) 998244353取模。3≤n,ai≤5000解析簡(jiǎn)單的01背包，先背包求出F[i][j]表示前i個(gè)數(shù)能夠湊成和為j的方案數(shù)，那么對(duì)于每個(gè)數(shù)a[i]，所有的F[i-1][0-a[i]]都是不合法的方案，把所有這樣的方案累加，最后再用2n 1減去不合法方案即可。標(biāo)程
2025年11月03日
閩公網(wǎng)安備 35021102000975號(hào)
