Codeforces Round #741 (Div. 2) ABCD(更新ing)

code forces round 741

没打,自己刷的题。


A题 能最大的时候即b==[r/2]+1,当l<=[r/2]+1时自然可以,当l>[r/2]+1那么直接r%l就可以了。

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>
 
using namespace std;
 
int main(){
	int t; scanf("%d",&t);
	while(t--) {
		int l,r; scanf("%d%d",&l,&r);
		if(l<=(r/2)+1) {
			printf("%d\n",r%((r/2)+1) );
		} else printf("%d\n",r%l);
		
	}
	return 0;
}

B题 枚举orz,枚举

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>

using namespace std;

char ss[55];
int a[55],num[55];
int main(){
	int t; scanf("%d",&t);
	while (t--) {
		int k; int jz = 0;
		for(int i=1;i<10;i++) num[i]=0;
		scanf("%d%s",&k,&ss[1]);
		if(k==1) {
			printf("%d\n",k);
			for(int i=1;i<=k;i++) putchar(ss[i]);
			puts("");
			continue;
		}
		for(int i=1;i<=k;i++) {
			a[i]=ss[i]-'0';
			num[a[i]]++;
			if(a[i]==1||a[i]==4||a[i]==6||a[i]==8||a[i]==9) {
				printf("1\n%d\n",a[i]);
				jz = -1; break;
			}
		}
		if(jz==-1) continue;
        if(k==2) {
			printf("%d\n",k);
			for(int i=1;i<=k;i++) putchar(ss[i]);
			puts("");
			continue;
		}
		for(int i=1;i<10;i++) {
			if(num[i]>=2) {
				jz = i; break;
			}
		}
		puts("2");
		if(jz>0) {
			printf("%d%d\n",jz,jz); continue;
		}
		for(int i=2;i<=k;i++) {
			if(a[i]==2||a[i]==5) {
				printf("%d%d\n",a[1],a[i]);
				jz = 233; break;
			}
		}
		if(jz>0) continue;
		for(int i=2;i<=k;i++) {
			if(a[i]==7) {
				printf("%d%d\n",a[1],a[i]);
				break;
			}
		}
	}
		
	return 0;
}

233

C题:水题。有0直接一半多+0和一半多不加0,然后就两倍了。如果全1,一半和一半两倍两个数列就可以了。

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>

using namespace std;
int t,n;
char ss[20005];
int x[20005];
int main(){
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		scanf("%s",ss+1);
		int lwz = -1;
		for(int i=1;i<=n;i++) {
			x[i] = ss[i]-'0';
			if(x[i]==0) lwz = i;
		}
		int mid = (n>>1);
		if(lwz!=-1) {
			if(lwz<=mid) {
				printf("%d %d %d %d\n",lwz,n,lwz+1,n);
				continue;
			} else {
				printf("%d %d %d %d\n",1,lwz,1,lwz-1);
				continue;
			}
		}
		int y = (mid<<1);
		printf("%d %d %d %d\n",1,y,1,mid);
	}
	return 0;
}
 // 先输出大的再输出小的

 

D题: 关于D1我们考虑一个区间如果是奇长度,那么我们找到一个 $ [sum/2] +1  $的中间去掉他,就会发现可以了。那么如果是偶数且不为0,那么随便去掉一个也转换成了奇长度的情况。

关于D2我们通过二分找到那个地方就可以了。(ps:看题解的时候学到了一个方法,就是在函数中开vector数组,然后前缀和+n防负就可以通过stl的lower_bound找到想要的某个前缀和位置)

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>

using namespace std;
const int maxn = 3e5+5;
int t,n,q;
int qzh[maxn];
char ss[maxn];
int qj(int l,int r) {
	return qzh[r] - qzh[l-1];
}
int main(){
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d",&n,&q);
		vector<vector<int> >ve(2*n+1);
		scanf("%s",ss+1);
		qzh[0] = n;
		ve[n].push_back(0);
		for(int i=1;i<=n;i++) {
			int x = (ss[i]=='+'?1:-1);
			if(i%2==0) x = -x;
			qzh[i] = qzh[i-1] + x;
			ve[qzh[i]].push_back(i);
		}
	//	cerr<<"sm"<<' '<<qzh[n];
		for(int i=1;i<=q;i++) {
			int l,r;
			scanf("%d%d",&l,&r);
			int sm = qzh[r] - qzh[l-1];
			if(sm==0) puts("0");
			else if(sm%2){
				puts("1");
				int re = qzh[l-1]+(sm>0?sm/2+1:sm/2-1);
				int x = *lower_bound(ve[re].begin(),ve[re].end(),l);
				printf("%d\n",x);
			}
			else {
				puts("2");
				printf("%d ",r); r--;
				sm = qzh[r] - qzh[l-1];
				int re = qzh[l-1]+(sm>0?sm/2+1:sm/2-1);				
				int x = *lower_bound(ve[re].begin(),ve[re].end(),l);
				printf("%d\n",x);		
			}
		}		
	}
	return 0;
}
上一篇:Python重命名文件夹下的文件


下一篇:AcWing 741. 斐波那契数列