【Codeforces】Round #516 (Div. 2)

传送门：CodeforcesRound510Div. 2

---

---

A.Make a triangle!

a+b>c

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

int a,b,c,ans;

int main(){
	int i,j,k;
	scanf("%d%d%d",&a,&b,&c);
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(b>c) swap(b,c);
    if(a+b>c) printf("0");
    else printf("%d",abs(c+1-a-b));
}

---

B. Equations of Mathematical Magic

$x\leq a$x≤a，要使$x+x\ xor \ a =a$x+x xor a=a，$x$x & $a=x$a=x即$x$x为$a$a的二进制子集时显然成立。

尝试证明$x$x & $a\neq x$a̸​=x时$x+x\ xor \ a\neq a$x+x xor a̸​=a：
设$x$x的某二进制位$i$i为1，而$a$a的该二进制为$0$0，必然一串连续的$i$i相加要进位到$a$a上为1的位置$j(j> i)$j(j>i)才行(同时需要保证$x+x\ xor \ a$x+x xor a的二进制位$j$j为0)，而$x$x的二进制位$j$j为0，$x\ xor \ a$x xor a的二进制为1，矛盾，所以不成立。

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

int t,a,ans,sum;

int main(){
	int i,j,k;
	scanf("%d",&t);
	for(;t;--t){
		scanf("%d",&a);
		ans=1;
		for(i=0;(1LL<<i)<=a;++i){
			if((a>>i)&1) ans<<=1;
		}
		printf("%d\n",ans);
	}
}

---

C. Oh Those Palindromes

这题坑了我好久。。。
实际上只需要排个序：对于每组相同的字母(个数为$k$k)，其贡献最多为$\dfrac{k(k+1)}{2}$2k(k+1)​，排序之后就能达到最优。

#include<bits/stdc++.h>
using namespace std;
int n;char s[100005]; 

int main(){
	scanf("%d%s",&n,s);sort(s,s+n);printf("%s",s);
	return 0;
}

→_→考试的时候没有想到，就乱搞了一个方法：
把每个字母按出现次数排序，每次优先取比它出现次数多一的字母来组成形如$ababa...ba$ababa...ba的串，没有比它出现次数多一的字母时就直接取自己组成$aaaa...a$aaaa...a的串。(其实本质上和排序是一样的)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,oc[27],sx[27],sum,ban[27];
int q[27],cnt,pre[26][N],st[N],nxt[N];
int a[N],b[N],ca,cb,mx[N];
char s[N];

inline bool cmp(const int&A,const int&B)
{return oc[A]<oc[B];}

int main(){
	int i,j,k,num,w;
	scanf("%d%s",&n,s+1);
	for(i=1;i<=n;++i)
	 oc[s[i]-'a']++;
	for(i=0;i<26;++i) sx[i]=i;
	sort(sx,sx+26,cmp);
	for(i=0; oc[sx[i]]==0 ;)
	  i++;
	for(;i<26;i=j){
		for(j=i;j<25 && oc[sx[j+1]]==oc[sx[j]];++j);
		num=j;j++;
		for(;i<=num;++i){
		  if(j<26 && oc[sx[j]]==oc[sx[i]]+1){
			 putchar('a'+sx[j]);
			 for(w=0;w<oc[sx[i]];++w) {putchar('a'+sx[i]);putchar('a'+sx[j]);}
			 j++;
		  }else if(i<num){
		  	 for(w=0;w<oc[sx[i]];++w) {
		  	 	putchar('a'+sx[i]);putchar('a'+sx[i+1]);
		  	 }
		  	 i++;
		  }else{
		  	for(w=0;w<oc[sx[i]];++w) putchar('a'+sx[i]);
		  }
		}
	}
    return 0;
}

---

D. Labyrinth

若一个位置$(i,j)$(i,j)可达，从起点$(r,c)$(r,c)至少需要左移$L$L，右移$R$R到达，则存在等式：
$c+R-L=j\to R-L=j-c$c+R−L=j→R−L=j−c
得到$R$R的同时也就得到了$L$L。
所以选择其中一个作为距离01dfs即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,M=4e6+10;

int n,m,la,lb,st,dis[M],ban[M],cg,ans;
char s[N];

int dx[6]={-1,1,0,0};
int dy[6]={0,0,-1,1};
int v[6]={0,0,1,0};

deque<int>Q;

int main(){
	int i,j,x,y,z,ix,iy,iz,lim,ori;
	scanf("%d%d",&n,&m);
	scanf("%d%d",&x,&y);
	st=(x-1)*m+y-1;ori=y-1;
	scanf("%d%d",&la,&lb);
	lim=0;
	for(i=0;i<n;++i){
	   scanf("%s",s);
	   for(j=0;j<m;++j){
	   	  ban[lim]=(s[j]=='*');
		  lim++;
	   }
	}
	memset(dis,0x7f,sizeof(int)*(lim+3));
	lim--;
	dis[st]=0;Q.push_back(st);
	for(;!Q.empty();){
		iz=Q.front();Q.pop_front();
		ix=iz/m;iy=iz%m;
		for(i=0;i<4;++i){
			x=ix+dx[i];y=iy+dy[i];z=x*m+y;
			if(x<0 || x>=n || y<0 || y>=m || ban[z] || dis[z]<=dis[iz]+v[i]) continue;
			dis[z]=dis[iz]+v[i];
			i==2? Q.push_back(z):Q.push_front(z);
		}
	}
	x=0;
	for(i=0;i<n;++i){
	 for(j=0;j<m;++j){
		 if(dis[x]<=la && dis[x]+j-ori<=lb) ans++;
	 	 x++;
	 }
    }
	printf("%d\n",ans);
	return 0;
}

---

E. Dwarves, Hats and Extrasensory Abilities

一个简单的二分。
关键在于看出数据范围的提示：
$1\leq n\leq30,0\leq x,y\leq 10^9$1≤n≤30,0≤x,y≤109。
刚好一个$Log$Log，于是初始$l=0,r=10^9$l=0,r=109每次放在$mid$mid，根据颜色收敛即可。

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

int n,x,y,mid,l,r=1e9,ori;
char s[10];
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		printf("1 %d\n",mid);
		cin>>s;
		if(i==1) ori=s[0];
		if(s[0]==ori) l=mid;
		else r=mid;
		mid=(l+r)>>1; 
	}
	printf("0 %d 2 %d\n",l,r);
	return 0;
} 

---

F. Candies for Children

乍一看觉得可以$O(\sqrt n)$O(n​)做，写到一半才发现无论选择枚举人数还是轮数
都不能保证复杂度。

看了$editorial$editorial发现这其实是一道分类讨论，可以两种方法结合来做，取$min(n^2，\dfrac kn)$min(n2，nk​)。

设总糖数为$tot$tot。这里假设均满足最后一个人取满的情况(若其为$sweet tooth$sweettooth则能够取2个，否则取1个)

$n^2$n2的做法：设最后多进行一轮的人数为$x$x，其余人数为$y(y=n-x)$y(y=n−x)，$x$x中$sweet\ tooth$sweet tooth个数为$a$a，$y$y中$sweet\ tooth$sweet tooth个数为$b$b。
直接枚举判断即可。

$\dfrac kn$nk​的做法：枚举场数$t(t\leq \dfrac kn)$t(t≤nk​)，存在等式：
$(x+a)\times (t+1)+(y+b)\times t=tot$(x+a)×(t+1)+(y+b)×t=tot

也即：
$a\times (t+1) + b\times t = const,const =tot-x\times (t+1)-y\times t$a×(t+1)+b×t=const,const=tot−x×(t+1)−y×t
$0\leq a\leq x,0\leq b\leq y$0≤a≤x,0≤b≤y

随便求出一组$a_0,b_0$a0​,b0​(可以不满足条件)，能够发现对于任意整数$z$z，
存在$a=a_0-tz,b=b_0+(t+1)z$a=a0​−tz,b=b0​+(t+1)z使得等式成立，所以所有合法的答案可以用如下形式表示：
$a=a_0-tz,b=b_0+(t+1)z$a=a0​−tz,b=b0​+(t+1)z
$max(\lceil \dfrac{a_0-x}{t}\rceil,\lceil\dfrac{-b_0}{t+1}\rceil)\leq z \leq min(\lfloor\dfrac{a_0}{t}\rfloor,\lfloor \dfrac{y-b_0}{t+1}\rfloor)$max(⌈ta0​−x​⌉,⌈t+1−b0​​⌉)≤z≤min(⌊ta0​​⌋,⌊t+1y−b0​​⌋)

答案即求$max(a+b)$max(a+b)，而由$a\times (t+1) + b\times t = const$a×(t+1)+b×t=const，得到：

$a+b=\dfrac{const-a}{t}$a+b=tconst−a​，代入$a_0$a0​，得到：$a+b=\dfrac{const-a_0}{t}+z$a+b=tconst−a0​​+z
直接$z_{max}$zmax​更新答案即可。

需要注意一些细节上的东西：
存在一种特殊的情况：最后一个人是$sweet tooth$sweettooth但是仅剩一颗糖，此时实际上的总糖数应为$tot+1$tot+1。
对于每种枚举都要考虑这种特殊情况，但注意必须要保证此时枚举到的$a\geq 1$a≥1。

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

ll n,l,r,tot,x,y,d,rd,ans=-1;

//上下取整
inline ll gt(ll x,ll y)
{
	if(x==0) return 0;
	return x>0?((x-1)/y+1):(x/y);	
}

inline ll ft(ll x,ll y)
{
	if(x==0) return 0;
	return x>0?(x/y):((x+1)/y-1);
}

int main(){
	ll i,j,res,sum;
	scanf("%I64d%I64d%I64d%I64d",&n,&l,&r,&tot);
	d=l<=r?(r-l+1):(r+n-l+1);rd=n-d;
	if(n<=5000){
		for(i=0;i<=d;++i)
		 for(j=0;j<=rd;++j){
		 	sum=n+i+j;res=(tot-1)%sum+1;
		 	if(res==d+i) ans=max(ans,i+j);
		 	else if(i && res==d+i-1) ans=max(ans,i+j);
		 }
	}else{
   	    ll lim=tot/n,dd=d<<1,mn,mx;
		if(tot+1>=d && tot+1<=dd) ans=max(ans,tot+1-d+rd);
		else if(tot>=d && tot<=dd) ans=max(ans,tot-d+rd);
		for(i=1;i<=lim;++i){
			res=tot-(i+1)*d-i*rd;
			if(res>=0){
			x=res%i;y=res/i-x;
			mx=min(ft(x,i),ft(rd-y,i+1));
			mn=max(gt(x-d,i),gt(-y,i+1));
		    if(mn<=mx)  ans=max(ans,(res-x)/i+mx);
		    }
		    res++;
		    if(res>=0){
		     x=res%i;y=res/i-x;
			 mx=min(ft(x-1,i),ft(rd-y,i+1));
			 mn=max(gt(x-d,i),gt(-y,i+1));
		     if(mn<=mx)  ans=max(ans,(res-x)/i+mx);
		    }
		}
	}
	printf("%I64d",ans);
	return 0;
}

---

这场考试还是比较有思维难度E,F