Codeforces Round #743 (Div. 2) ABC题解(持续更新)

CSP202109很菜地只拿了390。。。过来更更题解。


A水题,所有数位换到个位来减就好

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
 
using namespace std;
char ss[105];
int main(){
	int t,n;
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		scanf("%s",&ss[1]);
		int ans = 0;
		for(int i=1;i<n;i++) {
			if(ss[i]!='0') ans += 1 + ss[i]-'0';
		}
		ans += ss[n]-'0';
		printf("%d\n",ans);
	}
	   
	return 0;
}

B

顺着一个一个数字枚举A数组中的数,找到可以满足的最小B数组的数然后计算答案就可以了。(具体还可以利用上单调性)

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
 
using namespace std;
const int maxn = 2e5+5;
int t,n;
int a[maxn],b[maxn],pos[maxn];
int main(){
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
		for(int i=1;i<=n;i++) scanf("%d",&b[i]),pos[b[i]]=i;
		int ans = 2*n;
		int MX = 2*n;
		for(int i=2*n-1;i>=1;i-=2) {
			MX = min(MX,pos[i+1]);
			ans = min(ans,pos[i]-1+MX-1);
		}
		printf("%d\n",ans);
	}	
	return 0;
}

C 好像就是一个拓扑排序的事啊,,有环无解,无欢转移如果出边的点更大就max(f[x])否则max(f[x]+1)。

点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
 
using namespace std;
const int maxn = 2e5+5;
vector<int>ve[maxn];
int n,rd[maxn],f[maxn];
int qe[maxn],qf,qb;
void init() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&rd[i]);
		for(int j=1;j<=rd[i];j++) {
			int x; scanf("%d",&x);
			ve[x].push_back(i);
		}
	}
	int cnt=0;
	qf = 1; qb = 0;
	for(int i=1;i<=n;i++) {
		if(!rd[i]) {
			qe[++qb] = i; f[i]=1;
		} else f[i] = 0;
	}
	while(qf<=qb) {
		int x = qe[qf++]; cnt++;
		for(int y:ve[x]) {
			if(y>x) f[y] = max(f[y],f[x]);
			else f[y] = max(f[y],f[x]+1);
			if(--rd[y]==0) {
				qe[++qb] = y;
			}
		}
	}
	if(cnt!=n) puts("-1");
	else {
		int ans = 1;
		for(int i=1;i<=n;i++)
			ans = max(ans,f[i]);
		printf("%d\n",ans);
	}
	for(int i=1;i<=n;i++) ve[i].clear();
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--) {
		init();
	}
	return 0;
}

D我裂开来。。题解没看懂????wtf.....留给以后看吧。。嘴巴上口胡就是对于n为奇数,先要满足所有数的xor和为0,那么就按照1,3,5.....n-4,n-2这么搞就可以保证n个数都有ai=ai-1并且an,an-2,an-3为0,之后an-4,an-6.....1这么再来搞就可以全数列为0。对于偶数n就是一定有一个奇数个的前缀+一个奇数个的后缀都满足这个搞法?but证明没懂,更不会code.....orz太菜了太菜了。

上一篇:数据类型之【数值类型】的整数型 smallint


下一篇:Codeforces Round #743 (Div. 2)