提高组CSP-S2025初赛模拟卷3

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

1. 下面这段代码属于哪个算法的核心代码?()

int primes[N],cnt; bool v[N]; 
void get_primes(int n)
{
for (inti=2;i<=n; i++)
{
if(!v[i])
primes[cnt++]=i;
for (intj=0; ixprimes[j] <=n; j++) f
v[primes[j]*i=true; if(i%primes[j]==0)
break;
}
i
}

{{ select(1) }}

• 埃氏筛法
• 欧拉筛算法
• 分解质因数
• 中国剩余定理

2. 在Linux操作系统中,以下哪个命令的作用是分页显示普通文本类型文件CSP? ) {{ select(2) }}

• vi csp
• more csp
• cat csp
• Ls csp

3. 下列不属于视频文件格式的是( )。 {{ select(3) }}

• MPEG
• JPEG
• AVI
• WMV

4. 已知q为int类型变量,p为int*类型变量,下列赋值语句中不符合语法的是()。 {{ select(4) }}

• +q=* p ;
• * p=+q ;
• q=*(p+q);
• *(p+q)=q ;

5. 下列关于有向图和无向图的说法中,错误的是( {{ select(5) }}

• n个顶点的弱连通有向图最少有n-1条边
• n个顶点的强连通有向图最少有n条边
• n个顶点的简单有向图最多有n*(n-1)条边
• n个顶点的简单无向图最多有 $n*(n-1)/2$ 条边

6. 前序遍历和中序遍历相同的二叉树为且仅为( {{ select(6) }}

• 只有一个结点的独根二叉树
• 根结点没有右子树的二叉树
• 非叶子结点只有右子树的二叉树
• 非叶子结点只有左子树的二叉树

7. 以下哪个命令,在NOI Linux环境下能将一个名为csp.cpp的C++源文件编译并生成一个名为csp的可执行文件?() {{ select(7) }}

• g++csp.exe-ocsp.cpp
• g++-0 csp.cpp csp
• g++-ocsp csp.cpp
• g++csp.bat-o csp.cpp

8. 集合U={1,2,3,4,5,6,7,8,9,10},则U的元素两两互质的三元子集个数为()。 {{ select(8) }}

• 42
• 35
• 36
• 45

9. 以下关于排序算法的说法中错误的是()。 {{ select(9) }}

• 堆排序在最好和最坏情况下的时间复杂度都是 $O(n log n)$
• 归并排序在最好和最坏情况下的时间复杂度都是 $O(n log n)$
• 拓扑排序从入度为0的结点开始
• 快速排序在最好和最坏情况下的时间复杂度都是 $O(n log n)$

10. 以下哪种算法不属于贪心算法?( ) {{ select(10) }}

• 迪杰斯特拉算法
• KMP
• Kruskal
• 哈夫曼算法

11. 下列选项中,哪个不可能是下图的深度优先遍历序列?()

{{ select(11) }}

• 1,5,7,8,9,4,2,3,6
• 1,4,7,8,9,5,2,3,6
• 1,2,3,5,7,8,6,9,4
• 1,2,3,6,9,8,5,7,4

12. 下面new_mem函数的时间复杂度为()。

int mem[8192];
void new_mem(int n)
{
for (inti=1;i<=n; i++)
mem[i]=i;
for (int i=2; i<=n; i++) 
for (intj=i;j<=n; j+=i) 
mem[j]--;
}

{{ select(12) }}

• $O(n^2)$
• $O(n)$
• $O(n\log n)$
• $O(\log n)$

13. 以下关于动态规划算法的说法中,错误的是()。 {{ select(13) }}

• 递推实现动态规划算法的时间复杂度总是不低于递归实现
• 动态规划算法有递推和递归两种实现形式
• 动态规划算法将原问题分解为一个或多个相似的子问题
• 动态规划算法具有无后效性

14. 由50支队伍进行排球单循环比赛,胜一局积1分,负一局积0分,且任取27支队伍能找到一个全部战胜其余26支队伍的队伍和一支全部负于其余26支队伍的队伍,问这50支队伍总共最少有()种不同的积分。 {{ select(14) }}

• 51
• 50
• 49
• 48

15. 一个简单无向图有9个顶点、6条边。在最坏情况下,至少增加( )条边可以使其连通。 {{ select(15) }}

• 3
• 4
• 5
• 6

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特殊说明外,判断题每题1.5分,选择题每题3分,共计40分)

(1)

01 #include <iostream>
02 #include <algorithm>
03 #include<queue>
04 using namespace std;
05 typedef long long ll;
06 const LL MAXN=2e5+5;
07 Ll n,m,k;
08 struct node {
09 ll w,num;
10 bool operator<(const node&K)const{
11 return w>K.w;
12 }
13 }a[MAXN];
14 priority_queue<node>q;
15 int main(){
16 ios::sync_with_stdio(false);
17 cin>>n>>m>>k;
18 for(inti=1;i<=n;++i){
19 cin>a[i].w>>a[i].num;
20 }
21 sort(a+1,a+n+1);
22 q.push({-1000000000,1});
23 LL ans=0;
24 for(inti=n;i>=1;--i){
25 ll v=0;
26 while(!q.empty()){
27 node t=q.top();
28 q.pop();
29 if(t.w+k<a[i].w){
30 q.push(t);
31 break;
32 }
33 if(t.num<=a[i].num){
34 ans+=t.num;
35 q.push(a[i]);
36 if(t.num<a[i].num){
37 t.num-=a[i].num;
38 q.push(t);
39 }
40 break;
41 }
42 v+=t.num;
43 ans+=t.num;
44 a[i].num-=t.num;
45 }
46 if(v){
47 q.push({a[i].w,a[i].num});
48 }
49 }
50 cout<<ans<<endl;
51 return 0;
52 }

判断题

16. cout<<end1会强行刷新缓存区,在换行较多的情况下会比cout<<"\n'更慢。 {{ select(16) }}

• √
• ×

17. priority_queue位于头文件algorithm中。 {{ select(17) }}

• √
• ×

18. 该程序中,node经过sort后按照w的值从小到大排序。 {{ select(18) }}

• √
• ×

19. 交换第33行代码和第36行代码,程序在任意输入数据下输出不变。 {{ select(19) }}

• √
• ×

选择题(每题2分)

20. 若输入

3 5 2
9 4
7 6
5 5

则本程序的输出是( )。 {{ select(20) }}

• 9
• 10
• 14
• 15

21. 这段程序的时间复杂度为( )。 {{ select(21) }}

• O(1)
• O(N)
• O(N log N)
• O(N log² N)

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int N=2e5+5;
05 const int M=3e5+5;
06
07 struct edge{
08 int u,v,w;
09 }e[M]; 
10 inline bool cmp(edge aa,edge bb) { return aa.w>bb.w;}
11
12 int f[N];
13 int find(int x) { return x==f[x]?x:f[x]=find(f[x]);}
14
15 vector<int>mp[N];
16 int n,m,x,y,z,q,cnt; 
17 int val[N],fa[N],dep[N],top[N],son[N],tot[N];
18
19 void dfs1(int u)
20 {
21 tot[u]=1,dep[u]=dep[fa[u]]+1;
22 int siz=mp[u].size();
23 for(int i=0;i<siz;++i)
24 {
25 int v=mp[u][i];
26 if(v==fa[u]) continue;
27 fa[v]=u,dfs1(v);
28 tot[u]+=tot[v];
29 if(tot[v]>tot[son[u]]) son[u]=v;
30 }
31 }
32 void dfs2(int u,int Top)
33 {
34 top[u]=Top;
35 if(!son[u]) return;
36 dfs2(son[u],Top);
37 int siz=mp[u].size();
38 for(int i=0;i<siz;++i)
39 {
40 int v=mp[u][i];
41 if(!top[v]) dfs2(v,v);
42 }
43 }
44
45 int lca(int u,int v)
46 {
47 while(top[u]!=top[v])
48 {
49 if(dep[top[u]]<dep[top[v]]) swap(u,v);
50 u=fa[top[u]];
51 }
52 return dep[u]<dep[v]?u:v;
53 }
54
55 void kruskal()
56 {
57 sort(e+1,e+m+1,cmp);
58 for(int i=1;i<=n;++i) f[i]=i;
59 for(inti=1;i<=m;++i) {
60 int u=find(e[i].u),v=find(e[i].v);
61 if(u==v) continue; 
62 val[++cnt]=e[i].w;
63 f[cnt]=f[u]=f[v]=cnt;
64 mp[u].push_back(cnt),mp[v].push_back(cnt);
65 mp[cnt].push_back(u),mp[cnt].push_back(v);
66 } 
67 for(inti=1;i<=cnt;++i)
68 {
69 if(tot[i]) continue;
70 int rt=find(i);
71 dfs1(rt),dfs2(rt,rt);
72 }
73 }
74
75 int main()
76 {
77 scanf("%d%d%d",&n,&m,&q);
78 cnt=n;
79 for(int i=1;i<=m;++i)
80 {
81 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
82 }
83 kruskal();
84 while(q--)
85 {
86 scanf("%d%d",&x,&y);
87 if(find(x)!=find(y)) printf("-1\n");
88 else printf("%d\n",val[lca(x,y)]);
89 }
90 return0;
91 }

判断题

22. 两次dfs的目的在于,针对每个结点计算其所有子结点所构成子树的大小,进而找出子树大小最大的子结点,从而寻找lca。lca就是两点之间wi的最小值。 {{ select(22) }}

• √
• ×

23. 本段代码中N的范围错误,应该开至两倍大小。 {{ select(23) }}

• √
• ×

24. (2分)本段代码的并查集不可以用于可撤销操作。 {{ select(24) }}

• √
• ×

选择题

25. 若输入为

5 4 3 
1 2 5 
2 3 6 
3 4 1 
1 4 3 
1 5 
2 4 
1 3

则程序输出为( )。 {{ select(25) }}

• -1 3 5
• 0 3 5
• -1 5 5
• -1 5 1

26. 本段代码中,如果把并查集改为按秩合并+路径压缩并查集,则代码的时间复杂度 )。 {{ select(26) }}

• 降低
• 不变
• 升高
• 是随机值

27. (4分)以下说法中不正确的是()。 {{ select(27) }}

• 既然已经保证u≠vi,则第62行代码可以删除。
• 第41行的if语句与v!=son[u]等价。
• 第88行,如果考虑x=y的情况,那么程序只能输出-1。
• 第71行和第72行语句只会执行一次,因为很显然在dfs之前tot都为0,而一次dfs之后都为1,一直continue。

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int N=1e5+10;
05 int n,k,ans,val[N],L[N],R[N];
06 vector<int>vec;
07 struct BIT
08 {
09 int C[N];
10 inline void add(int x,int y) { for(;x<=n;x+=x&-x) C[x]=max(C[x],y);}
11 inline int query(int x)
12 {
13 int ans=0;
14 for(;x;x-=x&-x) ans=max(ans,C[x]);
15 return ans;
16 }
17 }le,re,S;
18 int main()
19 {
20 scanf("%d%d",&n,&k);
21 val[0]=1;val[n+1]=n+1;
22 for(inti=1;i<=n;i++)scanf("%d",&val[i]);
23 for(inti=1;i<=n;i++)vec.push_back(val[i]);
24 sort(vec.begin(),vec.end());
25 vec.erase(unique(vec.begin(),vec.end()),vec.end());
26 for(inti=1;i<=n;i++)
27 val[i]=lower_bound(vec.begin(),vec.end(),val[i])-vec.begin()+1;
28 for(int i=1;i<=n;i++)
29 {
30 L[i]=le.query(val[i])+1;
31 le.add(val[i],L[i]);
32 }
33 for(int i=n;i>=1;i--)
34 {
35 R[i]=re.query(n-val[i]+1)+1;
36 re.add(n-val[i]+1,R[i]);
37 }
38 for(inti=k+1;i<=n+1;i++)
39 {
40 S.add(val[i-k-1],L[i-k-1]);
41 ans=max(ans,S.query(val[i])+k+R[i]);
42 }
43 printf("%d",ans);
44 return 0;
45 }

判断题(每题2分)

28. 对于一个int类型的正整数x来说,Lowbit(x)<=X。 {{ select(28) }}

• √
• ×

29. 之所以将val[n+1]设置为n+1而不是1e6+1,是因为无论设置为什么值,这个位置都不会被访问。 {{ select(29) }}

• √
• ×

30. 在1 ≤i ≤n时,L[i]+R[i]有可能比答案更大。 {{ select(30) }}

• √
• ×

31. 本段代码的时间复杂度是O(nlogn)。 {{ select(31) }}

• √
• ×

选择题

32. 若输入

5 1
1 4 2 8 5

则程序输出为( )。 {{ select(32) }}

• 2
• 3
• 4
• 5

33. (4分)下列说法中正确的是()。 {{ select(33) }}

• 如果n变大100倍,其他条件不变,则C也要开大100倍空间。
• 这段代码的复杂度不是O(n log n),而是O(n²),因为vector的erase函数的复杂度是O(n),而里面嵌套的unique也是O(n),只不过这段代码的常数很小,因此能跑通10万。
• ans最大和val一样,最大为1e6。
• 第27行val[i]=lower_bound(vec.begin(),vec.end(),va[i])-vec.begin()+1 在这里用val[i]=upper_bound(vec.begin(),vec.end(),va[i])-vec.begin()+1 得到的结果一定与前者不同。

三、完善程序(单选题,每小题3分,共计30分)

(1)题目描述:

给定一棵树,边形如(ui,vi)。维护以下操作: op =1 ,指定一条边,将所有从ui出发、不经过这条边就能到达的点的点权加k: op=2 ,指定一条边,将所有从vi出发、不经过这条边就能到达的点的点权加k。 输出最终每个点的点权。初始点权为0。

01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 const int N=410000;
05 int u[N],v[N],depth[N],chafen[N],ans[N];
06 int n,q;
07 vector<int>mp[N];
08 void depdfs(int x,int fa,int dep)
09 {
10 depth[x]=dep;
11 for(inti=0;i<mp[x].size();i++)
12 {
13 int pt=mp[x][i];
14 if(pt!=fa) depdfs(pt,x,dep+1);
15 }
16 }
17 void chafendfs(int x,int fa,int v)
18 {
19 ①
20 ans[x]=v;
21 for(inti=0;i<mp[x].size();i++)
22 {
23 int pt=mp[x][i];
24 if(pt!=fa) chafendfs(pt,x,v);
25 }
26 }
27 signed main()
28 {
29 scanf("%lld",&n);
30 for (int i=1;i<n;i++)
31 {
32 scanf("%lld%lld",u+i,v+i);
33 ②
34 }
35 ③
36 scanf("%d",&q);
37 for (inti=1;i<=q;i++)
38 {
39 int op,e,val;
40 scanf("%lld%lld%lld", &op,&e,&val);
41 int ch,nch,chd,nchd;
42 if(op==1)
43 {
44 ch=u[e],nch=v[e];
45 chd=depth[ch],nchd=depth[nch];
46 if(chd<nchd)④
47 else chafen[ch]+=val;
48 }
49 if(op==2)
50 {
51 ⑤
52 chd=depth[ch],nchd=depth[nch];
53 if(chd<nchd) chafen[1]+=val,chafen[nch]-=val;
54 else chafen[ch]+=val;
55 }
56 }
57 chafendfs(1,0,0);
58 for (inti=1;i<=n;i++)printf("%lld\n",ans[i]);
59 return0;
60 }

34. ①处应填( {{ select(34) }}

• v+=chafen[x];
• v-=chafen[x];
• x+=chafen[v];
• x-=chafen[v];

35. ②处应填()。 {{ select(35) }}

• mp[u[i]].push_back(v[i]);
• mp[v[i]].push_back(u[i]);
• mp[u[i]].push_back(v[i]);mp[v[i]].push_back(u[i]);
• mp[v[i]].push_back(v[i]);mp[u[i]].push_back(u[i]);

36. ③处应填( )。 {{ select(36) }}

• depdfs(0,0,0);
• depdfs(0,0,1);
• depdfs(2,0,0);
• depdfs(1,0,1);

37. ④处应填( )。 {{ select(37) }}

• chafen[1]-=val,chafen[nch]+=val;
• chafen[1]+=val,chafen[nch]+=val;
• chafen[1]-=val,chafen[nch]-=val;
• chafen[1]+=val,chafen[nch]-=val;

38. ⑤处应填()。 {{ select(38) }}

• ch=v[e],nch=v[e];
• ch=v[e],nch=u[e];
• chu[e],nch=v[e];
• ch=u[e],nch=u[e];

(2)题目描述:

给定2n个数排成两排(每个数在2n个数中最多出现两次),一次操作可以交换任意一列中的两个数,求使每行中的数不重复的最少操作数。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int MAXN=50050; 
04 int N,h[MAXN],to[MAXN<<1],nxt[MAXN<<1],tp[MAXN<<1],tot; 
05 int vis1[MAXN<<1],vis2[MAXN<<1];
06 int type[MAXN],sum[MAXN];
07 int ans;
08 inline void add(int u,int v,int t){
09 to[++tot]=v,nxt[tot]=h[u],tp[tot]=t,h[u]=tot; 
10 }
11
12 pair<int,int>get(int x){ 
13 if(vis2[x]) return make_pair(①);
14 else if(vis1[x])return make_pair(1,vis1[x]);
15 else return②;
16 }
17 int dfs(int x,int fa){
18 sum[x]=1;
19 int res=③;
20 for(inti=h[x];i;i=nxt[i]){
21 if(sum[to[i]]) continue;
22 type[to[i]]=④;
23 res+=dfs(to[i],x);sum[x]+=sum[to[i]];
24 }
25 return res;
26 }
27 int sol(int x){
28 type[x]=1;
29 int now=dfs(x,x);
30 return min(now,sum[x]-now);
31 }
32
33 int main()
34 {
35 scanf("%d",&N); 
36 for(int i=1;i<=N;++i){
37 int d;scanf("%d",&d);
38 pair<int,int>temp=get(d);
39 if(temp.first){
40 add(i,temp.second,1),add(temp.second,i,1);
41 }
42 vis1[d]=i;
43 }
44 for(int i=1;i<=N;++i){
45 int d;scanf("%d",&d);
46 pair<int,int>temp=get(d);
47 if(temp.first==2){
48 add(i,temp.second,1),add(temp.second,i,1);
49 }
50 else if(temp.first==1){
51 ⑤
52 }
53 vis2[d]=i;
54 }
55 for(int i=1;i<=N;++i)
56 if(!sum[i])ans+=sol(i);
57 }
58 printf("%d\n",ans);
59
60 return 0;
61 }

39. ①处应填( )。 {{ select(39) }}

• 0,vis2[x]
• 1,vis2[x]
• 2,vis2[x]
• 3,vis2[x]

40. ②处应填()。 {{ select(40) }}

• 0
• (0,0)
• make_pair(0,0)
• pair(0,0)

41. ③处应填()。 {{ select(41) }}

• type[x]1
• type[x]81
• ~type[x]
• !type[x]

42. ④处应填()。 {{ select(42) }}

• type[x]
• type[x]^type[fa]
• type[i]
• type[i]^type[x]

43. ⑤处应填( )。 {{ select(43) }}

• add(i,temp.second,0),add(temp.second,i,1);
• add(i,temp.second,0),add(temp.second,1,0);
• add(i,temp.second,1),add(temp.second,i,1);
• add(i,temp.second,1),add(temp.second,i,0);