#159. 提高组CSP-S2025初赛模拟卷5

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

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

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

  1. C++语言中析构函数的主要作用是()。 {{ select(1) }}
  • 为对象分配内存空间
  • 对对象的静态数据成员进行初始化
  • 重载对象的运算符
  • 在对象生命周期结束时释放资源,执行清理任务
  1. 以下关于NOI Linux的文件操作需要十分谨慎的是( )。 {{ select(2) }}
  • rm -r
  • cp -a
  • mkdir
  • diff
  1. 以下哪一项并非STL中集合容器所具备的操作函数?( ) {{ select(3) }}
  • insert
  • swap
  • front
  • Lower_bound
  1. 设A = B = true, C = D = false,以下逻辑运算表达式的值为假的是()。 {{ select(4) }}
  • (-AAB)V(CADVA)
  • -(((AAB)VC)AD)
  • AA(BVCVD)VD
  • (AN(DVC)) B
  1. 阅读以下用动态规划解决0 - 1背包问题的函数,假设背包的容量是10kg,4个物品的a(重量)分别为1,3,4,6(单位为kg),每个物品对应的b(价值)分别为20,30,50,60,则函数的输出为( )。
int knapsack(int w,const vector<int> a,const vector<int> b,int n) { 
    vector<vector<int>> dp(n+1,vector<int>(W+1,0); 
    for (int i=1;i<=n; i++){ 
        for(int w=0;w<=W; w++){
            if(a[i-1]<=w){ 
                dp[i][w]=max(dp[i-1][w],dp[i-1][w-a[i-1]]+b[i-1]);
            }
            else{
                dp[i][w]=dp[i-1][w];
            }
        }
    }
    return dp[n][w];
}

{{ select(5) }}

  • 90
  • 100
  • 110
  • 140
  1. 给定一棵二叉树,其前序遍历结果为1245367,中序遍历结果为4521367,则这棵树的后序遍历结果为( )。 {{ select(6) }}
  • 5427631
  • 5472631
  • 4527631
  • 4257631
  1. 一棵有n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )。 {{ select(7) }}
  • O(log n)
  • O(n²)
  • O(n)
  • O(n log n)
  1. 下列选项中,()不是动态规划算法中常见的优化手段。 {{ select(8) }}
  • 滚动数组
  • 单调队列
  • 自动机
  • 状态压缩
  1. 下面哪个说法是错误的?() {{ select(9) }}
  • 向量又称矢量
  • 多重集合不是集合
  • 高斯消元法可以求逆矩阵和行列式
  • 矩阵只能做加减运算,不能做乘法运算
  1. 设正整数1 ≤n ≤2025,则使n⁵ - 5n³ + 4n + 15是完全平方数的可能的n的个数为()个。 {{ select(10) }}
  • 3
  • 0
  • 1
  • 2
  1. 以下哪种数据结构是线性数据结构?( ) {{ select(11) }}
  • trie
  • Treap
  • deque
  • Splay
  1. 冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和桶排序算法中有( )个是稳定的。 {{ select(12) }}
  • 3
  • 4
  • 5
  • 2
  1. 对于一个正整数n,如果能找到正整数a和b使得n = a + b + ab,则称n为奇特数,例如3 = 1 + 1 + 11就是一个奇特数,从1到100中有()个奇特数。 {{ select(13) }}
  • 74
  • 72
  • 73
  • 75
  1. 现有7把钥匙和7把锁,用这些钥匙随机开锁,则A1,A2,A3这三把钥匙全部不能打开对应锁的概率是()。 {{ select(14) }}
  • 3/7
  • 67/105
  • 12/35
  • 9/49
  1. 以下哪种方法不是解决哈希冲突的方法?() {{ select(15) }}
  • 开哈希法
  • 线性探查法
  • 二次探查法
  • 复杂哈希函数

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

(1)

01 #include <bits/stdc++.h>
02
03 #define N 1005
04 using namespace std;
05
06 int n,m,t,fi[N],nt,cnt,L[N*N][N],mh[N],ans;
07 bool vis[N];
08 char c[N];
09
10 struct pf{
11     int ne,to;
12 }L[N*N];
13
14 struct data{
15     int x,y;
16 }a[N];
17
18 inline void add(int x,int y){
19     L[++cnt].ne=fi[x];
20     L[cnt].to=y;
21     fi[x]=cnt;
22 }
23
24 inline int read(){
25     int res=0,f=1;char ch=getchar();
26     while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
27     while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
28     return res*f;
29 }
30
31 inline bool dfs(int u){
32     for(int i=fi[u];i;i=L[i].ne){
33         int v=L[i].to;
34         if(vis[v])continue;
35         vis[v]=1;
36         if(!mh[v]||dfs(mh[v])){
37             mh[v]=u;
38             return 1;
39         }
40     }
41     return 0;
42 }
43
44 int main(){
45     n=read(),m=read();
46     for(int i=1;i<=n;++i){
47         scanf("%s",c+1);
48         for(int j=1;j<=m;++j)
49             if(c[j]=='1')a[++t].x=i,a[t].y=j;
50     }
51     for(int i=1;i<=t;++i)
52         for(int j=i+1;j<=t;++j)
53             if(a[i].y+1==a[j].y&&a[i].x==a[j].x||(a[i].y==a[j].y&&a[i].x+1==a[j].x))L[i][j]=1;
54     for(int k=1;k<=t;++k)
55         for(int i=1;i<=t;++i)
56             for(int j=1;j<=t;++j)
57                 L[i][j]|=L[i][k]&&L[k][j];
58     for(int i=1;i<=t;++i)
59         for(int j=i+1;j<=t;++j)
60             if(L[i][j])add(i,j+t);
61     for(int i=1;i<=t;++i){
62         memset(vis,0,sizeof(vis));
63         if(dfs(i))++ans;
64     }
65     printf("%d\n",t-ans);
66     return 0;
67 }

假设1 ≤N,M≤20,输入1的个数不会超过200个,回答下列问题。

判断题

  1. 这段代码的时间复杂度为O(N²)。 {{ select(16) }}
  • √
  • ×
  1. 这段代码的空间复杂度为O(N²)。 {{ select(17) }}
  • √
  • ×
  1. t的最大值为n×m。 {{ select(18) }}
  • √
  • ×

选择题

  1. 若读入
5 5
00100
11111
00100
11111
00100

则程序运行跳出第51行的循环后,有多少个f[i][j]的初始值为1?() {{ select(19) }}

  • 10
  • 11
  • 12
  • 13
  1. 若读入
5 5
10101
10101
01110
11111
00100

则程序运行跳出第51行的循环后,有多少个f[i][j]的初始值为1?() {{ select(20) }}

  • 13
  • 14
  • 15
  • 16

(2)

01 #include <cstdio>
02 #include <iostream>
03 #include <algorithm>
04 #include <cstring>
05 using namespace std;
06 const int Maxn=3e5+10;
07 char s[Maxn],t[Maxn];
08 int a[Maxn],b[Maxn];
09 int f[Maxn];
10 int n;
11 inline bool cmp(int x,int y)
12 {
13     return x>y;
14 }
15 int main()
16 {
17     scanf("%s",s+1);
18     n=strlen(s+1);
19     for(int i=1;i<=n;++i)
20         a[i]=s[i]-'a';
21     scanf("%s",t+1);
22     for(int i=1;i<=n;++i)
23         b[i]=t[i]-'a';
24     sort(a+1,a+1+n);
25     sort(b+1,b+1+n,cmp);
26     int x=0,y=0,pos=n;
27     for(int i=1;i<=n;++i)
28     {
29         if(a[x+1]>=b[y+1]) {pos=i-1;break;}
30         if(i&1)f[i]=a[++x];
31         else f[i]=b[++y];
32     }
33     x=y=(n>>1)+1;
34     if((n&1)) ++x;
35     for(int i=n;i>pos;--i)
36     {
37         if((pos+(n-i+1))&1)f[i]=a[--x];
38         else f[i]=b[--y];
39     }
40     for(int i=1;i<=n;++i)
41         putchar(f[i]+'a');
42     putchar('\n');
43     return 0;
44 }

假设读入的两个字符串长度n满足1 ≤n ≤3e5,其他输入均合法,回答下列问题。

判断题

  1. 第25行排序的cmp函数使得b数组变为从大到小排列,为达到同样的效果也可以使用Less。 {{ select(21) }}
  • √
  • ×
  1. std::sort()的时间复杂度是随机的,从O(N)到O(N²)都有可能。 {{ select(22) }}
  • √
  • ×
  1. (2分)假设这里用的sort采用了快速排序,那么快速排序是稳定的,即对于i<j,当ai = aj时,排序后ai一定在aj前。 {{ select(23) }}
  • √
  • ×
  1. (2分)若将第33行代码x=y=(n>>1)+1;改为x=y=n>>1+1;,程序在所有相同输入下输出不变。 {{ select(24) }}
  • √
  • ×

选择题

  1. 若程序输入
tinkoff
zscoder

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

  • fzfsirk
  • fzfsidk
  • zfsfrik
  • Zfsfdik
  1. 下列说法中正确的是()。 {{ select(26) }}
  • strlen()和vector的size()函数的时间复杂度相同,都为O(N)。
  • 当输入两个相同的串时,该程序的输出也是这个串。
  • 当输入两个不同的串a,b时,该程序也可能输出与a或b相同的串。
  • 若将这段代码中的--y全部改成y--,程序依然可以输出相同的结果。
  1. 假设当n = 100时,第37行中的f[i]=a[--x];语句最多被执行多少次?( ) {{ select(27) }}
  • 8
  • 49
  • 50
  • 100

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 typedef long long LL;
04 const int N=1e6+5,INF=0x3f3f3f3f;
05 const LL mod =1e9+7;
06 int n,L,a,b;
07 bool flag[N];
08 int c[N];
09 int dp[N];
10 struct segtree{
11     int l,r,val;
12 #define L(x) tr[x].l
13 #define r(x) tr[x].r
14 #define val(x) tr[x].val
15 }tr[N<<1];
16 void pushup(int x){
17     val(x)=min(val(x<<1),val(x<<1|1));
18 }
19 void build(int l,int r,int x){
20     L(x)=l,r(x)=r,val(x)=INF;
21     if(l==r)return;
22     int mid=l+r>>1;
23     build(l,mid,x<<1),build(mid+1,r,x<<1|1);
24 }
25 void update(int pos,int v,int x){
26     if(L(x)==r(x)){
27         val(x)=v;
28         return;
29     }
30     int mid =L(x)+r(x)>>1;
31     if(mid>=pos)update(pos,v,x<<1);
32     else update(pos,v,x<<1|1);
33     pushup(x);
34 }
35 int query(int l,int r,int x){
36     if(l<=L(x)&&r(x)<=r) return val(x);
37     int mid=L(x)+r(x)>>1,res=INF;
38     if(l<=mid) res =query(l,r,x<<1);
39     if(r>mid)res=min(res,query(l,r,x<<1|1));
40     return res;
41 }
42 int main()
43 {
44     ios::sync_with_stdio(false);
45     cin.tie(nullptr);
46     cin>>n>>L>>a>>b;
47     for(int i=1;i<=n;i++){
48         int x,y;
49         cin>>x>>y;
50         c[x+1]++,c[y]--;
51     }
52     for(int i=1;i<=L;i++){
53         c[i]+=c[i-1];
54         if(c[i]>0)flag[i]=true;
55     }
56     build(0,L,1);
57     update(0,0,1);
58     for(int i=a*2;i<=L;i+=2){
59         if(flag[i])continue;
60         int ql=max(0,i-2*b),qr=i-2*a;
61         dp[i]=query(ql,qr,1)+1;
62         update(i,dp[i],1);
63     }
64     if(dp[L]>=INF)dp[L]=-1;
65     cout<<dp[L]<<'\n';
66     return 0;
67 }

假设对于输入满足1 ≤L ≤1e6,1 ≤A ≤B ≤1e3,1≤N≤1e3,1≤Si<Ei≤L;L定是一个偶数。

判断题

  1. 本段代码第15行中的N<1应该改成N<2,否则会发生数组下标越界。 {{ select(28) }}
  • √
  • ×

选择题

  1. dp数组的转移方程是( )。 {{ select(29) }}
  • dp[i]=min(dp[j]), i - b<=j<=i - a
  • dp[i]=min(dp[j]), i - b2<=j<=i - a2
  • dp[i]=min(dp[j])+1, i - b<=j<=i - a
  • dp[i]=min(dp[j])+1, i - b2<=j<=i - a2
  1. 若输入
2 8
1 2
6 7
3 6

则程序输出( )。 {{ select(30) }}

  • -1
  • 1
  • 2
  • 3
  1. 若输入
4 8
1 2
6 7
3 6
2 4
1 8

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

  • -1
  • 1
  • 2
  • 3
  1. 以下说法中正确的是( ) {{ select(32) }}
  • 第50行代码中的flag数组标记了[x + 1,y - 1]这个区间。
  • 第57行代码update(0,0,1);可删去,因为这是对第0个元素更新值,完全没有必要。
  • 第58行代码for(inti=a2;i<=l;i+=2)可以改成for(inti=a2;i<=l;i+=1)。
  • 第61行代码中的query(q1,qr,1)也可以写成query(ql,qr,0)。

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

(1)题目描述:

给你一个n×n的矩阵,你可以将k×k的连续子矩阵全部加一或者减一,初始时,有m个位置不是0,其他全部是0,请问你至少需要多少次操作才能将矩阵中的所有数都变为0?如果无法实现,请输出-1。 显然,利用差分性质能够实现快速修改,具体做法是按照顺序依次修改(1,1),(1,2),(1,n),…(n,n)。

01 #include <bits/stdc++.h>
02 #define ll long long
03 using namespace std;
04 ll d[5010][5010],f[5010][5010];
05 int n,m,k;
06 void cf(int x,int y,int c){
07     int xx=x+k,yy=y+k;
08     if(①){
09         cout<<"-1";
10         exit(0);
11     }
12     d[x][y]-=c;
13     d[xx][y]+=c;
14     d[x][yy]+=c;
15     ②;
16 }
17 int main(){
18     ll ans=0;
19     scanf("%d%d%d",&n,&m,&k);
20     while(m--){
21         int x,y;
22         ll z;
23         scanf("%d%d%lld",&x,&y,&z);
24         f[x][y]=z;
25     }
26     for(int i=1;i<=n;i++)
27         for(int j=1;j<=n;j++)
28             ③;
29         ll k=④;
30         if(k){
31             ans+=⑤;
32             cf(i,j,k);
33         }
34     }
35     printf("%lld",ans);
36     return 0;
37 }
  1. ①处应填( )。 {{ select(33) }}
  • xx>=n+1||yy>=n+1
  • xx>n+1&&yy>n+1
  • xx<1||yy<1
  • xx<1&&yy<1
  1. ②处应填()。 {{ select(34) }}
  • d[yy][xx]-=c
  • d[yy][xx]+=c
  • d[xx][yy]-=c
  • d[xx][yy]+=c
  1. ③处应填()。 {{ select(35) }}
  • -d[i-1][j-1]
  • d[i][j-1]-d[i-1][j-1]
  • d[i-1][j]-d[i-1][j-1]
  • d[i-1][j]+d[i][j-1]-d[i-1][j-1]
  1. ④处应填()。 {{ select(36) }}
  • d[i][j]
  • f[i][j]
  • d[i][j]+f[i][j]
  • d[i][j]-f[i][j]
  1. ⑤处应填( )。 {{ select(37) }}
  • 1
  • abs(k)
  • k
  • -k

(2)题目描述:

给定一个序列,选择一个前缀和一个与之不相交的后缀,使得所有被选择的数的异或和最大。 先计算并且插入所有后缀异或和bki,从前往后记录当前前缀和cur,删除后缀异或和并在Trie树里面寻找与cur对应的异或最大值,更新答案即可。

01 #include <bits/stdc++.h>
02 #define ll long long
03 #define reg register
04 #define F(i,a,b) for(reg int i=(a);i<=(b);i++)
05 inline ll read();
06 using namespace std;
07 const int N=1e5+10;
08 int n,trie[N*64][2],cnt=1,rec[N*64];
09 LL bk[N],a[N],ans;
10 inline void insert(ll x){
11     int p=1;
12     for(reg int i=62;i>=0;i--){
13         bool k=(x&(①));
14         if(!trie[p][k])trie[p][k]=++cnt;
15         p=trie[p][k];
16         ②;
17     }
18 }
19 inline void del(ll x){
20     int p=1;
21     for(reg int i=62;i>=0;i--){
22         bool k=(x&(1ll<<i));
23         if(rec[p] || !trie[p][k])return;
24         p=trie[p][k];
25         rec[p]--;
26     }
27 }
28 inline ll search(ll x){
29     int p=1;
30     ll s=0;
31     for(reg int i=62;i>=0;i--){
32         bool k=(x&(1ll<<i));
33         s<<=1;
34         int &to=③;
35         if(!to or !rec[to]){
36             if(trie[p][k])p=trie[p][k];
37             else break;
38         }
39         else p=to,s|=1;
40     }
41     return s;
42 }
43 int main(){
44     n=read();
45     F(i,1,n)a[i]=read();
46     for(reg int i=n;i>=1;i--)bk[i]=④,insert(bk[i]);
47     ll cur=0;
48     ans=search(cur);
49     F(i,1,n){
50         cur^=a[i];
51         ⑤;
52         ans=max(ans, search(cur));
53     }
54     printf("%lld",ans);
55     return 0;
56 }
57 inline ll read(){//快速读入
58     reg ll x=0;
59     reg char c=getchar();
60     while(!isdigit(c))c=getchar();
61     while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
62     return x;
63 }
  1. ①处应填( )。 {{ select(38) }}
  • 11l<<i
  • 1<<i
  • pow(4,i-1)
  • pow(4ll,i-1)
  1. ②处应填( )。 {{ select(39) }}
  • 不填写
  • rec[p]++
  • rec[p]--
  • rec[p]^=1
  1. ③处应填()。 {{ select(40) }}
  • trie[p][k]
  • trie[p][k^1]
  • ++cnt
  • --cnt
  1. ④处应填()。 {{ select(41) }}
  • bk[i]=bk[i+1]^a[i]
  • bk[i]=bk[i+1]^a[i+1]
  • bk[i]=bk[i-1]^a[i]
  • bk[i]=bk[i-1]^a[i-1]
  1. ⑤处应填()。 {{ select(42) }}
  • del(i)
  • del(bk[i+1])
  • del(bk[i])
  • del(bk[i-1])
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 闽ICP备2024031974号-1
  3. Powered by Hydro v5.0.0-beta.3 Community, Modified by Robinchen