\[\text{NOIP模拟赛-2023.11.10} \]
T1 进步科学
一棵以 \(1\) 为根的 \(n\) 个点的树，初始时所有点的点权都是 \(0\)，每个点有期望的点权（\(0\) 或 \(1\)）。每次操作可以选择一个点 \(i\) 变化它的点权，这个操作效果会在一秒后传给它的父亲，在 \(j\) 秒后传给它的 \(j\) 级祖先。特别的，如果有多个操作效果同时叠加于一个点，则该点不改变点权也不传递操作效果。每秒只能操作一次，问最少几秒能达到期望效果
\(1\leq n\leq 16\)
一眼状压，但是不会，于是贪心，最后怒砍 \(10\) 分
考虑枚举答案，设 \(f_{i,s}=0/1\) 表示第 \(i\) 秒时 \(s\) 状态是否可行，转移 \(f_{i,s}\rightarrow f_{i+1,s'}\)。问题就出在这个 \(s'\) 怎么搞
我一开始想 \(s\rightarrow s'\) 过于困难，但是其实有一种处理方法。我们可以将产生 \(s\) 的操作，即前 \(i\) 秒的这些操作全部后移一秒操作，然后直接考虑第一秒操作哪个点。那只要我们预处理出每个点操作 \(j\) 次的状态 \(sat_{i,j}\) 即可
code
#include<bits/stdc++.h>
using namespace std;
const int N=20,SS=(1<<16)+10;
int n,m,fa[N];
int sta[N][N],des,f[N][SS];
int main()
{
freopen("decoration.in","r",stdin);
freopen("decoration.out","w",stdout);
scanf("%d",&n);
for(int i=2; i<=n; i++)
scanf("%d",&fa[i]);
for(int i=1; i<=n; i++)
{
int x; scanf("%d",&x);
des^=(1<<i-1)*x;
}
for(int i=1; i<=n; i++)
{
int k=i;
for(int j=1; j<=n; j++)
{
if(k)
sta[i][j]=sta[i][j-1]^(1<<k-1);
else
sta[i][j]=sta[i][j-1];
k=fa[k];
}
}
f[0][0]=1; int S=(1<<n)-1;
for(int i=0; i<=n; i++)
{
if(f[i][des])
return printf("%d\n",i),0;
for(int s=0; s<=S; s++)
{
if(!f[i][s])
continue;
f[i+1][s]=1; // cout<<i<<" "<<s<<endl;
for(int j=1; j<=n; j++)
f[i+1][s^sta[j][i+1]]=1;
}
}
return 0;
}