CF1644D Cross Coloring
题意:
在一个 \(n\) 行 \(m\) 列的网格里执行 \(q\) 次操作,每次操作在 \(k\) 种颜色中 (没有初始颜色) 选择一种给第 \(x_i\) 行和第 \(y_i\) 列染色且覆盖原有颜色,问最终染色方案数
做法:
因为后染的色会覆盖先染的色,所以最后染的色一定不会被覆盖,不需要处理被覆盖的情况,所以我们从后向前枚举每次操作,如果当前列和当前行都已经被染色,那么这次操作会被后面的操作覆盖,对结果没有影响,不需要统计,否则共有 \(k\) 种染色方法,将答案 \(\times k\)。
特判:
当网格全部被覆盖,即 \(n\) 行或 \(m\) 列全部被覆盖时,前面的操作对最终结果都没有影响,直接跳出即可。
时间复杂度 \(O(TQ)\)
记得开 long long
!
代码:
#include<iostream>#define int long longusing namespace std;int T;int a[200010], b[200010];bool x[200010], y[200010];inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}int maxx(int x, int y){return x > y ? x : y;}signed main(){T = read();while(T--){int n=read(), m=read(), k=read(), q=read();int xf=0, yf=0, ans=1, c=maxx(n, m);for(int i=1; i<=c; i++){x[i] = y[i] = false;}for(int i=1; i<=q; i++){a[i] = read();b[i] = read();}for(int i=q; i>=1; i--){if(xf == n || yf == m){break;}bool flag = false;if(x[a[i]] == false){x[a[i]] = true;flag = true;xf ++;}if(y[b[i]] == false){y[b[i]] = true;flag = true;yf ++;}if(flag){ans *= k;ans %= 998244353;}}cout << ans << '\n';}return 0;}#include<iostream> #define int long long using namespace std; int T; int a[200010], b[200010]; bool x[200010], y[200010]; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int maxx(int x, int y) { return x > y ? x : y; } signed main() { T = read(); while(T--) { int n=read(), m=read(), k=read(), q=read(); int xf=0, yf=0, ans=1, c=maxx(n, m); for(int i=1; i<=c; i++) { x[i] = y[i] = false; } for(int i=1; i<=q; i++) { a[i] = read(); b[i] = read(); } for(int i=q; i>=1; i--) { if(xf == n || yf == m) { break; } bool flag = false; if(x[a[i]] == false) { x[a[i]] = true; flag = true; xf ++; } if(y[b[i]] == false) { y[b[i]] = true; flag = true; yf ++; } if(flag) { ans *= k; ans %= 998244353; } } cout << ans << '\n'; } return 0; }#include<iostream> #define int long long using namespace std; int T; int a[200010], b[200010]; bool x[200010], y[200010]; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int maxx(int x, int y) { return x > y ? x : y; } signed main() { T = read(); while(T--) { int n=read(), m=read(), k=read(), q=read(); int xf=0, yf=0, ans=1, c=maxx(n, m); for(int i=1; i<=c; i++) { x[i] = y[i] = false; } for(int i=1; i<=q; i++) { a[i] = read(); b[i] = read(); } for(int i=q; i>=1; i--) { if(xf == n || yf == m) { break; } bool flag = false; if(x[a[i]] == false) { x[a[i]] = true; flag = true; xf ++; } if(y[b[i]] == false) { y[b[i]] = true; flag = true; yf ++; } if(flag) { ans *= k; ans %= 998244353; } } cout << ans << '\n'; } return 0; }
© 版权声明
THE END
暂无评论内容