#10627. 提高组CSP-S2025初赛模拟卷10

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

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

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

  1. 在NOI Linux 2.0环境下,以下哪条命令能够实现指定C++特定版本进行编译? {{ select(1) }}
  • g++-g-std=c++11 main.cpp-omain
  • g++-g-std=c++14main.cpp-omain
  • g++-g-std=C++17main.cpp-omain
  • g++-g-std=c++20main.cpp-omain
  1. 下面有关格雷码的说法中,错误的是()。 {{ select(2) }}
  • 在格雷码中,任意两个相邻的代码在二进制下有且仅有一位不同
  • 长度为3的格雷码依次为000,001,010,01,100, 101, 110,111
  • 格雷码由贝尔实验室的Frank Gray在20世纪40年代提出
  • 格雷码是一种可靠性编码
  1. 以下哪个选项不属于STL中链表的操作函数?() {{ select(3) }}
  • resize
  • push_back
  • pop
  • front
  1. 下列关于namespace的说法中错误的是()。 {{ select(4) }}
  • namespace可以嵌套,例如 namespace X[namespace Y {inti;}}
  • namespace只可以在全局定义
  • namespace中可以存放变量和函数
  • 如果程序中使用using命令同时引用了多个namespace,并且namespace中存在相同的函数,会出现程序错误
  1. 某哈夫曼树(根结点为第1层)共有7个叶子结点,这棵树的高度不可能是( )。 {{ select(5) }}
  • 8
  • 6
  • 5
  • 4
  1. 现有一段3分钟的视频,它的播放速度是每秒24帧图像,每帧图像是一幅分辨率为1920像素x1080像素的32位真彩色图像。请问要存储这段原始无压缩视频,大约需要多少字节的存储空间?() {{ select(6) }}
  • 286.6 GB
  • 71.6 GB
  • 142.3 GB
  • 35.8 GB
  1. 在桶排序算法中,对于一个长度为 n 的序列,设桶的个数为 m ,在桶内使用插入排序,则其平均时间复杂度是()。 {{ select(7) }}
  • O(n m)
  • O(n²)
  • O(n+m+n²/m)
  • O(n+m)
  1. 以下判断一个整数n是否为奇数的代码中,错误的是( )。 {{ select(8) }}
  • if(n%2)
  • if(n&1)
  • if (n%2==1)
  • if (!(n%2==0))
  1. 下面关于计算机软硬件历史的说法中,错误的是()。 {{ select(9) }}
  • 第三代计算机使用了集成电路,降低了计算机的空间占用和成本
  • 20世纪80年代,微软公司开发出了MS-DOS操作系统
  • 图灵发明了名为"巨人"的计算机,破解了德军的ENIGMA密码
  • 第一台基于冯·诺依曼思想的计算机是1946年发明的ENIAC
  1. p,q为质数,p整除7q+1,q整除7p+1,则有()组不同的p和q组合。 {{ select(10) }}
  • 4
  • 6
  • 8
  • 10
  1. KMP算法属于与()相关的算法。 {{ select(11) }}
  • 并查集
  • 线段树
  • 字符串
  • 二分图
  1. 若集合I={1,2,3,4,5},选择集合I的两个非空子集A和B,要使得B中最小的数大于A中最大的数,一共有( )种不同的选择。 {{ select(12) }}
  • 50
  • 48
  • 47
  • 49
  1. 如果今天是星期一,那么对于任意正整数n,经过2025n+2023n+2025天后是( )。 {{ select(13) }}
  • 星期四
  • 星期三
  • 星期二
  • 星期一
  1. 6名参加信息学竞赛的学生A、B、C、D、E、F站成一排拍照,要求A一定要在B的左边(不一定相邻),一共有()种排列方法。 {{ select(14) }}
  • 720
  • 360
  • 480
  • 540
  1. 设甲、乙两人每次射击命中目标的概率分别为0.75和0.8,且各次射击相互独立,若按甲、乙、甲、乙…·的次序轮流射击,直到有一人击中目标就停止射击,则停止射击时,甲射击了两次的概率是()。 {{ select(15) }}
  • 7/120
  • 11/240
  • 19/400
  • 23/480

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

(1)

01 #include <bits/stdc++.h>
02
03 const int Max=100005;
04 long long t,n,p[Max],s[Max],a[Max],E;
05
06 int main(){
07 scanf("%Lld",&t);
08 while(t--){
09 scanf("%Lld",&n);
10 for (int i=1;i<=n; i++)
11 scanf("%Lld",&p[i]);
12 for (int i=1; i<=n; i++)
13 scanf("%Lld",&s[i]);
14 for (int i=0; i<=n; i++)
if(p[i]==-1&&s[i+1]==-1){
15
16 E=p[i]^s[i+1];
17 break;
18 }
19 for (int i=0;i<=n; i++){
20 if(p[i]==-1&&s[i+1]!=-1)
21 p[i]=E^s[i+1];
22 else if(p[i]!=-1&&s[i+1]==-1)
23 s[i+1]=E^p[i];
24 else if(p[i]==-1&&s[i+1]==-1)
25 p[i]=1;
26 if(i)
27 printf("%Lld ",p[i]^p[i-1]);
28 }
29 puts("");
30 }
31 }

保证每组数据均有-1 ≤p_i, s_i ≤2^60,且∑[p_i=-1]+∑[s_i=-1]=n,回答下列问题。

判断题

  1. 如果p[i]是int类型,则与原程序相比,不一定能输出正确答案。
  2. 将第29行中的puts()函数改成putchar(),程序的输出不变。
  3. (2分)当n=1时,程序输出p[1]与s[1]中非-1的那个数。
  4. (2分)E不会大于pi和si的最大值。

选择题

  1. 若程序输入为
1
4
-1-1-1-1
2357

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

  • 1627
  • 7261
  • 2612
  • 2162
  1. 若程序输入为
1
4
-134367-1
3178-1-13333

则程序输出中的第三个数为( )。 {{ select(21) }}

  • 3333
  • 333
  • 3178
  • 267

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int NR=1e3+10;
04 int n,s,t,ans=1000, a[NR],b[NR],f[2][NR];
05
06 int main(){
07 cin>>n>>s>>t;
08 if(s>=t){
09 for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
10 puts("0");
11 return 0;
12 }
13 memset(f[0],-9999,sizeof(f[0]));f[0][0]=s;
14 for(int i=0;i<ans;i++){
15 int now=i&1,pre=now^1;
16 for(int j=0;j<=t;j++)
17 for(int k=1;k<=n;k++)
if(f[now][j]!=-9999){
18
19 if(j+b[k]<=t)
f[now][j+b[k]]=max(f[now][j+b[k]],f[now][j]-a[k]);
20 else ans=i+1;
21 }
22 memset(f[pre],-9999,sizeof(f[pre]));
23 for(int j=0;j<=t;j++)
24 if(f[now][j]+j>=t) ans=i+1;
25 else f[pre][j]=f[now][j]+j;
26 }
27 cout<<ans<<endl;
28 return 0;
29 }

假设数据满足1 ≤n ≤100,1 ≤s;t ≤1000,1 ≤a_i,b_i ≤2^31,回答下列问题。

判断题(每题2分)

  1. 将第22行中的-9999999改为-1,程序输出不变。
  2. 本段代码的时间复杂度为O(n³)。
  3. 本段代码使用了滚动数组优化f数组空间。

选择题

  1. 假设某组输入为
1 18
11

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

  • 1
  • 2
  • 3
  • 4
  1. 假设某组输入为
218
11
28

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

  • 1
  • 2
  • 3
  • 4
  1. 如果删除第22行代码,则在输入相同时,程序输出与原来相比( )。 {{ select(27) }}
  • 变大或不变
  • 不变
  • 变小或不变
  • 以上情况都有可能

(3)

01 #include <bits/stdc++.h>
02
03 #define int long long
04 using namespace std;
05
06 const int INF=3e5+5;
07
08 string s1;
09 int sum[INF][35],t[35],La[35],la1[35];
10
11 int check(int l,int r){
12 int ans=0;
13 for (int i=0;i<26;i++)
14 if(sum[r][i]-sum[l-1][i])ans++;
15 return ans;
16 }
17
18 signed main()
19 {
20 ios::sync_with_stdio(false);
21 cin>>s1;int len=s1.size();s1=" "+s1;
22 for(int i=1;i<=len;i++){
23 for(int j=0;j<26;j++)
24 sum[i][j]=sum[i-1][j]+((s1[i]-'a')==j);
25 }
26 for (int i=1;i<=26;i++){
27 int j1=0,j2=0,sum1=0,sum2=0;
28 for (int k=1;k<=len;k++){
29 j1=max(j1,k-1);j2=max(j2,k-1);
30 while (j1+1<=len&&sum1<=i){
31 if(La[s1[j1+1]-'a']==0&&sum1==i)break;
32 La[s1[j1+1]-'a']++;
33 if (La[s1[j1+1]-'a']==1) sum1++;
34 j1++;
35 }
36 while (j2+1<=len&&sum2<i){
37 la1[s1[j2+1]-'a']++;
38 if (la1[s1[j2+1]-'a']==1) sum2++;
39 j2++;
40 }
41 if(sum2==i&&sum1==i)t[i]+=j1-j2+1;
42 la1[s1[k]-'a']--;
43 if (la1[s1[k]-'a']==0) sum2--;
44 la[s1[k]-'a']--;
45 if(La[s1[k]-'a']==0)sum1--;
46 }
47 }
48 cout<<check(1,len)<<"\n";
49 for(int i=1;i<=26;i++)
50 if(t[i])cout<<t[i]<<"\n";
51 return 0;
52 }

输入数据满足1 ≤|s1| ≤10^5,且为小写字母组成的字符串。

判断题

  1. 程序第一个输出的数字可能为0。
  2. 在第9行声明数组时,如果将声明t[35]改成t[25],程序一定发生运行错误。

选择题

  1. 若程序输入abca,则程序输出的最大值是( )。 {{ select(30) }}
  • 1
  • 2
  • 3
  • 4
  1. 程序在第50行输出的数字之和与字符串s1长度n的关系为( )。 {{ select(31) }}
  • 等于(n*(n+1))/2
  • 小于(n*(n+1))/2
  • 大于(n*(n+1))/2
  • 以上都有可能
  1. 当输入一个长度为n的字符串时,代码j1j2移动的最大次数约为()。 {{ select(32) }}
  • N
  • n*n
  • 26*n
  • 26nn

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

(1)题目描述:

有一个H行W列的网格,每一格都被涂成黑色或白色。 形式化地,有H个长为W的字符串S1,S2,.,SH。若Si.j是#,则网格中第i行第j列被涂为黑色;若Si.j是,则网格中第i行第j列被涂为白色。 若有一条从黑色方格到达白色方格的路径,途中只沿水平或垂直方向移动,所经相邻方格颜色不同,我们将这条路径称为合法路径。 求网格中有多少合法路径。

01 #include <bits/stdc++.h>
02 #define ll long long
03 #define ri register
04 #define al(x)x.begin(),x.end()
05 using namespace std;
06 const int N=401,M=N*N;
07 int n,m,f[M],g[M],sz[M];
08 ll ans;
09 char a[N][N];
10 inline int ord(int x,int y){return ①;}//压成一位
11 inline int find(int z){return f[z]==z?z:②;}//并查集
12 inline void merge(int x,int y){
13 x=find(x),y=find(y);
14 if(x==y) return;
15 f[x]=y,sz[y]+=sz[x],g[y]+=g[x];
16 sz[x]=g[x]=0;
17 }
18 int main(){
19 scanf("%d%d",&n,&m);
20 for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
21 for(int i=1;i<=n;i++)
22 for(int j=1;j<=m;j++)
23 if(③)a[i][j]=④,g[ord(i,j)]++;
24 for(int i=1;i<=n*m;++i)sz[i]=1,f[i]=i;
25 for(int i=1;i<=n;i++)
26 for(int j=1;j<=m;j++){
27 if(a[i][j]==a[i+1][j])
28 merge(ord(i,j),ord(i+1,j));
29 if(a[i][j]==a[i][j+1])
30 merge(ord(i,j),ord(i,j+1));
31 }
32 for(int i=1;i<=n*m;i++)
33 if(f[i]==i)ans+=⑤;
34 printf("%lld\n",ans);
35 return 0;
36 }
  1. ①处应填( )。 {{ select(33) }}
  • y*m+X
  • (y-1)*m+X
  • (x-1)*m+y
  • (x-1)*n+y
  1. ②处应填()。 {{ select(34) }}
  • f[z]:z
  • f[z]=find(f[z]):z
  • z:f[z]=find(z)
  • z:f[z]=find(f[z])
  1. ③处应填( )。 {{ select(35) }}
  • (i+j)==1
  • (i+j)%2
  • (i-j)%2==1
  • (i*j)%2
  1. ④处应填()。 {{ select(36) }}
  • a[i][j]=='#'?".':"#'
  • a[i][j]=='.'?".':"#'
  • ~a[i][j]
  • a[i][j]
  1. ⑤处应填()。 {{ select(37) }}
  • 1ll*g[i]*sz[i]
  • 1LLg[i](sz[i]-g[i])
  • 1llg[i](sz[i]-1)
  • g[i]

(2)题目描述:

给定n个由大写字母组成的字符串,选择尽量多的串,使得每个大写字母都出现偶数次。n ≤24。 (提示:采用折半搜索策略。)

01 #include <bits/stdc++.h>
02 #define MAXN 35
03 #define MAXM10005
04 using namespace std;
05 map<int,int>m;
06 int n,has[MAXN];
07 char ch[MAXM];
08
09 int lowbit(int x)
10 {
11 return x&-x;
12 }
13
14 int Calc(int x)
15 {
16 int res=0;
17 for(;①;res++);
18 return res;
19 }
20
21 int main()
22 {
23 while(cin>>n)
24 {
25 m.clear();
26 memset(has, 0, sizeof(has));
27
28 for(int i=0;i<n;i++){
29 scanf("%s",ch+1);
30 int len=strlen(ch+1);
31 for(int j=1;j<=len;j++)has[i]^=1<<(ch[j]-65);
32 }
33 int ans=0,n1=②,n2=n-n1;
34 for(int i=0;i<(1<<n1);i++)
35 {
36 int x=0;
37 for(int j=0;j<n1;j++)if(i&(1<<j))x^=has[j];
38 if(③)m[x]=i;
39 }
40 for(int i=0;i<(1<<n2);i++)
41 {
42 int x=0;
43 for(int j=0;j<n2;j++)if(i&(1<<j))x^=has[n1+j];
44 if(④)ans=max(ans,Calc((i<<n1)|m[x]));
45 }
46 printf("%d\n",Calc(ans));
47 for(int i=0;i<n;i++)if(⑤)printf("%d ",i+1);
48 puts("");
49 }
50 return 0;
51 }
  1. ①处应填( )。 {{ select(38) }}
  • x<=n;x+=lowbit(x)
  • X<=n;x-=lowbit(x)
  • x;x-=lowbit(x)
  • x;x+=lowbit(x)
  1. ②处应填()。 {{ select(39) }}
  • 1
  • n/2
  • n-1
  • n
  1. ③处应填( )。 {{ select(40) }}
  • !m.count(x)||Calc(m[x])<Calc(i)
  • !m.count(x)||Calc(m[x])<Calc(i)
  • m.count(x)&&Calc(m[x])<Calc(i)
  • m.count(x)||Calc(m[x])<Calc(i)
  1. ④处应填()。
    {{ select(41) }}
  • m.count(x)||Calc(ans)>Calc((i<<n1)|m[x])
  • m.count(x)||Calc(ans)<=Calc((i<<n1)|m[x])
  • m.count(x)&&Calc(ans)<Calc((i<<n1)|m[x])
  • m.count(x)&&Calc(ans)>=Calc((i<<n1)|m[x])
  1. ⑤处应填()。
    {{ select(42) }}
  • ans&(1<<i)
  • ans|(1<<i)
  • ans&(1<<(i-1))
  • ans|(1<<(i-1))
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 闽ICP备2024031974号-1
  3. Powered by Hydro v5.0.0-beta.3 Community, Modified by Robinchen