2021.11.3 CCPC Guilin copper making summary

1. Competition experience

I felt that the organizers were very happy from the beginning, and then all kinds of chat were very friendly. Blood loss didn't go offline. (I'm dead with the epidemic!!!)

I feel that this experience is quite good, but it's very hard for volunteers to work with the environment (hard for all volunteers!!!)

I think the quality of the questions is OK. Anyway, our team has only opened a few questions, at least from the open questions. The quality of the system is also very good. It's very comfortable to do questions and print. It can be maintained in the future~

The first XCPC brand in life. It's a pity that I didn't hit the silver, but it's acceptable.

2. Competition process

1. Warm up

Three Macao original questions were worked out. I did, but I didn't make it up.

Just write it and run away

Process strategy.

2. Race

I went to bed early the day before, but it was useless. I woke up in the middle of the night (although everyone is happy about the EDG champion, it's still not good to shout in the middle of the night).

The energy was OK at the beginning of the game.

But I saw this thing:

This is very uncomfortable!!!!

As a person who stayed up late and watched all LGD games in bed, why don't I BAN mammoth!!!

Then he signed in as soon as he was angry. (ACM has failed in three years, and we can't see our ancestors in long long)

After quickly signing two questions a and I, start to look at the questions separately.

Quickly locked a relatively signed question G and looked at the naked question with two-point answer.

Quickly ran up to knock, wrote for two minutes, felt false, changed CRB to write D, so the speed of light WA made a shot in the 40th minute

I wrote G instead, so I stumbled after two rounds of WA, and finally passed G in 73 minutes (+ 2)

Then Julytree ran and said that H was something that she had been practicing for a period of time. She wrote it very confidently. I don't know AC automata, so let her write it first.

Then the speed of light T drops.

During this period, CRB also came to WA and sent a D.

Then when h was adjusted to about 130 minutes (- 4), I found that only our team had handed in 4 rounds of H. I thought it was not necessarily false, so I quickly advised my teammates to change the question.

I've been watching E for an hour, but I still won't. (after a while, I found that the reading of the question was false. As expected, the reading of the question was not standardized, and my teammates cried.)

(an episode: the sixth edition Oxford Dictionary of the next team didn't have the word "endless". They were confused all the time. Fortunately, we are the seventh edition.)

Finally, in the middle of the 156 minute schedule, CRB passed D (+ 2) and officially entered the bronze medal area.

Then fall into a period of hang up.

Last year, I could remember the forging of iron in Kunming. So I thought to myself, will the answer be only 2 at most.

After thinking about it, there seems to be no counterexample. Isn't that a minimum cost ring?

So I sent dij up directly, and sure enough, AC (214 minutes). At that time, there was still one and a half hours left. CRB fed another idea of B. after discussion, it felt feasible and went on.

So a WA meal. It didn't come out in the end. Because we made a lot of mistakes in the early stage, the penalty was a little big, so we said goodbye to the silver medal.

After the game, I found that the idea was like a hair (crying!), alas!

3. Pass the title during the game

A.A Hero Named Magnus

Sign in question, LGD wins without waves

I.PTSD

Check in question

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T;ll n;
ll ans;
int a[1000500];
char x;
int main(){
	cin>>T;
	while(T--){
		ans=0;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			x=getchar();
			while(x!='0'&&x!='1')x=getchar();
			a[i]=x-'0';
		}
		int sum0=0;
		for(int i=n;i>=1;i--){
			if(sum0&&a[i]){
				sum0--;
				ans+=i;
			}
			else sum0++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

G.Occupy the Cities

Two point answer: for each answer, judge whether the left occupation of each point can be satisfied. If the left happens to be the answer, under the mark, the next point will run one more point when running to the left.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000005
int T;int n;
char s[N];
int a[N];
int ans;
int pos[N];
int b[N],cnt;
int check(int x){
	if(pos[1]-1>x) return 0;
	if(pos[1]-1==x) b[1]=1;
	for(int i=2;i<=cnt;i++){
		int now=pos[i]-pos[i-1]-1;
		
		if(now==0) continue;
		if(b[i-1]) now++;
		//cout<<now<<endl;
		if(now/2+now%2>x){
			return 0;
		}
		if(now/2==x){
			if(now%2==0) b[i]=1;
		}
	}
	if(b[cnt]){
		if(n-pos[cnt]+1>x) return 0;
	}
	else{
		if(n-pos[cnt]>x) return 0;
	}
	return 1;
}
int main(){
	cin>>T;
	while(T--){
		scanf("%d",&n);
		scanf("%s",s+1);cnt=0;
		for(int i=1;i<=n;i++){
			a[i]=s[i]-'0';
			if(a[i]) pos[++cnt]=i;
			b[i]=0;
		}
		int l=1,r=n;ans=0;
		if(cnt!=n) while(l<=r){
			int mid=(l+r)>>1;
			for(int i=1;i<=cnt;i++) b[i]=0;
			if(check(mid)){
				ans=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		
		printf("%d\n",ans);
	}
}
/*
1
7
0100101
*/

D.Assumption is All You Need

Structure, written by my teammates, I'm not good at it.
The general idea is to enumerate from back to front and change if possible. For each number to be changed, run from front to back to see if there is a complexity o(n^2) that can get a better solution by exchange

E.Buy and Delete

Graph theory, consider that all points can't afford to buy, that is, 0. If you can't afford the ring, that is, 1. If you can't afford the ring, that is, 2. So the answer is: run dijstra for each point. If there is a ring back to the starting point, judge whether you can afford it. Complexity o (nmlogn)

4. Summary

Penalty is very important!!!
Don't open questions that no one has ever asked~
It's still a pity. May be the only CCPC in service? It's a pity to strike copper~
Shenyang, come on! I hope I can get a piece of silver~
I wish CCPC better and better.