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太菜了太菜了。