题解归档 - cf2219E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2219E
• 本地来源：problems/cf2219E/idea.md
• 题目链接：https://codeforces.com/contest/2219/problem/E
• 原始标题：cf2219E Weird Chessboard

思路

cf2219E Weird Chessboard

pattern: GF(2) constructive / Steinhaus triangle / linear code max-weight word.

claim: Let a[i][j] be the output. A cell is good iff the xor of all pieces in rectangle (1,1)..(i,j) equals a[i][j]. Therefore the board must satisfy the local relation
a[i+1][j] = a[i][j] xor a[i][j+1], with the top row forced to zero except possibly the last cell.

necessary:

• Top row cells 1..n-1 and left column cells 1..n-1 are forced to zero.
• Once the last column is chosen, the whole board is determined.
• Equivalently, anti-diagonals can be generated from the main anti-diagonal, which is all ones if the top-right cell is 1; every later anti-diagonal has one free endpoint, and the rest is prefix xor of the previous anti-diagonal.

sufficient:

• Any construction obeying the anti-diagonal transition gives a valid board.
• Need total ones at least 3 * floor(n^2 / 10).

brute/check:

• Verified the local relation by explicit prefix checker for small boards.
• Tried local greedy on anti-diagonals: valid but fails e.g. n=100.
• Tried beam search over anti-diagonal endpoint choices; valid and often above 30%, but still has failing sizes (notably around n=423) even with large beam.
• Tried Max-XOR / local search formulation where every cell is an affine xor of endpoint choices; random and single-flip local improvements did not beat beam.
• Ran sequence_guess on exact small optimum values 1 3 5 9 11 15 21 27 31 39 45 53 ...; no local/OEIS hit.

edge:

• n=1 accepts a single 1.
• Construction output must be checker-verified by prefix parity and count before being marked submit-ready.

blocker:

• Need a proof-backed high-density anti-diagonal endpoint sequence or a deterministic construction that covers every n <= 5000. Current solution.cpp is only a skeleton and must not be submitted.

代码

来源：problems/cf2219E/solution.cpp

/* Author: likely
 * Time: YYYY-MM-DD HH:MM:SS
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5];
int main(){
    ll t,n,i,j,k,zc,pd,cur,dq,cnt,ans;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>s[i];
    }
    return 0;
}