2022 年河南省大学生程序设计竞赛 个人题解

---

title : 2022 年河南省大学生程序设计竞赛 个人题解
date : 2022-10-29
tags : ACM,题解
author : Linno

---

2022 年河南省大学生程序设计竞赛 个人题解

题目链接：https://codeforces.com/gym/103941

补题进度：6/12

A - Mocha 上小班啦

显然$n>10$无解，然后把0放在第二位，其他从小到大输出即可。

#include<bits/stdc  .h>
using namespace std;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	if(n>10){
		cout<<"-1\n";
	}else{
		cout<<"1";
		if(n>1) cout<<"0";
		for(int i=3;i<=n;  i) cout<<i-1;
		cout<<"\n"; 
	}
	return 0;
}

E - Serval 的俳句

枚举三种小写字母，分别在前中后，然后二分去找每个间隔位置就可以了。

#include<bits/stdc  .h>
using namespace std;
const int N=2e6 7;

int n;
int sum[30][N]; 
string str;

int fd(int st,int num,int ch){
	int L=st,R=n 1,M,ans=-1;
	while(R-L>1){
		M=((L R)>>1);
		if(sum[ch][M]-sum[ch][st-1]>=num) ans=M,R=M;
		else L=M;
	}
	if(sum[ch][L]-sum[ch][st-1]>=num) ans=R=L;
	return ans;
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	cin>>n;
	cin>>str;
	for(int i=1;i<=n;  i){
		for(int j=0;j<26;  j) sum[j][i]=sum[j][i-1] (str[i-1]==j 'a');	
	}
	for(int j=0;j<26;  j) sum[j][n 1]=sum[j][n];
	for(int i=0;i<26;  i){
		int pos1=fd(1,5,i);
		if(pos1==-1) continue;		
		for(int j=0;j<26;  j){
			int pos2=fd(pos1 1,7,j);
			if(pos2==-1) continue;
			for(int k=0;k<26;  k){
				int pos3=fd(pos2 1,5,k);
				if(pos3==-1) continue;
				//cout<<pos1<<" "<<pos2<<" "<<pos3<<" !!\n";
				for(int s1=1;s1<=5;s1  ) cout<<char(i 'a');
				for(int s2=1;s2<=7;s2  ) cout<<char(j 'a');
				for(int s3=1;s3<=5;s3  ) cout<<char(k 'a');
				return 0;
			}
		}
	}
	cout<<"none\n";
	return 0;
}
/*
17
aaaaabbbbbbbccccc
16
aaaaabbbbbbccccc
16
aaaabbbbbbbccccc
16
aaaaabbbbbbbcccc
18
aaaababbbbbbbccccc
30
abcdeabcdeabcdeabcdeabcdeabcde
67
abcdeabcdeabcdeabcdeabcdeabcdefffffffabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
*/

F - 集合之和

造几个小数据感受一下，除了2和4以外，我都可以用$d$个数的集合$A$来表示$2d-1$到 C d 2 C_d^2 Cd2的范围的集合$AA$，具体一点我们可以反过来求一个合适的$d$刚好使$2d-1<n$，然后将最后一个数右移，每移一位都会增加一种和。

#include<bits/stdc  .h>
#define int long long
using namespace std;
const int N=5e5 5;

int n,frac[N];

signed main(){
	ios::sync_with_stdio(0); 
	cin.tie(0);cout.tie(0);
	cin>>n;
	if(n==1) cout<<"1\n1\n";
	else if(n==2||n==4) cout<<"-1\n";
	else{
		int d=n/2;
		while(2*d-1<=n)   d;
		d--;
		int now=2*d-1,lf=d;
		while(now<n)   lf,  now;
		cout<<d<<"\n";
		for(int i=1;i<d;  i) cout<<i<<" ";
		cout<<lf<<"\n";
	}
	return 0;
} 

G - Mocha 上大班啦

骗人的题，这个操作完全不影响答案，直接输出所有字符串都是1的位置个数即可。

#include<bits/stdc  .h>
#define int long long
using namespace std;
const int N=1007,M=4005;
const int mod=998244353;

char mp[N][M];
int n,m,q,res[M];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;  i) res[i]=1;
	for(int i=1;i<=n;  i){
		for(int j=1;j<=m;  j){
			cin>>mp[i][j];
			res[j]*=(mp[i][j]-'0');
		}
	}
	cin>>q;
	while(q--){
		int i,j,l,r,p;
		cin>>i>>j>>l>>r>>p;
	}
	int ans=0;
	for(int j=1;j<=m;  j){
		ans=(ans res[j])%mod;
	}
	cout<<ans<<"\n";
	return 0;
}
/*
4 4
1100
1110
1111
1101
1
2 1 1 2 50
*/

H - 旋转水管

直接搜答案，注意细节。

#include<bits/stdc  .h>
using namespace std;
const int N=1e6 7;

int m,sy,ty;
bool vis[5][N],flag;
char s[5][N];

void dfs(int x,int y,int d){
	if(flag||x<2||x>4||y<1||y>m) return;
	if(x==4){
		if(y==ty) flag=1;
		return;
	}
	vis[x][y]=1;
	if(s[x][y]=='I'){
		if(d==0&&x 1<=4&&!vis[x 1][y]) dfs(x 1,y,d);
		else if(d==1&&!vis[x][y-1]) dfs(x,y-1,d);
		else if(d==2&&!vis[x-1][y]) dfs(x-1,y,d);
		else if(d==3&&!vis[x][y 1]) dfs(x,y 1,d); 
	}else{
		if(d==0||d==2){
			if(!vis[x][y 1]) dfs(x,y 1,3);
			if(!vis[x][y-1]) dfs(x,y-1,1);
		}else{
			if(!vis[x 1][y]) dfs(x 1,y,0);
			if(!vis[x-1][y]) dfs(x-1,y,2);
		}
	}
	vis[x][y]=0; //回溯！ 
}

void solve(){
	cin>>m>>sy>>ty;
	for(int i=2;i<=4;  i) for(int j=1;j<=m;  j) s[i][j]=0;
	for(int i=2;i<=3;  i) for(int j=1;j<=m;  j) cin>>s[i][j]; 
	flag=0;
	dfs(2,sy,0);
	if(flag) cout<<"YES\n";
	else cout<<"NO\n";	
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
6
3 1 3
ILL
LLI
1 1 1
I
I
3 1 3
IIL
LLI
3 1 3
ILL
LLI
3 1 3
III
LLL 
3 1 3
III
LIL 
*/

J - Mex Tree

#include<bits/stdc  .h>
using namespace std;
const int N=1e6 7;

int n,val[N],id[N],sz[N],mi[N],ans[N];
vector<int>G[N];

void dfs(int x,int f){
	mi[x]=val[x];sz[x]=1;
	for(auto to:G[x]){
		if(to==f) continue;
		dfs(to,x);
		mi[x]=min(mi[x],mi[to]);
		sz[x] =sz[to];
	}
	if(mi[x]>=val[x]) ans[val[x]]=n-sz[x]; 
	else ans[val[x]]=0;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;  i) cin>>val[i],id[val[i]]=i;
	for(int i=2,v;i<=n;  i){
		cin>>v;
		G[v].emplace_back(i);
		G[i].emplace_back(v); 
	}
	dfs(id[0],0); 
	for(int k=0;k<=n;  k){
		if(k==0){
			int mx=0;
			for(auto to:G[id[0]]){
				if(sz[to]>mx) mx=sz[to];
			}
			cout<<mx<<" ";
		}else if(k==n) cout<<n<<" ";
		else cout<<ans[k]<<" ";
	}
	cout<<"\n";
	return 0;
}

这篇好文章是转载于：学新通技术网