APIO2022 度假记

APIO2022

APIO, 但是是埃及主办, 姑且认为 A 是 Africa.

中国区这次是南京举办的, 在这边考试是禁止像 APIO 官方通知的那样访问互联网的, 也被禁止使用官方允许的自己提前编写的代码, 显然试题告诉我们访问互联网和复制代码也确实没有什么用.

T1

我当时没有看见不能用全局变量, 所以当时把这道题写了一个并查集合并陆地上去, 轻松过样例后提交全 WA. 当时我重新阅读要求之后才恍然大悟, 但是废了一份代码, 感觉难受. 我当时在疑惑它是怎么防止我们使用全局变量的.

如下是零分离谱代码:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include "mars.h"
unsigned Fa[16005], Stack[16005], *STop(Stack), Cnt(0), N;
inline unsigned Find(unsigned x) {
  while (Fa[x] ^ x) *(++STop) = x, x = Fa[x];
  while (STop > Stack) Fa[*(STop--)] = x;
  return x;
}
inline void Merge(unsigned x, unsigned y) { /*printf("Merge %u - %u\n", x, y);*/if(x ^ y) --Cnt, Fa[y] = x; }
inline unsigned Get(unsigned x, unsigned y) {/*printf("Get (%u, %u)\n", x, y);*/return x * N + y;}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n) {
  // printf("Here %u %u At %u Tot %u\n", i, j, k, N);
  // printf("%c %c %c\n%c %c %c\n%c %c %c\n", a[0][0][0], a[0][1][0], a[0][2][0], a[1][0][0], a[1][1][0], a[1][2][0], a[2][0][0], a[2][1][0], a[2][2][0]);
  if(!k) {
    unsigned Num;
	  if(!i) {
      if(!j) {
        N = (n << 1) + 1;
        if(a[0][0][0] == '1') ++Cnt, Num = Get(0, 0), Fa[Num] = Num;
        if(a[0][1][0] == '1') ++Cnt, Num = Get(0, 1), Fa[Num] = Num;
        if(a[1][0][0] == '1') ++Cnt, Num = Get(1, 0), Fa[Num] = Num;
        if(a[1][1][0] == '1') ++Cnt, Num = Get(1, 1), Fa[Num] = Num;
      }
      if(a[0][2][0] == '1') ++Cnt, Num = Get(0, j + 2), Fa[Num] = Num;
      if(a[1][2][0] == '1') ++Cnt, Num = Get(1, j + 2), Fa[Num] = Num;
    }
    if(!j) {
      if(a[2][0][0] == '1') ++Cnt, Num = Get(i + 2, 0), Fa[Num] = Num;
      if(a[2][1][0] == '1') ++Cnt, Num = Get(i + 2, 1), Fa[Num] = Num;
    }
    if(a[2][2][0] == '1') ++Cnt, Num = Get(i + 2, j + 2), Fa[Num] = Num;
    unsigned A, B;
    if(a[1][1][0] == '1') {
      A = Find(Get(i + 1, j + 1));
      if(a[1][0][0] == '1') Merge(A, Find(Get(i + 1, j)));
      if(a[0][1][0] == '1') Merge(A, Find(Get(i, j + 1)));
      if(a[1][2][0] == '1') Merge(A, Find(Get(i + 1, j + 2)));
      if(a[2][1][0] == '1') Merge(A, Find(Get(i + 2, j + 1)));
    }
    if(a[0][1][0] == '1') {
      A = Find(Get(i, j + 1));
      if(a[0][0][0] == '1') Merge(A, Find(Get(i, j)));
      if(a[0][2][0] == '1') Merge(A, Find(Get(i, j + 2)));
    }
    if(a[1][0][0] == '1') {
      A = Find(Get(i + 1, j));
      if(a[0][0][0] == '1') Merge(A, Find(Get(i, j)));
      if(a[2][0][0] == '1') Merge(A, Find(Get(i + 2, j)));
    }
    if(a[2][1][0] == '1') {
      A = Find(Get(i + 2, j + 1));
      if(a[2][0][0] == '1') Merge(A, Find(Get(i + 2, j)));
      if(a[2][2][0] == '1') Merge(A, Find(Get(i + 2, j + 2)));
    }
    if(a[1][2][0] == '1') {
      A = Find(Get(i + 1, j + 2));
      if(a[0][2][0] == '1') Merge(A, Find(Get(i, j + 2)));
      if(a[2][2][0] == '1') Merge(A, Find(Get(i + 2, j + 2)));
    }
	}
  if(k == n - 1) {
    // printf("Cnt %u\n", Cnt);
    std::string Rt(std::string(100, '0'));
    unsigned Cur(0);
    while (Cnt) Rt[Cur] = '0' + (Cnt & 1), Cnt >>= 1, ++Cur;
    return Rt;
  }
  return a[0][0];
}

然后就认为这个题可能要求我们用所给的空间去进行一个插头 DP, 但是很遗憾, 每一个阶段, 一个点的信息只能结合它右下方的点的信息更新, 而枚举顺序却是保证了每个点更新的时候, 它右下方的点都没有更新. 所以这是非常难以将信息逆向传递的, 而本阶段更新后的信息只能等下一个阶段才能更新别人.

但是我当时没有想到, 可以用给出的空间直接存储整个图, 在最后一个阶段直接进行 BFS 求解. 我们发现这样拿到的分是十分可观的. 而每个点的空间是 100bit100bit, 我们最后一个阶段可以访问 99 个点一共 900bit900bit 的空间, 可以存 30∗3030 * 30 的棋盘, 也就是 54′54'.

我下场之后一开始以为每一位可以是 char, 也就是存 8bit8bit, 所以误以为本题正解非常无脑, 只要存下整张图就可以 AC, 但是事实并非如此.

正解貌似还是类似插头 DP 的东西. 接下来是我的猜想:

每个点在第 ii 个阶段之后存储以它为左上角的边长 2i+32i+3 的棋盘信息, 显然不能直接存储每一位, 所以我们可以保存压缩后的结果. 我声称自己相信 41∗4141*41 的棋盘拓扑学不同胚的情况不会超过 21002^{100} 种.

其实还可以进一步压缩, 被完全包含的岛屿没有存储的必要, 所以可以直接记录对应的岛屿数量. 最多存在 841841 个岛屿, 所以每个点预留 11bit11bit 存储这个数量, 剩下的 89bit89bit 存压缩后的状态.

T2

这道题应该是耗时最短的吧. 一条边 (u,v)(u, v) 加入后能出现一个经过特殊点的环, 当且仅当存在一个特殊点 xx 使得 vv 能到 xx 且 xx 能到 uu. 因为显然对于特殊点, 如果一个点能到特殊点 ii, 那么它一定可以经过一开始就存在的那些边通往编号比 ii 大的所有特殊点, 因此每个点能到达的特殊点一定是特殊点的一个后缀, 所以每个点只要记录能到达的最小特殊点的编号 MnMn 即可. 同样地, 每个点还要维护能到达这个点的特殊点的最大编号 MxMx.

因为 MxMx 记录的是到达这个点的信息, 所以它沿着正向边有传递性, 而 MnMn 则是沿反向边有传递性的. 所以对于已经存在的边 (u,v)(u, v), 一定存在 Mnu≤MnvMn_u \leq Mn_v, Mxu≤MxvMx_u \leq Mx_v, 每次连边之后, 我们只要在正图中将 MxMx DFS 更新, 在反图中将 MnMn DFS 更新即可维护这两个值. 每次连边后如果 Mnv≤MxuMn_v \leq Mx_u, 则出现回路.

这样做的复杂度是 O(q(n+q))O(q(n + q)) 的, 因为每次连边都会进行 DFS.

但是因为每次 DFS 一个点的时候, 它的 MnMn 会减小或它的 MxMx 会增大, 所以复杂度还和 kk 有关, 每个点 DFS 的次数是 O(k)O(k) 的, 因此复杂度会变成 O(k(n+q))O(k(n + q)), 可以拿到 60′60'.

下面是 60′60' 的代码:

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 "game.h"
#include <vector>
#include <cstdio>
using namespace std;
unsigned Flg(0);
struct Node {
  vector<Node*> P, N;
  int Mx, Mn;
  inline void DFS1();
  inline void DFS2();
}a[300005];
vector<Node*> Cole;
unsigned K;
inline void Node::DFS1(){
  for (auto i:N) if(i->Mn > Mn) i->Mn = Mn, i->DFS1();
}
inline void Node::DFS2(){
  for (auto i:P) if(i->Mx < Mx) i->Mx = Mx, i->DFS2();
}
void init(int n, int k) {
  K = k;
  for (unsigned i(k); i < n; ++i) a[i].Mn = 0x3f3f3f3f, a[i].Mx = 0xafafafaf;
}
int add_teleporter(int u, int v) {
  // printf("Add %u - %u\n", u, v);
  if(u == v) return u < K;
  if(u < K && v < K) {
    if(u > v) Flg = 1;
    return Flg;
  }
  if(u < K) {
    a[v].Mx = max(u, a[v].Mx), a[v].DFS2();
    return a[v].Mn <= a[v].Mx;
  }
  if(v < K) {
    a[u].Mn = min(v, a[u].Mn), a[u].DFS1();
    return a[u].Mn <= a[u].Mx;
  }
  a[v].N.push_back(a + u);
  a[u].P.push_back(a + v);
  a[u].DFS2(), a[v].DFS1();
  return a[u].Mx >= a[v].Mn;
}
//-DEVAL -std=gnu++17 -O2 -pipe -static -s -o game stub.cpp game.cpp

T3

这个题意比较简单, 就是构造一个尽可能短的排列, 使它本质不同的上升子序列数量恰好为给定的 kk.

前 10′10' 要求的是线性长度即可, 如果我们有一个单调下降的长为 nn 的排列, 那么它的上升子序列有 n+1n + 1 个, 其中有一个空序列, 还有 nn 个长度为 11 的序列. 因此对于 kk, 我们只要构造长度为 k−1k - 1 的单调递减排列即可.

接下来就可以考虑倍增构造了, 一个长度为 nn 的单调递增排列有 2n2^n 个子序列, 它们都是单增的, 如果我们可以把一些这样的序列合并起来, 那么就可以在 O(log⁡2)O(\log^2) 的长度内构造出我们需要的排列了.

现在我们先不考虑空序列, 因为无论如何构造排列, 都存在一个空序列, 因此把 kk 减 11 然后考虑非空上升子序列数量即可. 如果不考虑空序列, 那么我们可以通过把两个排列拼起来得到一个单调递增子序列数量为两者之和的新排列, 具体方法是对于两个长度为 n1n_1, n2n_2 的排列, 我们把长为 n1n_1 的排列中每个元素增加 n2n_2, 然后把长为 n2n_2 的排列放到长度为 n1n_1 的排列后面.

这样合并的原理是对于合并后的排列, 可以以 n1n_1 位置为界, 大于等于 n1n_1 的位置都比小于 n1n_1 的位置上的元素小, 因此它的上升子序列不可能同时包含小于 n1n_1 的元素和不小于 n1n_1 的元素, 因此它的上升子序列和原来两个排列的上升子序列一一对应.

但是因为不计空序列, 所以长度为 nn 的上升排列的非空上升子序列是 2n−12^n - 1, 一开始想的是在每个上升排列后面加一个长为 11 的排列, 共同组成一个有 2n2^n 个上升子序列的模块, 但是因为合并的每个排列是可交换的, 所以我们可以先按 2n2^n 来计算, 然后统计一共少了多少子序列, 然后一并插入对应数量的长为 11 的序列来抹零. 最终长度的复杂度为 O(log⁡2k)O(\log^2 k).

但是显然在 log⁡k\log k 比较多的时候这样做是十分愚蠢的, 因此对于这个 O(log⁡k)O(\log k) 的尾巴, 我们可以递归在后面再构造一个对应数量的排列即可, 递归边界是 k=1k = 1, 直接构造长度为 11 的排列即可. 每层递归 kk 最多变成 log⁡k\log k, 因此层数为 O(α(k))O(\alpha (k)), 每层合并 O(log⁡k)O(\log k) 个长度 O(log⁡k)O(\log k) 的排列, 因此总长度的一个比较松的复杂度为 O(log⁡2kα(k))O(\log^2 k\alpha(k)), 不过显然真正的复杂度比这个要小得多, 可以认为是 O(log⁡2k)O(\log^2 k), 但是没有那么容易证.

下面这份代码可以得到 65.26′65.26':

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
#include "perm.h"
#include<vector>
#include<cstdio>
using namespace std;
inline unsigned Solve (vector<int> &x, long long k, unsigned Beg) {
  // printf("Solve %lld\n", k);
  if(k == 1) { x.push_back(0); return 1;}
  unsigned a[70], Cur(0), Cnt(0), Last(0);
  while (k) a[Cur] = (k & 1), ++Cur, k >>= 1;
  for (unsigned i(0); i < Cur; ++i) if(a[i]) Cnt += i, ++Last;
  // printf("Cnt %u\n", Cnt);
  unsigned Top(Cnt - 1);
  for (unsigned i(1); i < Cur; ++i) if(a[i]) {
    unsigned CR(Top - i + 1);
    for(unsigned j(0); j < i; ++j) x.push_back(CR++);
    Top -= i;
  }
  Last = Solve(x, Last, Beg + Cnt);
  for (unsigned i(0); i < Cnt; ++i) x[Beg + i] += Last;
  return Cnt += Last;
}
std::vector<int> construct_permutation(long long k) {
	vector<int> Rt;
  Solve(Rt, k - 1, 0);
  // for (auto i:Rt) printf("%u ", i); putchar(0x0A);
  return Rt;
}
//10000
//01100
//g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o perm grader.cpp perm.cpp

然后我们发现, 对于这种合并式的构造, 其实还有更高明的方法: 把所有 2n−12^n - 1 从小到大排序, 然后倒序枚举, 只要 k≥2i−1k \geq 2^i - 1, 就将一个长为 ii 的上升排列加入构造中, 然后把 kk 减少 2i−12^i - 1, 否则就将 ii 减 11, 这样是更加先进的 O(log⁡2k)O(\log^2 k) 做法, 复杂度不变, 但是可以拿到 71.2′71.2'.

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
#include "perm.h"
#include<vector>
#include<cstdio>
using namespace std;
long long List[70];
std::vector<int> construct_permutation(long long k) {
	vector<int> Rt, Rev;
  int Cnt(0);
  List[0] = 1, --k;
  for(unsigned i(1); i < 64; ++i) List[i] = List[i - 1] << 1;
  for(unsigned i(0); i < 64; ++i) --List[i];
  // for(unsigned i(0); i < 64; ++i) printf("%u %lld\n", i, List[i]);
  for(unsigned i(63); i; --i) {
    while (k >= List[i]) {
      // printf("k %lld List %lld Cnt %d i %u\n", k, List[i], Cnt, i);
      k -= List[i];
      // printf("k Bec %lld\n", k);
      for (int j(Cnt + i - 1); j >= Cnt; --j) /*printf("j %d\n", j),*/ Rev.push_back(j);
      Cnt += i;
      // printf("Done Add %d\n", Cnt);
    }
  }
  // printf("Size %d\n", Rev.size());
  for (unsigned i(Rev.size() - 1); ~i; --i) Rt.push_back(Rev[i]);
  // for (auto i:Rt) printf("%u ", i); putchar(0x0A);
  return Rt;
}
//10000
//01100
//g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o perm grader.cpp perm.cpp

如果想做到 O(log⁡k)O(\log k), 肯定不能是 O(log⁡k)O(\log k) 个排列合并起来. 现在重新考虑空序列.

如果一个含有 xx 个上升子序列的排列全部元素加 11, 然后在后面加一个 00 作为新元素, 那么这个新排列将存在 x+1x + 1 个上升子序列, 这 x+1x + 1 个子序列中有 xx 个是原排列就存在的, 第 x+1x + 1 个子序列是仅包含 00 的子序列. 而只要一个子序列包含 00, 那么它便不能再包含任何其它元素了, 因为其它元素都比 00 大且在 00 前面.

如果一个含有 xx 个上升子序列的排列全部元素加 11, 然后在前面加一个 00 作为新元素, 那么这个新排列将存在 2x2x 个上升子序列, 这 2x2x 个子序列中有 xx 个是原排列就存在的, 后 xx 个子序列是在原来存在的子序列的基础上, 在前面加一个 00 得到的. 因为 00 比任何元素都小, 而且最靠左, 所以 00 后面加一个上升子序列还是一个上升子序列.

所以我们可以只增加一个元素就可以实现将原排列的上升子序列数量倍增或者加 11, 所以可以直接根据 kk 的二进制情况进行操作. 初始上升子序列数量可以是 22 或 33, 也就是长度为 11 或 22 的下降子序列, 不存在上升子序列为 11 的非空排列. 接下来, 我们从高到低扫描 kk 的二进制表示, 如果遇到 00, 那么直接倍增上升子序列数量, 否则就先倍增, 然后加 11.

如果 kk 的二进制表示长度为 aa, 并且有 bb 个 11, 那么我们构造的序列长度就是 a+b−1a + b - 1, 因为 aa 和 bb 都是 log⁡k\log k 级别的, 所以构造的排列长度是 O(log⁡k)O(\log k) 的.

这份代码得到了 91.36′91.36':

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
#include "perm.h"
#include<vector>
#include<cstdio>
using namespace std;
long long List[70];
unsigned a[205], L(100), R(99), Mx(200);
inline void Pb() {/*printf("Pb %u", Mx - 1), */a[++R] = --Mx;}
inline void Pf() {/*printf("Pf %u", Mx - 1), */a[--L] = --Mx;}
std::vector<int> construct_permutation(long long k) {
	vector<int> Rt;
  unsigned b[70], Cur(0);
  L = 100, R = 99, Mx = 200;
  while (k) b[Cur] = (k & 1), k >>= 1, ++Cur; --Cur;
  // printf("Cur %u\n", Cur);
  Pb();
  if(b[Cur - 1]) Pb();
  for (unsigned i(Cur - 2); ~i; --i) {Pf(); if(b[i]) Pb();}
  for (unsigned i(L); i <= R; ++i) Rt.push_back(a[i] - Mx);
  // for (auto i:Rt) printf("%u ", i); putchar(0x0A);
  return Rt;
}
//1000000000000000000
//10000
//01100
//g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o perm grader.cpp perm.cpp
//71.2

总结

总分 0+60+91.36=151.360 + 60 + 91.36 = 151.36, 貌似略低于大众分 14+60+91.36=165.3614 + 60 + 91.36 = 165.36, 不过感觉 Cu 应该是有的. 今年的题目比去年的简单, 所以线一定比去年高.

事后回顾: 线下的线普遍比线上高, 这说明互联网也弥补不了实力的差距, 而线下银牌正如我认为的大众分: 165.36165.36, 而我以 1414 分的差距没拿到银牌, 这 14′14' 的来源就是 T1 的暴力存图.