A.Captain Flint and Crew Recruitment
题意：
定义了一种近似素数，当一个数可以用两个素数的乘积表示时，称他为近似素数。
现在请你把正整数n用四个不同的正整数的和表示，其中至少三个是近似素数。
题解：
直接分解成三个最小的近似素数和另外一个随便什么数的和即可。
#include<bits/stdc++.h> using namespace std; int t,n; int main () { scanf("%d",&t); while (t--) { scanf("%d",&n); if (n<=30) { printf("NO "); continue; } printf("YES "); //printf("6 10 14 %d ",n-20); if (n-30==6||n-30==10||n-30==14) { printf("6 10 15 %d ",n-31); } else { printf("6 10 14 %d ",n-30); } } }
B.Captain Flint and a Long Voyage
题意：
给出一个长度n，请你找到最小的长度为n的十进制数x，使得它转换为2进制后的的数去掉最后n位尽可能大。
题解：
测智题，对我这种智商低的选手不友好。答案就是前3/4是9，后1/4是8。
#include<bits/stdc++.h> using namespace std; const int maxn=11010; int t,n; int main () { scanf("%d",&t); while (t--) { scanf("%d",&n); int tt=n/4; if (n%4) tt++; for (int i=1;i<=n-tt;i++) printf("9"); for (int i=n-tt+1;i<=n;i++) printf("8"); printf(" "); } }
C.Uncle Bogdan and Country Happiness
题意：
给出一棵树，每个节点代表一个城市，每个城市有人口。一开始所有人都在首都1。
给出一个序列h，表示猜测的每个城市的开心人数和不开心人数的差值。
现在所有人从首都1开始返回自己的家乡，他们保持同步，到自己家乡之后会停止，他们可以在任意时刻改变自己的心情，但变成不开心之后就永远不开心了。
询问是否可能h数组的情况出现。
题解：
首先统计出每个节点的子树人口数，以此排除无法构造差值的节点（比如奇偶性不同就无法构造）
然后通过给定的h[i]算出每个节点开心的人数，然后做第二遍DFS，看一下每个节点的开心的人数和它所有子节点的开心的人数之和，如果小于则不合法。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; vector<int> g[maxn]; typedef long long ll; ll p[maxn]; ll h[maxn]; ll dfn[maxn];//记录每个城市的子树人口和 ll wjm[maxn];//计算出每个节点必须开心的人数 int t,n,m; int f; void dfs (int u,int pre) { dfn[u]=p[u]; for (int v:g[u]) { if (v==pre) continue; dfs(v,u); dfn[u]+=dfn[v]; } } void dfs1 (int u,int pre) { int sum=0; for (int v:g[u]) { if (v==pre) continue; dfs1(v,u); sum+=wjm[v]; } //printf("%d %d %d ",u,wjm[u],sum); if (sum>wjm[u]) f=0; } int main () { scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) g[i].clear(),dfn[i]=0; for (int i=1;i<=n;i++) scanf("%lld",p+i); for (int i=1;i<=n;i++) scanf("%lld",h+i); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs(1,0); f=1; for (int i=1;i<=n;i++) { // printf("%d %d ",dfn[i],h[i]); //if (dfn[i]-2*abs(h[i])<0) f=0; if (dfn[i]<h[i]||dfn[i]<-h[i]) f=0; if ((dfn[i]%2)^(abs(h[i])%2)) f=0; ll x=(dfn[i]+h[i])>>1; wjm[i]=x; } dfs1(1,0); if (f) printf("YES "); else printf("NO "); } }
D.Captain Flint and Treasure
题意：
给出两个序列a和b，一次操作你可以将ans+=a[i],a[b[i]]+=a[i]。询问最后ans的最大值。
题解：
拓扑排序，遇到负权值的节点就跳过，减少它给答案带来的贡献。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; typedef long long ll; ll a[maxn]; int b[maxn]; int inDegree[maxn]; int n; vector<int> g[maxn]; ll ans; void topo () { queue<int> q; for (int i=1;i<=n;i++) if (inDegree[i]==0) { q.push(i); } while (!q.empty()) { int u=q.front(); q.pop(); ans+=a[u]; if (b[u]==-1) continue; if (a[u]>0) { g[u].push_back(b[u]); a[b[u]]+=a[u]; } else { g[b[u]].push_back(u); } if (--inDegree[b[u]]==0) q.push(b[u]); } } int main () { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",a+i); for (int i=1;i<=n;i++) { scanf("%d",b+i); if (b[i]>0) { inDegree[b[i]]++; } } topo(); printf("%lld ",ans); vector<int> wjm; for (int i=1;i<=n;i++) for (int v:g[i]) inDegree[v]++; for (int i=1;i<=n;i++) if (inDegree[i]==0) wjm.push_back(i); for (int i=0;i<n;i++) { printf("%d ",wjm[i]); for (int v:g[wjm[i]]) if (--inDegree[v]==0) wjm.push_back(v); } }