ICPC_2020 上海站
待补完
B
题意
给两个 (ncdot m) 的字符矩阵 A B 代表一个扫雷的局面，'X' 代表对应位置有雷，'.' 代表对应位置是空的。
要求改变 B 矩阵中的一些字符，使得 A B 两个矩阵中所有空位上的数字之和相等。
要求改变的字符数量不超过 $lfloor frac{nm}{2} floor $ ，如无解输出 -1 。
(n,m leq 1000)
赛场上
开场就读了题，一眼不太会，于是就放了。
回头一看已经过了几百个队了。
于是硬着头皮做，结果还是不太会。鉴于过了这么多人，猜测有结论：肯定是把 B 变成 A 的某种同构（翻折旋转啥的）。
复制粘贴，写了快一百行的烂代码，一发WA
这时候发现把一个矩阵的雷和空格全部转置，数字之和相等。
大伙试图找反例——没找到，直呼不可战胜
于是把乱搞程序的翻折旋转加上了这个转置，顺利 AC 。大家纷纷表示这做法绝对是伪的，纯乱搞
正经题解
发现把一个矩阵的雷和空格全部转置，数字之和相等
结论正确性其实不是很难证明。
考虑原矩阵中某个雷周围有 (k) 个空格。
转置后，该雷变成空格对这 (k) 个数字之和的贡献是 (-k) 。
而这 (k) 个空格变成雷，反映在中间这个空格上的值就是 (k) 。
加起来对答案贡献为 (0) 。
这个证明并不严谨，但是总之结论是对的。
那么，若 B 需要变换多于 $lfloor frac{nm}{2} floor $ 个字符才能变成 A ，那么考虑把 B 变成转置后的 A 矩阵，一定只需要变换不超过 $lfloor frac{nm}{2} floor $ 个字符就可以了。于是做完了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1024;
char a[N][N], b[N][N];
int n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("
%s", a[i] + 1);
for (int i = 1; i <= n; ++i) scanf("
%s", b[i] + 1);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j )
cnt += (a[i][j] != b[i][j]);
if (cnt > n * m / 2) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = (a[i][j] == 'X')? '.': 'X';
}
for (int i = 1; i <= n; ++i)
printf("%s
", a[i] + 1);
return 0;
}
顺带一提赛场上是这样写的：
#include <bits/stdc++.h>
#define REP for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j)
using namespace std;
const int N = 1024;
int n, m, lim;
char a[N][N], b[N][N], c[N][N];
void output() {
for (int i = 1; i <= n; ++i) {
printf("%s
", a[i] + 1);
}
exit(0);
}
void copy() {
REP a[i][j] = c[i][j];
}
void turn() {
if (n != m) return ;
REP c[j][n - i + 1] = a[i][j];
copy();
}
int comp() {
int ans = 0;
REP ans += (a[i][j] != b[i][j]);
return ans;
}
void ccomp() {
if (comp() <= lim) output(); turn();
if (comp() <= lim) output(); turn();
if (comp() <= lim) output(); turn();
if (comp() <= lim) output(); turn();
}
void flip_x() {
REP c[i][j] = a[i][m - j + 1];
copy();
}
void flip_y() {
REP c[i][j] = a[n - i + 1][j];
copy();
}
void flip_tt() {
if (n != m) return ;
REP c[i][j] = a[j][i];
copy();
}
void rev() {
REP a[i][j] = (a[i][j] == '.') ? ('X') : ('.');
}
void cccomp() {
ccomp(); rev();
ccomp(); rev();
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("
%s", a[i] + 1);
for (int i = 1; i <= n; ++i) scanf("
%s", b[i] + 1);
lim = n * m / 2;
cccomp();
flip_x(); cccomp();
flip_x(), flip_y(); cccomp();
flip_x(); cccomp();
flip_x(), flip_y(), flip_tt(); cccomp();
flip_x(); cccomp();
flip_x(), flip_y(); cccomp();
flip_x(); cccomp();
puts("-1");
return 0;
}
C
待补完
D
第四发终于A掉这题的znr：「我直接切腹得了」
题意
考虑一个数轴。在 (p_1,p_2) 两个位置站了两个人，他们走路的速度分别为 (v_1,v_2) 。
现在要求两个人走完 ([0,n]) 之间的所有点，求最短时间。
(p_1,p_2leq nleq 10^9)
赛场上
显然就是个纯讨论推式子的题。
调试半天，一共交了四发WA，最后wjp发现我把一个 (v_1) 写成 (v_2) 了。
改掉就 A 了。
正经题解
首先给出一个观察：两个人都一刻不停的走动一定可以使答案更优，因此我们假设两人走路的时间 (t) 相同。
为了简化运算，令 (p_2=n-p_2) 表示长度。
首先考虑两个人都会转身的情况。显然地，两人会在同一位置转身，否则就会有一些点无法走到了。假设两人的起点到转身点的距离分别为 (x_1,x_2) ，分别考虑 (2^2) 种出发方向，那么我们有
分别解这几个方程就可以得到 (t) 与 (p_1,p_2,v_1,v_2) 的关系。
值得注意的是，解得的结果 (t) 很可能是非法的（如(p_1=p_2)时），需要特别判断
(tcdot v_i leq 2min(p_i,n-p_1-p_2)+max(p_i,n-p_1-p_2),~~i=1,2)
如该式不成立需要舍去。
考虑只有一个人转身的情况：
还有一种对称的就是：
我就是把这种的 (v_2) 写成 (v_1) 了（
考虑不转身的情况。
最后把所有的 (t) 放到一起求个 (min) 就得了。
附赛场AC代码
#include <bits/stdc++.h>
using namespace std;
int main() {
long double p1, p2, v1, v2, n;
int T; cin >> T;
while (T--) {
cin >> n >> p1 >> v1 >> p2 >> v2;
if (p1 > p2) {
swap(p1, p2);
swap(v1, v2);
}
p2 = n - p2;
long double t1 = (n + p1 + p2) / (v1 + v2),
t2 = (2 * n - p1 - p2) / (v1 + v2),
t3 = (2 * n + 2 * p1 - p2) / (2 * v1 + v2),
t4 = (2 * n + 2 * p2 - p1) / (2 * v2 + v1),
t5 = (min(p1, n - p1) * 2 + max(p1, n - p1)) / (v1),
t6 = (min(p2, n - p2) * 2 + max(p2, n - p2)) / (v2),
t7 = max((p1 / v1), (min(p2, n - p1 - p2) * 2 + max(p2, n - p1 - p2)) / v2),
t8 = max((p2 / v2), (min(p1, n - p1 - p2) * 2 + max(p1, n - p1 - p2)) / v1);
long double t9 = max((n - p1) / v1, (n - p2) / v2);
long double d = (n - p1 - p2);
if (t2 * v1 > 2 * min(d, p1) + max(d, p1)) t2 = 1e20;
if (t2 * v2 > 2 * min(d, p2) + max(d, p2)) t2 = 1e20;
if (t3 * v1 > 2 * min(d, p1) + max(d, p1)) t3 = 1e20;
if (t3 * v2 > 2 * min(d, p2) + max(d, p2)) t3 = 1e20;
if (t4 * v1 > 2 * min(d, p1) + max(d, p1)) t4 = 1e20;
if (t4 * v2 > 2 * min(d, p2) + max(d, p2)) t4 = 1e20;
if (t1 * v1 > 2 * min(d, p1) + max(d, p1)) t1 = 1e20;
if (t1 * v2 > 2 * min(d, p2) + max(d, p2)) t1 = 1e20;
long double ans = min(min(min(t1, t2), min(t3, t4)), min(min(t5, t6), min(t7, t8)));
ans = min(ans, t9);
printf("%.10Lf
", ans);
}
return 0;
}
I
题意
给 (n) 个同心圆，他们的半径之差是 (1) 。作 (m) 条过圆心的直线，把每个圆都分成均匀的 (2m) 份。
考虑所有直线与圆的交点以及圆心构成的点集。
求点集中任意两点最短距离的总和。
赛场上
不仅想出了 (O(n^3)) 解法，甚至想到了 (O(n^2)) 的。
然而我没把三方的调出来，队友也没时间写平方算法了。
总之就是呜呜呜了。
正经题解
首先考虑任意两个给定点之间的最短距离如何计算。
这里直接给出显然的结论：
-
若两个点不在同一个圆上，先由外层点经半径走到内层圆上
-
若两点在同一个圆上：
从 A 到 B 有三类可能的路径：
- 走圆弧 AB （ (LaTeX) 语法怎么写不了啊 ）
- 经过两条半径走 (A o O o B)
- 先走到里层的圆上，然后走圆弧，最后走回外层圆
考虑 (OA,OB) 的夹角是 ( heta) ，三种方式的路径长度显然分别为
- (R heta)
- (2R)
- (2R+( heta-2)r)
其中 (R,r) 分别代表外层和里层圆的半径。那么我们容易得到
[min(R heta,2R,2R+( heta-2)r) = egin{cases} R heta & heta leq 2\ 2R & heta > 2 end{cases} ]
在这个基础上，考虑怎么求所有点对的距离和：
(O(n^2m)) 算法是显然的：每一层上的各个点的地位相同，只要计算其中一个，把结果乘上(2m) 即可。考虑计算某个点到其他所有点的距离和，我们可以直接枚举所有的 (2nm) 个点依次计算。
考虑层级之间的位似放大关系可以优化到平方复杂度。