CF1574-EDU114

wflengxuenong · 2022-09-30 09:48:10 · 个人记录

D:

bfs,用优先队列，从最大值状态开始换小一个数的，如果遇到一个非m的状态，就是所求答案。

E:

//TJ
//要么行异色，要么列异色 
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
int n,m,k,pw[N],cx[N][2],cy[N][2],c[2],c1,c2;//cx,分奇数列和偶数列 
map<pair<int,int>,bool>mp;
inline void work(int x,int y,int v)
{
    if(!cx[x][0]&&!cx[x][1])n+=v;//* cx，cx[x][0]描述x行的奇数列填1或偶数列填0的情况。cx[x][1]代表奇数列填0，没填0和1，那么这个位置就随便填。 
    if(!cy[y][0]&&!cy[y][1])m+=v;//* cy，代表行随便填的情况。 
    if(cx[x][0]&&cx[x][1])c1+=v;//矛盾，例如奇数列了1，偶数列也填了1，这样就不是每列不同了，产生矛盾
    if(cy[y][0]&&cy[y][1])c2+=v;//如果奇数行填1，偶数行也填1，又产生矛盾 
//  cout<<"cx: "<<x<<":"<<cx[x][0]<<" "<<cx[x][1]<<"  cy"<<y<<":"<<cy[y][0]<<" "<<cy[y][1]<<endl; 
//  cout<<"  nm "<<n<<" "<<m<<" c1,c2:"<<c1<<" "<<c2<<endl;
}
/*
del 
例如：描述行相异的情况，
如果多个列内有数据，
    对n，m第一个work不会起作用。第二个也不会。
    对c1c2，删除会减少矛盾，先减去，如果矛盾存在，就继续加上。
只有当对唯一有数据的列操作时候-1无用，+1有用，增加一个*   
*/ 
inline void del(int x,int y,bool t)
{
    work(x,y,-1);//原来的 **1*、****，原来的这个1要删去符合条件才减去 
    --cx[x][(y&1)^t];//单点修改。 
    --cy[y][(x&1)^t];
    --c[(abs(x-y)&1)^t];
    work(x,y,1);
}
/*
ins 
例如：描述行相异的情况，
如果多个列内有数据，
    对n，m第一个work不会起作用。第二个也不会。 
    对c1c2，如果原来没矛盾，-1不会起作用。增加后，+1才可能起作用。 
只有当第一次变成有数的时候：-1有用，+1无用，减少一个*
*/ 
inline void ins(int x,int y,bool t)
{
    work(x,y,-1);
    ++cx[x][(y&1)^t];//x行，若1^1和0^0在奇数列填1和在偶数列填0的效果一样，奇数列填1相当于这一列需要的0个数增加了 
                    //奇数列有1相当于偶数列有0；奇数列有0相当于偶数列有1 ，
                    //cx[x][0]统计的是奇数列 填1或偶数列填0的个数 ;cx[x][1]记录奇数填0或偶数列填1的个数。 
    ++cy[y][(x&1)^t];
    ++c[(abs(x-y)&1)^t];// 描述左右45度线的奇偶性 ，a11填1和a12填0,a22填1，a21填0都是c[1],   
    /*
     c[0]   01   c[1] 10
            10        01  这种情况行也不同，列也不同，会重复统计 
    */ 
    work(x,y,1);
}
inline void print()
{
    int ans=add(c1?0:pw[n],c2?0:pw[m]);//如果c1非零，说明列有矛盾，不能列不同的方式填充！c2同理 
    // 如果没有c[0],那就要在行不同里面减去列不同的情况，c[1]同理。 
    ans=dec(ans,(c[0]==0)+(c[1]==0));
    printf("%d\n",ans);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    pw[0]=1;for(int i=1;i<=max(n,m);++i)pw[i]=add(pw[i-1],pw[i-1]);//无限制 2^i 
    while(k--)
    {
        int x,y,t;scanf("%d%d%d",&x,&y,&t);
        auto now=make_pair(x,y);
        if(mp.count(now))//如果存在，先删掉 
        {
            del(x,y,mp[now]);//删掉原来的0或者1 
            mp.erase(now);
        }
        if(t>=0)ins(x,y,t),mp[now]=t;//改成需要的0或者1. 
        print();
    }
    return 0;
}