hdu 5465 Clarke and puzzle(前缀和，异或，nim博弈)-白红宇

hdu 5465 Clarke and puzzle(前缀和，异或，nim博弈)

阅读量：4927 次

发布时间：2019-06-11

本文共 2935 字，大约阅读时间需要 9 分钟。

Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke split into two personality a and b, they are playing a game. There is a n∗m matrix, each grid of this matrix has a number ci,j. a wants to beat b every time, so a ask you for a help. There are q operations, each of them is belonging to one of the following two types: 1. They play the game on a (x1,y1)−(x2,y2) sub matrix. They take turns operating. On any turn, the player can choose a grid which has a positive integer from the sub matrix and decrease it by a positive integer which less than or equal this grid's number. The player who can't operate is loser. a always operate first, he wants to know if he can win this game. 2. Change ci,j to b.

Input

The first line contains a integer T(1≤T≤5), the number of test cases. For each test case: The first line contains three integers n,m,q(1≤n,m≤500,1≤q≤2∗105) Then n∗m matrix follow, the i row j column is a integer ci,j(0≤ci,j≤109) Then q lines follow, the first number is opt. if opt=1, then 4 integers x1,y1,x1,y2(1≤x1≤x2≤n,1≤y1≤y2≤m) follow, represent operation 1. if opt=2, then 3 integers i,j,b follow, represent operation 2.

Output

For each testcase, for each operation 1, print Yes if a can win this game, otherwise print No.

Sample Input

11 2 31 21 1 1 1 22 1 2 11 1 1 1 2

Sample Output

Yes No

Hint: The first enquiry: $a$ can decrease grid $(1, 2)$'s number by $1$. No matter what $b$ operate next, there is always one grid with number $1$ remaining . So, $a$ wins. The second enquiry: No matter what $a$ operate, there is always one grid with number $1$ remaining. So, $b$ wins.

Source

题目要求二维的nim游戏，考虑到nim的结论是xor和为0则必败、否则必胜，那么我们只需要维护子矩阵的xor和。由于xor有前缀和性质，所以我们可以用一个二维bit来维护(1, 1)-(a, b)的矩阵的xor和，然后由 $\ xor \ sum(x2, y1-1) \ xor \ sum(x1-1, y2) \ xor \ sum(x1-1, y1-1)sum(x2,y2) xor sum(x2,y1−1) xor sum(x1−1,y2) xor sum(x1−1,y1−1)来得到答案即可。单点修改在bit上是很容易的。$

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #include
                
                 13 #include
                 
                  14 #include 
                  
                   15 using namespace std;16 int dirx[]={ 0,0,-1,1};17 int diry[]={-1,1,0,0};18 #define PI acos(-1.0)19 #define max(a,b) (a) > (b) ? (a) : (b) 20 #define min(a,b) (a) < (b) ? (a) : (b)21 #define ll long long22 #define eps 1e-1023 #define MOD 100000000724 #define N 50625 #define inf 1e1226 int n,m,q;27 int mp[N][N];28 int a[N][N];29 int main()30 {31 int t;32 scanf("%d",&t);33 while(t--){34 scanf("%d%d%d",&n,&m,&q);35 for(int i=1;i<=n;i++){36 for(int j=1;j<=m;j++){37 scanf("%d",&mp[i][j]);38 a[i][j]=a[i][j-1]^mp[i][j];39 }40 }41 for(int i=0;i

View Code

转载于:https://www.cnblogs.com/UniqueColor/p/4830186.html

你可能感兴趣的文章