周赛round32

D 树形dp

每个节点有0或1的权值，设f(i)为从i节点出发，向叶子节点走，可以中途停下，所形成的数字中奇数的个数，求所有f(i)。奇数显然就是最后一位为1，所以这实际上就是要求每个节点所在子树权值为1叶结点个数。但又特殊规定：单独的叶节点不能形成一个数，因此叶节点虽然对祖先的f(i)有贡献，但对自己的f(i)无贡献。

所以这个dfs不能写成无返回值，f(i)初始化为当前节点权值，每次都把儿子节点的f(i)加进当前节点f(i)中的形式从，这样会把叶节点的f(i)也算成1。而应该写成有返回值，f(i)初始化为0，f(i)加上子节点递归返回值，返回f(i)加当前节点权值的形式，这样可以保证叶子节点f(i)为0，但仍能向上传递贡献。

当然也可以有别的写法，比如在正常的求权值为1叶节点个数基础上，加上一个将叶节点f(i)记为0

using namespace std;
const int N=1e5+10;
int a[N],d[N];
vector<int>b[N];
int dfs(int x,int f){
    for(int i:b[x]){
        if(i==f)continue;
        d[x]+=dfs(i,x);
    }
    return d[x]+a[x];//子树其他节点贡献加上自己贡献
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        char t;
        cin>>t;
        a[i]=t-'0';
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        b[u].push_back(v);
        b[v].push_back(u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)cout<<d[i]<<'\n';
}

E.前缀和记录奇偶

给一个数字，问起中有多少个区间是回文串？回文串分两种情况，如果长度为偶，要求区间内所有字符数量都为偶（包含0），如果长度为奇，要求区间内有且只有一种字符数量为奇。

暴力写法就是用前缀和统计0-9攻0种字符出现次数之和，然后枚举所有区间，判断是否满足上述条件，显然在1e5下是会超时的。

using namespace std;
const int N=1e5+10;
int cnt[10][N];
string s;
int main(){
    cin>>s;
    int n=s.size(),ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            if(s[i]-'0'==j){
                cnt[j][i+1]=cnt[j][i]+1;
            }
            else cnt[j][i+1]=cnt[j][i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int num=0;
            for(int p=0;p<10;p++){
                if((cnt[p][j]-cnt[p][i-1])%2==1)num++;
            }
            if((j-i+1)%2==1){
                if(num==1)ans++;
            }
            else{
                if(num==0)ans++;
            }
        }
    }
    cout<<ans;
}

但仔细想想，前述的回文串的条件只对各种字符个数的奇偶做出了要求，我们并不关心各种数字具体出现了几次，只用统计各种数字出现次数的奇偶性就可以了。并且要遍历所有区间，并不需要真的枚举所有区间，因为有些区间虽然边界不同，但字符奇偶是相同的，在对答案的贡献上他们都是相同的，可以视为一个状态出现了多次。

因此我们只遍历整个数组一遍，记录出现的各种状态出现的次数，然后每得到一个新的状态，就计算他和前面已出现的状态可以组成的回文区间个数。

具体来说，要记录每种状态的个数，需要开一个数组，以状态为下标，映射到出现次数。但10个字符出现次数这个状态怎么作为下标呢？有两种思路，一是开一个长度为10的vector记录状态，然后开一个把数组作为前键的映射map<vector,int>，我也是第一次知道数组还能作为前键；另一种思路是，每种状态实际上就是一个01串，可以视作一个二进制数字，然后这个数字可以直接作为数组下标，这就是一般状压的思路。

using namespace std;
const int N=1e5+10;
map<vector<int>,int>mp;
string s;
int main(){
    cin>>s;
    int n=s.size();
    long long ans=0;
    vector<int>t;
    for(int i=0;i<10;i++){
        t.push_back(0);//初始没有数字，所有字符出现次数都为0（偶）
    }
    mp[t]++;//初始状态也要存，因为后面都是前缀和，需要和初始状态做差
    //类似于维护区间和时sum(0)=0
    for(int i=0;i<n;i++){
        t[s[i]-'0']^=1;
  		//计算当前状态，当前字符个数奇偶性反转
        ans+=mp[t];
  		//前面和当前相同的状态所代表的区间，可以和当前区间构成回文区间
  		//当前区间为(1,x)，前面状态相同的区间为(1,y)
  		//x,y奇偶性相同，区间长度为偶
  		//做差后每种字符数量要么是奇减奇，要么是偶减偶
  		//(y,x)内所有字符个数一定都是偶数，构成回文
        for(int j=0;j<10;j++){
            vector<int>tt=t;
  			//枚举所有和当前状态只有一个字符奇偶性不同的状态
            tt[j]^=1;
            ans+=mp[tt];//这些区间和当前区间也能构成回文
            //x和y的奇偶性都和区间内字符个数和奇偶性相同，状态有一位不同，字符个数和奇偶不同
            //因此x,y奇偶不同，区间长度为奇。
            //(x,y)内，奇偶性不同的那种字符个数为奇数，其余相同的个数都为偶数
            //恰好只有一种字符个数为奇数，且区间长度为奇数，是回文串
        }
        mp[t]++;//当前状态也加入统计
    }
    cout<<ans;
}

这题很有教育意义的一点是，遍历子集或者子序列，统计有多少符合要求，很多时候不需要枚举所有区间或所有子集，而是可以只遍历一遍，每读一位，统计一下到目前为止，各种状态的个数，然后统计当前状态和前面所有出现的状态，可以构成多少对符合要求的方案，将方案数加入答案。最后把当前在状态加入统计。

这种思路应该叫啥我也不好说，但是感觉很多题都是类似的思路，比如树状数组求逆序对。

F.状压dp

一类很经典的状压dp，二维平面上，求满足规则的形状的个数/是否可达/达到的最小代价，这个规则只涉及当前行、列和附近有限行、列（通常都是之和相邻一行、列有关）

一般的思路是

1 根据规则写一个check函数，判断当前状态/相邻两个状态是否合法。一行、列的状态可以用一个数字表示，这个数字在x进制下，每一位表示每一个格子属于[0,x-1]中哪种状态

2 对于每一行，枚举当前行和上一行的所有状态，找出其中合法的组合，从从上一行转移到这一行，如果是求是否可行，那就是上一行可行，这一行也可行；如果是求个数，这一行状态个数加上一行状态个数；如果是求最小代价，到达这一行的最小代价=min(当前到达这一行的最小代价，到达上一行的最小代价+这一行变成当前状态的代价）……

3 最后遍历最后一行的所有状态，求答案

4 开始第一行时没有前一行，需要特殊的初始化

这题的特殊点在于，每个格子有三种状态，因此状态压缩时用的是三进制，不是二进制，因此不能用位运算压缩，需要手动计算三进制。但还是能压缩成一个数字。

using namespace std;
int n,m;
int p3[5]={1,3,9,27,81};
int b[4]={},dp[1050][100];
string a[4];
map<char,int>mp;
bool check(int x){//判断这一列是否合法
    for(int i=0;i<n;i++){//计算三进制下每一位
        b[i]=x%3,x/=3;
    }
    for(int i=0;i<n-1;i++){//判断相邻是否相等
        if(b[i]==b[i+1])return 0;
    }
    return 1;
}
bool check(int x,int y){//判断相邻两列是否合法
    for(int i=0;i<n;i++){
        if(x%3==y%3)return 0;//计算两个数的三进制下每一位
        x/=3,y/=3;//看是否相等
    }
    return 1;
}
int main(){
    cin>>n>>m;
    int i,j,k;
    mp['r']=0;
    mp['e']=1;
    mp['d']=2;
    memset(dp,0x3f,sizeof(dp));
    int ans=1e9;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<m;i++){
        if(i==0){//第一列初始化
            for(j=0;j<p3[n];j++){
                if(check(j)){//如果合法
                    int cnt=0;
                    for(k=0;k<n;k++){//计算从原始状态变成这个状态的代价
                        if(b[k]!=mp[a[k][i]])cnt++;
                    }
                    dp[0][j]=min(dp[0][j],cnt);//这个代价就是这种状态的初始值
                }
            }
        }
        else{
            for(j=0;j<p3[n];j++){
                if(check(j)){//枚举当前列合法状态
                    int cnt=0;
                    for(k=0;k<n;k++){
                        if(mp[a[k][i]]!=b[k]){
                            cnt++;//计算变成这个状态的的代价
                        }
                    }
                    for(k=0;k<p3[n];k++){
                        if(check(j,k)){//枚举合法的上一列
                            dp[i][j]=min(dp[i][j],dp[i-1][k]+cnt);
  							//从上一列转移过来
                        }
                    }
                }
                 
            }
        }
        if(i==m-1){//最后一列，统计答案
            for(j=0;j<p3[n];j++){
                ans=min(ans,dp[i][j]);
            }
        }
    }
    cout<<ans;
}