CF1644D Cross Coloring-Toy模板网

这篇具有很好参考价值的文章主要介绍了CF1644D Cross Coloring。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

CF1644D Cross Coloring

题意:

在一个 \(n\) 行 \(m\) 列的网格里执行 \(q\) 次操作，每次操作在 \(k\) 种颜色中 (没有初始颜色) 选择一种给第 \(x_i\) 行和第 \(y_i\) 列染色且覆盖原有颜色，问最终染色方案数

做法:

因为后染的色会覆盖先染的色，所以最后染的色一定不会被覆盖，不需要处理被覆盖的情况,所以我们从后向前枚举每次操作，如果当前列和当前行都已经被染色，那么这次操作会被后面的操作覆盖，对结果没有影响，不需要统计，否则共有 \(k\) 种染色方法，将答案 \(\times k\)。

特判:

当网格全部被覆盖，即 \(n\) 行或 \(m\) 列全部被覆盖时，前面的操作对最终结果都没有影响,直接跳出即可。

时间复杂度 \(O(TQ)\)

记得开 long long ！文章来源地址https://www.toymoban.com/news/detail-743507.html

代码:

#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;
}

到了这里，关于CF1644D Cross Coloring的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！