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

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

1. 已知开放集合 (S={x}) 规定,如果正整数x属于该集合,则2x和3x同样属于该集合。若该集合包含1,则该集合一定包含()。 {{ select(1) }}

• 2024
• 1536
• 2025
• 2026

2. 在C++语言中,STL deque类型不包含函数()。 {{ select(2) }}

• pop()
• front()
• back()
• size()

3. 在NOI Linux系统中,改变当前工作路径到上一级目录的命令是()。 {{ select(3) }}

• pwd
• Ls
• cd..
• mv

4. 在C++语言中,(-5)%5的值为( )。 {{ select(4) }}

• -1
• 0
• 1
• 5

5. 简单无向图有24条边且每个顶点的度数都是4,则图中有()个顶点。 {{ select(5) }}

• 24
• 10
• 16
• 12

6. 算法的复杂度分析中常用的大O表示法是()科学家最先引入的。 {{ select(6) }}

• 美国
• 德国
• 英国
• 法国

7. 稀疏表预处理的时间复杂度为()。 {{ select(7) }}

• O(log n)
• O(n)
• O(n log n)
• O(n²)

8. 以下选项中,()不属于AVL树插入结点破坏平衡的情况。 {{ select(8) }}

• RS型
• RL型
• LL型
• LR型

9. 数据结构中单调栈的特点不包括()。 {{ select(9) }}

• 单调栈这种优秀的数据结构简洁明了
• 单调栈的空间复杂度为O(n)
• 单调栈中的所有元素都会多次出入栈
• 顾名思义,单调栈中的元素呈单调性

10. 关于C++语言中的构造函数,下列说法中哪个是正确的?() {{ select(10) }}

• 构造函数的名称与类的名称相同,且没有返回值
• 构造函数不能被override
• 构造函数是用来销毁类对象的成员函数
• 每个类只有一个构造函数

11. 下面有关C++重载的说法中错误的是()。 {{ select(11) }}

• 两个参数个数不同的函数可以用相同的名字
• 两个参数类型不同的函数可以用相同的名字
• 两个类的方法可以用相同的名字
• 所有C++运算符均可以重载

12. 有n个顶点、m条边的图的深度优先搜索遍历算法的时间复杂度为()。 {{ select(12) }}

• O(n m)
• O(n+m)
• O(n)
• O(m)

13. 甲乙两人参加知识竞赛,每人抽1次(抽到的题目不再放回),共有6道选择题、4道判断题,甲乙两人至少有一个抽到选择题的概率是()。 {{ select(13) }}

• 3/5
• 2/3
• 13/15
• 3/4

14. 正整数n≥3称为理想数,若存在正整数k(1≤k≤n-1)使得C(n,k-1),C(n,k),C(n,k+1)构成等差数列,其中C(n,k)为从n个数中取k个数的组合数,C(n,k)=n!/(k!*(n-k)!),则不超过2025的理想数的个数为()。 {{ select(14) }}

• 46
• 45
• 44
• 43

15. 已知一棵二叉树有10个结点,则其中至多有()个结点有2个子结点。 {{ select(15) }}

• 6
• 5
• 4
• 3

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=1e5+5;
04 using ll=long long;
05 ll A,B,C;
06 int n,k,T,p[N],m7,mr,a[N],b[N];
07 bitset<N>VS;
08
09 inline bool ck(int P){
10     int x,d=0,R=2;
11     for(x=1;x<=n;++x)
12         if(p[x]<<1<P)p[x]=1e9,++d;
13     for(x=1;x<n;++x)
14         R=min(R,(p[x]<P)+(p[x+1]<P));
15     for(x=1;x<=n;++x)p[x]=b[x];
16     return d+R<=k;
17 }
18
19 int main(){
20     int i,j,x,y,z,L,r,md;
21     ios::sync_with_stdio(false);
22     cin>>T;
23     while(T--){
24         cin>>n>>k;
25         for(i=1;i<=n;++i)cin>>p[i],b[i]=p[i],a[i]=i;
26         if(n==k){
27             printf("1000000000\n");continue;
28         }else if(n==2){
29             printf("%d\n",max(p[1],p[2]));continue;
30         }
31         sort(a+1,a+n+1,[](int x,int y){return b[x]<b[y];});
32         L=0,r=1e9,A=0;
33         while(L<=r){
34             md=L+r>>1;
35             if(ck(md))A=md,L=md+1;
36             else r=md-1;
37         }
38         printf("%lld\n",A);
39     }
40     return 0;
41 }

假设1≤k≤1e5,2≤n≤1e5,1<ai≤1e9,回答下列问题。

判断题

16. 这段代码的时间复杂度为O(MlogN+MlogA)。 {{ select(16) }}

• √
• ×

17. 第31行中的sort没必要这么写,只需要写sort(a+1,a+n+1),程序执行能得到一样的结果。 {{ select(17) }}

• √
• ×

18. 这段代码的输出不会大于k。 {{ select(18) }}

• √
• ×

19. 当P越大时,check函数中的R也越大,但是不会大于2。 {{ select(19) }}

• √
• ×

选择题

20. 假设读入时b数组为1919810,则程序执行完毕后,b数组为( )。 {{ select(20) }}

• 1101989
• 1919810
• 1891019
• 114514

21. 假设输入为

1
4 1
146132

则输出为( )。 {{ select(21) }}

• 4
• 5
• 6
• 7

(2)

01 #include <bits/stdc++.h>
02 const int maxn=200100;
03 int n,a[maxn];
04 void solve(){
05     scanf("%d",&n);
06     for(int i=1;i<=n;++i) scanf("%d",&a[i]);
07     int lst=0;
08     for (int i=1; i<=n; ++i){
09         if(a[i]!=-1){
10             if(!lst){
11                 for(int j=i-1,o=1;;--j,o=1)a[j]=(o?a[i]*2:a[i]);
12                 lst=i;
13                 continue;
14             }
15             int x=lst,y=i;
16             while(y-x>1){
17                 if (a[x]>a[y]) a[x+1]=a[x]/2,++x;
18                 else if (a[x]<a[y]) a[y-1]=a[y]/2,--y;
19                 else a[x+1]=a[x]>1?a[x]/2:a[x]*2,++x;
20             }
21             if(a[y]!=a[x]/2&&a[x]!=a[y]*2) return (void)puts("-1");
22             lst=i;
23         }
24     }
25     if(!lst){
26         for(int i=1;i<=n;++i) printf("%d\n",(i&1)+1);
27         return;
28     }
29     for(int i=lst+1,o=1;i<=n;++i,o=1)a[i]=(o?a[lst]*2:a[lst]);
30     for(int i=1;i<=n;++i) printf("%d\n",a[i]);
31 }
32 int main(){
33     int T;
34     scanf("%d",&T);
35     while (T--) solve();
36     return 0;
37 }

假设t≤10,1≤n≤200000,-1≤ai≤1000000000,回答下列问题。

判断题

22. 这段代码的时间复杂度为O(NlogN)。 {{ select(22) }}

• √
• ×

23. 如果输入的ai全为-1,那么输出的第一个数是1。 {{ select(23) }}

• √
• ×

24. 第11行中a[j]的值取决于o,如果o为1,那么a[j]=a[i]*2,如果o为0,则a[j]=a[i]。 {{ select(24) }}

• √
• ×

选择题

25. 若程序输入为

1
8
-1-1-12-1-11-1

则输出(不考虑换行)是()。 {{ select(25) }}

• 42421212
• 42421112
• 12421212
• 12421112

26. 假设a[x]=15,a[y]=29,并且x=5,y=12,那么程序执行完第16~20行代码后,a[6]到a[11]的值分别是多少?( ) {{ select(26) }}

• 7313714
• 71429142914
• 737142914
• 77371429

27. 当第16行中的y-x的差大于( )时,这段代码一定不会输出-1。 {{ select(27) }}

• 54
• 60
• 63
• 无法保证

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int INF=5e5+5;
04 struct _node_data{
05     int l,r;
06 }aa[INF];
07 int n;
08 struct _set{
09     int v,id;
10     bool operator<(const _set &x)const{
11         return x.v>v;
12     }
13 };
14 multiset<_set>si;
15 bool cmp(_node_data xx,_node_data yy){
16     return xx.l<yy.l;
17 }
18 struct _node_edge {
19     int to_,next_;
20 }edge[INF<<1];
21 int head[INF],tot,vis[INF];
22 void add_edge(int x,int y) {
23     edge[++tot]=(_node_edge){y,head[x]};
24     head[x]=tot;return;
25 }
26 void DFS(int x){
27     if (vis[x]) return;
28     vis[x]=1;
29     for (int i=head[x];i;i=edge[i].next_){
30         int v=edge[i].to_;
31         DFS(v);
32     }
33     return;
34 }
35 int check(){
36     DFS(1);
37     for (int i=1;i<=n;i++)
38         if(!vis[i]) return false;
39     return true;
40 }
41 signed main()
42 {
43     ios::sync_with_stdio(false);
44     cin>>n;
45     for (int i=1;i<=n;i++)
46         cin>>aa[i].l>>aa[i].r;
47     sort(aa+1,aa+1+n,cmp);
48     int cnt=0;
49     si.insert({aa[1].r,1});
50     for (int i=2;i<=n;i++){
51         multiset<_set>::iterator it=si.lower_bound({aa[i].l,-1});
52         for(;it!=si.end();it++){
53             if(it->v>=aa[i].r)break;
54             cnt++;
55             if(cnt==n){
56                 cout<<"NO\n";
57                 return 0;
58             }
59             add_edge(i,it->id);
60             add_edge(it->id,i);
61         }
62         si.insert({aa[i].r,i});
63     }
64     if(cnt!=n-1){
65         cout<<"NO\n";
66         return 0;
67     }
68     if(!check()){
69         cout<<"NO\n";
70         return 0;
71     }
72     cout<<"YES\n";
73     return 0;
74 }

假设1≤n≤5e5,1≤li≤ri≤2n,并且输入均为整数,不会出现相同的(li,ri)。

判断题

28. 此题是判断一些线段满足一些性质后是否能构成一棵树,因为第65行判断cnt是否为n-1,即边的数量是否为n-1条。 {{ select(28) }}

• √
• ×

29. 这段代码的时间复杂度是O(N²logN)。 {{ select(29) }}

• √
• ×

30. _set类型在set中按照id从大到小排序。 {{ select(30) }}

• √
• ×

选择题

31. 如果输入

6
912
211
13
610
57
48

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

• YES
• NO
• NULL
• TRUE

32. 以下哪种情况一定会导致代码输出"NO"?() {{ select(32) }}

• 在本段代码中,DFS函数执行了n次
• 存在i使得li=ri=0[0,0]
• 存在重复出现的(li,ri)
• 所有线段都相交

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

• 如果li,ri数据范围扩大十倍,则时间复杂度变大。
• check函数中的DFS(1)改成DFS(n),程序输出不变。
• multiset完全没有必要,这会导致重复连边,但是因为本题要求一棵树,所以没有出现问题。
• 其实可以只连单向边,考虑x,y:当扫到x的时候会有(x,y)和(y,x),而扫到y时也会有(x,y)和(y,x)。

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

(1)题目描述:

给你一棵有n个结点的树,结点从1到n编号。你会按编号从小到大的顺序访问每个结点。经过树上的边需要收费。第i条边有单程票(只能用1次)价格Ci1和多程票(可以用无限次)价格Ci2。你在访问途中可能会重复走一条边,所以多程票有时更划算。请你求出从1访问到n最少需要多少费用。此时在树上差分即可。

01 #include <cstdio>
02 #include <iostream>
03 #include <cstring>
04
05 using namespace std;
06
07 const int N=2e5+10;
08
09 int n,fir[N],tot,fa[N][40],dep[N];
10 long long ans, val[N];
11 struct node {int to,nex,oned,twod;}e[N<<1];
12
13 void add(int u,int v,int xgf,int xrc)
14 {
15     e[++tot].to=v;
16     e[tot].oned=xgf;
17     e[tot].twod=xrc;
18     e[tot].nex=fir[u];
19     fir[u]=tot;
20     return;
21 }
22 void swap(int &x,int &y) {①;return ;}
23
24 void dfs(int x,int dad)
25 {
26     dep[x]=dep[dad]+1;
27     fa[x][0]=dad;
28     for(int i=1;(1<<i)<=dep[x];i++)
29         fa[x][i]=②;
30     for(int i=fir[x];i;i=e[i].nex)
31         if(e[i].to^dad)dfs(e[i].to,x);
32     return;
33 }
34
35 int lca(int x,int y)
36 {
37     if(dep[x]<dep[y]) swap(x,y);
38     for(int i=35;i>=0;i--)
39     {
40         if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
41     }
42     if(x ==y) return y;
43     for(int i=35;i>=0;i--)
44         if(③){x=fa[x][i];y=fa[y][i];}
45     return fa[x][0];
46 }
47
48 void solve(int x)
49 {
50     int u;
51     for(int i=fir[x];i;i=e[i].nex)
52         if(e[i].to^fa[x][0])
53         {
54             solve(e[i].to);
55             val[x]+=val[e[i].to];
56         }
57         else u=i;
58     ④
59     else ans+=e[u].twod;
60     return;
61 }
62
63 int main()
64 {
65     scanf("%d",&n);
66     for(int i=1,u,v,c1,c2;i<n;i++)
67     {
68         scanf("%d%d%d%d",&u,&v,&c1,&c2);
69         add(u,v,c1,c2);add(v,u,c1,c2);
70     }
71     dfs(1,0);
72     for(int i=1;i<n;i++) {
73         val[i]++;val[i+1]++;
74         ⑤
75     }
76     solve(1);
77     printf("%lld",ans);
78     return 0;
79 }

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

• x^=x^=y^=x
• x^=x^=x^=y
• x^=y^=x^=y
• x^=y^=y^=x

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

• fa[x][i+1]
• fa[x][i-1]
• fa[fa[x][i+1]][i+1]
• fa[fa[x][i-1]][i-1]

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

• fa[x][i]&&fa[y][i]
• fa[x][i]||fa[y][i]
• fa[x][i]==fa[y][i]
• fa[x][i]^fa[y][i]

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

• if(e[u].onedval[x]<e[u].twod)ans+=e[u].onedval[x];
• if(e[u].oned*val[x]<e[u].twod)ans+=e[u].twod;
• if(e[u].oned<e[u].twod)ans+=e[u].oned*val[x];
• if(e[u].oned<e[u].twod)ans+=e[u].twod;

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

• val[lca(i,i+1)]-=2
• val[lca(i,i-1)]-=2;
• val[lca(i,i+1)]-=1;
• val[lca(i,i-1)]-=1;

(2)题目描述:

给定一个n×m的矩阵h,求出所有大小为a×b的子矩阵中的最小值的和。矩阵的给定方式:给定g(0),x,y,z,它们表示一个序列g(i),而hij由该序列生成。其中g(i)=[g(i-1)*x+y]modz;hij=g[(i-1)*m+j-1]。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int n,m,a,b;
05 long long x,y,Z;
06 long long g[9000010];
07 int h[3005][3005];
08 int minn[3005][3005];
09 long long ans;
10 deque<int>p;
11
12 int main()
13 {
14     scanf("%d%d%d%d",&n,&m,&a,&b);
15     scanf("%lld%lld%lld%lld",g[0],&x,&y,&z);
16     for(int i=1;i<=9000005;i++)g[i]=(g[i-1]*x+y)%z;
17     for(int i=1;i<=n;i++)
18     {
19         for(int j=1;j<=m;j++)
20             h[i][j]=g[0];
21     }
22     for(int i=1;i<=n;i++)
23     {
24         while(!p.empty())p.pop_back();
25         for(int j=1;j<=m;j++)
26         {
27             while(!p.empty()&&p.front()<=j-b)if(!p.empty())②;
28             while(!p.empty()&&h[i][p.back()]>h[i][j]){if(p.empty())
29                 p.push_back(j);p.pop_back();
30                 ③
31             }
32         }
33     }
34     while(!p.empty())p.pop_back();
35     for(int j=1;j<=m;j++)
36     {
37         while(!p.empty())p.pop_back();
38         for(int i=1;i<=n;i++)
39         {
40             while(!p.empty()&&p.front()<=i-a){if(!p.empty())p.pop_front();}
41             while(!p.empty()&&④){if(p.empty())p.pop_back();}
42             p.push_back(i);
43             if(i>=a&&j>=b)
44                 ⑤
45         }
46     }
47     printf("%lld\n",ans);
48     return 0;
49 }

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

• g[(i-1)*m+j]
• g[(i-1)*m+j-1]
• g[i*m+j-1]
• g[i*m+j]

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

• p.pop_front();
• p.pop_back();
• p.push_back(++j);
• p.push_front(++j);

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

• minn[i][j]=h[i][1];
• minn[i][j]=h[i][0];
• minn[i][j]=h[i][p.front()];
• minn[i][j]=h[i][p.back()];

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

• minn[p.back()][j]>=minn[i][j]
• minn[p.front()][j]>=minn[i][j]
• minn[p.back()][j]<=minn[i][j]
• minn[p.front()][j]<=minn[i][j]

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

• h[p.back()][j]
• h[p.front()][j]
• minn[p.back()][j]
• minn[p.front()][j]