11.29-12.2

什么都没干。

12.3

偷的一个题目。

 

题意：

给一个N*N（N为偶数，N<=3000）的棋盘，上面放满黑白两面的棋子，我们用O表示白X表示黑，初始状态都是黑向上。

一次操作是选择一个棋子，与其同行或者同列的所有棋子（包括自己）翻面。

给一个最终局面，问：进行了几次操作？选择的是哪几个点？

 

分析：

首先选择的点在最终局面上一定是白子。

其次，对于最终局面的所有白子，无非两种情况。

1.操作中选择了这个子，并将与其同行同列的子翻转。

2.操作中选择了与这个子同行(列)的一个子翻转。

但是这两种白子具有区别。

由1.形成的白子其同行中的白子数等于其同列中的白子数。

简证：考虑初始局面，任意选一个位置翻，再选第二个位置翻的时候，必然与第一个子所在的行列都有且仅有一个交点。

　　　也就是使第一个子的行列都减少一个白子，同时我们注意到所有被选择翻的子其行列的白子数都是相等的，继续

　　　归纳即可。

由2.形成的白子其行列白子差为奇数，类似1.的方法来说明即可。

 

结论：在最终局面上寻找所有行列白子数相等的白子即为答案。

 

简陋datamaker

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 const int maxn = 3030; 9 char G[maxn][maxn];10 int visx[maxn], visy[maxn];11 12 void init(int n)13 {14 memset(visx, 0, sizeof(visx));15 memset(visy, 0, sizeof(visy));16 for(int i = 1; i <= n; i++)17 for(int j = 1; j <= n; j++)18 G[i][j] = 'X';19 return;20 }21 22 void change(int n, int x, int y)23 {24 G[x][y] = G[x][y] == 'O' ? 'X' : 'O';25 for(int i = 1; i <= n; i++)26 {27 if(i != y) G[x][i] = G[x][i] == 'O' ? 'X' : 'O';28 if(i != x) G[i][y] = G[i][y] == 'O' ? 'X' : 'O';29 }30 return;31 }32 33 void Print(int n)34 {35 printf("%d\n", n);36 for(int i = 1; i <= n; i++)37 {38 for(int j = 1; j <= n; j++)39 printf("%c", G[i][j]);40 puts("");41 }42 return;43 }44 45 int main(void)46 {47 srand(time(NULL));48 freopen("data.txt","w",stdout);49 FILE * f_out = fopen("ans.txt","w");50 int T = 100, N = 3000;51 printf("%d\n", T);52 for(int i = 1; i <= T; i++)53 {54 int n = 1;55 while( n % 2 == 1 ) n = rand() % (N - 1) + 1;56 init(n);57 int k = rand() % (n + 1), cnt = 0;58 for(int j = 1; j <= 10000; j++)59 {60 if(cnt == k) break;61 int x = rand() % (n - 1) + 1, y = rand() % (n - 1) + 1;62 if(visx[x] || visy[y]) continue;63 cnt++;64 visx[x] = visy[y] = 1;65 change(n, x, y);66 }67 Print(n);68 fprintf(f_out, "%d\n", min(k,cnt));69 }70 fclose(f_out);71 return 0;72 }
           
          
         
        
       
      

 

简陋solver

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 typedef pair
           
             pii; 8 const int maxn = 3030; 9 char G[maxn][maxn];10 int cntx[maxn], cnty[maxn];11 12 bool cmp(pii A, pii B)13 {14 if(A.first != B.first) return A.first < B.first;15 return A.second < B.second;16 }17 18 int main(void)19 {20 freopen("data.txt","r",stdin);21 freopen("out.txt","w",stdout);22 int T;23 scanf("%d", &T);24 while(T--)25 {26 int N;27 scanf("%d", &N);28 for(int i = 1; i <= N; i++)29 scanf("%s", G[i] + 1);30 31 memset(cntx, 0, sizeof(cntx));32 memset(cnty, 0, sizeof(cnty));33 34 for(int i = 1; i <= N; i++)35 for(int j = 1; j <= N; j++)36 if(G[i][j] == 'O') cntx[i]++, cnty[j]++;37 38 vector
            
              ans;39 for(int i = 1; i <= N; i++)40 {41 for(int j = 1; j <= N; j++)42 {43 if(G[i][j] != 'O' || cntx[i] != cnty[j]) continue;44 ans.push_back(pii(i,j));45 }46 }47 48 int L = ans.size();49 printf("%d\n", L);50 if(L)51 {52 for(int i = 0; i < L; i++) printf("%d %d ", ans[i].first, ans[i].second);53 puts("");54 }55 }56 return 0;57 }
            
           
          
         
        
       
      

 

简陋judge

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 const int maxn = 3030; 5 char G[maxn][maxn]; 6  7 void change(int n, int x, int y) 8 { 9     G[x][y] = G[x][y] == 'O' ? 'X' : 'O';10     for(int i = 1; i <= n; i++)11     {12         if(i != y) G[x][i] = G[x][i] == 'O' ? 'X' : 'O';13         if(i != x) G[i][y] = G[i][y] == 'O' ? 'X' : 'O';14     }15     return;16 }17 18 bool judge(int n)19 {20     for(int i = 1; i <= n; i++)21             for(int j = 1; j <= n; j++)22                 if(G[i][j] != 'X') return false;23     return true;24 }25 26 void Print(int n)27 {28     printf("%d\n", n);29     for(int i = 1; i <= n; i++)30     {31         for(int j = 1; j <= n; j++)32             printf("%c",G[i][j]);33         puts("");34     }35     return;36 }37 38 int main(void)39 {40     FILE * f_in = fopen("data.txt","r");41     FILE * f_ans = fopen("ans.txt","r");42     FILE * f_user = fopen("out.txt","r");43     int T;44     fscanf(f_in, "%d", &T);45     int ok = 1;46     for(int kase = 1; kase <= T; kase++)47     {48         int N;49         fscanf(f_in, "%d", &N);50         for(int i = 1; i <= N; i++)51             fscanf(f_in, "%s", G[i] + 1);52 53         int k, ans;54         fscanf(f_user, "%d", &k);55         fscanf(f_ans, "%d", &ans);56 57         for(int i = 1; i <= k; i++)58         {59             int x, y;60             fscanf(f_user ,"%d%d",&x, &y);61             change(N, x, y);62         }63 64         if(k != ans) {ok = 0; printf("%d\n", kase);}65         if(!judge(N)) {ok = 0; printf("%d\n", kase);}66         //Print(N);67     }68     puts(ok ? "AC" : "WA");69     fclose(f_in);70     fclose(f_ans);71     fclose(f_user);72     return 0;73 }
       
      

 

如果N为奇数怎么做呢？

容易发现，在奇数棋盘中，对于上述的1.与2.也有一些性质。

由1.形成的白子，行列白子差为0，行列白子和为2n-2k+2（自己算两次,k为翻的次数）。

由2.形成的白子，行列白子差为|n-1-2k|（k为翻的次数），行列白子和为n+1（自己算两次）。

所以对于一般的情况，我们仍可以统计行列白子数来做。

但是当满足n=2k-1时，1.与2.形成的白子行列和差全部相同，就无法用这种方法来找了。

这个情况的做法至今没想出来。先弃了。

 

12.4

什么都没干。

 

12.5

打个BC。压线上紫。

看自己的曲线也不是一点长进都没有吧。