Codeforcess834

Codeforcess

目录

• Codeforcess
  • A
    • • code：
  • B
    • • code：
  • C
    • • code：
  • C
    • • code：
  • E
    • • code：
  • F
    • • code：
  • F
    • • code：

A

暴力枚单个循环节

code：

#include 
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read()
{
	ll s=0,r=1;
	char c=C;
	for(;c<0||c>9;c=C) if(c==-3) r=-1;
	for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
	return s*r;
}
int t,la; 
char a[80],b[80]={'Y','e','s','Y','e','s','Y','e','s','Y','e','s'};
int main()
{
	t=read();
	while(t--)
	{
		scanf("%s",a+1);la=strlen(a+1);
		int pd=0;
		for(int k=0;k<=2;k++)
		{
			int tmppd=1;
			for(int i=1;i<=la;i++) if(a[i]!=b[(i+k)%3]) tmppd=0;
			pd|=tmppd;
		}
		if(pd==1) puts("YES");
		else puts("NO");
	}
	return 0;
}

B

从小到大暴力枚举，累加上没出现的，判断是否合法

code：

#include 
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read()
{
	ll s=0,r=1;
	char c=C;
	for(;c<0||c>9;c=C) if(c==-3) r=-1;
	for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
	return s*r;
}
const int N=110,M=3e5+10;
int t;
int m,s,sum;
int mp[M+10],a[N];
#define p1 puts("YES")
#define p2 puts("NO")
int main()
{
	t=read();
	int tmpsum=0;
	for(int i=1;i<=100;i++) tmpsum+=i,mp[tmpsum]=1;
	while(t--)
	{
		m=read(),s=read();sum=0;int pd=1;
		for(int i=1;i<=m;i++) a[i]=read(),sum+=a[i];
		sort(a+1,a+1+m);
		if(!mp[sum+s]){p2;continue;}
		int tmpsum=sum+s,del=1;
		while(tmpsum>0) tmpsum-=del++;
		if(tmpsum==0&&del>a[m]){p1;continue;} 
		else{p2;continue;} 
		
	}
	return 0;
}

C

经典做法，贪心。将区间的可行情况转化为两个端点进行讨论。

一个点一定范围之外才能走，对于一个区间，如果能走进区间，那么显然能走到两端点其中之一。
如果区间内两点可走，那么两端点必然相互可走。
以区间的两端点为媒介进行走，判断起点终点与两端点的可走情况，讨论出步数。

当时具体地考虑每种情况真是太蠢了，要先考虑优化。

code：

#include
using namespace std;
#define ll long long 
#define int ll
const int MaxN=2e5+100;
int N,M,T,L,R,x,a,b;
template
inline void qread(T &sum)
{
    sum=0;int boo=1;
    char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')boo=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
    sum*=boo;
}
template
void qput(T x)
{
    if(x<0) {x=-x;putchar('-');}
    if(x>9){qput(x/10);}
    putchar(x%10+48);
}
inline void Solve()
{
	qread(L);qread(R);qread(x);
	qread(a);qread(b);
	if(a==b)
	{
		qput(0);putchar('\n');return;
	}
	if(b>R||b
	{
		qput(-1);putchar('\n');return;
	}
	if(abs(b-a)>=x)
	{
		qput(1);putchar('\n');return;
	}
	if(abs(a-L)>=x&&abs(b-L)>=x)
	{
		qput(2);putchar('\n');return;
	}
	if(abs(a-R)>=x&&abs(b-R)>=x)
	{
		qput(2);putchar('\n');return;
	}
	if(abs(R-a)>=x&&abs(L-b)>=x)
	{
		qput(3);putchar('\n');return;	
	}
	if(abs(L-a)>=x&&abs(R-b)>=x)
	{
		qput(3);putchar('\n');return;
	}
	qput(-1);putchar('\n');return;
}
signed main()
{
    qread(T);
	while(T--) Solve();
}

C

求a*b后缀0最多，b<=c, a,c

相乘结果为10，只有10,2,5,1的情况。

先提因数10，再提2,5。
b中能用2,5消掉a的，尽量用，因为消耗小，再尽量用10

code：

#include 
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read()
{
	ll s=0,r=1;
	char c=C;
	for(;c<0||c>9;c=C) if(c==-3) r=-1;
	for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
	return s*r;
}
const ll inf=1e9;
int t;
ll n,m; 
inline void work()
{
		n=read(),m=read();ll tmpn=n;
		ll gs2=0,gs5=0,ans=0,sum2=1,sum5=1;
		while(n%10==0) n/=10;
		while(n%2==0) n/=2,gs2++,sum2*=5;
		while(n%5==0) n/=5,gs5++,sum5*=2;
		if(gs2)
		{
			for(ll i=inf;i>=1;i/=10) if(m>=sum2*i)
			{
				printf("%lld\n",(m/(sum2*i))*(sum2*i)*tmpn);
				return;
			}
			ans=1;
			while(ans*5<=m) ans*=5;
			printf("%lld\n",(m/(ans))*(ans)*tmpn);
			return;
		}
		if(gs5)
		{
			for(ll i=inf;i>=1;i/=10) if(m>=sum5*i)
			{
				printf("%lld\n",(m/(sum5*i))*(sum5*i)*tmpn);
				return;
			}
			ans=1;
			while(ans*2<=m) ans*=2;
			printf("%lld\n",(m/(ans))*(ans)*tmpn);
			return;
		}
		for(ll i=inf;i>=1;i/=10) if(m>=i)
		{
			printf("%lld\n",(m/(i))*(i)*tmpn);
			return;
		}
}
int main()
{
	t=read();
	while(t--) work();
	return 0;
}

E

暴力枚举使用223,232,322情况，不够就喝药

code：

#include 
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read()
{
	ll s=0,r=1;
	char c=C;
	for(;c<0||c>9;c=C) if(c==-3) r=-1;
	for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
	return s*r;
}
const ll N=2e5+10;
ll t;
ll n,h,gs; 
ll a[N];
inline void tj(ll v1,ll v2,ll v3)
{
	ll tmpgs,tmpsum,cs;
	tmpgs=0,tmpsum=h,cs=0;
	for(ll i=1;i<=n;i++)
	{
		while(a[i]>=tmpsum&&cs<3)
		{
			if(cs==0) tmpsum*=v1; 
			if(cs==1) tmpsum*=v2 ;
			if(cs==2) tmpsum*=v3;
			cs++;
		}
		if(a[i]
		{
			tmpgs++;
			tmpsum+=a[i]/2;
		}
	}
	gs=max(gs,tmpgs);
}
inline void work()
{
	n=read(),h=read();gs=0;
	for(ll i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	tj(2,2,3);tj(2,3,2);tj(3,2,2);
	cout<endl;
}
int main()
{
	t=read();
	while(t--) work();
	return 0;
}

F

最多p-1次，倒数第二位最多进1，直接讨论

code：

#include 
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read()
{
	ll s=0,r=1;
	char c=C;
	for(;c<0||c>9;c=C) if(c==-3) r=-1;
	for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
	return s*r;
}
const ll N=2e5+10,inf=1e9+7;
ll t,lb;
ll n,p;
ll a[N],b[N];
inline void work()
{
	n=read(),p=read();
	for(int i=1;i<=n;i++) a[i]=b[i]=read();
	sort(b+1,b+1+n);
	lb=unique(b+1,b+1+n)-(b+1);
	int tmpr=lb,tmpl=1,mxr=p,mnl=-1;
	while(tmpr>=1&&b[tmpr]==mxr-1) mxr--,tmpr--;
	while(tmpl<=lb&&b[tmpl]==mnl+1) mnl++,tmpl++;
	if(mxr==0){puts("0");return;}
	if(mnl>=a[n]-1){cout<-1<<endl;return;}
	int ans=p-a[n];b[++lb]=0;
	int tmpw=n-1;
	while(tmpw>=1&&a[tmpw]==p-1) tmpw--;
	b[++lb]=a[tmpw]+1;
	sort(b+1,b+1+lb);
	lb=unique(b+1,b+1+lb)-(b+1);
	tmpl=1,mxr=a[n]+1,mnl=-1;
	for(tmpr=lb;tmpr;tmpr--) if(b[tmpr]==a[n]) break;
	while(tmpr>=1&&b[tmpr]==mxr-1) mxr--,tmpr--;
	cout<0,mxr-1)<<endl;
}
int main()
{
	t=read();
	while(t--) work();
	return 0;
}

F

倒着做，用平衡树或者set维护比b_i小剩余最大的值

code：

#include 
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read()
{
	ll s=0,r=1;
	char c=C;
	for(;c<0||c>9;c=C) if(c==-3) r=-1;
	for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
	return s*r;
}
const int N=2e5+10;
int t;
int n,topt,rt;
int a[N],map[N],vis[N];
int ans[N],topq,askans;
struct xin{
	int l,r,v;
	double key;
}tr[N<<2];
inline int crt(int v)
{
	tr[++topt].v=v;
	tr[topt].l=tr[topt].r=0;
	tr[topt].key=rand();
	return topt;
}
inline void spilt(int x,int v,int &rtl,int &rtr)
{
	if(!x){rtl=rtr=0;return;}
	if(tr[x].v<=v)
	{
		rtl=x;
		spilt(tr[x].r,v,tr[x].r,rtr);
	}
	else
	{
		rtr=x;
		spilt(tr[x].l,v,rtl,tr[x].l);
	}
}
inline int merge(int x,int y)
{
	if(!x||!y) return x|y;
	if(tr[x].key<=tr[y].key)
	{
		tr[x].r=merge(tr[x].r,y);
		return x;
	}
	else
	{
		tr[y].l=merge(x,tr[y].l);
		return y;
	}
}
inline void add(int v)
{
	int x,y,z;
	z=crt(v);
	spilt(rt,v,x,y);
	rt=merge(merge(x,z),y);
}
inline void del(int v)
{
	int x,y,z;
	spilt(rt,v,x,y);
	spilt(x,v-1,x,z);
	z=merge(tr[z].l,tr[z].r);
	rt=merge(merge(x,z),y);
}
inline void ask(int x,int v)
{
	if(!x) return;
	if(tr[x].v<=v)
	{
		askans=max(askans,tr[x].v);
		ask(tr[x].r,v);
	} 
	else ask(tr[x].l,v);
}
inline void work()
{
	topt=0;rt=0;tr[rt].l=tr[rt].r=0;
	for(int i=1,edi=n/2;i<=edi;i++) vis[a[i]]=0;
	n=read();
	for(int i=1,edi=n/2;i<=edi;i++) a[i]=read(),vis[a[i]]++;
	for(int i=1,edi=n/2;i<=edi;i++) if(vis[a[i]]>1){puts("-1");return;}
	for(int i=1;i<=n;i++) add(i);
	for(int i=1;i<=n/2;i++) del(a[i]);
	for(int i=n/2;i>=1;i--)
	{
		askans=0;ask(rt,a[i]);
		if(!askans){puts("-1");return;}
		ans[i*2]=a[i];
		ans[i*2-1]=askans;
		del(askans);
	}
	for(int i=1;i<=n;i++) cout<" ";puts("");
}
int main()
{
	srand(time(0));
	t=read();
	while(t--) work();
	return 0;
}