本次比赛链接。说实话出的比较糟糕，题目难度的梯度非常不均匀。

A, B, C 题没什么好说的，跳过。

D. Med-imize

题目大意

给定一个包含 n 个 int 的数组 a，给定 k。在 a 中，每次选择长度刚好为 k 的任意的连续子数组进行删除，删除至 a 长度小于等于 k 为止。求删除操作结束后数组 a 最大可能的中位数值。

解题思路

二分搜索答案 + 动态规划。

当输入数组长度小于等于 k 时，答案就是当前数组的中位数。

如何在不排序的情况下求出一个数组的中位数呢？二分查找。

对每一个给定的值 x，建立另一个和 a 一样大的标签数组 b。
当 x<=a[i] 时，标记 b[i]=1；反之 b[i]=-1。
这样通过判断 b 数组和的正负性，我们就能判断 x 是否比中位数小了。

当 n>k 时，同理进行二分搜索答案。为了检查当前值是否小于最优可能解，我们只需使用动态规划求出 b 数组最大的和，检查其正负性。

如何用动归求 b 数组最大的和呢？

注意到每次删除完成后数组的长度为 m=((n-1)%k)+1。

注意到删除完成后的数组 a' 中的每一位一定来自于原数组： $$ a'[0],\cdots,a'[m-1]\Leftarrow a[i_0],\cdots,a[i_{m-1}] $$ 其中对应的原数组下标必须满足 $$ i_0\equiv0\mod k\ i_1\equiv1\mod k\ \vdots\ i_{m-1}\equiv m-1\mod k $$

为何？因为每次刚好删除的是 a 中连续的 k 个，删除之后并不影响每个下标模 k 的结果。

令 dp[i] 表示数组 a 中前 i 个数字中选择满足下标要求的 k 个数对应 b 数组之和的最大值，综上可得动态规划递推关系：

dp[0]=b[0]
如果 i%k==0&&i>0，dp[i]=max(dp[i-k],b[i])（有可能把 i 之前的所有全删除了，从 i 开始）
否则
如果 i<=k，dp[i]=dp[i-1]+b[i]。（只有选上当前数字）
如果 i>k，dp[i]=max(dp[i-1]+b[i],dp[i-k])。（要么选当前数字，要么把包括这个数字之前总共 k 个数字都删了，选第 i-k 个数字）

最后只需检查 dp[n-1] 是否大于零即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,k,a[maxn],dp[maxn],b[maxn];
bool jg(int med){
    for(int i=0;i<n;i++){
        b[i]=a[i]>=med?1:-1;
    }
    dp[0]=b[0];
    for(int i=1;i<n;i++){
        if(i%k==0) dp[i]=max(dp[i-k],b[i]);//必然为删除后数组的第一个数
        else{
            dp[i]=dp[i-1]+b[i];
            if(i>k){
                dp[i]=max(dp[i],dp[i-k]);
            }
        }
    }
    return bool(dp[n-1]>0);
}
void work(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int l=1,r=1e9;
    while(l<=r){
        int mid=(l+r)/2;
        if(jg(mid)){
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<r<<endl;
    return;
}
int main(){
    int test_case;
    cin>>test_case;
    while(test_case--){
        work();
    }
    return 0;
}

E. Xor-Grid Problem

题目大意

给一个 $n\times m$ 的矩阵，两种操作：

选定第 $i$ 行，将该行的每一个数都替换成该数对应列的所有数的异或值；
选定第 $j$ 列，将该列的每一个数都替换成该数对应行的所有数的异或值。

可以执行操作任意次。最后计算矩阵的“美丽值”： $$ beauty(a)=\sum|a_{x,y}-a_{r,c}| $$ 对矩阵中任意两个共享一条边的格子。

求最小的“美丽值”。

解题思路

观察到：

尝试连续对某一行进行两次相同的操作，发现结果不变
尝试对第 $i$ 行进行操作，再尝试对第 $i'$ 行进行操作，发现 $i'$ 行上的数字刚好就是原始第 $i$ 行上的数字。

本质上相当于：

将原始的矩阵拓展一行一列变成 $(n+1)\times(m+1)$。$a[i][m+1]$ 就是第 $i$ 行所有数的异或值，同理 $a[n+1][j]$ 就是第 $j$ 列所有数的异或值。

每一次操作就是将第 $i$ 行（或第 $j$ 列）与第 $n+1$ 行（或第 $m+1$ 列）进行交换。妙蛙

现在问题就转化为行和列的排列问题。

接下来拆解美丽值，美丽值可以分为两部分，横向的相邻格和纵向的相邻格。（在操作结束之后，扩展的那一行/列就不要参与到美丽值的计算中了！）

计算 $dr[u][v]$ 表示第 $u$ 行和第 $v$ 行的差值；$dc[u][v]$ 表示对应列的差值。

因此美丽值可以转化为 $$ \sum_{i=2}^{ndr[r_{i-1}][r_i]+\sum_{i=2}}mdc[c_{i-1}][c_i] $$ $dr,dc$ 可以看成两个邻接矩阵分别对应两张图。此问题等价于 TSP。

F. Dyn-scripted Robot

题目大意

有一个机器人初始位于平面坐标 $(0,0)$ 上。给定一个长度为 $n$ 的指令序列，让机器人上下左右移动。这个指令序列将执行 $k$ 次。机器人被限制在高度为 $h$，宽度为 $w$ 的一个矩形区域中。当机器人在边界上如果指令会导致出界，则立即将该方向上所有指令取反。比如当机器人位于右边界时，此时指令向右，则机器人自动将指令序列中所有的左指令变成右指令，右指令变成左指令。

求在整个过程中机器人回到原点的次数。

解题思路

Easy Version

$n,w,h\le10^6,k\le n$.

仔细思考，其实不用考虑反弹的情况，让机器人自由移动，出界的时候其实就相当于进入了一个镜像对称的空间。

其实就相当于有四面镜子分别摆放在矩形区域的四个边上，那么实际上 $(2wc_1,2hc_2),c_1,c_2\in\mathbb Z$ 都可以视作原点。所以分别经过取模 $2w,2h$，机器人就限制在了长宽为 $2w,2h$ 的矩形中。

记 $(x_i,y_i)$ 为机器人执行第一遍指令序列时每一步所在的位置。则指令完成后机器人位于 $(x_n,y_n)$。

此后机器人在执行第 $j$ 遍指令序列时的第 $i$ 个指令，所在的位置为 $(jx_n+x_i,jy_n+y_i)$。同时，需要满足

\[ x\equiv0\mod 2w\Rightarrow x_i\equiv-jx_n\mod 2w\\ \]

\[ y\equiv0\mod 2h\Rightarrow y_i\equiv-jy_n\mod 2h \]

直接遍历 $0$ 到 $k-1$，对每一遍指令序列满足同余关系数量求和。最终得到答案。

可以用 map 存储执行第一遍指令序列机器人位于长宽为 $2w,2h$ 的矩形内每一个点的经过次数。

Hard Version

$k\le10^{12}$

$k$ 的范围导致了不能遍历 $k$，猜想是在同余方程上做文章。

不会