首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 2025年CCF非专业级别软件能力认证第二轮 (CSP-S)提高级C++语言试题

2025年CCF非专业级别软件能力认证第二轮 (CSP-S)提高级C++语言试题 VIP

信息学奥赛-提高级 共 4 题 2025 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

T1社团招新

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; vector&lt;int&gt; a, b, c; int main() {     int t;     cin &gt;&gt; t;     while(t--) {         //清空vector         a.clear();b.clear();c.clear();         int n, ans = 0;         cin &gt;&gt; n;         for (int i = 1; i &lt;= n; i++) {             int x, y, z;             cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;             if (x &gt;= y &amp;&amp; x &gt;= z) {                 ans += x;                 a.push_back(x - max(y, z));             } else if (y &gt;= x &amp;&amp; y &gt;= z) {                 ans += y;                 b.push_back(y - max(x, z));             } else {                 ans += z;                 c.push_back(z - max(x, y));             }         }         //判断         n /= 2;         if (a.size() &lt;= n &amp;&amp; b.size() &lt;= n &amp;&amp; c.size() &lt;= n) {             cout &lt;&lt; ans &lt;&lt; endl;         } else {             if (a.size() &gt; n) {                 sort(a.begin(), a.end());                 for (int i = 0; i &lt; a.size()-n; i++) {                     ans -= a[i];                 }             } else if (b.size() &gt; n) {                 sort(b.begin(), b.end());                 for (int i = 0; i &lt; b.size()-n; i++) {                     ans -= b[i];                 }             } else {                 sort(c.begin(), c.end());                 for (int i = 0; i &lt; c.size()-n; i++) {                     ans -= c[i];                 }             }             cout &lt;&lt; ans &lt;&lt; endl;         }     }     return 0; }</pre>
这道题暂未补解析。
2. 简答题

T2道路修复

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int MAXN = 1e4 + 5; const int MAXM = 1e6 + 5; //快速读入  inline int read() {     int x=0,f=1;char ch=getchar();     while (ch&lt;'0'||ch&gt;'9'){if (ch=='-') f=-1;ch=getchar();}     while (ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-48;ch=getchar();}     return x*f; } //边结构体 struct edge{     int u, v;     int w;  //边权 }; int n, m, k; vector&lt;edge&gt; OG;  //原图 vector&lt;edge&gt; NG;  //新图 int c[11];        //乡镇改造费用 int fa[MAXN+10];  //并查集 bool z[11];       //标记乡镇是否被选中 //按边权排序 bool cmp(edge x, edge y) { return x.w &lt; y.w; } // 标准并查集操作 int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); } void merge(int x, int y) {     x = findroot(x);     y = findroot(y);     fa[x] = y; } //第一次kruskal,用于求出s=0的答案,并删去m条边中后续不可能被选中的边 long long kruskal_first() {     for (int i = 1; i &lt;= n; i++) fa[i] = i;  //并查集初始化     long long res = 0;     int cnt = n - 1;  //需要选取n-1条     for (edge i : OG) {         if (!cnt) return res;  //选完就退出         int x = findroot(i.u), y = findroot(i.v);         if (x != y) {             merge(x, y);  //合并             cnt--;             res += i.w;             NG.push_back(i);  //将第一次MST选中的边加入新图         }     }     return res; } //加入乡镇后的MST long long kruskal(int s) {     for (int i = 1; i &lt;= n+k; i++) fa[i] = i;  //并查集初始化     memset(z, 0, sizeof z);  //标记数组初始化     long long res = 0;     int cnt = n - 1;     for (int i = 0, j = 1; i &lt; k; i++, j &lt;&lt;= 1) {         if (s &amp; j) {  //按二进制拆分状态             z[i] = 1;             res += c[i];             cnt++;         }     }     for (edge i : NG) {         if (!cnt) return res;         //如果边的连接点有乡镇,需要判断边是否存在         if ((i.u &gt; n &amp;&amp; !z[i.u-n-1]) || (i.v &gt; n &amp;&amp; !z[i.v-n-1])) continue;         int x = findroot(i.u), y = findroot(i.v);         if (x != y) {             merge(x, y);             cnt--;             res += i.w;         }     }     return res; } int main() {     int u, v, w;     n = read();     m = read();     k = read();     for (int i = 0; i &lt; m; i++) {         u = read();         v = read();         w = read();         OG.push_back({u, v, w});     }     //排序原图并进行第一次kruskal     sort(OG.begin(), OG.end(), cmp);     long long ans = kruskal_first();     //cout &lt;&lt; ans &lt;&lt; endl;     for (int j = 0; j &lt; k; j++) {         c[j] = read();         for (int i = 1; i &lt;= n; i++) {             w = read();             NG.push_back({n+j+1, i, w});         }     }     sort(NG.begin(), NG.end(), cmp);     int MAXK = 1 &lt;&lt; k;     //对于乡镇的所有选取状态进行kruskal     for (int s = 1; s &lt; MAXK; s++) ans = min(ans, kruskal(s));     printf("%lld", ans);     return 0; }</pre>
这道题暂未补解析。
3. 简答题

T3谐音替换

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; typedef unsigned long long ll; const int P = 1e9+7, Q=1e9+9, B=457, C=997; ll next_hash (ll prev, int chr) {     ll a = prev &gt;&gt; 32, b = prev &amp; -1u; chr ++;     a = (a * B + chr) % P;     b = (b * C + chr) % Q;     return (a &lt;&lt; 32) | b; } const int maxl = 5002424; const int maxn = 200083; struct node { int pt, nxt [27]; } trie [maxl*2+maxn]; struct pn {     int rt;     unordered_map &lt;ll, int&gt; mp; } pns [maxn]; int ctc, ptc; char s [maxl], t [maxl]; void q_diff (int len, int&amp; dnq, int&amp; dxq) {     int nq = len+1, xq=-1;     int i;     for (i=0; i&lt;len; i++)     if (s [i] != t [i])     nq = min (nq, i), xq = max (xq, i);     dnq = nq; dxq = xq; } #define jnode(var,chr) if(trie[var].nxt[chr])var=trie[var].nxt[chr];else var=trie[var].nxt[chr]=++ctc #define ord(ch) (ch=='#'?26:ch-'a') void add_s (int idx) {     scanf ("%s%s", s, t);     int len = strlen (s);     if (strcmp (s, t) == 0) return;     int nq, xq; q_diff (len, nq, xq);     int i, cur = 0;     for (i=nq; i&lt;=xq; i++)     {         jnode (cur, ord (s [i]));         jnode (cur, ord (t [i]));     }     jnode (cur, 26);     for (; i&lt;len; i++)     jnode (cur, ord (s [i]));     int pt = trie [cur] .pt;     if (pt == 0) pt = trie [cur] .pt = ++ptc;     cur = pns [pt] .rt;     if (cur == 0) cur = pns [pt] .rt = ++ctc;     for (i=nq-1; i&gt;=0; i--)     jnode (cur, ord (s [i]));     trie [cur] .pt ++; } void dfs_pn (int rt, int cur, ll ch, int cn) {     pns [rt] .mp [ch] = cn = trie [cur] .pt += cn;     int i, m;     for (i=0; i&lt;27; i++)     if (m = trie [cur] .nxt [i])     dfs_pn (rt, m, next_hash (ch, i), cn); } ll hashes [maxl]; int query (void) {     scanf ("%s%s", s, t);     int len = strlen (s);     if (strlen (t) != len) return 0;     int nq, xq; q_diff (len, nq, xq);     int i, cur = 0;     for (i=1; i&lt;=nq; i++) hashes [i] = next_hash (hashes [i-1], ord (s [nq-i]));     for (i=nq; i&lt;=xq; i++)     {         if (0 == (cur = trie [cur] .nxt [ord (s [i])])) return 0;         if (0 == (cur = trie [cur] .nxt [ord (t [i])])) return 0;     }     if (0 == (cur = trie [cur] .nxt [26])) return 0;     int ans = 0;     for (i=xq; i&lt;len; i++)     {         if (trie [cur] .pt != 0)         {             int l = 0, r = nq;             pn&amp; cpn = pns [trie [cur] .pt];             while (l &lt; r)             {                 int m = l+r+1 &gt;&gt; 1;                 if (cpn.mp.count (hashes [m])) l = m;                 else r = m-1;             }             ans += cpn.mp [hashes [l]];         }         if (i != len-1)         if (0 == (cur = trie [cur] .nxt [ord (t [i+1])]))         break;     }     return ans; } int main (void) {     int n, q; scanf ("%d%d", &amp;n, &amp;q);     int i; for (i=1; i&lt;=n; i++) add_s (i);     for (i=1; i&lt;=ptc; i++) dfs_pn (i, pns [i] .rt, 0, 0);     for (i=1; i&lt;=q; i++) printf ("%d\n", query ()); }</pre>
这道题暂未补解析。
4. 简答题

T4员工招聘

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; #define pb push_back #define fi first #define se second using namespace std; bool MEM; using ll=long long; using ld=long double; using pii=pair&lt;int,int&gt;; using pll=pair&lt;ll,ll&gt;; const int I=1e9; const ll J=1e18,N=507,P=998244353; ll fac[N]; ll n,m,c[N],sum[N],k,w[N],ans; int dp[N][N][N]; char s[N]; void mian() { fac[0]=1; for (ll i=1;i&lt;N;i++) fac[i]=fac[i-1]*i%P; scanf("%lld%lld%s",&amp;n,&amp;m,s+1); for (ll i=1;i&lt;=n;i++) if (s[i]-'0'==1) k++,w[k]=i-k; if (!k) return cout&lt;&lt;"0",void(); for (ll i=1;i&lt;=n;i++) scanf("%lld",&amp;c[i]),sum[c[i]]++; for (ll i=1;i&lt;=n;i++) sum[i]+=sum[i-1]; dp[0][0][0]=1; for (ll i=1,o=1;i&lt;=k;i++) for (ll x=0;x&lt;i;x++) for (ll y=0;x+y&lt;i;y++) { (dp[i][x+1][y]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定第 i 个人走  (dp[i][x][y+1]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定他没走,容斥它  (dp[i][x][y]+=dp[i-1][x][y])%=P; // 指定他没走,不容斥它  } for (ll x=0;x&lt;=k-m;x++) for (ll y=0;x+y&lt;=k;y++) (ans+=(y&amp;1?P-1:1)*dp[k][x][y]%P*fac[n-x-y])%=P; cout&lt;&lt;ans; } bool ORY; int main() { // while (1) // int t; for (scanf("%d",&amp;t);t--;) mian(); cerr&lt;&lt;"\n"&lt;&lt;abs(&amp;MEM-&amp;ORY)/1048576&lt;&lt;"MB"; return 0; }</pre>
这道题暂未补解析。