C. 墨提斯的排列

考点：格雷码，二进制运算

题意：构造一个长度为2的n次方的排列，使得相邻两项异或值异或值之和最小

为什么错？弄错了规律（规律就是相邻两个数二进制码只能相差一个1，且出现不同的地方越低位越好，反正就是没找到这个规律，然后格雷码刚好符合这个规律）

AC代码

//格雷码做法
void whale_solve(){
    int n;cin>>n;
    int N=1<<n;
    vector<int>a(N);
    for(int i=0;i<N;i++) a[i]=i;
    for(int i=0;i<N;i++) cout<<(a[i]^(a[i]>>1))<<" ";
}

//不懂格雷码的做法
void whale_solve(){
    int n;cin>>n;
    vector<int>p={0};
    for(int i=0;i<n;i++){
        int add=1<<i;
        for(int j=p.size()-1;j>=0;j--) p.push_back(p[j]+add);
    }
    for(int i=0;i<p.size();i++) cout<<p[i]<<" ";
}

当 n=0 时：序列 = [0]

当 n=k 时：序列 = [G(k-1), reverse(G(k-1)) + 2^{k-1}]

//n=1->0,1
初始: p = [0]
i=0: add = 1<<0 = 1
倒序遍历 p: j=0 → p[0]=0 → 添加 0+1=1
结果: p = [0, 1]

//n=2->0,1,3,2
初始: p = [0, 1]  (n=1的结果)
i=1: add = 1<<1 = 2
倒序遍历 p:
  j=1: p[1]=1 → 添加 1+2=3
  j=0: p[0]=0 → 添加 0+2=2
结果: p = [0, 1, 3, 2]

//n=3->0,1,3,2,6,7,5,4
初始: p = [0, 1, 3, 2]
i=2: add = 1<<2 = 4
倒序遍历 p:
  j=3: p[3]=2 → 添加 2+4=6
  j=2: p[2]=3 → 添加 3+4=7
  j=1: p[1]=1 → 添加 1+4=5
  j=0: p[0]=0 → 添加 0+4=4
结果: p = [0, 1, 3, 2, 6, 7, 5, 4]

可以发现：排列以一对递增（相差1），一对递减（相差1）的规律组成，并以一种特殊的镜像呈现出来，这正是j逆序循环的原因。

H. 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学

考点：STL，暴力

题意：单点修改，区间查询最大值，具体背景看原题。

为什么错？不懂如何维护最大值，觉得可能会超时

AC代码

using ll=long long;

void whale_solve(){
    int n,m,q;cin>>n>>m>>q;
    vector<vector<ll>>sum(n+1,vector<ll>(m+1,0));
    array<ll,3>ma={0,0,0};//最大值数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;cin>>a;
            for(int dx=-2;dx<=2;dx++){
                int k=2-abs(dx);//循环范围
                for(int dy=-k;dy<=k;dy++){
                    int x=i+dx,y=j+dy;
                    if(x<1||y<1||x>n||y>m) continue;//超出范围跳过
                    sum[x][y]+=a;//记录每个点范围内的总和
                    ma=max(ma,{sum[x][y],x,y});//维护最大值和位置
                }
            }
        }
    }
    while(q--){
        int x,y,z;cin>>x>>y>>z;
        for(int dx=-2;dx<=2;dx++){
            int k=2-abs(dx);
            for(int dy=-k;dy<=k;dy++){
                int xx=x+dx,yy=y+dy;
                if(xx<1||yy<1||xx>n||yy>m) continue;
                sum[xx][yy]+=z;
                ma=max(ma,{sum[xx][yy],xx,yy});
            }
        }
        cout<<ma[1]<<" "<<ma[2]<<"\n";
    }
}