1007 Even Tree Split
先考虑最简单的情况，如下图的边\((3,4)\)，我们把这条边切掉，最后会留下一部分的点数为2，另一部分的点数依然是偶数。
进一步思考可以知道，对于边\((u,v)\)，只要v子树的点数是偶数，这条边就可以切除。
再进一步，统计所有可以切除的边的数量，可以知道，只要从中选择任意多条，都可以切除两个或多个偶数个点的部分。直接套组合数公式即可。
const int N=1e5+5,M=2*N,p=998244353;
typedef long long ll;
int T;
int n;
int e[M],ne[M];
int h[N],idx;
int sz[N];
int cnt;
int qmi(int a,int k,int p){
int tmp=1;
while(k){
if(k&1)tmp=(ll)tmp*a%p;
k>>=1;
a=(ll)a*a%p;
}
return tmp;
}
void adde(int x,int y){
e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}
void dfs(int u,int fa){
sz[u]=1;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(v==fa)continue;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]%2==0)cnt++;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
idx=0; memset(h,-1,sizeof(h));
int x,y;
cnt=0;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
adde(x,y); adde(y,x);
}
dfs(1,0);
printf("%d\n",(qmi(2,cnt,p)-1+p)%p);
}
return 0;
}
1003 Wavy Tree
很容易猜到贪心方案。
按每个下标属于波峰还是波谷分两种情况考虑：1. 奇峰偶谷，2. 偶峰奇谷。
然后第一个点不动，从左往右枚举，每个点贪心地移动最少的步数直到满足条件。
const int N=1e6+5;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef long long ll;
int T;
int b[N];
int c[N];
int n;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
memcpy(b,c,sizeof(c));
ll ans=INF,res=0;
//奇谷偶峰
for(int i=2;i<=n;i++){
if((i&1) && b[i]>=b[i-1]){ res+=b[i]-b[i-1]+1; b[i]=b[i-1]-1; }
else if(!(i&1) && b[i]<=b[i-1]){ res+=b[i-1]-b[i]+1; b[i]=b[i-1]+1;}
}
ans=min(ans,res);
memcpy(b,c,sizeof(c));
res=0;
//偶谷奇峰
for(int i=2;i<=n;i++){
if((i&1) && b[i]<=b[i-1]){ res+=b[i-1]-b[i]+1; b[i]=b[i-1]+1; }
else if(!(i&1) && b[i]>=b[i-1]){ res+=b[i]-b[i-1]+1; b[i]=b[i-1]-1;}
}
ans=min(ans,res);
printf("%lld\n",ans);
}
return 0;
}
1009 Painting Game
手动膜你到了n=7的情况后，感觉应该找一些规律了。
首先想不太可能是在中间随便放，于是我们从左往右考虑。
对于第一手的情况，两人的最优操作如下（A表示Alice，B表示Bob）：
因为这样A可以一次封住两个格子，B可以使x位置成为必填（最后谁填都无所谓）
对于一个黑格子之后的两个回合，两人的最优操作：
同样的，A是为了封住尽可能多的格子，B是为了创造出x这个必填位置。
因此，我们可以发现必然会存在长度为7的循环节。
typedef long long ll;
int T;
int n;
char s[8];
int a[6][2]={//长度小于7直接打表
{1,1},
{1,1},
{1,2},
{2,2},
{2,3},
{3,3},
};
int lft[2][7]={//余数部分直接打表
{0,0,1,1,2,2,3},
{0,0,1,1,1,2,2},
};
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
scanf("%s",s+1);
if(s[1]=='A'){
if(n<=6)printf("%d\n",a[n-1][0]);
else{
int res=1;
n-=2;//先处理第一手的情况
res+=n/7*3+lft[0][n%7];//循环节和余数
printf("%d\n",res);
}
}
else{
if(n<=6)printf("%d\n",a[n-1][1]);
else{
int res=2;
n-=3;
res+=n/7*3+lft[1][n%7];
printf("%d\n",res);
}
}
}
return 0;
}
1004 Average Replacement
动手模拟、猜结论、并查集连通块。
找规律可以直接发现的：
- 同一连通块中的点最后值相同。
- 最后答案和点的度数有一定关联。
加上一点灵机一动，猜到：
\[每个连通块内的\sum a[i]*(deg[i]+1)是定值 \]所以最终收敛的数就是用上面那个定值除以\((deg[i]+1)\)。
const int N=1e5+5;
typedef long long ll;
int T;
int n,m;
int w[N];
int f[N],d[N];
ll up[N],dn[N];
int findx(int x){
if(f[x]!=x)return f[x]=findx(f[x]);
else return x;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++){
f[i]=i,d[i]=0;
up[i]=dn[i]=0;
}
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
d[x]++,d[y]++;
int fx=findx(x), fy=findx(y);
if(fx!=fy)f[fx]=fy;
}
for(int i=1;i<=n;i++){
int fx=findx(i);
up[fx]+=(ll)w[i]*(d[i]+1);
dn[fx]+=(d[i]+1);
}
for(int i=1;i<=n;i++)printf("%lf\n",1.0*up[findx(i)]/dn[findx(i)]);
}
return 0;
}