Background

最近点对问题:给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。

一个广为人知的随机做法是这样的:

我们充分发扬人类智慧:
将所有点全部绕原点旋转同一个角度,然后按 $x$ 坐标排序
根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 $5$ 个点来计算答案
这样速度快得飞起,在 $n=1000000$ 时都可以在 1 s 内卡过

——P1429 平面最近点对(加强版)最高赞题解。

当然,上面这个声称看起来就不对——因为随一次失败概率显然可能很大。之前也有传言这个有类似根号的正确性下界保证,然后我暑假整理模板的时候也相信了这一点,不过,仔细想起来,这是不对的!

当然,不对得并不是很明显,我先和 Chihao 讨论得出了一个构造方法,然后在几何画板上画出来后,发现角度存在非常牛逼的等角关系,交给几何大师证明了一下发现显然对;之后,路过的毛哥哥一语中的,发现构造的点就在一个圆上,然后就发现这个题性质更美妙了。

因此我就出了这个题,放在了 IEEE 21 算法课第一次上机作业的附加题里:

Continue reading

以后再卡构造我是狗

1227G. Not Same

给定 $n$ 个 $[1, n]$ 的数,要求操作至多 $n + 1$ 次数,每次操作将一个独特的下标集合的数减一,要求将所有数变成 $0$。

1110G. Tree-Tac-Toe

给一个树,树上有些点染了先手的颜色,其余点没染色。现在先后手轮流给没染色的点染黑白,如果某种颜色形成了一个大小不小于 3 的同色联通块则立刻获胜,如果染满了则平局。问最优策略下的游戏结果。




spolier 烂掉了,手动分割线




Solutions

Sol 1227G

我尝试的第一种构造是:第 $i$ 次操作强制删 $i$,不删 $i \bmod n+ 1$。但是这样对于

5
5 1 1 1 1

的数据就解掉了,因为会在输出两行 1 0 0 0 0。后来改成了 $i – 1$ 才行,Tommy 证了,是真的。

#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n;
int a[N], b[N][N];
pair<int, int> c[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) c[i] = {a[i], i};
    sort(c + 1, c + n + 1);
    memset(b, -1, sizeof b);
    for (int i = 1; i <= n; i++) {
        a[c[i].second]--;
        b[i][c[i].second] = 1;
        b[i + 1][c[i].second] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; a[c[i].second] && j <= n + 1; j++) {
            if (b[j][c[i].second] == -1) b[j][c[i].second] = 1, a[c[i].second]--;
        }
    }
    bool flag = 0;
    for (int i = 1; i <= n; i++) flag |= b[n + 1][i] == 1;
    printf("%d\n", n + flag);
    for (int i = 1; i <= n + flag; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d", max(0, b[i][j]));
        }
        puts("");
    }
}

Sol 1110G

Tommy 太神啦!什么题都做过不愧是体重比我重 60 斤的 Tommmmmmmmmmmmy。 首先和井字棋相同,先手必不败,我不会直接证但是感受下外加后面的构造可以证明,我们先不考虑初始颜色,讨论如下:

  1. 存在度数为 4 的点,则先手必胜;
  2. 存在度数为 3 的点存在两个出度的度数不小于 2,则先手必胜。
  3. 存在两个距离为偶数的度数为 3 的点,则先手必胜,这一种情况可以看成 1 的拓展。
  4. 其余情况为平局,包括只有两个度数为 3 的距离为奇数的点以及链。

这么讨论很显然,我就差这么 一 点就想到第三个了,但是很可惜做不到。我是狗!

接下来还要处理有颜色的点,可以转化为:先手选择了这个点,那么后手必然要选择我新建的辅助节点。这其实可以通过外接一个根度数为 $2$ 的大小为 $3$ 的子树来做到。于是就做完了。

#include <bits/stdc++.h>
using namespace std;

#define N 2011111

int n, node;
vector <int> E[N];
char s[N / 4];
bool ans;
int dep[N];
bool vis[2];

void dfs(int x, int fa) {
    if (E[x].size() >= 4) ans = 1;
    else if (E[x].size() == 3) {
        int tot = 0;
        for (auto v : E[x]) tot += E[v].size() > 1;
        if (tot >= 2) ans = 1;
        if (vis[dep[x]]) ans = 1;
        vis[dep[x]] = 1;
    }
    for (auto v : E[x]) if (v != fa) dep[v] = dep[x] ^ 1, dfs(v, x);
}

void work() {
    scanf("%d", &n);
    node = n;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'W') {
            E[i].push_back(++node);
            E[node].push_back(i);
            node += 2;
            E[node - 2].push_back(node - 1);
            E[node - 1].push_back(node - 2);
            E[node - 2].push_back(node - 0);
            E[node - 0].push_back(node - 2);
        }
    }
    vis[0] = vis[1] = 0;
    ans = 0;
    dfs(1, -1);
    if (ans) puts("White");
    else puts("Draw");
    for (int i = 1; i <= node; i++) E[i].clear();
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) work();
}

不围棋(NoGo)是一种在 \(9 \times 9\) 的棋盘上进行的一种棋类游戏,游戏下子限制为禁止在棋盘上产生围棋中的吃子,最终无法行动的一方失败,另一方获得胜利。详见 Botzone 上的 NoGo。 = = 这个东西作为 AI 大作业就意味着要……爆肝……然后我把我的 Documentation 粘在下面了…… 还是挺高兴的,第一次写出了 UCT,打爆了上次想写却没写出好的五子棋 AI 的我。

Continue reading