2023牛客多校第三场

B 很烦的dp

f[2][300][300][300]
需要前缀和优化+滚动数组

f[i][x][y][k]

D 扩展域并查集之种类并查集的最小代价

1 到 n表示行变
n+1~ 2n表示行不变
2n+1~ 3n表示列变
3n+1~ 4n表示列不变
对于一个需要变换的点比如说solve(int op)函数中a[i][j]!=op的话就需要变
那么一定是行变列不变，或者行不变列变(总之要奇数次变换)
如果不需要变的话，那么就是行不变列不变或者行变列变(总之要偶数次变换)
把决策的方案合并起来，最终一定是变不能和不变在一个并查集里面，否则return -1
然后对于行变，代价是1，列变，代价也是1，我们用
$m p [f in d (i)] + + (1 <= i <= n 和 2 n + 1 <= i <= 2 n)$
然后
$f or (a u t o [x, y] : m p) an s = min (an s, y)$
这道题还可以扩展，比如说每一行变换的代价是a[i],不变的代价是b[i],列变的代价是c[i],列不变的代价是d[i],求全0或者全1的最小代价
我认为这道题是一道很好的题

#include<bits/stdc++.h>
using namespace std;const int N=2020;
int p[N*4],n,a[N][N];int find(int x){if(p[x]==x)return x;return p[x]=find(p[x]);
}
//行 (1 n) (n+1 2n) 
//列 2n+1 3n 3n+1 4n
int same(int i,int j){return find(i)==find(j);
}
void merge(int i,int j){p[find(i)]=find(j);
}
int sz[N*4];
int solve(int op){for(int i=1;i<=n*4;i++)p[i]=i,sz[i]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=a[i][j]^op;if(x==1){//如果 要改 结果（行不改列不改） 或者 （行改列改）就不行if(same(i,j+2*n)||same(i+n,j+3*n))return 1e9;merge(i,j+3*n);merge(i+n,j+2*n);}else{if(same(i,j+3*n)||same(i+n,j+2*n))return 1e9;merge(i,j+2*n);merge(i+n,j+3*n);}}}
//     for(int i=1;i<=n;i++){
//         if(same(i,i+n))return 1e9;
//         int j=i+2*n;
//         if(same(j,j+n))return 1e9;
//     }map<int,int>mp;for(int i=1;i<=n;i++)mp[find(i)]++;for(int i=2*n+1;i<=3*n;i++)mp[find(i)]++;int ans=1e9;for(auto [x,y]:mp)ans=min(ans,y);return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){char c;cin>>c;if(c=='1')a[i][j]=1;}int ans=min(solve(0),solve(1));if(ans==1e9)ans=-1;cout<<ans;
}

G 二维马拉车+二维哈希

二维哈希+二分勉强能冲过去

#include <bits/stdc++.h>#define el '\n'
using namespace std;
typedef long long ll;
const int N = 2010;
const ll X = 149, Y = 941;int n, m;
int p[N];
ll px[N], py[N];
ll h1[N][N], h2[N][N];
char s[N][N];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);px[0] = 1;for (int i = 1; i <= n; ++i) px[i] = px[i - 1] * X;py[0] = 1;for (int i = 1; i <= m; ++i) py[i] = py[i - 1] * Y;for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {h1[i][j] = h1[i - 1][j] * X + h1[i][j - 1] * Y - h1[i - 1][j - 1] * X * Y + s[i][j];h2[i][j] = h2[i - 1][j] * X + h2[i][j - 1] * Y - h2[i - 1][j - 1] * X * Y + s[n - i + 1][m - j + 1];}auto get = [&](ll h[][N], int x1, int x2, int y1, int y2) {--x1, --y1;ll X = px[x2 - x1], Y = py[y2 - y1];return h[x2][y2] - h[x2][y1] * Y - h[x1][y2] * X + h[x1][y1] * X * Y;};ll ans = 0;for (int i = 1; i <= n; ++i) {int mr = 0, mid;for (int j = 1; j <= m; ++j) {if (j < mr) p[j] = min(p[mid * 2 - j], mr - j);else p[j] = 1;while (1) {int x1 = i - p[j], x2 = i + p[j];int y1 = j - p[j], y2 = j + p[j];if (x2 > n || x1 <= 0 || y2 > m || y1 <= 0) break;if (get(h1, x1, i, y1, y2) != get(h2, n + 1 - x2, n + 1 - i, m + 1 - y2, m + 1 - y1)) break;++p[j];}if (j + p[j] > mr) mr = j + p[j], mid = j;ans += p[j];}}for (int i = 1; i < n; ++i) {int mr = 0, mid;for (int j = 1; j < m; ++j) {if (j < mr) p[j] = min(p[mid * 2 - j], mr - j);else p[j] = 1;while (1) {int x1 = i - p[j] + 1, x2 = i + p[j];int y1 = j - p[j] + 1, y2 = j + p[j];if (x2 > n || x1 <= 0 || y2 > m || y1 <= 0) break;if (get(h1, x1, i, y1, y2) != get(h2, n + 1 - x2, n - i, m + 1 - y2, m + 1 - y1)) break;++p[j];}if (j + p[j] > mr) mr = j + p[j], mid = j;ans += p[j] - 1;}}printf("%lld\n", ans);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char num[2001][2001];
ll h[2001][2001];
ll H[2001][2001];
ll px[2001]={1},py[2001]={1};
const int X=1145,Y=141981;
const int mod=998244353;
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",num[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){h[i][j]=((h[i-1][j]*X+h[i][j-1]*Y-h[i-1][j-1]*X*Y+num[i][j])%mod+mod)%mod;H[i][j]=((H[i-1][j]*X+H[i][j-1]*Y-H[i-1][j-1]*X*Y+num[n-i+1][m-j+1])%mod+mod)%mod;}for(int i=1;i<=2000;i++){px[i]=px[i-1]*X%mod;py[i]=py[i-1]*Y%mod;}function<bool(int,int,int,int)>check=[&](int x,int y,int a,int b){ll mid=h[x][y]-h[a-1][y]*px[x-a+1]-h[x][b-1]*py[y-b+1]+h[a-1][b-1]*px[x-a+1]%mod*py[y-b+1];x=n-x+1;y=m-y+1;a=n-a+1;b=m-b+1;swap(x,a);swap(y,b);mid-=H[x][y]-H[a-1][y]*px[x-a+1]-H[x][b-1]*py[y-b+1]+H[a-1][b-1]*px[x-a+1]%mod*py[y-b+1];return !(mid%mod);};ll ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int l=0,r=min({n-i,m-j,i-1,j-1});while(l<r){int mid=l+r+1>>1;if(check(i+mid,j+mid,i-mid,j-mid))l=mid;else r=mid-1;}ans+=l+1;if(i>1&&j>1){if(!check(i,j,i-1,j-1))continue;l=0,r=min({n-i,m-j,i-2,j-2});while(l<r){int mid=l+r+1>>1;if(check(i+mid,j+mid,i-1-mid,j-1-mid))l=mid;else r=mid-1;}ans+=l+1;}}printf("%lld",ans);
}

I 倍增

学习倍增的另一种用法
jmp[x][i]表示从x点变换2的i次方所能达到的最高节点
U[x][i]表示从x点以颜色i不用变换所能达到的最高节点，递推，父亲更新儿子

核心函数jump(int &x,int y)
从x点跳到低于y的代价是多少for(i=20 ~ i)ans+=1<<i
然后如果能到y，一定是不需要变换颜色的
还剩最后一步合并同类块，也就是说x跳到z，y也跳到z了，判断是否能用同一种颜色，这个时候就枚举i=0~ 60判断是否能同时有x用颜色i跳过最近公共祖先z且有y用颜色i跳过最近公共祖先z,如果没有的话ans就需要+1， ans就是跳跃步数dep[x]+dep[y]-2*dep[z] + 变换次数(jump)

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=5e5+10;
int n,q,f[N][21],U[N][60],jmp[N][21],dep[N],ans;
long long a[N];
vector<int>g[N];
void dfs(int u,int fa=0){f[u][0]=fa;dep[u]=dep[fa]+1;int up=-1;for(int i=0;i<60;i++){U[u][i]=U[fa][i];if( (a[u]>>i&1)&&U[u][i]==-1)U[u][i]=u;if(~a[u]>>i&1)U[u][i]=-1;int j=U[u][i];if(up==-1|| (j!=-1&&dep[up]>dep[j]) )up=j;}jmp[u][0]=up;for(int i=1;i<=20;i++){f[u][i]=f[f[u][i-1]][i-1];if(jmp[u][i-1]!=-1)jmp[u][i]=jmp[jmp[u][i-1]][i-1];}for(auto j:g[u]){if(j==fa)continue;dfs(j,u);}
}
int lca(int x,int y){if(x==y)return x;if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];return f[x][0];
}
void jump(int &x,int y){//x->y 上跳，同时记录ans的代价for(int i=20;i>=0;i--)if(jmp[x][i]!=-1&&dep[jmp[x][i]]>dep[y])x=jmp[x][i],ans+=1<<i;
}
int so(){int x,y;cin>>x>>y;if(x==y)return 0;int z=lca(x,y);ans=dep[x]+dep[y]-2*dep[z];if(dep[x]<dep[y])swap(x,y);if(y==z){jump(x,y);int fa=f[x][0];if(a[x]&a[fa])return ans;else return -1;}jump(x,z),jump(y,z);if(jmp[x][0]==-1||jmp[y][0]==-1)return -1;if(dep[jmp[x][0]]>dep[z]||dep[jmp[y][0]]>dep[z])return -1;int need=1;for(int i=0;i<60;i++){if(U[x][i]==-1||U[y][i]==-1)continue;if(dep[U[x][i]]>dep[z]||dep[U[y][i]]>dep[z])continue;need=0;break;}return ans+need;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(U,-1,sizeof U);memset(jmp,-1,sizeof jmp);cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1,a,b;i<n;i++){cin>>a>>b,g[a].push_back(b),g[b].push_back(a);}dfs(1);while(q--)cout<<so()<<'\n';
}