第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）

题意：给定一张 $n\times m$ 的扫雷图 A 和 B。让你修改 B ，使得它们扫雷图上的数字之和相加相等。修改次数不超过 $\lfloor \frac {nm}{2} \rfloor$

思路：

首先分析一下 A 和 A 的反图，可以发现它们的数字之和是相等的。可以对有雷和无雷连一条边。边的数量，就是贡献的数量。现在把图取反了，依然是原来的连边情况，贡献不变。
所以计数图 A 和 B 的不同点的数量，如果超过了一半，就输出 A 的反图就好了。

题意：
在这里插入图片描述

思路：

枚举两维 i 和 j ，把式子分为两部分。左边部分，用数位DP计算的个数 cnt ，右边部分在枚举的 i 和 j 第一次取 1 的时候(也就是在 i + j 取最高位的时候)，累加到答案上去。

题意：在 $[0, n]$ 上有两个人，分别在 $p_1,p_2$ ，速度为 $v_1,v_2$ 。问最短需要多少时间走完全程。

思路：分成两部分

题意：给定 n、k，问有多少个长度为 $n$ 的排列满足对任意的 $\in [k,n]$ ， $a_i>min(a_{i-1},\dots,a_{i-k})$ 。

思路：

这里唯一的限定在于最小值的位置。它只能出现在 [1,k] 的位置。最小值位置 p 确定之后，p 的左边可以任意排，p 的右边与左边的联系，也因为最小值的关系而消失了，所以右边变成了一个新的子问题。
设 dp[i] 表示长度为 i 的排列的方案数
$dp[i]=\sum_{j=1}^{min(i,k)} dp[i-j] \times C(i-1,j-1)\times (j-1)!$
优化一下可得：
$\frac {dp[i]}{i!}=\sum_{j=1}^{min(i,k)} \frac {dp[i-j]}{(i-j)!} \times \frac 1i$

思路：把奇数 * 奇数的情况排除。

题意：内外两个环分别有 k 个点散布在 0 到 n - 1 上。现在对它们做匹配，问至少要转动多少的距离，才能够使得 k 个点都恰好匹配一次，且匹配的结构刚好是 1 对 1 的。

思路：

首先要想到：每个点和最终的匹配点之间连线，是没有交点的。不然一定不是最优的。
然后就可以枚举外环的点与内环的点匹配，然后得到每个点需要转动的距离 c。这里记录的都是顺时针方向的距离，也就是 $b_{i+d}$ 顺转动 $c_i$ 可以到达 $a_i$ 。（只有统计同一方向上的 c ，才能够做）
对这些距离 $c$ 从小到大排序。对于一个 $c_i$ 来说，如果顺时针走 $c_i$ 步，那么小于等于 $c_i$ 都可以满足，如果逆时针走 $n-c_i$ 步，那么所有大于等于 $c_i$ 的都可以满足条件。
所以，就可以利用距离的间隔来更新答案。 $c_1$ 是最小的所以可以绕一圈来更新答案，即 $n-c_1$ 。或者直接用最大值 $c_k$ 顺时针走 $c_k$ 步。
然后就可以枚举 $c_i$ 和 $c_{i+1}$ 。先让 $c_i$ 顺着走，然后倒回来，在让 $c_{i+1}$ 逆时针走。即 $2c_i+n-c_{i+1}$ 。也可以先让 $c_{i+1}$ 逆时针走，再让 $c_i$ 顺着走，即 $2(n-c_{i+1})+c_i$

题意：求 n 个环，m 条等分线之间所有交点的距离之和。

思路：

题意：给定一个网格图。一条轨迹定义为：起点和终点在网格上。中间没有穿越过其他的整点。问从(0,0) 达到(n,m) 的轨迹的最短长度是多少。

思路：

题意：给定 n 个可忽略的文件名， m 个不可忽略的文件名。问最少可以忽略几个文件名。

思路：给文件名按照前缀动态开点。给不可忽略的文件，最后设置 sz 为 1 。从叶走到根，更新 sz 。如果一个点的 sz >0 就说明不可被忽略。