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