CSP第一轮测试模拟题八

您的姓名：

阅读程序（ 程序输入不超过数组或字符串定义的范围 ； 判断题正确填 √ ，
错误填× ； 除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分 ）
1.
01 #include <cstdio>
02 #include <cstring>
04 using namespace std;
06 char s[10000];
07 int cnt[26];
09 int main()
{
     scanf("%s", s);
11 for (int i = 0; i < strlen(s); ++i) {
12     if (cnt[s[i] - 'a'] <= 50) {
13            s[strlen(s)] = s[i];
14      }
15     ++cnt[s[i] - 'a'];
16 }
17 printf("%s\n", s);
18 return 0;
19 }
假设设初始时输入的字符串长度不超过 500 ，且不是空串 。 完成下面的判
断题和单选题：
⚫ 判断题
1) 将程序第 11 行中的“++i”改为“i++”，程序运行结果 不会改变（ ）

将程序第 11 行改为“for(int i=0,len=strlen(s);i<len;++i)”，
程序的运行结果 不会改变，同时程序的运行效率将 得到提升（ ）

对于任意一个出现了 a 到 z 中所有的字符、且各字符出现的次数不小于50 的字符串 b，总存在一个字符串 a，使得将字符串 a 输入程序后的运
行结果为字符串 b。（ ）

程序的输出字符串长度一定 不小于 1300（注：1300=50×26）。（ ）

设输入字符串长度为 x（1≤x≤500），输出字符串长度为 y，则关于 x 和
y 的大小关系 正确的是（ ）。

设字符串 w 为 abcd...z，即从 a 到 z 在 w 中依次出现一次，
共 26 个 字 符 。 若 输 入 为 w 重 复 出 现 两 次 的 结 果 （ 即
abcdefg...zabcdefg...z，则输出结果为（ ）。

2.
01 #include <cstdio>

03 const int N = 5010;
04 const int M = 20010;
05 const int inf = 1073741823;

07 int e, bg[N], nx[M], to[M], wt[M];
08 inline void link(int u, int v, int w) {
09     to[++e] = v;
10     nx[e] = bg[u];
11     wt[e] = w;
12     bg[u] = e;
13 }
14
15 int n, m, u, v, w;
16 int f[N], h[N << 1];
17
18 void update(int x, int y) {
19     x += n - 1;
20     for (h[x] = y; x; x >>= 1)
21         h[x >> 1] = f[h[x]] < f[h[x^1]] ? h[x] : h[x^1];
22     }
23
24 int main() {
25     scanf("%d%d", &n, &m);
26     for (int i = 0; i != m; ++i) {
27         scanf("%d%d%d", &u, &v, &w);
28         link(u, v, w);
29     }
30     int nn = n << 1;
31     for (int i = 1; i <= n; ++i) {
32         for (int j = 1; j != nn; ++j)
33             h[j] = 0;
34         for (int j = 0; j <= n; ++j)
35             f[j] = inf;
36         f[i] = 0;
37         update(i, i);
38     for (int j = i; true; j = h[1]) {
39         if (f[j] == inf) break;
40         for (int k = bg[j]; k; k = nx[k]) {
41             if (f[j] + wt[k] < f[to[k]]) {
42                 f[to[k]] = f[j] + wt[k];
43                 update(to[k], to[k]);
44                 }
45         }
46         update(j, 0);
47     }
48     for (int j = 1; j <= n; ++j)
49         printf("%d%c", f[j], "\n "[j != n]);
50     }
51     return 0;
52 }
以下程序的输入是一张带边权的有向图，完成下面的判断题和单选题：
⚫ 判断题
1) 将程序中所有的 “!=” 替换为 “<”，程序将仍然正常运行且输出的结
果不会改变。 （ ）

2) 为了保证程序正常运行，输入的边数必须不大于 2 × 10^4 。 （ ）

程序的输出是一个 n×n 的整数矩阵。 （ ）

将程序第 34 行的 “j=0” 替换为 “j=1”，程序将仍然正常运行且输
出的结果不会改变。 （ ）

当输入的图中所有边的边权均为一个相同的正整数，且有
∑𝑥 𝑖 < 1073741823 时，“update” 函数被调用的次数为（ ）。

当输入的边权均为正整数时，程序在最坏情况下的时间复杂度为 （ ）。

3.
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 #define N 105
05 #define INF 1e9
06
07 int dis1[N][N], dis2[N][N];
08 int mp[N][N], n, m;
09
10 void fun1(int dis[N][N]) {
11     static bool vis[N];
12     for (int i = 1; i <= n; i++) {
13         for (int j = 1; j <= n; j++) {
14             dis[i][j] = mp[i][j];
15            }
16     }
17     for (int i = 1; i <= n; i++) {
18            for (int j = 1; j <= n; j++) vis[j] = 0;
19             for (int k = 1; k <= n; k++) {
20                     int now = 0;
21                     for (int j = 1; j <= n; j++) {
22                         if (!vis[j] && (!now || dis[i][now] > dis[i][j]))
23                                 now = j;
24                         }
25                     vis[now] = 1;
26                     for (int j = 1; j <= n; j++) {
27                         if(!vis[j]&&dis[i][j] > dis[i][now]+mp[now][j]){
28                                 dis[i][j] = dis[i][now] + mp[now][j];
29                         }
30                     }
31             }
32         }
33 }
34 void fun2(int dis[N][N]) {
35     for (int i = 1; i <= n; i++)
         {
36         for (int j = 1; j <= n; j++)
            {
37             dis[i][j] = mp[i][j];
38         }
39     }
40     for (int i = 1; i <= n; i++) {
41         for (int j = 1; j <= n; j++) {
42             for (int k = 1; k <= n; k++) {
43                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
44             }
45            }
46       }
47 }
48
49 int main() {
50     cin >> n >> m;
51     for (int i = 1; i <= n; i++) {
52         for (int j = 1; j <= n; j++) {
53                 if (i == j) mp[i][j] = 0;
54                 else mp[i][j] = INF;
55             }
56     }
57     for (int i = 1; i <= m; i++) {
58             int u, v, w;
59             cin >> u >> v >> w;
60             mp[u][v] = w;
61     }
62     fun1(dis1);
63     fun2(dis2);
64     int ans = 0;
65     for (int i = 1; i <= n; i++) {
66         for (int j = 1; j <= n; j++) {
67             if (dis1[i][j] != dis2[i][j])
68             ans++;
69         }
70     }
71     cout << ans << endl;
72     return 0;
73 }
以下程序的输入数据满足 数据满足 𝟐 ≤ n≤ 100,𝟐 ≤ 𝒏 ≤n(n−1)/2，且只保证不存在重边，即不存在 重边，即不存在 (𝒗 _𝒋 ,𝒘 _𝒋 ) = (𝒗 _𝒌 ,𝒘 _𝒌 ) (𝒋 ≠ 𝒌)， ，边权 w _i ∈ [1,10 ^𝟔 ] 。如果 。如果 u 到 v不可达，则认为距离为 INF 。 完成下面的判断题和单选题：
⚫ 判断题
1) 该代码的 dis1[i][j] 不一定是 i 到 j 的最短路。( )

输出 可能为 1 。( )

将第 19 行的 k <= n 修改为 k < n ，不影响答案。( )

对于稀疏图（n,m 不同阶），fun1() 对于单个 i 求 dis[i][j]
(1 ≤ 𝑗 ≤ n) ，最快可以做到 Θ((n + m)logm) 。( )

对于以下的输入数据，输出结果为（ ）。
5 8
3 2 2
2 4 2
1 4 3
3 1 2
4 3 3
5 2 3
1 5 1
1 2 2

若输入数据 “n=5” ，输出 ans 的最大可能值为 （ ）。

三 、 完善 程序（ 单选题，每小题 3 分，共计 30 分 ）
1. （装备穿戴问题）有 n 件装备，穿戴第 i 件装备需要玩家的力量值 至少为 𝑏 𝑖 ，穿戴该装备后会让玩家的力量值增加 𝑐 𝑖 。现在请问玩家的初始力量值最小是多少，才能以某种顺序穿戴上所有的装备？
输入：第一行是一个整数 n（1 ≤ 𝑜 ≤ 10 ³ ）；第二行有 n 个整数，第 i 个整数表示 𝑏 𝑖 （0 ≤ 𝑏 𝑖 ≤ 10 ⁹ ）；第三行有 n 个整数，第 i 个整数表示 𝑐 𝑖（0 ≤ 𝑐 𝑖 ≤ 10 ⁶ ）。
提示：使用二分+贪心的方法解决这个问题，先对装备按顺序进行排序，然后二分答案，并贪心地进行选择。试补全程序。


① 处应填（ ）

② 处应填（ ）

③ 处应填（ ）。

④ 处应填（ ）

⑤ 处应填（ ）

（打音游）小 A 最近喜欢上了一款音游，并希望在结算时得到特定分数，
例如 1919810 分。这款音游的得分计算方式如下：一共有 n 个音符，将
一千万（10 ⁷ ）分平分给所有音符得到基础得分 𝑦 = 10 ⁷ /n（保留 保留非整数部分），其中有 m 个音符根据是否击中可以获得 x+1 分或者 0 分，剩下的n-m 个音符根据击中精度可以获得 x+1，x，x/2，0 分中的一个，最后将总得分 向下取整即可得到最终得分。
给定 n,m，小 A 想知道他可以得到多少种不同的分数。
输入为两个非负整数，分别表示 n,m；满足1 ≤ n ≤ 10 ⁷ ，0 ≤ 𝑛 ≤ m。输出为一个正整数表示答案。试补全程序。


① 处应填（ ）

② 处应填（ ）

③ 处应填（ ）

④ 处应填（ ）

⑤ 处应填（ ）