欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Codeforces】Round #516 (Div. 2)

程序员文章站 2022-05-09 22:58:03
...

传送门: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

xax\leq a,要使x+x xor a=ax+x\ xor \ a =axx & a=xa=xxxaa的二进制子集时显然成立。

尝试证明xx & axa\neq xx+x xor aax+x\ xor \ a\neq a
xx的某二进制位ii为1,而aa的该二进制为00,必然一串连续的ii相加要进位到aa上为1的位置j(j&gt;i)j(j&gt; i)才行(同时需要保证x+x xor ax+x\ xor \ a的二进制位jj为0),而xx的二进制位jj为0,x xor ax\ 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

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

#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...baababa...ba的串,没有比它出现次数多一的字母时就直接取自己组成aaaa...aaaaa...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)至少需要左移LL,右移RR到达,则存在等式:
c+RL=jRL=jcc+R-L=j\to R-L=j-c
得到RR的同时也就得到了LL
所以选择其中一个作为距离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

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

#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(n)O(\sqrt n)做,写到一半才发现无论选择枚举人数还是轮数
都不能保证复杂度。

看了editorialeditorial发现这其实是一道分类讨论,可以两种方法结合来做,取min(n2kn)min(n^2,\dfrac kn)

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

n2n^2的做法:设最后多进行一轮的人数为xx,其余人数为y(y=nx)y(y=n-x)xxsweet toothsweet\ tooth个数为aayysweet toothsweet\ tooth个数为bb
直接枚举判断即可。

kn\dfrac kn的做法:枚举场数t(tkn)t(t\leq \dfrac kn),存在等式:
(x+a)×(t+1)+(y+b)×t=tot(x+a)\times (t+1)+(y+b)\times t=tot

也即:
a×(t+1)+b×t=const,const=totx×(t+1)y×ta\times (t+1) + b\times t = const,const =tot-x\times (t+1)-y\times t
0ax,0by0\leq a\leq x,0\leq b\leq y

随便求出一组a0,b0a_0,b_0(可以不满足条件),能够发现对于任意整数zz
存在a=a0tz,b=b0+(t+1)za=a_0-tz,b=b_0+(t+1)z使得等式成立,所以所有合法的答案可以用如下形式表示:
a=a0tz,b=b0+(t+1)za=a_0-tz,b=b_0+(t+1)z
max(a0xt,b0t+1)zmin(a0t,yb0t+1)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(a+b)max(a+b),而由a×(t+1)+b×t=consta\times (t+1) + b\times t = const,得到:

a+b=constata+b=\dfrac{const-a}{t},代入a0a_0,得到:a+b=consta0t+za+b=\dfrac{const-a_0}{t}+z
直接zmaxz_{max}更新答案即可。

需要注意一些细节上的东西:
存在一种特殊的情况:最后一个人是sweettoothsweet tooth但是仅剩一颗糖,此时实际上的总糖数应为tot+1tot+1
对于每种枚举都要考虑这种特殊情况,但注意必须要保证此时枚举到的a1a\geq 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