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

2024年CCF非专业级别软件能力认证第二轮 (CSP-J)入门级C++语言试题 VIP

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

一、简答题

1. 简答题

T1 扑克牌

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;set&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;     set&lt;string&gt; st;     while (n--) {         string s;         cin &gt;&gt; s;         st.insert(s);     }     cout &lt;&lt; 52 - st.size() &lt;&lt; endl;     return 0; }</pre>
解析:

题目给出已有的牌,要求计算最少需要补充多少张牌才能凑齐一副完整的扑克牌(52张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。

2. 简答题

T2 地图探险

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;cstring&gt; using namespace std; const int N = 1e3 + 5; int n, m, k, x, y, d, dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; char mp[N][N]; bool vis[N][N]; int main() {     int t;     cin &gt;&gt; t;     while (t--) {         memset(vis, false, sizeof (vis));         cin &gt;&gt; n &gt;&gt; m &gt;&gt; k &gt;&gt; x &gt;&gt; y &gt;&gt; d;         for (int i = 1; i &lt;= n; i++)             for (int j = 1; j &lt;= m; j++)                 cin &gt;&gt; mp[i][j];         vis[x][y] = true;         while (k--) {             int nx = x + dir[d][0], ny = y + dir[d][1];             if (!(nx &gt;= 1 &amp;&amp; nx &lt;= n &amp;&amp; ny &gt;= 1 &amp;&amp; ny &lt;= m &amp;&amp; mp[nx][ny] == '.')) {                 d = (d + 1) % 4;                 continue;             }             x = nx, y = ny;             vis[nx][ny] = true;         }         int ans = 0;         for (int i = 1; i &lt;= n; i++) {             for (int j = 1; j &lt;= m; j++) {                 if (vis[i][j] == true)                     ans++;             }         }         cout &lt;&lt; ans &lt;&lt; endl;     }     return 0; }</pre>
解析:

需要的变量 / 数组

描述机器人状态需要的3个变量:

x:位置。

y:位置。

d:朝向(0~3)。

vis数组:

当机器人走过[x, y],vis[x][y] = true。

dir数组:

dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}。

[x + dir[d][0], y + dir[d][1]]表示当机器人朝向为d时往前走一步之后的位置。

d = 0: 右 (0, 1)。

d = 1: 下 (1, 0)。

d = 2: 左 (0, -1)。

d = 3: 上 (-1, 0)。

核心思想

vis[x][y] = true;
while (k--) {
    int nx = x + dir[d][0], ny = y + dir[d][1]; // 计算下一步的位置
    if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) { // 是否能走
        d = (d + 1) % 4; // 若不能走 右转
        continue;
    }
    x = nx, y = ny; // 若能走 更新
    vis[nx][ny] = true;
}
3. 简答题

T3 小木棍

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; string Solve(int n) {     if (n == 1)         return "-1";     if (n % 7 == 0)         return string(n / 7, '8');     if (n % 7 == 1)         return "10" + string((n - 8) / 7, '8');     if (n % 7 == 2)         return "1" + string((n - 2) / 7, '8');     if (n % 7 == 3)         return n == 3 ? "7" : n == 10 ? "22" : "200" + string((n - 17) / 7, '8');     if (n % 7 == 4)         return n == 4 ? "4" : "20" + string((n - 11) / 7, '8');     if (n % 7 == 5)         return "2" + string((n - 5) / 7, '8');     if (n % 7 == 6)         return "6" + string((n - 6) / 7, '8'); } int main() {     int t;     cin &gt;&gt; t;     while (t--) {         int n;         cin &gt;&gt; n;         cout &lt;&lt; Solve(n) &lt;&lt; endl;     }     return 0; }</pre>
解析:

拼出0~9分别需要的木棍数量:

求解思想:

因为拼出8所需的木棍最多(7根),所以用8,可以使位数更少

在保证位数最少的前提下,还要尽可能把高位的数字变小(必须保证位数最小)

按照思想,可以找到这样的规律:

4. 简答题

T4 接龙

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int N = 1e5 + 5, R = 105; vector&lt;int&gt; s[N]; int n, k, q; vector&lt;vector&lt;int&gt; &gt; Solve(int mx) {     vector&lt;vector&lt;int&gt; &gt; dp(R, vector&lt;int&gt;(mx + 5, -1));     dp[0][1] = -2;     for (int r = 1; r &lt;= 100; r++) {         for (int i = 1; i &lt;= n; i++) {             int lst = -1;             for (int j = 0; j &lt; s[i].size(); j++) {                 int tmp = s[i][j];                 if (lst != -1 &amp;&amp; j - lst + 1 &lt;= k) {                     if (dp[r][tmp] == -1)                         dp[r][tmp] = i;                     else if (dp[r][tmp] != i)                         dp[r][tmp] = -2;                 }                 if (dp[r - 1][tmp] != -1 &amp;&amp; dp[r - 1][tmp] != i)                     lst = j;             }         }     }     return dp; } int main() {     int t;     cin &gt;&gt; t;     while (t--) {         int mx = -1;         cin &gt;&gt; n &gt;&gt; k &gt;&gt; q;         for (int i = 1; i &lt;= n; i++) {             int l;             cin &gt;&gt; l;             s[i].clear();             s[i].resize(l);             for (int j = 0; j &lt; l; j++) {                 cin &gt;&gt; s[i][j];                 mx = max(mx, s[i][j]);             }         }                  vector&lt;vector&lt;int&gt; &gt; dp = Solve(mx);         while (q--) {             int r, c;             cin &gt;&gt; r &gt;&gt; c;             cout &lt;&lt; (dp[r][c] != -1 ? 1 : 0) &lt;&lt; endl;         }     }     return 0; }</pre>
解析:

解题思路

本文的解题思想为dp。

dp[r][x]:接龙 r 轮、以 x 结尾的状态:

dp[r][x] = -1:不可实现。

dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。

dp[r][x] = -2:可以通过多个词库实现。

代码解析

完整的求解部分:

vector<vector<int> > Solve(int mx) {
    vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
    dp[0][1] = -2;
    for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
                int tmp = s[i][j];
                if (lst != -1 && j - lst + 1 <= k) {
                    if (dp[r][tmp] == -1)
                        dp[r][tmp] = i;
                    else if (dp[r][tmp] != i)
                        dp[r][tmp] = -2;
                }

                if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
                    lst = j;
            }
        }
    }
    return dp;
}

逐行分析

mx:所有词库中的最大值,用于构建dp的第二个维度。

dp的大小为R(最大轮数) * mx(所有词库中的最大值)。

vector<vector<int> > Solve(int mx) {
	vector<vector<int> > dp(R, vector<int>(mx + 5, -1));

dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。

dp[0][1] = -2;

r:轮数。

i:尝试让第 i 个人接龙。

j:第 i 个人词库中第 j 个词语。

lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。

for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
            }
        }
    }

获取当前人员 i 的词库中第 j 个词语。

如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:

那么选择子序列[lst, j]开始接龙。

更新当前状态。

如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。

int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
    if (dp[r][tmp] == -1)
        dp[r][tmp] = i; // 首次发现路径则记录序列i
    else if (dp[r][tmp] != i)
        dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}

if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
    lst = j;