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

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],⋯ ,a′[m−1]⇐a[i0],⋯ ,a[im−1]a'[0],\cdots,a'[m-1]\Larr a[i_0],\cdots,a[i_{m-1}]

其中对应的原数组下标必须满足

i0≡0mod  ki1≡1mod  k⋮im−1≡m−1mod  ki_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] 是否大于零即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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×mn\times m 的矩阵，两种操作：

  1. 选定第 ii 行，将该行的每一个数都替换成该数对应列的所有数的异或值；
  2. 选定第 jj 列，将该列的每一个数都替换成该数对应行的所有数的异或值。

可以执行操作任意次。最后计算矩阵的“美丽值”：

beauty(a)=∑∣ax,y−ar,c∣beauty(a)=\sum|a_{x,y}-a_{r,c}|

对矩阵中任意两个共享一条边的格子。

求最小的“美丽值”。

解题思路

观察到：

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

本质上相当于：

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

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

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

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

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

因此美丽值可以转化为

∑i=2ndr[ri−1][ri]+∑i=2mdc[ci−1][ci]\sum_{i=2}^ndr[r_{i-1}][r_i]+\sum_{i=2}^mdc[c_{i-1}][c_i]

dr,dcdr,dc 可以看成两个邻接矩阵分别对应两张图。此问题等价于 TSP。

F. Dyn-scripted Robot

题目大意

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

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

解题思路

Easy Version

n,w,h≤106,k≤nn,w,h\le10^6,k\le n.

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

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

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

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

x≡0mod  2w⇒xi≡−jxnmod  2wy≡0mod  2h⇒yi≡−jynmod  2hx\equiv0\mod 2w\Rarr x_i\equiv-jx_n\mod 2w\\ y\equiv0\mod 2h\Rarr y_i\equiv-jy_n\mod 2h

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

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

Hard Version

k≤1012k\le10^{12}

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

不会😭