CF1644D Cross Coloring

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

© 版权声明
THE END
喜欢就支持一下吧
点赞10 分享
pride relates more to our opinion of ourselves, vanity to what we would have others think of us.
骄傲多半涉及我们自己怎样看待自己,而虚荣则涉及我们想别人怎样看我们
评论 抢沙发

请登录后发表评论

    暂无评论内容