D. Cross Coloring(逆向思维 + 点覆盖问题)_学习

D. Cross Coloring(逆向思维 + 点覆盖问题)

创始人

2025-05-28 01:44:27

Problem - D - Codeforces

有一张纸，可以用大小为n × m的网格表示:n行和m列的单元格。所有的细胞最初都是白色的。G操作已应用于该工作表。其中的i可以描述为:2i yi-从k种非白色中选择一种，然后给整行和整列y上色。新颜色应用于每个单元格，而不管该单元格在操作之前是否被着色。应用所有q运算后的薄片称为着色。如果至少有一个单元格被着色，则两种颜色是不同的有多少种不同的颜色?打印数字模998 244 353。输入第一行包含一个整数t (1

Example

input

Copy

1 1 3 2

1 1

2 2 2 3

2 1

1 1

2 2

output

Copy

3
4

注意:

如果使用#define int long long 是无法通过这道题的会T

以后输入输出都用scanf,

题解

用于涂改是按顺序的,所以一个点是什么颜色都是由最后一次在这个点上染色决定的

所以我们反过来考虑

如果点没有被染色过,不考虑

记录点最后一次被染色,可以染k种,所以乘k

如何判断一个点被染过色

1.所有行被染过都不考虑了

2.所有列被染过都不考虑了

3.该行该列被染过不考虑了

用两个数组记录行列是否被染过即可

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//#define int long long
const int N = 4e6 + 10;
typedef pair PII;
int x[N],y[N];
PII p[N];
int mod =  998244353;
void solve() 
{int n,m,k,q;scanf("%d%d%d%d",&n,&m,&k,&q);int a = 0,b = 0;int ans = 1;for(int i = 1;i <= n;i++){x[i] = 0;}for(int j = 1;j <= m;j++){y[j] = 0;}for(int i = 1;i <= q;i++){scanf("%d%d",&p[i].first,&p[i].second);}for(int i = q;i >= 1;i--){if(a == n||b == m||(x[p[i].first]&&y[p[i].second])){continue;}if(!x[p[i].first]){x[p[i].first] = 1;a++;}if(!y[p[i].second]){y[p[i].second] = 1;b++;}ans = 1ll*ans*k%mod;}printf("%d\n",ans); 
}//1 2 4
signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;
scanf("%d",&t);while (t--) {solve();}
}
//1 1 1 0 1//1 1 1 0 1
//1 1 1 0 1
//1 1 1 0 1
//0 1 1 1 1
//0 1 1 1 1

下一篇：通过指针引用字符串详解，以及字符指针变量和字符数组的比较

D. Cross Coloring(逆向思维 + 点覆盖问题)

相关内容

热门资讯