企业专业建站,手机网站打不开的解决方法,唐山企业网站模板建站,安微省住房和城乡建设厅网站2023牛客多校第三场
B 很烦的dp
f[2][300][300][300] 需要前缀和优化滚动数组
f[i][x][y][k]
D 扩展域并查集之种类并查集的最小代价
1 到 n表示行变 n1~ 2n表示行不变 2n1~ 3n表示列变 3n1~ 4n表示列不变 对于一个需要变换的点比如说solve(int op)函数中a[i][j]!op的话就…2023牛客多校第三场
B 很烦的dp
f[2][300][300][300] 需要前缀和优化滚动数组
f[i][x][y][k]
D 扩展域并查集之种类并查集的最小代价
1 到 n表示行变 n1~ 2n表示行不变 2n1~ 3n表示列变 3n1~ 4n表示列不变 对于一个需要变换的点比如说solve(int op)函数中a[i][j]!op的话就需要变 那么一定是行变列不变或者行不变列变(总之要奇数次变换) 如果不需要变的话那么就是行不变列不变或者行变列变(总之要偶数次变换) 把决策的方案合并起来最终一定是变不能和不变在一个并查集里面否则return -1 然后对于行变代价是1列变代价也是1我们用 m p [ f i n d ( i ) ] ( 1 i n 和 2 n 1 i 2 n ) mp[find(i)](1in 和 2n1i2n) mp[find(i)](1in和2n1i2n) 然后 f o r ( a u t o [ x , y ] : m p ) a n s m i n ( a n s , y ) for(auto [x,y]:mp)ansmin(ans,y) for(auto[x,y]:mp)ansmin(ans,y) 这道题还可以扩展比如说每一行变换的代价是a[i],不变的代价是b[i],列变的代价是c[i],列不变的代价是d[i],求全0或者全1的最小代价 我认为这道题是一道很好的题
#includebits/stdc.h
using namespace std;const int N2020;
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) (n1 2n)
//列 2n1 3n 3n1 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 i1;in*4;i)p[i]i,sz[i]0;for(int i1;in;i){for(int j1;jn;j){int xa[i][j]^op;if(x1){//如果 要改 结果行不改列不改 或者 行改列改就不行if(same(i,j2*n)||same(in,j3*n))return 1e9;merge(i,j3*n);merge(in,j2*n);}else{if(same(i,j3*n)||same(in,j2*n))return 1e9;merge(i,j2*n);merge(in,j3*n);}}}
// for(int i1;in;i){
// if(same(i,in))return 1e9;
// int ji2*n;
// if(same(j,jn))return 1e9;
// }mapint,intmp;for(int i1;in;i)mp[find(i)];for(int i2*n1;i3*n;i)mp[find(i)];int ans1e9;for(auto [x,y]:mp)ansmin(ans,y);return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(int i1;in;i)for(int j1;jn;j){char c;cinc;if(c1)a[i][j]1;}int ansmin(solve(0),solve(1));if(ans1e9)ans-1;coutans;
}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 X1145,Y141981;
const int mod998244353;
int main(){int n,m;scanf(%d%d,n,m);for(int i1;in;i)scanf(%s,num[i]1);for(int i1;in;i)for(int j1;jm;j){h[i][j]((h[i-1][j]*Xh[i][j-1]*Y-h[i-1][j-1]*X*Ynum[i][j])%modmod)%mod;H[i][j]((H[i-1][j]*XH[i][j-1]*Y-H[i-1][j-1]*X*Ynum[n-i1][m-j1])%modmod)%mod;}for(int i1;i2000;i){px[i]px[i-1]*X%mod;py[i]py[i-1]*Y%mod;}functionbool(int,int,int,int)check[](int x,int y,int a,int b){ll midh[x][y]-h[a-1][y]*px[x-a1]-h[x][b-1]*py[y-b1]h[a-1][b-1]*px[x-a1]%mod*py[y-b1];xn-x1;ym-y1;an-a1;bm-b1;swap(x,a);swap(y,b);mid-H[x][y]-H[a-1][y]*px[x-a1]-H[x][b-1]*py[y-b1]H[a-1][b-1]*px[x-a1]%mod*py[y-b1];return !(mid%mod);};ll ans0;for(int i1;in;i)for(int j1;jm;j){int l0,rmin({n-i,m-j,i-1,j-1});while(lr){int midlr11;if(check(imid,jmid,i-mid,j-mid))lmid;else rmid-1;}ansl1;if(i1j1){if(!check(i,j,i-1,j-1))continue;l0,rmin({n-i,m-j,i-2,j-2});while(lr){int midlr11;if(check(imid,jmid,i-1-mid,j-1-mid))lmid;else rmid-1;}ansl1;}}printf(%lld,ans);
}I 倍增
学习倍增的另一种用法 jmp[x][i]表示从x点变换2的i次方所能达到的最高节点 U[x][i]表示从x点以颜色i不用变换所能达到的最高节点递推父亲更新儿子
核心函数jump(int x,int y) 从x点跳到低于y的代价是多少for(i20 ~ i)ans1i 然后如果能到y一定是不需要变换颜色的 还剩最后一步合并同类块也就是说x跳到zy也跳到z了判断是否能用同一种颜色这个时候就枚举i0~ 60判断是否能同时有x用颜色i跳过最近公共祖先z且有y用颜色i跳过最近公共祖先z,如果没有的话ans就需要1 ans就是 跳跃步数dep[x]dep[y]-2*dep[z] 变换次数(jump)
#includebits/stdc.h
// #define int long long
using namespace std;
const int N5e510;
int n,q,f[N][21],U[N][60],jmp[N][21],dep[N],ans;
long long a[N];
vectorintg[N];
void dfs(int u,int fa0){f[u][0]fa;dep[u]dep[fa]1;int up-1;for(int i0;i60;i){U[u][i]U[fa][i];if( (a[u]i1)U[u][i]-1)U[u][i]u;if(~a[u]i1)U[u][i]-1;int jU[u][i];if(up-1|| (j!-1dep[up]dep[j]) )upj;}jmp[u][0]up;for(int i1;i20;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(jfa)continue;dfs(j,u);}
}
int lca(int x,int y){if(xy)return x;if(dep[x]dep[y])swap(x,y);for(int i20;i0;i--)if(dep[f[x][i]]dep[y])xf[x][i];if(xy)return x;for(int i20;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
void jump(int x,int y){//x-y 上跳同时记录ans的代价for(int i20;i0;i--)if(jmp[x][i]!-1dep[jmp[x][i]]dep[y])xjmp[x][i],ans1i;
}
int so(){int x,y;cinxy;if(xy)return 0;int zlca(x,y);ansdep[x]dep[y]-2*dep[z];if(dep[x]dep[y])swap(x,y);if(yz){jump(x,y);int faf[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 need1;for(int i0;i60;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;need0;break;}return ansneed;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(U,-1,sizeof U);memset(jmp,-1,sizeof jmp);cinnq;for(int i1;in;i)cina[i];for(int i1,a,b;in;i){cinab,g[a].push_back(b),g[b].push_back(a);}dfs(1);while(q--)coutso()\n;
}
