Codeforces 405C Unusual Product

发表于 | 分类于 |
字数统计: 413 字

题目链接

题解

因为觉得这是一道出的很好的模拟题，所以拿过来了。
上文中提到的flip操作其实就是取反。
暴力做法是$O(nq)$的，挂。
看数据，考虑有没有什么接近线性的做法：我们将整个结果展开。
比如这么一个方阵：

他的unusual square 就是由于是在模$2$的环境下进行，这个式子后半部分都是没有用的东西。所以只要时时刻刻维护前面平方项的和即可。
然而…每一次操作都必然改变一项且仅改变一个平方项，使之从0变1或从1变0.
所以做法就是

  1. 读入时不保留矩阵，只算平方项
  2. 更新时只要知道它更新了即可，然后把平方和异或1。
    这个算法的复杂度就是$O(n^2+q)-O(1)$的。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <cctype>
    #define INF 2000000000
    using namespace std;
    typedef long long ll;
    int n,sum=0,lg[1005],q,jc;
    //保留对角线只是我无聊...
    int read(){
        int f=1,x=0;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
        while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
        return f*x; 
    }	
    void init(){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&((i==j)?lg[i]:jc));
        for(int i=0;i<n;i++)
            sum^=lg[i];
    }
    void solve(){
        scanf("%d",&q);
        int op;
        for(int i=0;i<q;i++){
            scanf("%d",&op);
            if(op==3)printf("%d",sum);
            else scanf("%d",&jc),sum^=1; 
        }
    }
    int main(){
        init();
        solve();
        return 0;
    }