C题 Draw Grids
给定一个 \(n*m\) 大小的点阵，两个人轮流选取两个相邻点（上下或者左右）连接，但是不可以使图中生成一个环，不能进行操作者输。问先手必胜还是必败？
\(1\leq n,m\leq 4\)
出题人出这么小的数据规模，是有意想让选手写暴力的（而且应该还不少）。但是这题有一个更简单的数学写法：
多个点相连，不能成环，那么最多也就是连成一个树。一共 \(n*m\) 个点，那么至多连 \(n*m-1\) 条边，所以我们判断一下边的奇偶性就好了。
（话说这个只能相邻点连边的限制好像没啥用啊
#include<bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
cin >> n >> m;
puts((n * m - 1) % 2 ? "YES" : "NO");
return 0;
}
D题 Er Ba Game
纯模拟题，照着模拟一下就行了，但是需要细心研判各种平局的情况。
#include<bits/stdc++.h>
using namespace std;
string solve()
{
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
if (a1 > b1) swap(a1, b1);
if (a2 > b2) swap(a2, b2);
if (a1 == a2 && b1 == b2)
return "tie";
if (a1 == 2 && b1 == 8)
return "first";
else if (a2 == 2 && b2 == 8)
return "second";
if (a1 == b1 && a2 != b2)
return "first";
if (a1 != b1 && a2 == b2)
return "second";
if (a1 == b1 && a2 == b2)
return a1 > b1 ? "first" : "second";
int c1 = (a1 + b1) % 10, c2 = (a2 + b2) % 10;
if (c1 > c2) return "first";
else if (c1 < c2) return "second";
else {
if (b1 > b2) return "first";
else if (b1 < b2) return "second";
else return "tie";
}
}
int main()
{
int T;
cin >> T;
while (T--) cout << solve() << endl;
return 0;
}
F题 Girlfriend
在一个空间内，存在 \(A,B,C,D\) 四个定点和 \(P,Q\) 两个动点，满足 \(PA \geq k_1PB,QC \geq k_2QD\)，显然 \(P,Q\) 各自的轨迹占据了一片空间，此时问 \(P,Q\) 轨迹覆盖的空间并。
\(0 \leq x_i,y_i,z_i \leq 1000, 1 < k_1,k_2 \leq 100\)
在平面上，\(P,Q\) 两点显然构成了阿波罗尼斯圆，在空间上也是类似的，推理过程如下：
-
直接照着题意写出不等式，有
\[\sqrt{(x-x_A)^2+(y-y_A)^2+(z-z_A)^2} \geq k_1*\sqrt{(x-x_B)^2+(y-y_B)^2+(z-z_B)^2} \] -
简单平方约分后得
\[(k_1^2-1)x^2-2(k_1^2x_B-x_A)x + (k_1^2-1)y^2-2(k_1^2y_B-y_A)y+(k_1^2-1)z^2-2(k_1^2z_B-z_A)z = (x_A^2+y_A^2+z_A^2) - k_1^2 * (x_B^2+y_B^2+z_B^2) \]所以我们令
\[A= \frac{k_1^2x_B-x_A}{k_1^2-1},B = \frac{k_1^2y_B-y_A}{k_1^2-1},C=\frac{k_1^2z_B-z_A}{k_1^2-1},D=(x_A^2+y_A^2+z_A^2) - k_1^2 * (x_B^2+y_B^2+z_B^2) \]
将原方程化为了 \(x^2-2Ax+y^2-2By+z^2-2Cz=D\) 的形式。
- 配方得\[(x-A)^2+(y-B)^2+(z-C)^2=D+A^2+B^2+C^2 \]故圆心为 \((A,B,C)\)，半径为 \(\sqrt{D+A^2+B^2+C^2}\)
此时我们就可以得到两个圆的圆心和半径，顺便求出两个圆之间的距离，这样子就转化为了另外一个问题：
已知两个圆的半径和圆心之间的距离，求体积交。
这个是纯数学内容，略，下面直接给出代码：
#include<bits/stdc++.h>
using namespace std;
const double PI = 3.1415926535;
struct Point {
double x, y, z;
};
double dis(Point A, Point B) {
return sqrt(pow(A.x - B.x, 2.0) + pow(A.y - B.y, 2.0) + pow(A.z - B.z, 2.0));
}
struct Circle {
Point p;
double r;
double getVol() {
return 4.0 / 3.0 * PI * r * r * r;
}
};
Circle createCircle(Point u, Point v, double k) {
Circle ans;
double A = 2 * (u.x - k * k * v.x) / (k * k - 1);
double B = 2 * (u.y - k * k * v.y) / (k * k - 1);
double C = 2 * (u.z - k * k * v.z) / (k * k - 1);
double D = ((u.x * u.x + u.y * u.y + u.z * u.z) - k * k * (v.x * v.x + v.y * v.y + v.z * v.z))
/ (k * k - 1);
ans.p.x = -A / 2.0;
ans.p.y = -B / 2.0;
ans.p.z = -C / 2.0;
ans.r = sqrt(D + (A * A + B * B + C * C) / 4);
return ans;
}
double calcCircleVol(Circle cyh, Circle jhw) {
double d = dis(cyh.p, jhw.p);
double r1 = cyh.r, r2 = jhw.r;
if (d >= r1 + r2) return 0.0;
if (d <= fabs(r1 - r2)) {
return (cyh.r < jhw.r) ? cyh.getVol() : jhw.getVol();
}
//体积并
double h1=r1-(r1*r1-r2*r2+d*d)/(2.0*d);
double h2=r2-(r2*r2-r1*r1+d*d)/(2.0*d);
double v1=PI*h1*h1*(3.0*r1-h1)/3.0;
double v2=PI*h2*h2*(3.0*r2-h2)/3.0;
double s = cyh.getVol() + jhw.getVol() - v1 - v2;
//体积交
return cyh.getVol() + jhw.getVol() - s;
}
void solve()
{
Point A, B, C, D;
double k1, k2;
//read
cin >> A.x >> A.y >> A.z;
cin >> B.x >> B.y >> B.z;
cin >> C.x >> C.y >> C.z;
cin >> D.x >> D.y >> D.z;
cin >> k1 >> k2;
//solve
Circle cyh = createCircle(A, B, k1), jhw = createCircle(C, D, k2);
printf("%.10lf\n", calcCircleVol(cyh, jhw));
}
int main()
{
int T;
cin >> T;
while (T--) solve();
return 0;
}
I题 Penguins
给定两个 \(20*20\) 大小的地图，地图上有空地和石块。
现在有两个企鹅，分别在左边地图的 \((20,20)\) 和 \((20,1)\) 上面（作为起点）。每次进行移动指令（共有四种：上（U），下（D），左（L），右（R）），他们两个都会进行镜像移动（上下保持一致，但是左右相反，例如下达左移动指令，左边的企鹅向左，右边的企鹅向右）。如果移动的时候某个企鹅碰上石头，那么它不会移动，退回之前的位置，但是另外一个正常移动（除非他也碰到了石头）。当左右两个企鹅分别到达 \((1,20)\) 和 \((1,1)\) 时，游戏胜利。
现在我们需要找出到达终点的最短步数和移动指令，并且在地图上面显示出移动路径。如果存在多个最短走法，要求字典序最小（D < L < R < U）。
保证存在一条（一对）从起点到终点的路径，且两个起点上面都没石头。
本题分成两部分：求最短路径和打印路径。
这是一个典型的迷宫图，所以直接广搜即可，用 \(\operatorname{vis}(a,b,c,d)\) 表示左边企鹅在 \((a,b)\)，右边企鹅在 \((c,d)\) 的状态。数据范围还不错，所以不需要任何优化。
要求字典序最小，最笨的方法是保存所有路径后一一比较，但是有一个更简单的方法：广搜内部直接按照 D < L < R < U 的顺序来拓展，这样就可以保证第一个到达终点的节点的路径是最小的了。
显示路径的话，看起来麻烦，实际上只要一点小技巧就行了：开一个 \(\operatorname{pre}\) 数组，记录下前一个状态的坐标，外加是怎么转移过来的，到达终点的时候直接一路逆回去就得到了全部路径。（这个方法不至用于广搜打印路径，还常常用于一些其他算法之中，例如 EK 算法进行最大流增广的时候，就用这个方式一路把前面的边上全部减去一定的流量）
这题整体上思维难度不大，就是代码不太好写，老年选手手已经生疏了，打了一个多小时才打对，幸好没罚时一遍过。
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n = 20;
char map1[N][N], map2[N][N];
void read() {
char s1[N], s2[N];
for (int i = 1; i <= 20; ++i) {
scanf("%s%s", s1 + 1, s2 + 1);
for (int j = 1; j <= 20; ++j)
map1[i][j] = s1[j], map2[i][j] = s2[j];
}
}
//BFS
struct Node {
int x1, y1, x2, y2;
};
int dis[N][N][N][N];
char pre[N][N][N][N];
Node Last[N][N][N][N];
char ans_map1[N][N], ans_map2[N][N];
void print_ans(Node ans) {
//
printf("%d\n", dis[ans.x1][ans.y1][ans.x2][ans.y2]);
//
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
ans_map1[i][j] = map1[i][j];
ans_map2[i][j] = map2[i][j];
}
}
stack<char> s;
Node now = ans;
while (pre[now.x1][now.y1][now.x2][now.y2] != 'S') {
s.push(pre[now.x1][now.y1][now.x2][now.y2]);
//
ans_map1[now.x1][now.y1] = 'A';
ans_map2[now.x2][now.y2] = 'A';
now = Last[now.x1][now.y1][now.x2][now.y2];
}
ans_map1[n][n] = 'A';
ans_map2[n][1] = 'A';
while (!s.empty()) {
putchar(s.top());
s.pop();
}
puts("");
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
putchar(ans_map1[i][j]);
putchar(' ');
for (int j = 1; j <= n; ++j)
putchar(ans_map2[i][j]);
puts("");
}
return;
}
queue<Node> q;
int main()
{
read();
//
memset(dis, -1, sizeof(dis));
dis[n][n][n][1] = 0;
pre[n][n][n][1] = 'S';
q.push((Node){n, n, n, 1});
while (!q.empty()) {
Node now = q.front(), to; q.pop();
if (now.x1 == 1 && now.y1 == n && now.x2 == 1 && now.y2 == 1) {
print_ans(now);
return 0;
}
//D
to = now;
to.x1++, to.x2++;
if (to.x1 > n || map1[to.x1][to.y1] == '#') to.x1--;
if (to.x2 > n || map2[to.x2][to.y2] == '#') to.x2--;
if (to.x1 != now.x1 || to.x2 != now.x2) {
if (dis[to.x1][to.y1][to.x2][to.y2] == -1) {
dis[to.x1][to.y1][to.x2][to.y2] = dis[now.x1][now.y1][now.x2][now.y2] + 1;
pre[to.x1][to.y1][to.x2][to.y2] = 'D';
Last[to.x1][to.y1][to.x2][to.y2] = now;
q.push(to);
}
}
//L
to = now;
to.y1--, to.y2++;
if (to.y1 < 1 || map1[to.x1][to.y1] == '#') to.y1++;
if (to.y2 > n || map2[to.x2][to.y2] == '#') to.y2--;
if (to.y1 != now.y1 || to.y2 != now.y2) {
if (dis[to.x1][to.y1][to.x2][to.y2] == -1) {
dis[to.x1][to.y1][to.x2][to.y2] = dis[now.x1][now.y1][now.x2][now.y2] + 1;
pre[to.x1][to.y1][to.x2][to.y2] = 'L';
Last[to.x1][to.y1][to.x2][to.y2] = now;
q.push(to);
}
}
//R
to = now;
to.y1++, to.y2--;
if (to.y1 > n || map1[to.x1][to.y1] == '#') to.y1--;
if (to.y2 < 1 || map2[to.x2][to.y2] == '#') to.y2++;
if (to.y1 != now.y1 || to.y2 != now.y2) {
if (dis[to.x1][to.y1][to.x2][to.y2] == -1) {
dis[to.x1][to.y1][to.x2][to.y2] = dis[now.x1][now.y1][now.x2][now.y2] + 1;
pre[to.x1][to.y1][to.x2][to.y2] = 'R';
Last[to.x1][to.y1][to.x2][to.y2] = now;
q.push(to);
}
}
//U
to = now;
to.x1--, to.x2--;
if (to.x1 < 1 || map1[to.x1][to.y1] == '#') to.x1++;
if (to.x2 < 1 || map2[to.x2][to.y2] == '#') to.x2++;
if (to.x1 != now.x1 || to.x2 != now.x2) {
if (dis[to.x1][to.y1][to.x2][to.y2] == -1) {
dis[to.x1][to.y1][to.x2][to.y2] = dis[now.x1][now.y1][now.x2][now.y2] + 1;
pre[to.x1][to.y1][to.x2][to.y2] = 'U';
Last[to.x1][to.y1][to.x2][to.y2] = now;
q.push(to);
}
}
}
return 0;
}
K题 Stack
给定一个类似于单调栈的代码，如下所示：
stack<int> s; for (int i = 1; i <= n; ++i) { while (!s.empty() && s.top() > a[i]) s.pop(); s.push(a[i]); b[i] = s.size(); }现在我们知道排列 \(\{a_n\}\) 的长度 \(n\)，但是不知道里面的具体元素。但是我们知道 \(\{b_n\}\) 里面的 \(k\) 项元素（以及他们的下标）。现在，我们需要判断能否根据此来构造一个排列 \(\{a_n\}\)，如果能的话就打印他，不能就输出 -1。
\(1 \leq k \leq n \leq 10^6\)
基于构造的解法
我们不难想到在完全知道 \(\{b_n\}\) 时如何还原排列 \(\{a_n\}\) ：依次寻找 \(b_i=k(k=1,2,\cdots,n)\) 的值，如果有多个就从后向前，依次填上从 \(1\) 到 \(n\) 的数，如下所示：（凭借直觉这么写的，具体原因不太好用文字解释，可以看代码，顺带找几个样例手玩一下）
//
const int N = 1000010;
int b[N], a[N];
//邻接表
int tot = 0, data[N], Head[N], Next[N];
void add(int p, int val) {
data[++tot] = val;
Next[tot] = Head[p], Head[p] = tot;
}
//主代码
void create() {
for (int i = 1; i <= n; ++i)
add(b[i], i);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int k = Head[i]; k; k = Next[k])
a[data[k]] = ++cnt;
}
那么问题来了：这个数列 \(\{b_n\}\) 怎么构造？
我们不难发现数列 \(\{b_n\}\) 满足下面这两个性质：
-
\(i \geq b_i\) ，这个很显然：\(b_i\) 记录的是这个单调栈任意时刻的元素数量，而其上限正是 \(i\)
-
\(b_{i+1}-b_i \leq 1\)，这也很显然：每次最多往栈里面推一个元素，甚至需要推出来一些。
这个公式还可以变形一下，变成 \(b_{i+1}-b_i \leq (i + 1)- i\) ，也就是 \(i-b_i\leq (i+1)-b_{i+1}\) 。
综上，我们可以综合一下这个性质：数列 \({n-b_n}\) 为非负数列，且单调不降。
我的队友想出了如下的构造方法，我也只是知道这代码确实没错，但是具体是怎么想出来的我也不太清楚：
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, k;
struct Node {
int p, x;
} a[N];
bool cmp1(Node &rhs1, Node &rhs2) {
return rhs1.p < rhs2.p;
}
//
int b[N], ans[N];
//
int tot = 0, data[N], Head[N], Next[N];
void add(int p, int val) {
data[++tot] = val;
Next[tot] = Head[p], Head[p] = tot;
}
//
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < k; ++i)
scanf("%d%d", &a[i].p, &a[i].x);
sort(a, a + k, cmp1);
//check
for (int i = 0, Last = 0; i < k; Last = a[i].p - a[i].x, ++i)
if (a[i].p - a[i].x < Last) {
printf("-1");
return 0;
}
//
for (int i = 0; i < k; ++i)
b[a[i].p] = a[i].x;
//construct
if (!b[n]) b[n] = 1;
for (int i = n; i > 0; i--)
if (!b[i]) {
if (b[i + 1] > 1) b[i] = b[i + 1] - 1;
else b[i] = 1;
}
//build
for (int i = 1; i <= n; ++i)
add(b[i], i);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int k = Head[i]; k; k = Next[k])
ans[data[k]] = ++cnt;
for (int i = 1; i <= n; ++i)
printf("%d ", ans[i]);
return 0;
}
基于图论的解法
假设某时刻，序列中有 \([a_1,a_2,a_5,a_7]\) 这四个元素，此时我们想要加入 \(a_8\)，但是发现 \(a_2,a_5,a_7\) 都要比他大，所以我们需要将这三个数弹出来，然后插入 \(a_8\)。我们发现，这时候似乎可以发现，如果我们将 \(\{a_n\}\) 中的 \(n\) 个数视作 \(n\) 个节点，那么他们的大小关系就形成了一个有向无环图。在知晓 \(\{a_n\}\) 的时候我们可以构造出这个 DAG，但是在知道 \(\{b_n\}\) 的时候我们同样可以构造出这个 DAG（时刻根据 \(b_i\) 的大小来推测此时推出了几个数，推进去了几个数）。当我们对于 \(\{b_n\}\) 里面的数了解不全的时候，只是 DAG 可能的赋值方式增多了，但是同样有解（当然了，发现 DAG里面有环，或者构造的时候发现了错误，例如栈里面没元素了还要 pop 啥的，此时就无解了）。
显然，每个元素都只需要进出栈一次，再加上拓扑排序，总复杂度仅仅是 \(O(n)\) 。
有一说一，这题真不容易往图论上面想，一实验室的人看到伪代码和排列，基本上都是往构造想的。
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, k, a[N], b[N];
//Graph
const int M = 10000010;
int tot = 0, ver[M], Head[N], Next[M];
int indegree[N];
void addEdge(int u, int v) {
indegree[v]++;
ver[++tot] = v;
Next[tot] = Head[u], Head[u] = tot;
}
//
bool construct() {
stack<int> s;
for (int i = 1; i <= n; ++i) {
if (!b[i]) {
if (!s.empty()) addEdge(s.top(), i);
s.push(i);
}
else {
if ((int)s.size() < b[i] - 1) return false;
while (s.size() >= b[i]) {
addEdge(i, s.top());
s.pop();
}
if (!s.empty()) addEdge(s.top(), i);
s.push(i);
}
}
return true;
}
void topoSort() {
queue<int> q;
for (int i = 1; i <= n; ++i)
if (!indegree[i]) q.push(i);
int cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
a[u] = ++cnt;
for (int i = Head[u]; i; i = Next[i]) {
int v = ver[i];
indegree[v]--;
if (!indegree[v]) q.push(v);
}
}
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < k; ++i) {
int p, x;
scanf("%d%d", &p, &x);
b[p] = x;
}
if (!construct()) {
puts("-1");
return 0;
}
topoSort();
for (int i = 1; i <= n; ++i) {
printf("%d ", a[i]);
}
return 0;
}