E.Counting Rectangles

思路：将每个(hi,wi)看成是一个二维平面上的点，该点的值为hi*wi，那么求(h1,w1),(h2,w2)之间点的值的和就等价于求点(h1+1,w1+1),(h2+1,w2+1)之间的矩形的值的和，可以直接二维前缀和求解

代码：

const int N = 1010;
const int mod=1e9+7;

void slove(){
   int n,m;
   cin>>n>>m;
   ll q[N][N];
   mm(q,0);
   cout << q[2][2] << endl;
   return;
   _for(i,0,n){
    int h,w;
    cin>>h>>w;
    q[h][w]+=h*w;
   }
    _for(i,0,N){
        _for(j,1,N){
            q[i][j]+=q[i][j-1];
        }
    }
    _for(i,1,N){
        _for(j,0,N){
            q[i][j]+=q[i-1][j];
        }
    }
   _for(i,0,m){
    int h1,w1,h2,w2;
    cin>>h1>>w1>>h2>>w2;
    h1+=1,w1+=1,h2+=1,w2+=1;
    if(h1>h2||w1>w2){
        cout << 0 << endl;
    }
    else{
        ll res=q[h2][w2]-q[h2][w1-1]-q[h1-1][w2]+q[h1-1][w1-1];
        cout << res << endl;
    }
   }
}

F.L-shapes

思路1：可以发现，如果合法的话每个深色块的周围8个格子一定刚好有两个深色的，同时这三个块一定不在一条线上。满足上述条件还不够，例如:

. * .
* . *
. * .

因此对每个深色点，还要dfs一下看看这个联通块的大小是否为3，如果不为3的话返回false

代码：

int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};
int px[4]={-1,0,0,1},py[4]={0,-1,1,0};

bool st[N][N];
char f[N][N];

int n,m;

int dfs(int i,int j){
    st[i][j]=true;
    int res=1;
    _for(k,0,4){
        int x=i+px[k],y=j+py[k];
        if(x<1||x>n||y<1||y>m)continue;
        if(st[x][y])continue;
        if(f[x][y]=='.')continue;
        res+=dfs(x,y);
    }
    return res;
}

bool judge(int i,int j){
    if(st[i][j])return true;
    int cnt=dfs(i,j);
    return cnt==3;
}

void slove(){
    mm(st,0);
   cin>>n>>m;
   _fore(i,0,n+1){
    _fore(j,0,m+1){
        f[i][j]='.';
    }
   }
   _fore(i,1,n){
    _fore(j,1,m){
        cin>>f[i][j];
    }
   }
   bool flag=true;
   _fore(i,1,n){
    _fore(j,1,m){
        if(f[i][j]=='*'){
            int cnt=0;
            _for(k,0,8){
                int x=i+dx[k],y=j+dy[k];
                if(f[x][y]=='*')cnt++;
            }
            if(cnt!=2){
                flag=false;
                break;
            }
            else{
                if(f[i-1][j]=='*'&&f[i+1][j]=='*'){
                    flag=false;
                    break;
                }
                if(f[i][j+1]=='*'&&f[i][j-1]=='*'){
                    flag=false;
                    break;
                }
                if(!judge(i,j)){
                    flag=false;
                    break;
                }
            }
        }
    }
    if(!flag)break;
   }
   if(flag)cout << "YES" << endl;
   else cout << "NO" << endl;
}

思路2：找拐角点，每个深色拐角点的上下左右四个方向一定恰好有两个深色点，且这三个神色点不在同一直线上。对每一个拐角点，将这三个深色点染成同一个颜色。在处理完后，遍历二维数组，若满足要求的话首先每个深色点都必须被染色，其次每个染色点的周围8个格子的染色点的颜色都必须和该格子相同，不然就会有相邻的L

代码：

int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int px[8]={-1,-1,-1,0,0,1,1,1},py[8]={-1,0,1,-1,1,-1,0,1};

int col[N][N];
char f[N][N];

int n,m;

void slove(){
    mm(col,0);
   cin>>n>>m;
   _fore(i,0,n+1){
    _fore(j,0,m+1){
        f[i][j]='.';
    }
   }
   _fore(i,1,n){
    _fore(j,1,m){
        cin>>f[i][j];
    }
   }
   int now=1;
   bool flag=true;
   _fore(i,1,n){
    _fore(j,1,m){
        if(f[i][j]=='*'){
            if(col[i][j])continue;
            int cnt=0;
            _for(k,0,4){
                int x=i+dx[k],y=j+dy[k];
                if(f[x][y]=='*')cnt++;
            }
            if(cnt==2){
                if(f[i-1][j]=='*'&&f[i+1][j]=='*'){
                    flag=false;
                    break;
                }
                if(f[i][j+1]=='*'&&f[i][j-1]=='*'){
                    flag=false;
                    break;
                }
                col[i][j]=now;
                _for(k,0,4){
                    int x=i+dx[k],y=j+dy[k];
                    if(f[x][y]=='*'){
                        col[x][y]=now;
                    }
                }
                now++;
            }
        }
    }
    if(!flag)break;
   }
   _fore(i,1,n){
    _fore(j,1,m){
        if(f[i][j]=='*'&&!col[i][j]){
            flag=false;
            break;
        }
        if(f[i][j]=='*'){
            _for(k,0,8){
                int x=i+px[k],y=j+py[k];
                if(col[x][y]&&col[x][y]!=col[i][j]){
                    flag=false;
                    break;
                }
            }
        }
    }
    if(!flag)break;
   }
   if(flag)cout << "YES" << endl;
   else cout << "NO" << endl;
}

G. Even-Odd XOR

思路：将偶数位置元素的异或值与奇数位置元素的异或值相等的要求转换成偶数位置元素异或值⊕奇数位置元素的异或值等于0，因此只要构造出一个序列满足每个元素互不相同且所有元素异或值等于0即可。可以采用这样一种构造方法：将0~n-2位置的元素赋值为0~n-2，设前n-2个元素的最高位为第x位，从1开始算，然后n-1位置的元素1<<x，最后让第n个位置元素为前n-1个元素的异或值即可。这样所有元素的异或值为0.下面证明这种构造方法不会出现重复元素：首先前n-1个元素一定不同的，而第n个元素一定与前n-2个元素不同，因为第n个元素最高位1比前n-2个元素的最高位1位置都高，如果第n个元素与第n-1个元素相同的话，说明前n-2个元素的异或值为0，此时只用将第n-2个元素的值加一然后用同样的方法求出第n-1和第n个位置元素即可，这样构造出来的序列一定不会有相同的元素

代码：

void slove(){
   int n;
   cin>>n;
   int ans[n];
   int tem=0;
   _fore(i,0,n-3){
    ans[i]=i;
    tem^=i;
   }
   if(tem==0){
    tem^=ans[n-3];
    ans[n-3]++;
    tem^=ans[n-3];
   }
   int mmax=ans[n-3];
    int cnt=0;
    while(mmax){
        cnt++;
        mmax>>=1;
    }
    int res=1<<cnt;
    ans[n-2]=res;
    ans[n-1]=ans[n-2]^tem;
    _for(i,0,n)cout << ans[i] << " ";
    cout << endl;
}