---

title : 2022 Jiangsu Collegiate Programming Contest
date : 2022-7-29
tags ：ACM,练习记录
author : LINNO

---

2022 Jiangsu Collegiate Programming Contest比赛题解

顺序：I->A->K->L->C->B

题意见PPT，这里分享做法。

I - Cutting Suffix

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

int vis[N],type=0;
string str;

void Solve(){
	cin>>str;
	int n=str.length();
	for(int i=0;i<n;++i){
		if(!vis[str[i]-'a']){
			++type;
		}
		vis[str[i]-'a']++;
	}
	if(type==1){
		cout<<n-1<<"\n";
	}else{
		cout<<"0\n";
	}
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	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

A - PENTA KILL!

#include 
using namespace std;
int n,num,pos,p,cnt[1005];
string a,b,st[1005][1005];
bool check(int x,int y) {
	for (int i=0; i<=4; ++i)
		for (int j=i+1; j<=4; ++j)
			if (st[x][y+i]==st[x][y+j]) return false;
	return true;
}
int main() {
	cin>>n;
	for (int i=1; i<=n; ++i) {
		cin>>a>>b;
		pos=0;
		for (int j=1; j<=num; ++j)
			if (st[j][0]==a) {
				pos=j;
				break;
			}
		if (pos==0) {
			st[++num][0]=a;
			st[num][1]=b;
			cnt[num]++;
		} else {
			cnt[pos]++;
			st[pos][cnt[pos]]=b;
		}
	}
	for (int i=1; i<=num; ++i) {
		for (int j=1; j+4<=cnt[i]; ++j)
			if (check(i,j)) {
				cout<<"PENTA KILL!";
				return 0;
			}
	}
	cout<<"SAD:(";
	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

K - aaaaaaaaaaA heH heH nuN

#include 
#define int long long
using namespace std;
long long T,n,m,f[100],p,g[100];
signed main() {
	for (int i=1; i<=32; ++i)
		f[i]=(1ll<<i)-1ll;
	cin>>T;
	while (T--) {
		cin>>n;
		m=n;
		p=0;
		memset(g,0,sizeof(g));
		for (int i=32; i>=1; i--)
			if (m>=f[i]) {
				g[i]=m/f[i];
				m=m%f[i];
				p=max(p,i);
			}
		printf("nunhehhe");

		for (int i=p; i>=1; i--) {
			for (int j=1; j<=g[i]; ++j)
				putchar('h');
			putchar('a');
		}
		printf("\n");
	}
	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

L - Collecting Diamonds

#include
#define Max 200500
using namespace std;
typedef long long ll;
int main () {
	string s;
	cin>>s;
	int cnt=0;
	int cc[Max];
	bool b[Max];
	int len=s.length();
	for(int i=0; i<len; ++i) {
		if(s[i]=='B') {
			cc[++cnt]=0;
			if(i%2) {
				b[cnt]=1;
			} else b[cnt]=0;
			for(int j=1; i-j>=0&&i+j<len; j++) {
				if(s[i-j]=='A'&&s[i+j]=='C')
					cc[cnt]++;
				else {
					break;
				}
			}
			if(cc[cnt]==0)
				cnt--;
		}
	}
	ll sum=0;
	ll ans=0;
	for(int i=cnt; i>0; --i) {
		//cout<
		if(b[i]&&cc[i]>1) {
			ans++;
			cc[i]--;
			b[i]=0;
		}
	}
	for(int i=1; i<=cnt; ++i) {
		if(b[i]==0) {
			if(cc[i]>sum) {
				ans+=sum;
			} else {
				ans+=cc[i]-1;
			}
			ans++;
			sum++;
		} else {
			ans++;
			if(sum>0) {
				sum++;
			}
		}
	}
	cout<<ans;
	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

C - Jump and Treasure

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 1e16
#define int long long
#define pii pair<int,int>
#define mk make_pair
using namespace std;
const int N=3e6+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

int n,Q,lst,jmp,a[N],ans[N],vis[N];

int query(int x){
	if(vis[x]) return ans[x];
	vis[x]=1;
	deque<pii>q;
	q.push_back(mk(0,0));
	for(int j=x,res;j<=n;j+=x){
		while(q.size()&&j-q.front().first>jmp) q.pop_front();  //越界弹出队头
		if(q.size()) res=q.front().second+a[j];
		else res=a[j]; 
		while(q.size()&&res>=q.back().second) q.pop_back(); //弹出后面较小的值 
		q.push_back(mk(j,res));
	}
	while(q.size()&&q.front().first+jmp<n+1) q.pop_front();
	return ans[x]=q.front().second;
}

void Solve(){
	cin>>n>>Q>>jmp;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1,x;i<=Q;++i){
		cin>>x;
		if(x>jmp){
			cout<<"Noob\n";
			continue;
		}else cout<<query(x)<<"\n";
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	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

B - Prime Ring Plus

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int N=2e4+7,M=2e7+7;

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

int n,mxflow=0,vis[N],dis[N],dep[N],pre[N],T,S;
vector<int>G[N];
vector<int>tmp;
vector<int>ans[N];

int pri[N],np[N],tot=0;
void init(){
	np[1]=1;
	for(int i=2;i<N;++i){
		if(!np[i]) pri[++tot]=i; 
		for(int j=1;j<=tot&&pri[j]*i<N;++j){
			np[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}

struct E{
	int v,w,nxt;
}e[M];

int head[N],cur[N],cnt=1;
inline void addedge(int u,int v,int w){
	e[++cnt]=(E){v,w,head[u]};head[u]=cnt;
	e[++cnt]=(E){u,0,head[v]};head[v]=cnt;
}

inline bool bfs(){
	memset(dep,-1,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	queue<int>q;
	q.push(S);dep[S]=0;
	while(q.size()){
		int fro=q.front();
		q.pop();
		for(int i=head[fro];i;i=e[i].nxt){
			int to=e[i].v,dis=e[i].w;
			if(dis>0&&dep[to]==-1){
				dep[to]=dep[fro]+1;
				q.push(to);
				if(to==T) return true;
			}
		}
	}
	return false;
} 

inline int dfs(int p=S,int flow=inf){
	if(p==T) return flow;
	int lft=flow;
	for(int i=cur[p];i&&lft;i=e[i].nxt){
		cur[p]=i;
		int to=e[i].v,dis=e[i].w;
		if(dis>0&&dep[to]==dep[p]+1){
			int c=dfs(to,min(dis,lft));
			lft-=c;
			e[i].w-=c;
			e[i^1].w+=c;
		}
	}
	return flow-lft;
}

void Dinic(){
	while(bfs()){
		mxflow+=dfs();
	}
}

void find(int x){
	tmp.emplace_back(x);
	for(auto y:G[x]){
		if(!vis[y]) vis[y]=1,find(y);
	}
}

signed main(){
	init();
	n=read();
	if((n&1)||n==2){
		puts("-1");
		return 0; 
	}
	S=0;T=n+1;
	for(int i=1;i<=n;i+=2){
		for(int j=2;j<=n;j+=2){
			if(!np[i+j]){
				addedge(i,j,1);
			}
		}
	} 
	for(int i=1;i<=n;i+=2) addedge(S,i,2);
	for(int i=2;i<=n;i+=2) addedge(i,T,2);
	Dinic();
	if(mxflow<n){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i+=2){
		for(int j=head[i];j;j=e[j].nxt){
			int to=e[j].v,cap=e[j].w;
			if(S<to&&to<T&&!cap){
				G[i].push_back(to);
				G[to].push_back(i);
			}
		}
	}
	memset(vis,0,sizeof(vis));
	int now=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			find(i);
			ans[++now].push_back(tmp.size());
			for(auto j:tmp) ans[now].emplace_back(j);
			tmp.clear();
		}
	}
	write(now);putchar('\n');
	for(int i=1;i<=now;i++){
		for(int j=0;j<ans[i].size();j++){
			write(ans[i][j]);putchar(" \n"[j==ans[i].size()-1]);
		}
	}
	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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137