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

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

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

一、简答题

1. 简答题

假期计划(holiday)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;algorithm&gt; #include &lt;string.h&gt; #include &lt;cctype&gt; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; typedef long long ll; typedef unsigned long long ull; const int INF = 0x3f3f3f3f; inline int read() {     char ch = getchar();     int x = 0, f = 1;     while (!isdigit(ch)) {         if (ch == '-') f = -1;         ch = getchar();     }     while (isdigit(ch)) {         x = (x &lt;&lt; 3) + (x &lt;&lt; 1) + ch - '0';         ch = getchar();     }     return x * f; } inline void write(int x) {     if (x &lt; 0) {         putchar('-');         x = -x;     }     if (x &gt; 9) {         write(x / 10);     }     putchar(x % 10 + '0'); } const int cp = 998244353; inline int ksm(int a, int b) {     int ret = 1;     for (; b; b &gt;&gt;= 1, a = 1ll * a * a % cp) {         if (b &amp; 1) {             ret = 1ll * ret * a % cp;         }     }     return ret; } inline int inv(int x) {     return ksm(x, cp - 2); } inline int rev(int p, int q) {     return 1LL * p * inv(q) % cp; } const int N = 2505; int n, m, K, pos[N][3], f[N][N]; ull a[N], ans; vector&lt;int&gt; G[N]; queue&lt;int&gt; Q; void bfs(int S) {     f[S][S] = 1;     Q.push(S);     while (!Q.empty()) {         int x = Q.front();         Q.pop();         for (auto v : G[x]) {             if (f[S][v] &lt; 0) {                 f[S][v] = f[S][x] + 1;                 Q.push(v);             }         }     } } void check(int A, int B, int C, int D) {     if (!A || !B || !C || !D) return;     if (A == B || A == C || A == D || B == C || B == D || C == D) return;     if (f[1][A] &gt; K || f[A][B] &gt; K || f[B][C] &gt; K || f[C][D] &gt; K || f[D][1] &gt; K) return;     ans = max(ans, a[A] + a[B] + a[C] + a[D]); } signed main() {     memset(f, -1, sizeof(f));     n = read(), m = read(), K = read() + 2;     for (int i = 2; i &lt;= n; ++i) {         cin &gt;&gt; a[i];     }     for (int i = 1, x, y; i &lt;= m; ++i) {         x = read(), y = read();         G[x].push_back(y);         G[y].push_back(x);     }     bfs(1);     for (int i = 2; i &lt;= n; ++i) {         bfs(i);         for (int j = 2; j &lt;= n; ++j) {             if (f[i][j] != -1 &amp;&amp; f[1][j] != -1 &amp;&amp; f[i][j] &lt;= K &amp;&amp; f[1][j] &lt;= K &amp;&amp; i != j) {                 int x = j;                 if (a[x] &gt; a[pos[i][0]]) swap(x, pos[i][0]);                 if (a[x] &gt; a[pos[i][1]]) swap(x, pos[i][1]);                 if (a[x] &gt; a[pos[i][2]]) swap(x, pos[i][2]);             }         }     }     for (int B = 2; B &lt;= n; ++B) {         for (int C = 2; C &lt;= n; ++C) {             if (B != C &amp;&amp; f[B][C] &lt;= K &amp;&amp; f[B][C] != -1) {                 for (int i = 0; i &lt; 3; ++i) {                     for (int j = 0; j &lt; 3; ++j) {                         check(pos[B][i], B, C, pos[C][j]);                     }                 }             }         }     }     cout &lt;&lt; ans;     return 0; }</pre><p><br/></p>
这道题暂未补解析。
2. 简答题

策略游戏(game )


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; #define MAXN 100001 #define int long long int n, m, q, l_1, r_1, l_2, r_2; int ans, ans1, ans2, ans3, ans4, ans5, ans6; struct Block {     #define MAXM 331  // 块的个数     int n, len, tot;     int a[MAXN], bl[MAXN];     int L[MAXM], R[MAXM];  // 每个块的左端点和右端点     int maxn[MAXM], minn[MAXM];  // 每个块的最大值和最小值     Block(int x) {  // 构造函数         n = x;     }     void init() {  // 初始化         len = sqrt(n);  // 块长         tot = (n - 1) / len + 1;  // 块的数量         R[0] = 0;         for (int i(1); i &lt;= tot; ++i) {  // 求 L,R             L[i] = R[i - 1] + 1;             R[i] = i * len;         }         R[tot] = n;  // 注意最后一个块的右端点         for (int i(1); i &lt;= tot; ++i) {             maxn[i] = LLONG_MIN;             minn[i] = LLONG_MAX;             for (int j(L[i]); j &lt;= R[i]; ++j) {                 bl[j] = i;  // j 在第 i 个块                 maxn[i] = max(maxn[i], a[j]);                 minn[i] = min(minn[i], a[j]);             }         }     }     int gmin(int l, int r) {         int p(bl[l]), q(bl[r]), res(LLONG_MAX);         if (p == q) {  // 当 l,r 处于同一个块时,暴力枚举             for (int i(l); i &lt;= r; ++i) {                 res = min(res, a[i]);             }             return res;         }         for (int i(l); i &lt;= R[p]; ++i) {             res = min(res, a[i]);  // 枚举第一个块         }         for (int i(p + 1); i &lt; q; ++i) {             res = min(res, minn[i]);  // 枚举中间的块         }         for (int i(L[q]); i &lt;= r; ++i) {             res = min(res, a[i]);  // 枚举最后一个块         }         return res;     }     int gmax(int l, int r) {  // 同gmin,求最大值         int p(bl[l]), q(bl[r]), res(LLONG_MIN);         if (p == q) {             for (int i(l); i &lt;= r; ++i) {                 res = max(res, a[i]);             }             return res;         }         for (int i(l); i &lt;= R[p]; ++i) {             res = max(res, a[i]);         }         for (int i(p + 1); i &lt; q; ++i) {             res = max(res, maxn[i]);         }         for (int i(L[q]); i &lt;= r; ++i) {             res = max(res, a[i]);         }         return res;     } }; int f(int x) {  // 模拟 B 的决策     if (x &gt;= 0) {         return ans6;     }     return ans5; } signed main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin &gt;&gt; n &gt;&gt; m &gt;&gt; q;     Block a(n), b(m), a2(n), a3(n);  // a2 为负数处理、a3 为非负数处理     for (int i(1); i &lt;= n; ++i) {         cin &gt;&gt; a.a[i];         a2.a[i] = a3.a[i] = a.a[i];         if (a.a[i] &lt; 0) {             a3.a[i] = LLONG_MAX;  // 非负数集合中排除负数         } else {             a2.a[i] = LLONG_MIN;  // 负数集合中排除非负数         }     }     for (int i(1); i &lt;= m; ++i) {         cin &gt;&gt; b.a[i];     }     a.init();    // 初始化块结构(不能在构造函数中初始化)     b.init();     a2.init();     a3.init();     while (q--) {         cin &gt;&gt; l_1 &gt;&gt; r_1 &gt;&gt; l_2 &gt;&gt; r_2;         // 获取区间最值         ans1 = a.gmax(l_1, r_1);         ans2 = a.gmin(l_1, r_1);         ans3 = a2.gmax(l_1, r_1);         ans4 = a3.gmin(l_1, r_1);         ans5 = b.gmax(l_2, r_2);         ans6 = b.gmin(l_2, r_2);         // 计算可能的最大值         ans = max(ans1 * f(ans1), ans2 * f(ans2));  // A取最大值和最小值的情况         if (ans3 != LLONG_MIN) {             ans = max(ans, ans3 * f(ans3));  // A取负数最大值         }         if (ans4 != LLONG_MAX) {             ans = max(ans, ans4 * f(ans4));  // A取非负数最小值         }         cout &lt;&lt; ans &lt;&lt; '\n';     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

星战(galaxy)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 5e5 + 5; int n, m, q, a[N]; long long to[N], sum[N], tot, ans; int main() {     mt19937 rnd(time(0));     scanf("%d%d", &amp;n, &amp;m);          for (int i = 1; i &lt;= n; ++i) {         ans += (a[i] = rnd());     }          for (int i = 1, u, v; i &lt;= m; ++i) {         scanf("%d%d", &amp;u, &amp;v);         to[v] += a[u];         sum[v] = to[v];         tot += a[u];     }          scanf("%d", &amp;q);     for (int i = 1, t, u, v; i &lt;= q; ++i) {         scanf("%d%d", &amp;t, &amp;u);                  if (t == 1) {             scanf("%d", &amp;v);             to[v] -= a[u];             tot -= a[u];         }         if (t == 2) {             tot -= to[u];             to[u] = 0;         }         if (t == 3) {             scanf("%d", &amp;v);             to[v] += a[u];             tot += a[u];         }         if (t == 4) {             tot += sum[u] - to[u];             to[u] = sum[u];         }                  puts(tot == ans ? "YES" : "NO");     }          return 0; }</pre><p><br/></p>
这道题暂未补解析。
4. 简答题

数据传输(transmit)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; #define ll long long using namespace std; const ll N = 200500, B = 20, K = 3; ll n, q, T; ll v[N], mn[N]; vector&lt;ll&gt; e[N]; ll f[B][N], dep[N]; ll dis[B][N][K][K]; void gi(ll &amp;x, ll y) {     x = min(x, y); } void dfs(ll k, ll fa) {     dep[k] = dep[fa] + 1;     f[0][k] = fa;          for (ll i = 1; i &lt; B; i++) {         f[i][k] = f[i - 1][f[i - 1][k]];     }          auto D = dis[0][k];     if (T == 1) {         D[0][0] = v[fa];     }     if (T == 2) {         D[0][0] = D[1][0] = v[fa];         D[0][1] = 0;     }     if (T == 3) {         D[0][0] = D[1][0] = D[2][0] = v[fa];         D[0][1] = D[1][2] = 0;         D[2][2] = mn[k];     }          for (ll i = 1; i &lt; B; i++) {         for (ll x = 0; x &lt; 3; x++) {             for (ll y = 0; y &lt; 3; y++) {                 for (ll z = 0; z &lt; 3; z++) {                     gi(dis[i][k][x][z], dis[i - 1][k][x][y] + dis[i - 1][f[i - 1][k]][y][z]);                 }             }         }     }          for (auto to : e[k]) {         if (to != fa) {             dfs(to, k);         }     } } ll lca(ll x, ll y) {     if (dep[x] &lt; dep[y]) {         swap(x, y);     }          for (ll i = B - 1; i &gt;= 0; i--) {         if (dep[f[i][x]] &gt;= dep[y]) {             x = f[i][x];         }     }          if (x == y) {         return x;     }          for (ll i = B - 1; i &gt;= 0; i--) {         if (f[i][x] != f[i][y]) {             x = f[i][x];             y = f[i][y];         }     }          return f[0][x]; } vector&lt;ll&gt; calc(ll k, ll l) {     vector&lt;ll&gt; res(3, v[k]);          for (ll i = B - 1; i &gt;= 0; i--) {         if (dep[f[i][k]] &lt; dep[l]) {             continue;         }                  vector&lt;ll&gt; nw = res;         fill(res.begin(), res.end(), 1e18);                  for (ll x = 0; x &lt; 3; x++) {             for (ll y = 0; y &lt; 3; y++) {                 gi(res[y], nw[x] + dis[i][k][x][y]);             }         }                  k = f[i][k];     }          return res; } ll calcdis(ll x, ll y) {     ll l = lca(x, y);     auto F = calc(x, l), G = calc(y, l);     ll res = 1e18;          gi(res, F[0] + G[0] - v[l]);          for (ll i = 0; i &lt; T; i++) {         for (ll j = 0; j &lt; T; j++) {             gi(res, F[i] + G[j] + (mn[l] * (i + j &gt; T)));         }     }          return res; } int main() {     ios::sync_with_stdio(0);     cin &gt;&gt; n &gt;&gt; q &gt;&gt; T;          for (ll i = 1; i &lt;= n; i++) {         cin &gt;&gt; v[i];         mn[i] = v[i];     }          for (ll i = 1; i &lt; n; i++) {         ll x, y;         cin &gt;&gt; x &gt;&gt; y;         e[x].push_back(y);         e[y].push_back(x);         mn[x] = min(mn[x], v[y]);         mn[y] = min(mn[y], v[x]);     }          memset(dis, 1, sizeof(dis));     dfs(1, 0);          while (q--) {         ll s, t;         cin &gt;&gt; s &gt;&gt; t;         cout &lt;&lt; calcdis(s, t) &lt;&lt; '\n';     }          return 0; }</pre><p><br/></p>
这道题暂未补解析。