提高组CSP-S2025初赛模拟卷4
提高组CSP - S2025初赛模拟卷4
一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)
- 已知小写字母a的ASCII码为97,下列C++代码的输出结果是( )
#include <iostream>
using namespace std;
int main() {
char a='a';
a++;
cout<<a;
return 0;
}
{{ select(1) }}
- a
- b
- 97
- 98
- 以下代码段的时间复杂度是()。
void Merge(int a[],int left,int mid,int right){
int temp[right - left+1];
int i=left,j=mid+1,k=0;
while (i<=mid && j<=right){
if (a[i]<a[j])
temp[k++] =a[i++];
else
temp[k++] =a[j++];
}
while (i<=mid)
temp[k++] =a[i++];
while (j<=right)
temp[k++] =a[j++];
for (int m=left,n=0;m<=right;m++,n++)
a[m]=temp[n];
}
void Merge_Sort(int a[],int left,int right){
if(left == right) return;
int mid =(left + right)/2;
Merge_Sort(a,left,mid);
Merge_Sort(a,mid+1,right);
Merge(a,left,mid, right);
}
{{ select(2) }}
- O(nlogn)
- O(n)
- O(logn)
- O(n²)
- 以下哪个方案可以合理解决或缓解哈希表冲突?() {{ select(3) }}
- 弃用发生冲突的新元素
- 用新元素覆盖发生冲突的元素
- 用新元素覆盖冲突位置的下一个位置
- 将新元素放置在冲突位置之后的第一个空位
- 在数组H[x]中,若存在(i<j)&&(H[i]>H[j]),则称(H[i],H[j])为数组H[x]的一个逆序对。对于序列17,14,11,29,3,16,18,15,其中有()个逆序对。 {{ select(4) }}
- 13
- 11
- 12
- 14
- 以下()操作不属于STL模板优先队列的操作函数。 {{ select(5) }}
- push
- pop
- erase
- size
- 以下选项中,()没有涉及C++语言的面向对象特性。 {{ select(6) }}
- 在C++中构造一个类或结构体
- 在C++的排序应用中调用sort函数
- 在C++中调用用户定义的类成员
- 在C++中构造来源于同一基类的多个派生子类
- (2023)₁₀+(2025)₁₆和以下哪个选项相等?( ) {{ select(7) }}
- (10252)₁₀
- (280A)₁₆
- (24012)₈
- (24016)₈
- 三个互不相等的正整数的最大公约数为20,最小公倍数为20000,那么这样的不同的正整数组的个数为()。 {{ select(8) }}
- 42
- 48
- 50
- 52
- 关于排序算法,下面的说法中哪个是错误的?() {{ select(9) }}
- 堆排序和桶排序不一样,堆排序是基于比较的
- 堆排序不是一个稳定的排序算法
- 堆排序和快速排序在最坏情况下的时间复杂度都是O(n²)
- 删除堆顶元素,需要交换堆顶元素和最后一个元素,并重新调整
- 假设用V=(d1,d2,d3,d4,d5,d6,d7)来表示某无向图的7个顶点的度数,下面给出的哪组V值是非法的?() {{ select(10) }}
- {5,3,3,3,3,2,2}
- {3,2,3,2,3,6,3}
- {2,3,2,3,2,3,3}
- {1,1,3,4,3,3,3}
- 与图论有关的典型算法中不能处理负权值的是( )。 {{ select(11) }}
- 弗洛伊德算法
- Tarjan算法
- SPFA算法
- 迪杰斯特拉算法
- 有如下代码:
#include<iostream>
using namespace std;
const int MAXN=10;
int dp[MAXN][MAXN];
int main()
{
for (int j=1;j<MAXN;++j)
dp[0][j]=j;
for(int i=1;i<MAXN;++i)
dp[i][0]=i;
for (int i=1;i<MAXN; ++i)
for (int j=1;j<MAXN; ++j)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
cout<<2*dp[8][4]+1<<"\n";
return 0;
}
则程序输出的结果为()。 {{ select(12) }}
- 2021
- 2023
- 2025
- 2027
- 下列选项中,哪个可能是下图的广度优先遍历序列?( )
{{ select(13) }}
- 1,3,5,7,4,2,6,8,9
- 9,4,2,1,3,7,5,6,8
- 1,3,5,7,6,8,9,4,2
- 9,4,7,2,1,3,5,6,8
- 从1到20中任取两个数a和b,a+b不是3的倍数的不同取法有( )种。 {{ select(14) }}
- 180
- 126
- 150
- 175
- 某班级有 n 位同学,编号从1到 n ,联欢晚会抽奖时从1到 n 号中抽出两位同学获得特等奖,现在抽出的两位同学的编号之和为5的概率为1/14,则 n 为()。 {{ select(15) }}
- 10
- 9
- 8
- 7
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特殊说明外,判断题每题1.5分,选择题每题3分,共计40分)
(1)
01 #include<bits/stdc++.h>
02
03 using namespace std;
04
05 const int N=3e5+5,mod=1e9+7;
06 int n,m,a[N],sum[N],lsh[N],f[N];
07 inline int mod_add(int x,int y){
08 x+=y;
09 return x>=mod?x-mod:x;
10 }
11 struct BIT {
12 int c[N];
13 inline void modify(int x,int k){
14 while (x<=m){
15 c[x]=mod_add(c[x],k);
16 x+=(x&-x);
17 }
18 }
19 inline int query(int x){
20 int res=0;
21 while(x){
22 res=mod_add(res,c[x]);
23 x-=(x&-x);
24 }
25 return res;
26 }
27 }odd,even;
28
29 signed main()
30 cin>>n;
31 for (int i=1;i<=n; i++)
32 cin>>a[i];
33 for(int i=1;i<=n;i++)
34 sum[i]=mod_add(sum[i-1],a[i]);
35 for(int i=1;i<=n;i++)
36 lsh[++m]=sum[i];
37 lsh[++m]=0;
38 sort(lsh+1,lsh+m+1);
39 m=unique(lsh+1,lsh+m+1)-lsh-1;
40 even.modify(1,1);
41 for(int i=1;i<=n; i++){
42 int pos = lower_bound(lsh+1,lsh+m+1,sum[i])-lsh;
43 if(sum[i]&1){
44 f[i]=mod_add(odd.query(pos),mod_add(even.query(m),mod-even.query(pos-1)));
45 odd.modify(pos,f[i]);
46 } else {
47 f[i]=mod_add(mod_add(odd.query(m),mod-odd.query(pos-1)),even.query(pos));
48 even.modify(pos,f[i]);
49 }
50 }
51 cout<<f[n]<<endl;
52 return 0;
53 }
对于所有数据,保证1 ≤n ≤3e5,0≤ai<1e9+7。
判断题
- 这段代码的空间复杂度为O(N)。 {{ select(16) }}
- √
- ×
- 如果a数组从0开始存的话,这段代码也能输出正确结果。 {{ select(17) }}
- √
- ×
- 如果不进行取模,f[n]可能会大于int的最大值。 {{ select(18) }}
- √
- ×
选择题
- 如果程序输入
4
1 0 0 0 0 0 0 0 0 6 1 5 1 0 0 0 0 0 0 0 4
则程序输出( )。 {{ select(19) }}
- 1
- 2
- 3
- 4
- 对于以下哪种输入,程序输出为0?( ) {{ select(20) }}
- 1 1
- 1 2
- 2 1 1
- 2 2 2
- 如果程序输入
7
1 2 3 4 5 6 7
则程序输出( )。 {{ select(21) }}
- 1
- 2
- 3
- 4
(2)
01 #include <iostream>
02 #include <algorithm>
03 #include <vector>
04 #include <map>
05 #include <set>
06 #include <numeric>
07 using namespace std;
08 typedef long long ll;
09 typedef vector<int> vi;
10 const int _=5e5*4+1;
11 map<int,vector<int>*>mp;
12 int n,a[_],b[_],last;
13 int o[_];
14 set<int>si;
15 typedef set<int>::iterator sit;
16 sit prei(sit sx) {return --sx; }
17 sit sufi(sit sx) {return ++sx;}
18 class SOL{
19 public:
20 map<int,int>mtr;
21 void radd(int l,int r,int val){
22 mtr[l]+=val,mtr[r+1]-=val;
23 }
24 void rans(){
25 ll ans0=accumulate(a+1,a+n+1,0ll),a=0;
26 for(int i=1;i<=n;i++)
27 cout<<(ans0+=(a+=mtr[i]))<<endl;
28 }
29 }TR;
30 int pre[_],suf[_];
31 bool cmp(int i1,int i2){
32 if(a[i1]==a[i2]) return i1<i2;
33 else return a[i1]<a[i2];
34 }
35 int main(){
36 ios::sync_with_stdio(0),
37 cin.tie(0),cout.tie(0);
38 cin>>n;
39 for(int i=1;i<=n;i++){
40 cin>>a[i],
41 a[i+n]=a[i];
42 if(last==0||a[i]<a[last])
43 last=i+n;
44 }
45 for(int i=1;i<=n;i++)
46 a[i]=a[last-n+i];
47 iota(o+1,o+n+1,1),
48 sort(o+1,o+n+1,cmp);
49 si=set<int>(o+1,o+n+1);
50 for(int i=1;i<=n;i++)
51 si.insert(o[i]),
52 pre[o[i]]=*prei(si.find(o[i])),
53 suf[o[i]]=*sufi(si.find(o[i]));
54
55 for(int i=1;i<=n;i++)
56 ++pre[i];
57 if(a[i]<a[i-1])
58 TR.radd(1,i-pre[i],a[i]);
59 if(a[i]>a[suf[i]])
60 TR.radd(suf[i]-i,suf[i]-pre[i],-a[i]);
61 }
62 TR.rans();
63 }
假设1 ≤n ≤5e5,1 ≤a[i] ≤1e9,回答下列问题。
判断题
- 不考虑空间问题,本段代码只需要_>=5e5*2+1,就不会发生数组越界。 {{ select(22) }}
- √
- ×
- 本段代码使用了二阶前缀和。 {{ select(23) }}
- √
- ×
- 在本段代码第58行与第60行中,实际上是向TR加上或者减去一个等比数列。( ) {{ select(24) }}
- √
- ×
选择题
- 该算法的时间复杂度为( )。 {{ select(25) }}
- O(N²)
- O(log²N)
- O(N)
- O(N log N)
- 如果输入如下:
6
171 814 231 366 761 96897
则程序输出的第一个数为()。 {{ select(26) }}
- 3862
- 3861
- 3860
- 3859
- (4分)如果输入如下:
10
99 101 068 2100000000 1000000000 1000000000
则程序输出的第一个数为( )。 {{ select(27) }}
- 1000000054
- 2000000053
- 3000000054
- 3000000053
(3)
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N=1e5+5,base=20;
04 int f[1<<base],state[1<<base],cnt[1<<base],a[N];
05 int n,ans;
06 void dfs(int u,int now,int state){
07 f[state] =min(f[state],u-1);
08 if(u>5) return;
09 for(int i=now;i<=base;i++)
10 dfs(u+1,i,(state|(1<<i))&((1<<base)-1));
11 }
12 int main(){
13 memset(f,0x7f, sizeof(f));
14 dfs(1,1,1);
15 for(int mid=1;mid<(1<<base);mid<<=1)
16 for(int i=0;i<(1<<base);i+=(mid<<1))
17 for(int j=0;j<mid;j++)
18 f[i+j]=min(f[i+j],f[i+j+mid]);
19 for(int i=1;i<(1<<base);i++)
20 if(!(i&1))f[i]=min(f[i],f[i>>1]);
21 scanf("%d",&n);
22 for(int i=1;i<=n;i++){
23 scanf("%d",&a[i]);
24 for(int j=2;j*j<=a[i];j++){
25 if(a[i]%j==0){
26 int c=0;
27 while(a[i]%j==0)++c,a[i]/=j;
28 state[j]|=(1<<c);
29 ++cnt[j];
30 }
31 }
32 if(a[i]>1)++cnt[a[i]],state[a[i]]|=2;
33 }
34 for(int i=2;i<=100000;i++){
35 if(cnt[i]!=n) state[i]|=1;
36 ans+=f[state[i]];
37 }
38 printf("%d",ans);
39 return 0;
40 }
对于100%的数据,有1 ≤n ≤10⁵,1<ai≤10⁹。
判断题
- 代码第12行运行后,f的所有值都变成-1。 {{ select(28) }}
- √
- ×
- 设x的二进制表示为1000010111010,f[x]在dfs运行完成之后为6。 {{ select(29) }}
- √
- ×
选择题
- 关于第14~18行代码,以下说法中正确的是()。 {{ select(30) }}
- 对于集合i,如果i的所有非自身子集si能被组合出来,那么f[i]=min(f[si])。
- 对于集合i,如果i的所有非自身子集si能被组合出来,那么f[i]=max(f[si])。
- 对于集合i,如果i<<k能被组合出来(1<=k<=20),那么f[i]=min(f[i<<k])。
- 对于集合i,如果i>>k能被组合出来,且二进制下1的个数相同(1<=k<=20),那么f[i]=min(f[i>>k])-1。
- 下列关于第6~10行dfs的描述,正确的是()。 {{ select(31) }}
- 删去这段代码,程序复杂度不变。
- 如果改成u>6才return,其他条件不变,则程序输出不变。
- 如果改成u>4就return,则当base=15时,原程序与新程序执行完dfs后,f数组相同。
- dfs执行完后,f[0]=-1,但因为后面根本不会访问f[0],所以程序依然输出正确结果。
- 关于本段代码,下列说法中正确的是()。 {{ select(32) }}
- 程序执行完毕后,对于state[i],假设当前值为x,并且有一个a[j]恰好能被i^k整除,那么x&(1<<k - 1)必然非零。
- f[i]表示在背包下状态为i所需要的物品最小值,例如f[1000111010]=4,因为{1,2,3,4}是一个符合条件的情况。
- 本段代码的时间复杂度为O(3^base),因为main里面出现了枚举子集的子集。
- 假如a[1]=30,当读入a[1]并执行代码后,cnt[2]=cnt[4]=cnt[8]=0。
三、完善程序(单选题,每小题3分,共计30分)
(1)题目描述:
农场是一块N×N的方格田地(2≤N≤100),某些相邻的田地之间有道路分隔,外围有高围栏防止牛离开。牛可以在任意相邻田地间自由移动(北、东、南、西),但不喜欢过马路。 农场上有K头牛(1 ≤K ≤100,K ≤N²),每头牛位于不同的田地中。如果两头牛之间要相互访问必须至少穿越一条路,这对牛就被认为是"遥远的"。请计算有多少对牛是"遥远的"。 分析:直接记录牛的方位,用dfs染色,记录每个连通块上牛的个数,并且把它们两两相乘即可。
01 #include <cstdio>
02 #include <iostream>
03 #include <algorithm>
04 #include <cstring>
05 #include <vector>
06 using namespace std;
07 int n,k;
08 int road;
09 int a[105][105][4];
10
11 int color[105][105];
12 int b[105][105];
13 int x,y,x1,y1;
14 int num;
15 int all;
16 long long ans;
17 vector<int> area;
18 int dx[4]={-1,0,1,0};
19 int dy[4]={0,1,0,-1};
20 void dfs(int x,int y)
21 {
22 if(①){
23 return;
24 }
25 if(color[x][y]!=-1){
26 return;
27 }
28 color[x][y]=num;
29 if(b[x][y]==1){
30 all++;
31 }
32 for(int i=0;i<4;i++){
33 if(a[x][y][i]==1){
34 continue;
35 }
36 int xx=x+dx[i];
37 int yy=y+dy[i];
38 dfs(xx,yy);
39 }
40 }
41 int main()
42 {
43 cin>>n>>k>>road;
44 for(int i=1;i<=road;i++){
45 cin>>x>>y>>x1>>y1;
46 if(x==x1){
47 a[x][min(y,y1)][1]=1;
48 ②;
49 } else {
50 a[min(x,x1)][y][2]=1;
51 ③;
52 }
53 }
54 for(int i=1;i<=k;i++){
55 cin>>x>>y;
56 b[x][y]=1;
57 }
58 area.push_back(0);
59 memset(color,-1,sizeof(color));
60 for(int i=1;i<=n;i++){
61 for(int i1=1;i1<=n;i1++){
62 if(④){
63 all=0;
64 num++;
65 dfs(i,i1);
66 area.push_back(all);
67 }
68 }
69 }
70 for(int i=1;i<num;i++){
71 for(int i1=i+1;i1<=num;i1++){
72 ⑤;
73 }
74 }
75 cout<<ans;
76 return 0;
77 }
- ①处应填()。 {{ select(33) }}
- x<1|| y<1|| x>n|| y>n
- x>1|| y>1|| x<n|| y<n
- x>=1&& y>=1&& x<=n && y<=n
- x1 && y1 && xn && yn
- ②处应填()。 {{ select(34) }}
- a[x][max(y,y1)][0]=1;
- a[x][max(y,y1)][1]=1;
- a[x][max(y,y1)][2]=1;
- a[x][max(y,y1)][3]=1;
- ③处应填( )。 {{ select(35) }}
- a[max(x,x1)][y][0]=1;
- a[max(x,x1)][y][1]=1;
- a[max(x,x1)][y][2]=1;
- a[max(x,x1)][y][3]=1;
- ④处应填()。 {{ select(36) }}
- color[i][i1]!=-1
- color[i][i1]==-1
- b[i][i1]==1
- b[i][i1]!=1
- ⑤处应填()。 {{ select(37) }}
- ans+=area[i]+area[i1];
- ans+=area[i]-area[i1];
- ans+=area[i]*area[i1];
- ans+=area[i]/area[i1];
(2)题目描述:
对n个单词进行加密。加密过程如下。 (i)选择一个英文字母表的排列作为密钥。 (ii)将单词中的a替换为密钥中的第一个字母,b替换为密钥中的第二个字母,以此类推。 例如,以qwertyuiopasdfghjklzxcvbnm作为密钥对cezar加密后,将得到etmqk。请你给出一种构造方式,最初的第ai个单词位于第i位。请你判断这能否实现。如果能,请给出任意一种可行的密钥。考虑使用拓扑排序完成,代码如下。
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N= 1e2+50;
04 int n, ord[N],in[N];
05 char ans[N],wrd[N][N];
06 vector<int>e[N],s;
07 void add(int x,int y)
08 {
09 for(int i=1;i<=①;i++)
10 if(wrd[x][i]!=wrd[y][i])
11 {
12 e[wrd[x][i]].push_back(wrd[y][i]);
13 if(②)in[wrd[x][i]]=0;
14 if(③)in[wrd[y][i]]=1;
15 else in[wrd[y][i]]++;
16 return;
17 }
18 if(strlen(wrd[x]+1)>strlen(wrd[y]+1))puts("NE"),exit(0);
19 }
20 void topo()
21 {
22 queue<int>q;
23 for(int i='a'; i<='z';i++)if(!in[i])q.push(i);
24 while(!q.empty())
25 {
26 int u=q.front();
27 q.pop();s.push_back(u);
28 for(auto v:e[u])
29 if(!(--in[v])) q.push(v);
30 }
31 }
32 signed main()
33 {
34 scanf("%d",&n);
35 for(int i='a';i<='z';i++)in[i]=-1;
36 for(int i=1;i<=n;i++)scanf("%s",wrd[i]+1);
37 for(int i=1;i<=n;i++)scanf("%d",ord+i);
38 for(int i=1; i< n; i++)
39 for(④)
40 add(ord[i],ord[i+1]);
41 topo();
42 for(int i='a';i<='z';i++)if(in[i]>0) return puts("NE"),0;puts("DA");
43 int cnt=0;
44 for(auto i:s) ans[i]='a'+cnt++;
45 for(int i='a'; i<='z';i++)
46 {
47 if(!ans[i])printf("%c",⑤);
48 else printf("%c",(char)ans[i]);
49 }
50 return 0;
51 }
- ①处应填()。 {{ select(38) }}
- min(strlen(wrd[x]+1),strlen(wrd[y]+1))
- max(strlen(wrd[x]+1),strlen(wrd[y]+1))
- strlen(wrd[x]+1)
- strlen(wrd[y]+1)
- ②处应填()。 {{ select(39) }}
- in[wrd[x][i]]!=-1
- in[wrd[x][i]]==-1
- in[wrd[x][i]]==0
- in[wrd[x][i]]!=0
- ③处应填()。 {{ select(40) }}
- in[wrd[y][i]]!=-1
- in[wrd[y][i]]==-1
- in[wrd[y][i]]==0
- in[wrd[y][i]]!=0
- ④处应填()。 {{ select(41) }}
- int o=i;o<n;o++
- int o=i;o<=n;o++
- int o=i+1;o<n;o++
- int o=i+1;o<=n;o++
- ⑤处应填()。 {{ select(42) }}
- (char)('z'-cnt--)
- (char)('z'---cnt)
- (char)('a'+cnt++)
- (char)('a'+++cnt)