「考试总结」ZROI-21-CSP7连-DAY6 总结

发表于 更新于 分类于
ZROI-21-CSP7连-DAY6 总结

#T1 聚会

#题意简述

给定一个长度为 \(n(n\leq5\times10^5)\) 的 01 串，一个位置 \(x\) 的价值为 \(x\) 到离它最近 1 的距离，问价值和。多组数据。

#大体思路

从两个方向分别扫一遍即可。

#Code

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
#define ll long long

const int N = 5e5;
const ll INF = 1e12;

char s[N];
int t, n, a[N]; ll f[N], ans;

int main() {
    scanf("%d", &t);
    for (int i = 1; i <= t; ++ i) {
        printf("Case #%d: ", i);
        memset(f, 0x3f, sizeof(f));
        scanf("%d%s", &n, s); ans = 0;
        for (int i = 0; i < n; ++ i)
          a[i + 1] = s[i] - '0';
        ll lst = -INF;
        for (int i = 1; i <= n; ++ i) {
            if (a[i]) lst = i;
            f[i] = min(f[i], (ll)i - lst);
        }
        lst = INF;
        for (int i = n; i >= 1; -- i) {
            if (a[i]) lst = i;
            f[i] = min(f[i], lst - (ll)i);
        }
        for (int i = 1; i <= n; ++ i)
          ans += f[i];
        printf("%lld\n", ans);
    }
    return 0;
}

#T2 跳房子

#题意简述

一个长为 \(n(n\leq1000)\) 的严格递增的序列 \(\{x_i\}(x_i\leq10^{18})\)，当且仅当 \(i<j\) 且 \(x_i|x_j\) 时由 \(i\) 向 \(j\) 连边，得到一个有向无环图，每条边边可以染成三种不同的颜色，要求不允许出现连续的长度大于 \(3\) 的相同颜色的边出现，输出染色方案。

#大体思路

定义函数 \(f(x)\)，有 \(2^{f(x)}\leq x<2^{f(x)+1}\)，按如下方式进行染色：

  • 如果有 \(\left\lfloor\dfrac {f(x_i)} 4\right\rfloor=\left\lfloor\dfrac {f(x_j)} 4\right\rfloor\)，那么将 \(i\to j\) 标为 \(1\)；
  • 如果有 \(\left\lfloor\dfrac {f(x_i)} {16}\right\rfloor=\left\lfloor\dfrac {f(x_j)} {16}\right\rfloor\)，那么将 \(i\to j\) 标为 \(2\)；
  • 其余的标为 \(3\)。

正确性从二进制考虑，显然这样分，就是每四位分为一小组，每四小组分为一大组，总共 \(4\) 大组，每一小组内的最长路径经过不超过 \(4\) 个点，同样的，最长的、将四个大组全部相连的路径长度不超过 \(3\)。

#Code

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
#define ll long long

const int N = 1000010;
const int M = 1010;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

ll n, f[N], x[N];

inline int calc(int a, int b) {
    if (f[a] / 4 == f[b] / 4) return 1;
    else if (f[a] / 16 == f[b] / 16) return 2;
    else return 3;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++ i) read(x[i]);
    for (int i = 1; i <= n; ++ i) {
        f[i] = f[i - 1];
        while ((1ll << f[i]) <= x[i]) ++ f[i];
        -- f[i];
    }
    for (int i = 2; i <= n; ++ i) {
        for (int j = 1; j < i; ++ j)
          printf("%d ", calc(j, i));
        puts("");
    }
    return 0;
}

#T3 人结

#题意简述

圆上有 \(n(3\leq n\leq500)\) 个点，顺时针编号为 \(1,2,\dots,n\)，每个点与两个点相连，要求通过移动点在圆上的位置，使得最终的边没有交叉的一个环。

#大体思路

注意到当且仅当原图不联通时无解；而当有解时最终得到的环的形态是唯一的，又注意到操作的可逆性，于是转化为将一个 \(n\)-排列环变成顺时针方向为 \(1,2,\dots,n\) 的环。

考虑复制一遍断环为链，然后为保证次数最少，一定是一次就把一个不在自己位置上的数放到自己位置上，于是就变为在 \(2n\) 长度的序列上选中长度为 \(n\) 的段，求这一段的最长上升子序列长度，取最大值即可。

由于不能保证最开始得到的环是顺时针方向，所以需要反转后在求一遍。时间复杂度 \(O(n^2\log n)\).

#Code

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
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 1010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T &a, T &b) {return a > b ? a : b;}
template <typename T> inline T Min(T &a, T &b) {return a < b ? a : b;}

struct Edge {int u, v, nxt;} e[N];

int n, a[N], head[N], ecnt(1), vis[N], tot, ans;

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

void get_ring(int x) {
    vis[x] = true; a[++ tot] = x; 
    for (int i = head[x]; i; i = e[i].nxt)
      if (!vis[e[i].v]) get_ring(e[i].v);
}

#define lb(t, l, x) lower_bound(t + 1, t + l + 1, x)

void get_ans() {
    int f[N], st[N], stp; 
    for (int i = 1; i <= n; ++ i) a[i + n] = a[i];
    for (int i = 1; i <= n; ++ i) {
        mset(f, 0); mset(st, 0); stp = 0;
        for (int j = i; j <= i + n - 1; ++ j) {
            if (a[j] > st[stp]) st[++ stp] = a[j];
            else {
                int pos = lb(st, stp, a[j]) - st;
                st[pos] = a[j];
            }
            f[j - i + 1] = stp;
        }
        ans = Max(ans, f[n]);
    }
}

int main() {
    while (1) {
        read(n); if (!n) break;
        mset(head, 0); ecnt = 1, tot = ans = 0;
        for (int i = 1; i <= n; ++ i) {
            int x, y; read(x), read(y);
            add_edge(i, x); add_edge(i, y);
        }
        mset(vis, 0); mset(a, 0); get_ring(1);
        if (tot != n) {printf("Not solvable.\n"); continue;}
        else printf("Knot solvable.\n");
        get_ans(); reverse(a + 2, a + n + 1);
        get_ans(); printf("%d\n", n - ans);
    }
    return 0;
}

#T4 辣椒

#题意简述

将一棵 \(n(n\leq2\times10^5)\) 个点的树通过断掉两条边变为三部分，定义差值为三部分中的最大大小减去最小大小，求最小差值。

#大体思路

先来考虑 \(O(n^2)\) 做法，即枚举两个点 \(x,y\)，表示将这两个点向父亲的边断掉，则三部分的大小有以下两种情况（记 \(siz_x\) 为以 \(x\) 为根的子树大小）：

  • \(y\) 是 \(x\) 的祖先，那么大小分别为 \(siz_x,siz_y-siz_x,n-siz_y\)；
  • \(y\) 与 \(x\) 无祖孙关系，那么大小分别为 \(siz_x,siz_y,n-siz_x-siz_y\)；

直接进行维护即可。

来考虑优化，假如当前选择的点为 \(x\)，那么考虑从根到 \(x\) 路径上的点，需要在其中找到一个点 \(x\) 使得 \(|siz_y-\dfrac{n+siz_x}2|\) 最小，这个点集可以用 set 维护，然后直接 lower_bound() 查找即可，当从某个点向下深入时需要将该点加入该集合；

同样的，维护一个已经处理过但不是 \(x\) 的祖先的点集，需要在其中找到一个点 \(y\) 使得 \(|siz_y-\dfrac{n-siz_x}2|\) 尽可能小，同样可用 set 维护，注意当从一个点退出时，需要将该点从直系集合中取出，加入旁系集合。

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

#Code

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
69
70
71
const int N = 500010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T abs(T &x) {return x < 0 ? -x : x;}
template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}
template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

struct Edge {int u, v, nxt;} e[N];

int n, head[N], ecnt(1), siz[N], ans = INF;

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

inline int calc(int x, int y, int z) {
    return Max(x, Max(y, z)) - Min(x, Min(y, z));
}

void get_size(int x, int f) {
    siz[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == f) continue;
        get_size(e[i].v, x);
        siz[x] += siz[e[i].v];
    }
}

set <int> lineal, colla, neg_lineal, neg_colla;

void solve(int x, int f) {
    if (!lineal.empty()) {
        int pos = *lineal.lower_bound((n + siz[x]) / 2);
        ans = Min(ans, calc(n - pos, siz[x], pos - siz[x]));
    }
    if (!colla.empty()) {
        int pos = *colla.lower_bound((n - siz[x]) / 2);
        ans = Min(ans, calc(siz[x], pos, n - siz[x] - pos));
    }
    if (!neg_lineal.empty()) {
        int pos = -(*neg_lineal.lower_bound(-(n + siz[x]) / 2));
        ans = Min(ans, calc(n - pos, siz[x], pos - siz[x]));
    }
    if (!neg_colla.empty()) {
        int pos = -(*neg_colla.lower_bound(-(n - siz[x]) / 2));
        ans = Min(ans, calc(siz[x], pos, n - siz[x] - pos));
    }
    lineal.insert(siz[x]); neg_lineal.insert(-siz[x]);
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].v != f) solve(e[i].v, x);
    lineal.erase(siz[x]); neg_lineal.erase(-siz[x]);
    colla.insert(siz[x]); neg_colla.insert(-siz[x]);
}

int main() {
    read(n);
    for (int i = 1; i < n; ++ i) {
        int u, v; read(u), read(v);
        add_edge(u, v); add_edge(v, u);
    }
    get_size(1, 0); solve(1, 0);
    printf("%d", ans); return 0;
}