cf Round 764(Div. 3)(cf Round 764(Div. 3))

C

二分图匹配裸题。

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

const int N=55,M=255;
struct graph{
    int nxt,to;
}e[M];
int a[N],g[N<<1],fr[N<<1],cnt,n,t;
bool u[N<<1];
inline void adde(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline bool match(int x){
    for(int i=g[x];i;i=e[i].nxt)
        if(!u[e[i].to]){
            u[e[i].to]=true;
            if(!fr[e[i].to]||match(fr[e[i].to])){
                fr[e[i].to]=x;return true;
            }
        }
    return false;
}
inline int hungary(){
    int ret=0;
	memset(fr,0,sizeof(fr));
    for(int i=1;i<=n;i++){
        memset(u,0,sizeof(u));
        if(match(i)) ++ret;
    }
    return ret;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		cnt=0;
		memset(g,0,sizeof(g));
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			while(a[i]){
				if(a[i]<=n){
					adde(i,a[i]+n);
				}
				a[i]/=2;
			}
		}
		if(hungary()==n) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

D

Description
给定一个大小为n的字符串,把它们分给k个组(组不可以为空,但字符可以不分给任何组),组中字符要可以组成回文串,求最短字符串的最长长度。
Solution
二分+贪心。
贪心的时候,如果回文串长度为奇数,预先把最中间的字符取了(优先用总个数为奇数的字符,用总个数为偶数的字符时尽量集中)。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,M=30;
int a[M],tot[M],n,k,t;
char s[N];
bool chk(int ans){
	for(int i=0;i<26;++i) a[i]=tot[i];
	
	if(ans&1){
		--ans;
		int cnt=0;
		for(int i=0;i<26;++i)
			if(a[i]&1){
				--a[i];
				if(++cnt==k) break;
			}
		for(int i=0,d;i<26&&cnt<k;++i){
			d=min(a[i],k-cnt);
			a[i]-=d;cnt+=d;
		}
	}
	
	for(int i=1,len;i<=k;++i){
		len=0;
		for(int j=0,d;j<26;++j){
			d=min(ans-len,a[j]);
			if(d&1) --d;
			len+=d;a[j]-=d;
		}
		if(len<ans) return false;
	}
	return true;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);
		memset(tot,0,sizeof(tot));
		for(int i=1;i<=n;++i){
			++tot[s[i]-'a'];
		}
		int l=0,r=n,mid;
		while(l<r){
			mid=(l+r+1)>>1;
			if(chk(mid)) l=mid;
			else r=mid-1;
		}
		printf("%d\n",l); 
	}
}

F

Description
交互题,给定n,需要猜出x \((1\leq x<n)\)。
你可以询问+c,则x=x+c,返回\(\lfloor\frac{x}{n}\rfloor\)
Solution
构造出二分即可:对于需要验证的mid,我们取能够使\(x_0=mid\)时,\(x_0+\sum c_i=0\;(mod\;n)\)的c。

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

int main(){
	int n,sc=0,ans;
	scanf("%d",&n);
	int l=1,r=n-1;
	while(l<r){
		int mid=(l+r+1)>>1;
		int c=n-(sc+mid)%n;
		sc+=c; 
		printf("+ %d\n",c);fflush(stdout);
		scanf("%d",&ans);
		l=max(l,ans*n-sc);
		r=min(r,ans*n-sc+n-1);
	}
	printf("! %d\n",l+sc);fflush(stdout);
	return 0;
}
————————

C

Bipartite graph matching naked question.

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

const int N=55,M=255;
struct graph{
    int nxt,to;
}e[M];
int a[N],g[N<<1],fr[N<<1],cnt,n,t;
bool u[N<<1];
inline void adde(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline bool match(int x){
    for(int i=g[x];i;i=e[i].nxt)
        if(!u[e[i].to]){
            u[e[i].to]=true;
            if(!fr[e[i].to]||match(fr[e[i].to])){
                fr[e[i].to]=x;return true;
            }
        }
    return false;
}
inline int hungary(){
    int ret=0;
	memset(fr,0,sizeof(fr));
    for(int i=1;i<=n;i++){
        memset(u,0,sizeof(u));
        if(match(i)) ++ret;
    }
    return ret;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		cnt=0;
		memset(g,0,sizeof(g));
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			while(a[i]){
				if(a[i]<=n){
					adde(i,a[i]+n);
				}
				a[i]/=2;
			}
		}
		if(hungary()==n) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

D

Description
Given a string of size n, divide them into k groups (the group can not be empty, but the characters can not be assigned to any group). The characters in the group can form a palindrome string to find the longest length of the shortest string.
Solution
Dichotomy + greed.
When greedy, if the length of the palindrome string is an odd number, take the middle character in advance (give priority to the characters with an odd number in total, and try to concentrate the characters with an even number in total).

#include<bits/stdc++.h>
using namespace std;
const int N=200005,M=30;
int a[M],tot[M],n,k,t;
char s[N];
bool chk(int ans){
	for(int i=0;i<26;++i) a[i]=tot[i];
	
	if(ans&1){
		--ans;
		int cnt=0;
		for(int i=0;i<26;++i)
			if(a[i]&1){
				--a[i];
				if(++cnt==k) break;
			}
		for(int i=0,d;i<26&&cnt<k;++i){
			d=min(a[i],k-cnt);
			a[i]-=d;cnt+=d;
		}
	}
	
	for(int i=1,len;i<=k;++i){
		len=0;
		for(int j=0,d;j<26;++j){
			d=min(ans-len,a[j]);
			if(d&1) --d;
			len+=d;a[j]-=d;
		}
		if(len<ans) return false;
	}
	return true;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);
		memset(tot,0,sizeof(tot));
		for(int i=1;i<=n;++i){
			++tot[s[i]-'a'];
		}
		int l=0,r=n,mid;
		while(l<r){
			mid=(l+r+1)>>1;
			if(chk(mid)) l=mid;
			else r=mid-1;
		}
		printf("%d\n",l); 
	}
}

F

Description
Interactive question, given n, you need to guess x \ ((1 \ Leq X & lt; n) \).
You can ask + C, then x = x + C, and return \ (\ lfloor \ frac {x} {n} \ rfloor \)
Solution
Construct a dichotomy: for the mid to be verified, we take the C of \ (x_0 + \ sum c_i = 0 \; (MOD \; n) \) when \ (x_0 = mid \).

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

int main(){
	int n,sc=0,ans;
	scanf("%d",&n);
	int l=1,r=n-1;
	while(l<r){
		int mid=(l+r+1)>>1;
		int c=n-(sc+mid)%n;
		sc+=c; 
		printf("+ %d\n",c);fflush(stdout);
		scanf("%d",&ans);
		l=max(l,ans*n-sc);
		r=min(r,ans*n-sc+n-1);
	}
	printf("! %d\n",l+sc);fflush(stdout);
	return 0;
}