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

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

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

一、简答题

1. 简答题

1、廊桥分配


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;bits/stdc++.h&gt; using namespace std; const int Maxn = 1e5 + 5; struct e {     int st, ed; } a[Maxn]; bool cmp(e x, e y) {     return x.st &lt; y.st; } priority_queue&lt;int&gt; hp_id; priority_queue&lt;pair&lt;int, int&gt;&gt; hp_ed; int n, m1, m2, ca[Maxn], cb[Maxn]; int main() {     scanf("%d%d%d", &amp;n, &amp;m1, &amp;m2);          for (int i = 1; i &lt;= m1; ++i) {         scanf("%d%d", &amp;a[i].st, &amp;a[i].ed);     }          sort(a + 1, a + m1 + 1, cmp);          for (int i = 1; i &lt;= n; ++i) {         hp_id.push(-i);     }          for (int i = 1; i &lt;= m1; ++i) {         if (!hp_ed.empty()) {             while (-hp_ed.top().first &lt; a[i].st) {                 hp_id.push(-hp_ed.top().second);                 hp_ed.pop();                 if (hp_ed.empty()) {                     break;                 }             }         }                  if (!hp_id.empty()) {             int x = -hp_id.top();             hp_id.pop();             ca[x]++;             hp_ed.push(make_pair(-a[i].ed, x));         }     }          for (int i = 1; i &lt;= n; ++i) {         ca[i] += ca[i - 1];     }          while (!hp_ed.empty()) {         hp_ed.pop();     }     while (!hp_id.empty()) {         hp_id.pop();     }          for (int i = 1; i &lt;= m2; ++i) {         scanf("%d%d", &amp;a[i].st, &amp;a[i].ed);     }          sort(a + 1, a + m2 + 1, cmp);          for (int i = 1; i &lt;= n; ++i) {         hp_id.push(-i);     }          for (int i = 1; i &lt;= m2; ++i) {         if (!hp_ed.empty()) {             while (-hp_ed.top().first &lt; a[i].st) {                 hp_id.push(-hp_ed.top().second);                 hp_ed.pop();                 if (hp_ed.empty()) {                     break;                 }             }         }                  if (!hp_id.empty()) {             int x = -hp_id.top();             hp_id.pop();             cb[x]++;             hp_ed.push(make_pair(-a[i].ed, x));         }     }          for (int i = 1; i &lt;= n; ++i) {         cb[i] += cb[i - 1];     }          int mx_ans = 0;     for (int i = 0; i &lt;= n; ++i) {         mx_ans = max(mx_ans, ca[i] + cb[n - i]);     }          printf("%d", mx_ans);          return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;bits/stdc++.h&gt; using namespace std; // 计算某类航班(国内或国际)分配bridgeNum个廊桥时,能停靠的最大飞机数 int countPlanes(vector&lt;pair&lt;int, int&gt;&gt;&amp; flights, int bridgeNum) {     if (bridgeNum == 0) return 0;     sort(flights.begin(), flights.end()); // 按到达时间升序排序     // used: 存储(离开时间, 廊桥编号),小根堆(按离开时间排序,便于释放过期廊桥)     priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, greater&lt;&gt;&gt; used;     // idle: 存储空闲廊桥编号,小根堆(便于分配最小编号的空闲廊桥)     priority_queue&lt;int, vector&lt;int&gt;, greater&lt;&gt;&gt; idle;     for (int i = 1; i &lt;= bridgeNum; ++i) {         idle.push(i);     }     int res = 0;     for (auto&amp; flight : flights) {         int arrTime = flight.first, depTime = flight.second;         // 释放所有离开时间 &lt;= 当前航班到达时间的廊桥(将这些廊桥加入空闲队列)         while (!used.empty() &amp;&amp; used.top().first &lt;= arrTime) {             idle.push(used.top().second);             used.pop();         }         // 若有空闲廊桥,分配给当前航班         if (!idle.empty()) {             int bridgeId = idle.top();             idle.pop();             used.push({depTime, bridgeId});             res++;         }     }     return res; } int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int n, m1, m2;     cin &gt;&gt; n &gt;&gt; m1 &gt;&gt; m2;     vector&lt;pair&lt;int, int&gt;&gt; domestic, international;     // 读取国内航班信息     for (int i = 0; i &lt; m1; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         domestic.emplace_back(a, b);     }     // 读取国际航班信息     for (int i = 0; i &lt; m2; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         international.emplace_back(a, b);     }     // 计算国内分配0~n个廊桥时的最大停靠数     vector&lt;int&gt; ca(n + 1);     for (int i = 0; i &lt;= n; ++i) {         ca[i] = countPlanes(domestic, i);     }     // 计算国际分配0~n个廊桥时的最大停靠数     vector&lt;int&gt; cb(n + 1);     for (int i = 0; i &lt;= n; ++i) {         cb[i] = countPlanes(international, i);     }     // 枚举所有分配方案,找到最大值     int maxAns = 0;     for (int i = 0; i &lt;= n; ++i) {         maxAns = max(maxAns, ca[i] + cb[n - i]);     }     cout &lt;&lt; maxAns &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。
2. 简答题

2、括号序列


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;bits/stdc++.h&gt; #define LL long long using namespace std; const int N = 550, mo = 1e9 + 7; LL dp[N][N][5]; int n, k; char S[N]; signed main() {     scanf("%d%d", &amp;n, &amp;k);     scanf("%s", S + 1);          // 初始化边界     for (int i = 1; i &lt;= n; ++i) {         dp[i][i - 1][0] = 1;     }          // 枚举区间长度     for (int len = 1; len &lt;= n; ++len) {         // 枚举左右端点         for (int i = 1, j = i + len - 1; j &lt;= n; ++i, ++j) {             // 处理长度不超过k的*或?序列             if (len &lt;= k &amp;&amp; dp[i][j - 1][0] &amp;&amp; (S[j] == '*' || S[j] == '?')) {                 dp[i][j][0] = 1;             }                          // 用子区间转移(长度至少为2才有意义)             if (len &gt;= 2) {                 // 判断左右端点是否为匹配的括号                 if ((S[i] == '(' || S[i] == '?') &amp;&amp; (S[j] == ')' || S[j] == '?')) {                     dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] +                                     dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % mo;                 }                                  // 枚举子区间的断点                 for (int t = i; t &lt;= j - 1; ++t) {                     dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % mo;                     dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % mo;                     dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % mo;                 }             }                          // 合并状态             dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % mo;         }     }          printf("%lld", dp[1][n][3]);     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;bits/stdc++.h&gt; using namespace std; typedef long long LL; const int N = 550; const int MOD = 1e9 + 7; int n, k; char s[N]; LL dp[N][N][5]; // dp[i][j][0~4] 分别对应不同状态 int main() {     scanf("%d%d", &amp;n, &amp;k);     scanf("%s", s + 1); // 字符串从下标1开始存储     // 初始化:空区间是合法的*串(用于后续转移)     for (int i = 1; i &lt;= n; ++i) {         dp[i][i - 1][0] = 1;     }     // 枚举区间长度     for (int len = 1; len &lt;= n; ++len) {         // 枚举左端点i,右端点j = i + len - 1         for (int i = 1, j = i + len - 1; j &lt;= n; ++i, ++j) {             // 状态0:*串,长度&lt;=k,且j位置可填*或?,且[i,j-1]是*串             if (len &lt;= k &amp;&amp; dp[i][j - 1][0] &amp;&amp; (s[j] == '*' || s[j] == '?')) {                 dp[i][j][0] = 1;             }             // 长度至少为2时,处理其他状态             if (len &gt;= 2) {                 // 状态1:(A)形式,判断i和j是否可作为括号                 if ((s[i] == '(' || s[i] == '?') &amp;&amp; (s[j] == ')' || s[j] == '?')) {                     dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] +                                     dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % MOD;                 }                 // 枚举断点t,拆分区间为[i,t]和[t+1,j]                 for (int t = i; t &lt; j; ++t) {                     // 状态2:A*B,A是状态3,B是状态0                     dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % MOD;                     // 状态3:A*B,A是状态2或3,B是状态1;或直接由状态1转移(后续会加)                     dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % MOD;                     // 状态4:A*B,A是状态0,B是状态3                     dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % MOD;                 }                 // 状态3还可由自身的状态1转移而来(总合法状态包含(A)形式)                 dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % MOD;             }         }     }     // 最终答案:整个区间[1,n]的合法超级括号序列数量(状态3)     printf("%lld\n", dp[1][n][3]);     return 0; }</pre><p></p>
这道题暂未补解析。
3. 简答题

3、回文


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int t, n, l, r, l1, r1; int a[1000010], ton1[1000010], ton[1000010], vis[1000010]; stack&lt;int&gt; q; vector&lt;int&gt; q1; int read() {     int asd = 0, qwe = 1;     char zxc;     while (!isdigit(zxc = getchar())) {         if (zxc == '-') {             qwe = -1;         }     }     while (isdigit(zxc)) {         asd = asd * 10 + zxc - '0';         zxc = getchar();     }     return asd * qwe; } int dfs(int k) {     // cout &lt;&lt; k &lt;&lt; " " &lt;&lt; l1 &lt;&lt; " " &lt;&lt; r1 &lt;&lt; " " &lt;&lt; l &lt;&lt; " " &lt;&lt; r &lt;&lt; " " &lt;&lt; q.size() &lt;&lt; endl;     if (k == n / 2) {         for (int i = 0; i &lt;= n / 2 - 1; i++) {             if (q1[i] == 1) {                 cout &lt;&lt; "L";             } else {                 cout &lt;&lt; "R";             }         }         while (!q.empty()) {             int x = q.top();             q.pop();             if (a[l] == x) {                 cout &lt;&lt; "L";                 l++;             } else {                 cout &lt;&lt; "R";                 r--;             }         }         cout &lt;&lt; endl;         return 1;     } else {         // cout &lt;&lt; ton[l1 + 1] &lt;&lt; l - 1 &lt;&lt; ton[l1 + 1] &lt;&lt; r + 1 &lt;&lt; endl;         if (vis[a[l1 + 1]] == 0 &amp;&amp; (ton[l1 + 1] == l - 1 || ton[l1 + 1] == r + 1)) {             l1++;             if (ton[l1] == l - 1) {                 l--;             } else {                 r++;             }             q1.push_back(1);             q.push(a[l1]);             vis[a[l1]] = 1;             return dfs(k + 1);         } else if (vis[a[r1 - 1]] == 0 &amp;&amp; (ton[r1 - 1] == l - 1 || ton[r1 - 1] == r + 1)) {             r1--;             if (a[ton[r1]] == a[l - 1]) {                 l--;             } else {                 r++;             }             q1.push_back(2);             q.push(a[r1]);             vis[a[r1]] = 1;             return dfs(k + 1);         } else {             return 0;         }     } } int main() {     // freopen("palin.in" , "r" , stdin);     // freopen("palin.out" , "w" , stdout);     t = read();     while (t--) {         n = read() * 2;         l1 = 0;         r1 = n + 1;                  while (!q.empty()) {             q.pop();         }         q1.clear();                  for (int i = 1; i &lt;= n; i++) {             vis[i] = ton1[i] = ton[i] = 0;         }                  for (int i = 1; i &lt;= n; i++) {             a[i] = read();             if (ton1[a[i]]) {                 ton[i] = ton1[a[i]];                 ton[ton1[a[i]]] = i;             } else {                 ton1[a[i]] = i;             }         }                  // 第一种尝试:从左侧开始         vis[a[++l1]] = 1;         l = r = ton[l1];         q1.push_back(1);         q.push(a[l1]);                  if (dfs(1) == 0) {             // 重置状态,尝试从右侧开始             for (int i = 1; i &lt;= n; i++) {                 vis[i] = 0;             }             q1.clear();             l1 = 0;             r1 = n + 1;                          while (!q.empty()) {                 q.pop();             }                          vis[a[--r1]] = 1;             l = r = ton[r1];             q1.push_back(2);             q.push(a[r1]);                          if (dfs(1) == 0) {                 cout &lt;&lt; -1 &lt;&lt; endl;             }         }     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
4. 简答题

4、交通规划


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;queue&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; typedef long long ll; const int MAXN = 360005;  // 增大数组容量适配题目规模 const ll INF = 1e18; struct Edge {     int to, rev;     ll cap;     Edge(int t, int r, ll c) : to(t), rev(r), cap(c) {} }; vector&lt;Edge&gt; g[MAXN]; int level[MAXN], iter[MAXN]; int n, m, T; // 添加双向边 void add_edge(int from, int to, ll cap) {     g[from].emplace_back(to, (int)g[to].size(), cap);     g[to].emplace_back(from, (int)g[from].size() - 1, 0);  // 反向边初始容量为0 } // BFS构建层次图 void bfs(int s) {     memset(level, -1, sizeof(level));     queue&lt;int&gt; q;     level[s] = 0;     q.push(s);     while (!q.empty()) {         int u = q.front();         q.pop();         for (const Edge&amp; e : g[u]) {             if (e.cap &gt; 0 &amp;&amp; level[e.to] &lt; 0) {                 level[e.to] = level[u] + 1;                 q.push(e.to);             }         }     } } // DFS寻找增广路 ll dfs(int u, int t, ll f) {     if (u == t) return f;     for (int&amp; i = iter[u]; i &lt; g[u].size(); ++i) {         Edge&amp; e = g[u][i];         if (e.cap &gt; 0 &amp;&amp; level[u] &lt; level[e.to]) {             ll d = dfs(e.to, t, min(f, e.cap));             if (d &gt; 0) {                 e.cap -= d;                 g[e.to][e.rev].cap += d;                 return d;             }         }     }     return 0; } // 计算最大流(最小割) ll max_flow(int s, int t) {     ll flow = 0;     while (true) {         bfs(s);         if (level[t] &lt; 0) return flow;         memset(iter, 0, sizeof(iter));         ll f;         while ((f = dfs(s, t, INF)) &gt; 0) {             flow += f;         }     } } // 射线编号转网格坐标(修正版) pair&lt;int, int&gt; get_coord(int p) {     p--;  // 转为0基索引     if (p &lt; m) {                // 上边界:(1, p+1)         return {0, p};     }     p -= m;     if (p &lt; n-1) {              // 右边界:(p+2, m)         return {p+1, m-1};     }     p -= n-1;     if (p &lt; m) {                // 下边界:(n, m-p)         return {n-1, m-1 - p};     }     p -= m;                     // 左边界:(n-p, 1)     return {n-1 - p, 0}; } int main() {     // 移除文件操作,适配标准输入输出     scanf("%d%d%d", &amp;n, &amp;m, &amp;T);          // 存储水平和垂直边的权重     vector&lt;vector&lt;ll&gt;&gt; horizontal(n-1, vector&lt;ll&gt;(m));     vector&lt;vector&lt;ll&gt;&gt; vertical(n, vector&lt;ll&gt;(m-1));          // 读取水平边(上下相邻格子)     for (int i = 0; i &lt; n-1; ++i) {         for (int j = 0; j &lt; m; ++j) {             scanf("%lld", &amp;horizontal[i][j]);         }     }          // 读取垂直边(左右相邻格子)     for (int i = 0; i &lt; n; ++i) {         for (int j = 0; j &lt; m-1; ++j) {             scanf("%lld", &amp;vertical[i][j]);         }     }          while (T--) {         int k;         scanf("%d", &amp;k);                  // 清空图结构         for (int i = 0; i &lt; MAXN; ++i) {             g[i].clear();         }                  int S = 0;                  // 源点(黑色)         int T_node = n * m + 1;     // 汇点(白色)         int node_cnt = n * m;       // 网格节点总数                  // 连接水平相邻格子(i,j)和(i+1,j)         for (int i = 0; i &lt; n-1; ++i) {             for (int j = 0; j &lt; m; ++j) {                 int u = i * m + j + 1;  // 网格节点编号从1开始                 int v = (i+1) * m + j + 1;                 ll cap = horizontal[i][j];                 add_edge(u, v, cap);                 add_edge(v, u, cap);  // 双向边             }         }                  // 连接垂直相邻格子(i,j)和(i,j+1)         for (int i = 0; i &lt; n; ++i) {             for (int j = 0; j &lt; m-1; ++j) {                 int u = i * m + j + 1;                 int v = i * m + (j+1) + 1;                 ll cap = vertical[i][j];                 add_edge(u, v, cap);                 add_edge(v, u, cap);  // 双向边             }         }                  // 处理附加点约束         for (int i = 0; i &lt; k; ++i) {             ll x3;             int p, t;             scanf("%lld%d%d", &amp;x3, &amp;p, &amp;t);                          // 获取射线对应的网格坐标             auto [r, c] = get_coord(p);             if (r &lt; 0 || r &gt;= n || c &lt; 0 || c &gt;= m) {                 // 无效坐标处理                 continue;             }                          int node = r * m + c + 1;  // 转换为节点编号                          if (t == 1) {  // 必须染黑色(连接到源点)                 add_edge(S, node, INF);    // 保证不会被割开                 add_edge(node, S, x3);     // 附加权重             } else {        // 必须染白色(连接到汇点)                 add_edge(node, T_node, INF);  // 保证不会被割开                 add_edge(T_node, node, x3);   // 附加权重             }         }                  // 计算并输出最小割(最大流)         printf("%lld\n", max_flow(S, T_node));     }          return 0; }</pre><p><br/></p>
这道题暂未补解析。