由于蒟蒻今年 S 组只拿了 \(15\) 分，作为机房最低分与另一位没过线的同志（今年 SD NOIP体验线为 \(25\) 分）在教练的安排下开始了复活赛比赛，时长两个小时，三个题目，谁分数高谁获得推荐名额。
不过还是要吐槽一下，教练从网上找了个三个 DP 题，真是无语了
题目链接
由于是复活赛，教练没有给出题解，只能自己写了
T1 一开始看像是贪心，后来假了（耗费了 \(10\) min），然后想到线性 DP，但是一看数据范围 \(1\le m\le 10^9\) 直接炸了，复杂度里不能有 \(m\)，没想出来只能打了 \(60\) 分部分分（\(1\le m \le10^5\)）,结果后来没时间，写了个 dfs 挂了。正解是注意到当这个数大于 \(4*7-4-7\) 即 \(17\) 时就都能到达，直接离散化全都缩成一个点就行，这里的结论来自于小凯的疑惑，还有就是这道题我感觉很熟悉，是因为这道题就是过河的弱化版，我还做过只是忘记了，哎。
T2 我只看了一眼，好像是二位价值 DP，但是因为忘记了方差公式变形，直所以接去做 T3，没做 T2。考完问了一下才知道方差公式可以变形为：
\(s^2=\sum_{i=1}^{n} (a_{i}-\bar{a})^2\)
\(=\sum_{i=1}^{n} a_{i}^2-2n\sum_{i=1}^{n} a_{i}\bar{a}+n \bar{a}^2\)
\(=\sum_{i=1}^{n} a_{i}^2-2n \bar{a}^2+n \bar{a}^2\)
\(=\sum_{i=1}^{n} a_{i}^2-n \bar{a}^2\)
\(=\sum_{i=1}^{n} a_{i}^2-(\sum_{i=1}^{n}a_{i})^2\)
所以就能知道最后求得的就是 \((n-m+1)\sum_{i=1}^{n} a_{i}^2-(\sum_{i=1}^{n}a_{i})^2\)
所以可以枚举每一种和所对应的平方和做一遍 DP（因为最大加和不超过 \(1800\)）,状态表示 \(dp[i][j][k]\) 就表示在第 \(i\) 行第 \(j\) 列加和为 \(k\) 的最小平方和，状态转移方程为：
向下：\(dp_{i,j,k}=min(dp_{i,j,k},dp_{i-1,j,k-a_{i,j}}+a_{i,j}^2);\)
向右：\(dp_{i,j,k}=min(dp_{i,j,k},dp_{i,j-1,k-a_{i,j}}+a_{i,j}^2);\)
最后的答案就是：\(\min_{k=0}^{1800} (n+m-1)dp_{n,m,k}-k^2\)
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=30;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int T=read(),t,a[N+5][N+5],dp[N+5][N+5][2*N*N+5];
int main(){while(T--){t++;int n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<=1800;k++)dp[i][j][k]=1<<30;dp[1][1][a[1][1]]=a[1][1]*a[1][1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i==1 && j==1)continue;for(int k=0;k<=1800;k++){if(i>1 && k>=a[i][j])dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-a[i][j]]+a[i][j]*a[i][j]);if(j>1 && k>=a[i][j])dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-a[i][j]]+a[i][j]*a[i][j]);}}}int ans=1<<30;for(int k=0;k<=1800;k++){if(dp[n][m][k]==1<<30)continue;int cnt=(n+m-1)*dp[n][m][k]-k*k;ans=min(ans,cnt);}printf("Case #%d: %d\n",t,ans);}return 0;
}
T3 我一眼出是换根 DP,但是我忘记怎么写了，手推了一个小时的式子结果错了，主要是第二个 dfs 错了，我一开始想的是：\(ans_{y}=ans_{x}+(size_{x}-size_{y}-1)dist[y]-size_{y}dist[y]\)，考完才想起来，每次换根都会导致原有的 \(dist\) 数组发生改变，不应该乘 \(dist\) 而是要乘 \(x\) 与 \(y\) 之间的边权 \(w\)，即 \(ans_{y}=ans_{x}+*(n-2size_{y})w\)，还有这里的 \((n-2size_{y})w\) 与上面的 \((size_{x}-size_{y}-1)w-size_{y}w)\) 是一样的
所以当 \(m=0\) 时的代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int n,m,dist[N],siz[N],ans[N],f[N];
vector< pair<int,int> > edges[N];
inline void dfs1(int x,int father){siz[x]=1;for(auto y:edges[x]){if(y.first!=father){dfs1(y.first,x);siz[x]+=siz[y.first];f[x]+=f[y.first]+siz[y.first]*y.second;}}
}
inline void dfs2(int x,int father){for(auto y:edges[x]){if(y.first!=father){ans[y.first]=ans[x]+(n-2*siz[y.first])*y.second;dfs2(y.first,x);}}
}
int main(){
// freopen("warehouse.in","r",stdin);
// freopen("warehouse.out","w",stdout);n=read(),m=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=read();edges[x].push_back({y,z});edges[y].push_back({x,z});}dfs1(1,1);ans[1]=f[1];dfs2(1,1);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}
但是这道题最难得点不在于换根 DP，而是每次边权 \(\bigoplus m\) ，这个就比较麻烦了，不过可以先把每个边权变成减去其除以 \(16\) （因为 \(m\) 的范围为 \(1\le m \le 15\)）的余数，并把余数单独拿出来放后面处理，先用处理后的边权跑一遍正常的换根 DP，然后统计每条路径的长度处理余数，如果路径长度是偶数就不变（因为连续异或上两次一样的数不放声改变），否则就异或一次就行，最后加起来就是答案