CF1676D
题意
给定一个无根树，点从 \(1\) 到 \(n\) 编号。你需要给每个点分配一个正整数权值 \(w_i\)。定义一个节点为好节点，当且仅当其权值等于所有相邻节点的权值之和。
请最大化好节点的个数，并且在好节点个数最大的前提下最小化所有节点的权值和。
分析
我们先考虑一种特殊情况，当 \(n=2\) 时我们有唯一可以使一个点和它的父亲都为好的节点，这样我们先特判这种情况。
而后我们考虑设两个状态来转移本题。我们设 \(f_{i,1/0}\) 表示该点是好的节点或不好的节点子树内好的节点数（包含该点）。显然我们有一个节点和它的父亲不能同时为好的节点。而后我们显然有转移
\(f_{u,0}=\sum \min({f_{son[u],0},f_{son[u],1}})\)
\(f_{u,1}=\sum f_{sum[u],0}\)。
而后我们考虑设 \(g_{i,1/0}\) 表示该点是好的节点或者不好的节点子树内点权和（包含该点）。显然
\(g_{u,1}=\sum g_{son[u],0}\)。
当 \(f_{u,0}=f_{u,1}\) 时有 \(g_{u,0}=\sum min(g_{son[u],0},g_{son[u],1})\)。
当 \(f_{u,0}>f_{u,1}\) 时有 \(g_{u,0}=\sum f_{son[u],0}\)。
当 \(f_{u,0}<f_{u,1}\) 时有 \(g_{u,0}=\sum f_{son[u],1}\)。
而后我们考虑一种方案，即若该点为好的节点该点权值为 \(deg[i]\) 否则为 \(1\)。显然最优。而后我们考虑怎么标记。我们考虑再进行一次 \(mark\) 操作，如果该点的父亲被标记那么显然它肯定不能被标记，而后如果该点被该点不被标记是 \(f\) 值大或者 \(f\) 值相同 \(g\) 值更小，那么不被标记，反之被标记。而后我们下传这个标记给他的儿子，这样使得它的儿子必须不能被标记，这样 dfs 下去显然可以得出一个方案。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n;
vector<int> G[N<<2];
int deg[N];
int f[N<<2][2],g[N<<2][2];
void dfs(int u,int father){
f[u][1]=1,g[u][1]=deg[u],g[u][0]=1;
for(int k:G[u]) if(k!=father){
dfs(k,u);
f[u][1]+=f[k][0];
g[u][1]+=g[k][0];
f[u][0]+=max(f[k][0],f[k][1]);
if(f[k][0]==f[k][1]) g[u][0]+=min(g[k][0],g[k][1]);
else g[u][0]+=(f[k][0]>f[k][1]?g[k][0]:g[k][1]);
}
}
bool mrk[N];
void mark(int u,int father,bool fl){
if(fl) mrk[u]=0;
else{
if(f[u][0]>f[u][1]||f[u][0]==f[u][1]&&g[u][0]<g[u][1])
mrk[u]=0;
else mrk[u]=1;
}
for(int k:G[u]){
if(k!=father)
mark(k,u,mrk[u]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int u,v;scanf("%d%d",&u,&v);G[u].push_back(v),G[v].push_back(u);
++deg[u],++deg[v];
}
if(n==2) return printf("2 2\n1 1\n"),0;
dfs(1,0);
mark(1,0,0);
printf("%d %d\n",max(f[1][0],f[1][1]),f[1][0]==f[1][1]?min(g[1][0],g[1][1]):(f[1][0]>f[1][1]?g[1][0]:g[1][1]));
for(int i=1;i<=n;i++) printf("%d ",mrk[i]?deg[i]:1);
return 0;
}
魔法珠
题意
SG函数：首先得到\(x\)的因数，然后获得到他们的\(SG\)值，作为他们的子游戏的\(SG\)值异或起来，当这个值异或其中一个\(SG\)值时，根据异或的性质，可以得到除了他以外的\(SG\)值。而后我们使用\(map\)记录他们可到的状态，而后从\(0\)到\(cnt\)枚举最小的\(mex\)记它为\(SG[x]=mex\)。
分析
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
int SG[N];
int _SG(int x){
if(x==1&&x==0) return 0;
int yz[N];
int cnt=0;
for(int i=1;i<x;i++) if(x%i==0) yz[++cnt]=i;
int tmp=0;
for(int i=1;i<=cnt;i++) tmp^=_SG(yz[i]);
map<int,bool> mp;
for(int i=1;i<=cnt;i++) mp[tmp^SG[yz[i]]]=1;
int mex;
for(int i=0;i<=cnt;i++){
if(!mp[i]){
mex=i;break;
}
}
return SG[x]=mex;
}
int n,a[N];
int main(){
while(cin>>n){
int sum=0;
memset(SG,-1,sizeof SG);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) sum^=_SG(a[i]);
if(sum) printf("freda\n");
else printf("rainbow\n");
}
return 0;
}