2022提高级 CSP-S 初赛模拟试题（11）

• 分類：CSP-S 提高组
• 來源：https://lib.nbdp.net/paper/138.html

---

2022提高级 CSP-S 初赛模拟试题（11）

一、单选题（每题 2 分，共 30 分） 查看答案

---

第 1 题 请选出以下最大的数( )。

• A. (2333)10
• B. (999)16
• C. (10101111)2
• D. 2^11

答案：

---

第 2 题 微型计算机中，( ) 的存取速度最快。

• A. 高速缓存
• B. 寄存器
• C. 外存储器
• D. 内存储器

答案：

---

第 3 题 128 KB包含( )个二进制位。

• A. 128×1000
• B. 128×1000×8
• C. 128×1024
• D. 128×1024×8

答案：

---

第 4 题 有一个空队列Q，对下列待进队的数据元素序列a,b,c,d,e,f依次进行:进队,进队,进队,出队,进队,出队,出队,进队。则操作完成后队首元素为( ) 。

• A. a
• B. c
• C. d
• D. e

答案：

---

第 5 题 设变量x为int型且已赋值则以下语句能将x二进制下第0~k-1位清零，并保持其余位不变的操作是( )。

• A. x &=(1 << k)-1
• B. x│=(1 << k)-1
• C. x &=~((1 << k)-1)
• D. x│=~((1 << k)-1)

答案：

---

第 6 题 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，有19条边的二分图至少有( )个 顶点。

• A. 8
• B. 9
• C. 10
• D. 11

答案：

---

第 7 题 字符串abede中有( )个非空子串。

• A. 15
• B. 14
• C. 17
• D. 16

答案：

---

第 8 题 以下排序算法中，( ) 是不稳定排序。

• A. 桶排序
• B. 归并排序
• C. 冒泡排序
• D. 选择排序

答案：

---

第 9 题 由数字1,2,3,4,5,6,7(同一数字可以重复使用)所组成的不同的三位数中有( )个是3的倍数。

• A. 43
• B. 72
• C. 78
• D. 115

答案：

---

第 10 题 快速排序的最坏时间复杂度是( ) 。

• A. O(n^2)
• B. O(nlog^2 n)
• C. O(n log n)
• D. O(n)

答案：

---

第 11 题 图灵是( )人。

• A. 中国
• B. 日本
• C. 英国
• D. 美国

答案：

---

第 12 题 用邻接矩阵来存储一张具有n个顶点，m条边的图。则进行深度优先遍历运算的时间复杂度为( )。

• A. O(n^2)
• B. O(m^2)
• C. O(nm)
• D. O(n+m)

答案：

---

第 13 题 1414至多可以表示为( )个不同的正整数之和。

• A. 50
• B. 51
• C. 52
• D. 53

答案：

---

第 14 题 下列语言中属于解释执行的语言是( )。

• A. C++
• B. Pascal
• C. C
• D. Python

答案：

---

第 15 题 在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。 下列物品中不允许选手自带的是( )。

• A. 笔
• B. 纸
• C. 准考证
• D. 身份证

答案：

---

二、判断题（每题 2 分，共 20 分）

---

第 16 题

#include <bits/stdc++.h>
using namespace std;
int n,a[5000],c[65536];
int main() {
	cin>>n;

	for (int i=0; i<n; i++) {
		cin>>a[i];
	}
	
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (i!=j) {
				c[a[i] ^ a[j]]++;
			}
		}
	}

	int t=0;

	for (int i=0; i<=65535; i++) {
		if (c[i]>c[t]) {
			t=i;
		}
	}
	
	cout<<t<<endl;
	return 0;
}

除特殊声明外，假设输入的n和a[i]都是不超过65535的非负整数，完成下面的判断 区和单选题:

判断题

---

第 17 题

#include<bits/stdc++.h>
#define N 100000
using namespace std;
int n, Fac[N+5], FacInv[N+5],MOD=1e9+7;
char s1[N+5],s2[N+5];
int C(int x,int y) {
	return 1LL*Fac[x]*FacInv[y]%MOD*FacInv[x-y]%MOD;
}
int quick_pow(int x,int y) {
	int t=1;

	while (y) {
		if(y&1) {
			t=1LL*t*x%MOD;
		}

		x=1LL*x*x%MOD;
		y>>=1;
	}

	return t;
}
int main() {
	Fac[0]=1;

	int T,Mx=0;
	scanf ("%d", &T);

	while (T--) {
		scanf ("%d",&n) ;
		int t1=0,t2=0,ans=0;
		scanf ("%s",s1) ;

		while (Mx<n) {
			Mx++;
			Fac[Mx] = 1LL*Fac[Mx-1]*Mx%MOD;
			FacInv[Mx]=quick_pow(Fac[Mx],MOD-2);
		}

		for (int i=0; i<n; i++) {
			if (s1[i]=='1') {
				t1++;
			}
		}

		scanf ("%s",s2);

		for (int i=0; i<n; i++) {
			if (s2[i]=='1') {
				t2++;
			}
		}

		int i=0;
		
		while (t1+t2-i>n) {
			i++;
		}
		
		for (; i<=min(t1,t2); i++) {
			ans+=C(n,t1+t2-2*i) ,ans%=MOD;
		}
		
		printf ("%d\n",ans) ;
	}
	
	return 0;
}

除特殊声明外，假设输入的n是不超过10^3的正整数，输入的字符串是01串，完成下面的判断题和单选题:

判断题

---

第 18 题

#include<bits/stdc++.h>
#define mod 1926
using namespace std;
int a[2001][2001],pw[1005];
int DP(int n,int m) {
	if (a[n][m] !=0) {
		return a[n][m];
	}

	if (n<m) {
		return 0;
	}

	if (n==m||m==0) {
		return a[n][m]-1;
	}

	if (m==-1) {
		a[n][m] =n%mod;
		return n%mod;
	} else {
		a[n][m]=(DP(n-1,m-1)%mod+DP(n-1,m)%mod)%mod;
		return a[n][m];
	}
}
int q,n,m, ans;
int main() {
	cin>>q;
	pw[0]=1;

	for (int i=1; i<1005; i++)
		pw[i]=2LL*pw[i-1]%mod;

	while (q--) {
		cin>>n>>m;
		ans=(pw[m+1]-2-m+mod)%mod;

		for (int j=n+1; j<=m; j++) {
			ans--;

			for (int i=j+1; i<=m; i++)
				ans=(ans-DP(i,j)+mod)%mod;
		}
		
		cout<<ans<<'\n';
	}

	return 0;
}

除特殊声明外，假设输入的n,m是不超过2000的正整数，完成下面的判断题和单选题:

判断题

---

三、编程题（每题 25 分，共 50 分）

---

第 19 题 (方案统计)给定一个n*m的矩形迷宫，有k种不同的颜料，有些格子已 经填上了某种颜色，现在需要将其他格子也填上颜色，使得从左，上角到右下角的任意路径经过的格子中，每种颜色都至多出现一次。移动只能沿着相邻的格子，且只能向下或者向右。 请你计算所有可能的方案数量，答案对10^9+7取模。 数据范围:1≤n,m≤1000,1≤k≤10

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,m,k, cnt[50],a[1005][1005], sum,f[1005][1005],ps,ans,vv;
int dfs(int x,int y) {
	if (y==m+1) {
		return dfs(x+1,1);
	}
	
	if (x==n+1)
		return 1;
		
	int s=n+m, num=0,mar=0,res=0,las=0;
	f[x][y]=__(1)__;

	for (int i=1; i<=k; i++) {
		if (!(f[x][y] & (1<<i-1))) {
			++num;
		}
	}

	if (num<__(2)__)
		return 0;

	if (a[x][y]==0) {
		for (int i=1; i<=k; i++) {
			if(__(3)__) {
				if (cnt[i]==0) {
					if (mar)
						res+=__(4)__,res %= mod;
					else {
						mar=1;
						cnt[i]++;
						f[x][y]|=1<<i-1;
						las=dfs(x,y+1);
						f[x][y] ^=1<<i-1;
						cnt[i]--;
						res+=las;
						res%=mod;
					}
					
					continue;
				}
				
				cnt[i]++;
				f[x][y]|=1<<i-1;
				res+=dfs(x,y+1);
				f[x][y]^=1<<i-1;
				cnt[i]--;
				res%=mod;
			}
		}
	} else {
		if (!(f[x][y] & (1<<a[x][y]-1))) {
			f[x][y]|=1<<a[x][y]-1;
			res+=dfs(x,y+1);
			f[x][y] ^=1<<a[x][y]-1;
			res %= mod;
		}
	}
	
	return res ;
}
int main() {
	cin>>n>>m>>k;
	vv=__(5)__;
	
	if (k<vv) {
		puts ("0");
		return 0;
	}
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin>>a[i][j];
			cnt[a[i][j]]++;
		}
	}
	
	ans=dfs(1,1);
	cout<<ans<<endl;
	return 0;
}

---

第 20 题 (树的权值)给定一棵以1为根节点的拥有N个节点的带点权树， 初始时每个点的点权均为0，有Q次操作，每次操作有两种类型:

• 1u,以u为根节点的子树内每个点的点权均加1。
• 2uv,将节点u到节点v的简单路径上的点的点权均加1。

每次操作后询问使 $\sum_{y=1}^{N}A_y \times dist(x,y)$ 最小的x，其中dist(x,y)表示点x到点y的路径上的边数，如果有多个，请输出离根节点1最近的那个。 数据范围:N,Q≤10^5。

提示:显然答案就是求带权重心，直接上轻重链剖分，以线段树上二分求出中位数，每次倍增向上跳，判断是否符合条件即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+10;
int n,m, fir[N], nxt[N<<1],son[N<<1],tot;
int dep[N], sz[N],mx[N], dfn[N], top[N],bk[N],cnt,f[N][21];
inline void Add(int x,int y) {
	nxt[++tot]=fir[x];
	fir[x]=tot;
	son[tot]=y;
}
inline void Dfs1 (int x,int fa) {
	int i;
	f[x][0]=fa;
	sz[x]=1;
	dep[x]=dep[fa]+1;
	
	for (i=fir[x]; i; i=nxt[i])
		if (son[i] !=fa) {
			Dfs1 (son[i],x);
			sz[x]+=sz[son[i]];
			
			if (__(1)__)
				mx[x]=son[i];
		}
}
inline void Dfs2(int x,int Top) {
	top[x]=Top;
	dfn[x]=++cnt;
	bk[cnt]=x;

	if (mx[x])
		Dfs2(mx[x], Top);
		
	int i;
	
	for (i=fir[x]; i; i=nxt[i])
		if (son[i]!=f[x][0] && son[i] !=mx[x]) {
			Dfs2 (son[i],son[i]);
		}
}
LL T[N<<2],tg[N<<2];
inline void pushup(int x) {
	T[x]=T[x<<1]+T[x<<1|1];
}
inline void pushdown(int x,int l,int r) {
	if (tg[x]) {
		int mid=l+r>>1;
		T[x<<1]+=tg[x]*(mid-l+1);
		T[x<<1|1]+=tg[x]*(r-mid);
		tg[x<<1]+=tg[x];
		tg[x<<1|1]+=tg[x];
		tg[x]=0;
	}
}
inline void Modify(int L,int R,int v,int x=1,int l=1,int r=n) {
	if (L<=l && r<=R) {
		T[x]+=__(2)__;
		tg[x]+=v;
		return;
	}
	
	pushdown(x,l,r);
	int mid=l+r>>1;
	
	if (L<=mid)
		Modify(L,R,v,x<<1,l,mid) ;
		
	if (R>mid)
		Modify(L,R,v,x<<1|1,mid+1,r);
		
	pushup(x);
}
inline LL QuerySum(int L, int R, int x=1,int l=1, int r=n) {
	if (L<=1 && r<=R)
		return T[x];
		
	LL S=0;
	pushdown(x,l,r);
	int mid=l+r>>1;
	
	if (L<=mid)
		S+=QuerySum(L,R,x<<1,l,mid);
		
	if (R>mid)
		S+=QuerySum(L,x<<1|1,mid+1,r);
		
	return S;
}
inline int QueryG(LL k,int x=1,int l=1,int r=n) {
	if (l==r)
		return __(3)__ ;

	pushdown(x,l,r);
	int mid=l+r>>1;
	
	if (T[x<<1]>=k)
		return QueryG(k,x<<1,l,mid);
	else
		return QueryG(k-T[x<<1],x<<1|1,mid+1,r);
}
inline void Update(int x,int y) {
	while (top[x] !=top[y]) {
		if (dep[top[x]]<dep[top[y]])
			swap(x,y) ;
			
		Modify (dfn[top[x]],dfn[x],1);
		x=f[top[x]][0];
	}
	
	if (dfn[x]>dfn[y])
		swap(x,y);
		
	Modify(dfn[x],dfn[y],1);
}
inline int Query() {
	LL k=T[1]/2+1;
	int j,i=bk[QueryG(k)];
	
	if(__(4)__)
		return i;
		
	for (j=20; ~j; j--)
		if (f[i][j] && __(5)__)
			i=f[i][j];

	return f[i][0];
}
int main() {
	int i,j,o,x,y;
	
	for (cin>>n,i=1; i<n; i++) {
		cin>>x>>y;
		Add(x,y);
		Add(y,x);
	}
	
	Dfs1(1,0);
	Dfs2(1,1);

	for (j=1; j<=20; j++)
		for (i=1; i<=n; i++)
			f[i][j]=f[f[i][j-1]][j-1];

	for (cin>>m; m--;) {
		cin>>o>>x;

		if (o==1)
			Modify (dfn[x], dfn[x]+sz[x]-1,1);
		else {
			cin>>y;
			Update(x,y);
		}
		
		cout <<Query()<<endl;
	}
	
	return 0;
}

---