CSP 2022 提高组&普及组总结

提高组

T1 假期计划

题目大意：有$n$个点，$m$条边，每个点都有一个权值。现在要从第一个点开始，走到四个点在走回家，每走一次可以经过$k$个点。

设$f[i][0/1/2]$表示从第一个点走两次到第$i$个点的权值和的最大值、次大值、次次大值，用$bfs$求出$f$值，最后求解即可。

code

#include
using namespace std;
int n,m,k,x,y,tot=0,d[20005],l[20005],r[20005],z[3005],g[3005][3],v[2505][2505];
long long ans,a[3005];
queue<int>q;
void add(int xx,int yy){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void bfs(int v0){
	q.push(v0);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=r[u];i;i=l[i]){
			if(z[d[i]]) continue;
			z[d[i]]=1;v[v0][d[i]]=v[v0][u]+1;
			q.push(d[i]);
		}
	}
}
int main()
{
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);++k;
	for(int i=2;i<=n;i++) scanf("%lld",&a[i]);
	a[0]=a[1]=-2e18;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) v[i][j]=k+1;
		v[i][i]=0;
		memset(z,0,sizeof(z));
		z[i]=1;
		bfs(i);
		v[i][i]=v[i][1]=k+1;
	}
	for(int i=2;i<=n;i++){
		if(v[1][i]>k) continue;
		for(int j=2;j<=n;j++){
			if(v[i][j]>k) continue;	
			if(a[i]>a[g[j][0]]){
				g[j][2]=g[j][1];g[j][1]=g[j][0];g[j][0]=i;
			}
			else if(a[i]>a[g[j][1]]){
				g[j][2]=g[j][1];g[j][1]=i;
			}
			else if(a[i]>a[g[j][2]]){
				g[j][2]=i;
			}
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
			if(v[i][j]>k) continue;
			for(int v1=0;v1<=2;v1++){
				for(int v2=0;v2<=2;v2++){
					if(i==g[j][v2]||g[i][v1]==j||g[i][v1]==g[j][v2]) continue;
					ans=max(ans,a[i]+a[j]+a[g[i][v1]]+a[g[j][v2]]);
				}
			}
		}
	}
	printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

T2 策略游戏

题目大意：给一个长度为$n$的数组$A$和一个长度为$m$的数组$B$，$C_{i,j}=A_i\times B_j$。有$q$轮游戏，每轮给定一个范围，小L先选一个$i$，小$Q$后选一个$j$。小$L$想使$C_{i,j}$尽可能大，小Q想使$C_{i,j}$尽可能小。两人都会使用最优策略，求每轮游戏中最后的$C_{i,j}$的值

分类讨论：
1.若在范围中选择的$A_i$大于$0$，则$B_i$为范围中的最小值

• 若$B_i$最小值大于$0$，则$A_i$取大于$0$的最大值
• 若$B_i$最小值小于$0$，则$A_i$取大于$0$的最小值
• 若$B_i$最小值等于$0$，则$A_i$取大于$0$的任意值

2.若在范围中选择的$A_i$小于$0$，则$B_i$为范围中的最大值

• 若$B_i$最大值大于$0$，则$A_i$取小于$0$的最大值
• 若$B_i$最大值小于$0$，则$A_i$取小于$0$的最小值
• 若$B_i$最大值等于$0$，则$A_i$取小于$0$的任意值

3.若在范围中选择的$A_i$等于$0$，则$C_{i,j}$为$0$

在三种情况中取最小值就是答案

我用的是倍增，用线段树也可以过，时间复杂度为$O(q\log n)$

code

#include
using namespace std;
int n,m,q,l1,r1,l2,r2,lg[100005],ze[100005];
long long mx,mn,ans,a[100005],b[100005],mxb[100005][20],mnb[100005][20];
long long mx1[100005][20],mx2[100005][20],mn1[100005][20],mn2[100005][20];
long long fmx1(int l,int r){
	if(l==r) return mx1[l][0];
	return max(mx1[l][lg[r-l+1]],mx1[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
long long fmn1(int l,int r){
	if(l==r) return mn1[l][0];
	return min(mn1[l][lg[r-l+1]],mn1[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
long long fmx2(int l,int r){
	if(l==r) return mx2[l][0];
	return max(mx2[l][lg[r-l+1]],mx2[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
long long fmn2(int l,int r){
	if(l==r) return mn2[l][0];
	return min(mn2[l][lg[r-l+1]],mn2[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int main()
{
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);lg[0]=-1;
	for(int i=1;i<=max(n,m);i++) lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]>0){
			mx1[i][0]=mn1[i][0]=a[i];
			mx2[i][0]=-1e9-1;mn2[i][0]=0;
		}
		else if(a[i]<0){
			mx2[i][0]=mn2[i][0]=a[i];
			mx1[i][0]=0;mn1[i][0]=1e9+1;
		}
		ze[i]=ze[i-1]+(a[i]==0);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld",&b[i]);
		mxb[i][0]=mnb[i][0]=b[i];
	}
	for(int i=1;i<=19;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			mx1[j][i]=max(mx1[j][i-1],mx1[j+(1<<i-1)][i-1]);
			mx2[j][i]=max(mx2[j][i-1],mx2[j+(1<<i-1)][i-1]);
			mn1[j][i]=min(mn1[j][i-1],mn1[j+(1<<i-1)][i-1]);
			mn2[j][i]=min(mn2[j][i-1],mn2[j+(1<<i-1)][i-1]);
		}
		for(int j=1;j+(1<<i)-1<=m;j++){
			mxb[j][i]=max(mxb[j][i-1],mxb[j+(1<<i-1)][i-1]);
			mnb[j][i]=min(mnb[j][i-1],mnb[j+(1<<i-1)][i-1]);
		}
	}
	while(q--){
		ans=-2e18;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		if(l2==r2) mx=mn=b[l2];
		else{
			mx=max(mxb[l2][lg[r2-l2+1]],mxb[r2-(1<<lg[r2-l2+1])+1][lg[r2-l2+1]]);
			mn=min(mnb[l2][lg[r2-l2+1]],mnb[r2-(1<<lg[r2-l2+1])+1][lg[r2-l2+1]]);
		}
		if(fmx1(l1,r1)>0){
			if(mn<0) ans=max(ans,mn*fmn1(l1,r1));
			else ans=max(ans,mn*fmx1(l1,r1));
		}
		if(fmn2(l1,r1)<0){
			if(mx<0) ans=max(ans,mx*fmn2(l1,r1));
			else ans=max(ans,mx*fmx2(l1,r1));
		}
		if(ze[r1]-ze[l1-1]>0) ans=max(ans,0ll);
		printf("%lld\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

T3 星战

没有AC

T4 数据传输

没有AC

提高组总结

没有拿完应得的分，分数230。

普及组

T1 乘方

题目大意：给出$a$和$b$，如果$a^b$小于等于$10^9$，则输出$a^b$，否则输出$-1$

快速幂，每做一次判断一次，时间复杂度为$O(\log n)$

直接乘也行，特判$1$之后，因为$2^{30}>10^9$，所以最多只会乘不超过$30$次。

我用的是快速幂。

code

#include
using namespace std;
long long a,b,x,s,inf=1e9;
int main()
{
// 	freopen("pow.in","r",stdin);
// 	freopen("pow.out","w",stdout);
	scanf("%lld%lld",&a,&b);
	x=a;s=1;
	for(;b;b>>=1){
		if(x>inf||s>inf){
			printf("-1");
			return 0;
		}
		if(b&1) s=s*x;
		x=x*x;
	}
	if(s>inf) s=-1; 
	printf("%lld",s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

T2 解密

题目大意：$k$次询问，每次给出$n,e,d$，求正整数$p,q$，使$n=p\times q，e\times d=(p-1)(q-1)+1$

$p\times q=n$
$p+q=p\times q-(p\times q-p-q+2)+2=n-e\times d+2$

$p\times q,p+q$已知，那么$p,q$就是方程$x^2-(p+q)x+p\times q=0$的两个根，用求根公式即可求出，最后判断是否为正整数即可。

求根公式：$x_1=\frac{-b+\sqrt{b^2-4ac}}{2a},x_2=\frac{-b-\sqrt{b^2-4ac}}{2a}$

code

#include
using namespace std;
int t;
long long a,b,c,d,d1,v1,v2,p,q;
int main()
{
// 	freopen("decode.in","r",stdin);
// 	freopen("decode.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld%lld",&a,&b,&c);
		v1=a-b*c+2;
		v2=a;
		d=v1*v1-4*v2;
		if(d<0){
			printf("NO\n");
			continue;
		}
		d1=sqrt(d);
		if(d1*d1!=d){
			printf("NO\n");
			continue;
		}
		d=d1;
		if((v1+d)%2==1){
			printf("NO\n");
			continue;
		}
		p=(v1-d)/2;q=(v1+d)/2;
		if(p<=0){
			printf("NO\n");
			continue;
		}
		printf("%lld %lld\n",p,q);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

T3 逻辑表达式

题目大意：给出一个逻辑表达式，其中包含左右括号，&，|，0，1。
括号优先级最大，&优先级第二，|优先级最小。当计算a&b时，若a为0，则不计算b；当计算a|b时，若a为1，则不计算b。称以上两种情况为短路。求逻辑表达式的值，以及&短路的次数和|短路的次数。如果某处短路包含在更外层的短路，则这处短路不计。

设$gt(l,r)$表示求逻辑表达式中$[l,r]$部分&和|分别短路的次数，返回该部分的值。那么在处理$[l,r]$的时候：

• 如果这一段有|且不被括号包含，则处理|之前的，如果=1，则|短路一次
• 否则如果这一段有&且不被括号包含，则处理&之前的，如果=0，则&短路一次
• 如果这一段有|或&但都被括号包含，那$l,r$的位置一定是左右括号，$gt(l+1,r-1)$
• 如果这一段没有|也没有&，那么$l==r$，这个位置一定是0或1，返回相应值即可

code

#include
using namespace std;
int n,v1,v2,ans,h[1000005],v[1000005],dep[1000005];
int vt[1000005],lt[1000005],vk[1000005],lk[1000005];
char s[1000005];
int gt(int l,int r,int d){
	if(l==r) return s[l]-'0';
	if(s[l]=='('&&s[r]==')'&&v[l]==r) return gt(l+1,r-1,d+1);
	if(lt[r]>=l){
		int i=lt[r];
		if(gt(l,i-1,d)){
			++v2;return 1;
		}
		else return gt(i+1,r,d);
	}
	int i=lk[r];
	if(!gt(l,i-1,d)){
		++v1;return 0;
	}
	else return gt(i+1,r,d);
}
int main()
{
	// freopen("expr.in","r",stdin);
	// freopen("expr.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1,k=0;i<=n;i++){
		if(s[i]=='(') h[++k]=i;
		else if(s[i]==')'){
			v[h[k]]=i;--k;
		}
		dep[i]=k;
		if(s[i]=='|') vt[k]=i;
		else if(s[i]=='&') vk[k]=i;
		lt[i]=vt[k];lk[i]=vk[k];
	}
	ans=gt(1,n,0);
	printf("%d\n%d %d",ans,v1,v2);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

T4 上升点列

题目大意：给出平面上的$n$个点和一个$k$，$k$表示可以在平面上添加$k$个点。添加后要从这$n+k$个点中选出若干个整数点并组成一个序列，使序列中任意相邻两点间的欧几里得距离恰好为$1$且横坐标、纵坐标值均单调不减。

首先，将点按$x$值从小到大排序，$x$值相等则按$y$值从小到大排序。

然后，我们设$f[i][j]$表示以第$i$个点为终点，已经放了$j$个点的最长序列的长度。每两个点连一条边，共连$n^2$条边。依次遍历每个点，更新$f[i][j]$。每个点更新的时间复杂度为$O(nk)$，总时间复杂度为$O(n^{2}k)$

code

#include
using namespace std;
int n,k,tot=0,ans=0,d[500005],l[500005],r[500005],v[500005],ct[505],f[505][105];
queue<int>q;
struct node{
	int x,y;
}w[505];
void add(int xx,int yy,int zz){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;v[tot]=zz;++ct[yy];
}
int main()
{
	// freopen("point.in","r",stdin);
	// freopen("point.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&w[i].x,&w[i].y);
		f[i][0]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&w[i].x<=w[j].x&&w[i].y<=w[j].y){
				add(i,j,w[j].x-w[i].x+w[j].y-w[i].y-1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!ct[i]) q.push(i);
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=r[u];i;i=l[i]){
			for(int j=v[i];j<=k;j++){
				f[d[i]][j]=max(f[d[i]][j],f[u][j-v[i]]+1);
			}
			--ct[d[i]];
			if(ct[d[i]]==0) q.push(d[i]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			ans=max(ans,f[i][j]);
		}
	}
	printf("%d",ans+k);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

普及组总结

普及组考得还不错，分数400分。