剑锋所指,心之所向。

edu30 场 c2e 第 5 场。

时间很合适,现场参加了,结果被 C 搞自闭了。

AC A, B, D,rk 3000+,罚时恐怖,竟然还涨了分(

C1 - Simple Polygon Embedding

求边长为 1 的正 2n\ (2 | n) 边形最小外接正方形边长。

外接正方形指,正 2n 边形的每一个顶点,都在该正方形边上或内部。


可以证明,最短边长为中心到边的距离。

答案即为 \cot \dfrac{\pi}{2n}

from math import *

pi = acos(-1)

if __name__ == "__main__":
    t = int(input())
    while t >= 1:
        n = int(input())
        print(1 / (tan(pi / (2 * n))))
        t = t - 1

C2 - Not So Simple Polygon Embedding

题目如上,2 \not|\ n

可以证明,最小距离为,当正 2n 边形的最下边与正方形平行时,将其旋转 (\dfrac{90}{n})\degree 后,其到靠左的顶点即为最小边长。答案即为 \dfrac{\cos(\frac{\pi}{4n})}{\sin(\frac{\pi}{2n})}

D - Multiset

维护一个集合,支持删除第 k 大,插入数 a\ (a \leq 10^6)。输出操作完之后的集合中的任意一个数。

m \leq 10^6


值域较小,考虑对值域建 BIT,维护每个值的元素个数。这样可以在 O(\log n) 的时间内查询某个数的 rk。

对于删除操作,二分找到第 k 大。

最后任意找一个数即可。

时间复杂度 O(n \log^2 n)

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

const int MAXN = 1e6 + 10;

int n, q;

struct BIT {
    int bit[MAXN];
    void add(int x, int val) { for (; x <= n; x += (x & -x)) bit[x] += val; }
    int sum(int x) { int ret = 0; for (; x; x -= (x & -x)) ret += bit[x]; return ret; }
} t;

void opt1(int k) {
    t.add(k, 1);
}

void opt2(int k) {
    int l = 1, r = n, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (t.sum(mid) >= k) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    t.add(ans, -1);
}

int work() {
    for (int i = 1; i <= n; ++i) {
        if (t.sum(i) - t.sum(i - 1) > 0) {
            return i;
        }
    }
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        t.add(x, 1);
    }
    for (int i = 1, k; i <= q; ++i) {
        scanf("%d", &k);
        if (k >= 1) opt1(k);
        else opt2(-k);
    }
    if (t.sum(n) == 0) { puts("0"); return 0; }
    printf("%d\n", work());
    return 0;
}

不过 BIT 是可以做到 O(n \log n),可以参考论文鸽的代码

除了 BIT 外,还有一种直接二分的做法。

二分最后的那个值,check 最后集合中是否有 \geq 0 个数在他左边即可。这样我们一定能二分到最小的值。

时间复杂度 O(n \log n)

E - Graph Coloring

n\ (n \leq 5000) 个点的图,要求给每个点一个权值 a\ (a \in \{1, 2, 3\}),使得对于 (u, v) \in V,均有 |u_a - v_a| = 1,且恰有 n1, n2, n3 个点,其权值为 1, 2, 3。判断是否存在,并求出一种合法的方案。


很有意思的题。

首先,对于合法的方案,所有权值为 1, 3 的点,与权值为 2 的点,构成一个二分图。

其次,对于合法方案中权值为 1, 3 的点,其值可以任意调换而不影响正确性。

那么我们对于每一个连通块,都通过 dfs 判断是否为二分图,这是存在答案的必要条件。

之后,考虑如何将这 k 个连通块分配权值。具体而言,对于每一个连通块,要么将其左部赋为 2,右部赋为 1, 3,要么反过来。

考虑背包,f(i, j)\text{True} 表示存在一种合法方案,使得前 i 个连通块,有 j 个点的权值为 2。转移显然为:

f(i, j) = f(i, j) \operatorname{or} f(i - 1, j - a_i) \operatorname{or} f(i - 1, j - b_i)

其中,a_i, b_i 分别表示第 i 个连通块的左部,右部大小。

转移时记录从哪里来即可求得答案。

时间复杂度 O(n^2)

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

const int MAXN = 5000 + 10;

int n, m, n1, n2, n3, ans[MAXN];

int cnt, col[MAXN];
vector<int> G[MAXN], cc[MAXN], cl[MAXN][2];

bool is_ok = true;
void dfs(int u) {
    if (!is_ok) return ;
    if (!col[u]) col[u] = 1;
    cc[cnt].push_back(u), cl[cnt][col[u] - 1].push_back(u);
    for (auto v : G[u]) {
        if (!col[v]) {
            col[v] = 3 - col[u], dfs(v);
        } else {
            if (col[v] != 3 - col[u]) {
                is_ok = false;
                return ;
            } else continue;
        }
    }
}

int f[MAXN][MAXN], pre[MAXN][MAXN];

int main() {
    scanf("%d %d %d %d %d", &n, &m, &n1, &n2, &n3);
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!col[i]) {
            is_ok = true;
            ++cnt;
            dfs(i);
            if (!is_ok) { puts("NO"); return 0; }
        }
    }
    f[0][0] = 1;
    /*
    for (int i = 1; i <= cnt; ++i) {
        printf("cc %d::\n", i);
        for (auto u : cl[i][0]) printf("%d ", u);
        puts("");
        for (auto u : cl[i][1]) printf("%d ", u);
        puts("");
    }
    */
    for (int i = 1; i <= cnt; ++i) {
        for (int j = cl[i][0].size(); j <= n; ++j) {
            if (f[i - 1][j - cl[i][0].size()]) {
                f[i][j] = 1, pre[i][j] = 1;
            }
        }
        for (int j = cl[i][1].size(); j <= n; ++j) {
            if (f[i - 1][j - cl[i][1].size()]) {
                f[i][j] = 1, pre[i][j] = 2;
            }
        }
    }
    if (!f[cnt][n2]) { puts("NO"); return 0; }
    puts("YES");
    for (int i = cnt, cur = n2; i >= 1; --i) {
        // printf("-- %d %d %d--\n", i, cur, pre[i][cur]);
        for (auto u : cc[i]) {
            // printf("u : %d\n", u);
            if (col[u] == pre[i][cur]) ans[u] = 2;
            else {
                if (n1 >= 1) n1--, ans[u] = 1;
                else ans[u] = 3;
            }
        }
        cur -= cl[i][pre[i][cur] - 1].size();
    }
    for (int i = 1; i <= n; ++i) printf("%d", ans[i]);
    return 0;
}

总结

  • D 刚上去了

  • 罚时太高,交之前应该再检查一下

OI-数据结构-树状数组 OI-二分答案 OI-计算集合 OI-图论-二分图

CWOI 6-6 提高练习赛 2 测试题解与总结
上一篇 «
斜率优化学习笔记
» 下一篇