「考试总结」ZROI-21-NOIP冲刺-TEST2 总结

发表于 分类于
ZROI-21-NOIP冲刺-TEST2 总结

#T1 幻方

#题意简述

给定⼀个 \(3\times 3\) 矩阵，矩阵中恰好有 \(1-9\) 这 \(9\) 个整数。 你可以进⾏若⼲次操作，每次操作交换其中相邻的两个数，操作完后使得：

  • 矩阵每⼀⾏的和为 \(15\)；
  • 矩阵每⼀列的和为 \(15\)；
  • 矩阵两条对⻆线的和为 \(15\)；

问最少需要⼏次操作。多组数据，\(T\leq50\).

#大体思路

合法的情况很少，只有 \(8\) 种，而所有的状态只有 \(9!=362880\) 种，每次变换只有 \(12\) 种，直接 BFS 即可，注意需要记忆化，所以需要写 Hash 表。时间复杂度 \(O(T\cdot9!)\).

#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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 500010;
const int M = 3000010;
const int MOD = 2908361;
const ll std_block[8] = {
    276951438, 294753618, 438951276, 492357816,
    618753294, 672159834, 816357492, 834159672,
};

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;
}

struct Status {ll val; int cnt;};
struct Hash {
    int head[M], nxt[N], cnt, val[N];

    inline void init() {cnt = 0; mset(head, 0);}
    inline void insert(ll x) {
        int H = x % MOD; val[++ cnt] = x;
        nxt[cnt] = head[H], head[H] = cnt;
    }

    inline int find(ll x) {
        int H = x % MOD;
        for (int i = head[H]; i; i = nxt[i])
          if (val[i] == x) return i;
        return -1;
    }
} hsh;

int t, T, vis[N]; ll p[11];

inline ll change(ll x, int op) {
    int p1 = 0, p2 = 0;
    if (op == 1) p1 = 1, p2 = 2; else if (op == 2) p1 = 2, p2 = 3;
    else if (op == 3) p1 = 1, p2 = 4; else if (op == 4) p1 = 2, p2 = 5;
    else if (op == 5) p1 = 3, p2 = 6; else if (op == 6) p1 = 4, p2 = 5;
    else if (op == 7) p1 = 5, p2 = 6; else if (op == 8) p1 = 4, p2 = 7;
    else if (op == 9) p1 = 5, p2 = 8; else if (op == 10) p1 = 6, p2 = 9;
    else if (op == 11) p1 = 7, p2 = 8; else if (op == 12) p1 = 8, p2 = 9;
    int n1 = x % p[p1] / p[p1 - 1], n2 = x % p[p2] / p[p2 - 1];
    x -= n1 * p[p1 - 1] + n2 * p[p2 - 1];
    x += n1 * p[p2 - 1] + n2 * p[p1 - 1];
    return x;
}

Status q[N]; int frt, tal, a[N];

inline void prework() {
    for (int i = 1; i <= 9; ++ i) a[i] = i;
    for (int i = 1; i <= 362880 - 1; ++ i) {
        ll val = 0;
        for (int j = 1; j <= 9; ++ j)
          val *= 10, val += a[j];
        hsh.insert(val);
        next_permutation(a + 1, a + 9 + 1);
    }
}

int bfs(ll st) {
    frt = 0, tal = -1; q[++ tal] = (Status){st, 0};
    while (frt <= tal) {
        ll now = q[frt].val; int sp = q[frt ++].cnt;
        if (vis[hsh.find(now)] == -1) return sp;
        for (int i = 1; i <= 12; ++ i) {
            ll ns = change(now, i), hns = hsh.find(ns);
            if (vis[hns] == -1) return sp + 1;
            if (vis[hns] != T) {
                q[++ tal] = (Status){ns, sp + 1};
                vis[hns] = T;
            }
        }
    }
    return -1;
}

int main() {
    hsh.init(); p[0] = 1; read(t); prework();
    for (int i = 1; i <= 10; ++ i)
      p[i] = p[i - 1] * 10;
    for (int i = 0; i <= 7; ++ i)
      vis[hsh.find(std_block[i])] = -1;
    for (T = 1; T <= t; ++ T) {
        ll x = 0, y = 0;
        for (int i = 0; i <= 8; ++ i)
          read(y), x = x * 10 + y;
        printf("%d\n", bfs(x));
    }
    return 0;
}

#T2 数集

#题意简述

维护一个一开始为空的集合 \(S\)，有总共 \(q(q\leq2^{20})\) 次以下三种操作：

  • 加入一个数 \(x\)；
  • 询问 \(\max_{y\in S}x\text{ xor }y,\max_{y\in S}x\text{ and }y,\max_{y\in S}x\text{ or }y\)；
  • 询问 \(\max_{y\in S}x\text{ xor }y\)；

其中 \(x\leq2^{20}\).

#大体思路

最大异或和可以直接用 01 trie 维护，下面讨论 and/or 的维护。

  • 对于 \(\text{and}\)，显然我们希望自高到低位的 1 尽可能被选上；
  • 对于 \(\text{or}\)，显然我们希望自高到低位的 \(0\) 尽可能被补成 1；

再来考虑一个数 \(x\) 的贡献，显然它所有的子集都是可以通过选择 \(x\) 得到，于是每插入一个 \(x\) 就对它的子集进行标记，查询时按上面的思路进行贪心即可。

#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
const int N = 2000010;

int lg[N];

struct Node {int ch[2], val, s;};
struct Trie {
    Node p[N]; int rt, cnt;

    inline Trie() {rt = cnt = 0;}
    void insert(int x) {
        int now = rt;
        for (int i = 20; ~i; -- i) {
            int k = (x >> i) & 1;
            if (!p[now].ch[k])
              p[now].ch[k] = ++ cnt;
            now = p[now].ch[k];
        }
        p[now].val = x;
    }

    int query_xor(int x) {
        int now = rt;
        for (int i = 20; ~i; -- i) {
            int k = !((x >> i) & 1);
            if (!p[now].ch[k])
              now = p[now].ch[!k];
            else now = p[now].ch[k];
        }
        return p[now].val ^ x;
    }
} t;

int q, marked[1 << 20];

void mark(int x) {
    marked[x] = 1;
    for (int i = 19; ~i; -- i)
      if (x >> i & 1 && !marked[x ^ (1 << i)])
        mark(x ^ (1 << i));
}

int main() {
    scanf("%d", &q);
    while (q --) {
        int op, x; scanf("%d%d", &op, &x);
        if (op == 1) t.insert(x), mark(x);
        else if (op == 3) printf("%d\n", t.query_xor(x));
        else {
            printf("%d ", t.query_xor(x)); 
            int res1 = 0, res2 = 0;
            for (int i = 19; ~i; -- i)
              if (x >> i & 1 && marked[res1 | (1 << i)])
                res1 |= (1 << i);
            for (int i = 19; ~i; -- i)
              if (!(x >> i & 1) && marked[res2 | (1 << i)])
                res2 |= (1 << i);
            printf("%d %d\n", res1 & x, res2 | x);
        }
    }
    return 0;
}

#T3 染色

#题意简述

⼀棵 \(n(n\leq3\times10^5)\) 个点的树上有两个⿊点 ，其余都是⽩点。 接下来，每过⼀个单位时间，树上的每个⿊点可以选择⼀个它相邻的点染⿊。 请问，在最优策略的情况下，⾄少要经过多少个单位时间，才能把整棵树染⿊。

#大体思路

显然最优策略是所需时间最长的子树尽可能先选，我们可以在原树上二分，将原树分为两棵树，尽可能让分出来的答案接近一定是最优的。

#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
72
73
74
75
76
77
78
79
80
81
82
83
84
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

const int N = 300010;
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 << 1];

int n, a, b, head[N], ecnt(2), pre[N], op = 1;
int g[N], pass[N], pcnt, f[N], gcnt, tag;

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_path(int x, int fa) {
    if (x == b) {op = 0; return;}
    for (int i = head[x]; i && op; i = e[i].nxt) {
        if (e[i].v == fa) continue;
        pre[e[i].v] = i, get_path(e[i].v, x);
    }
}

inline void connect() {
    get_path(a, 0); int now = b;
    while (e[pre[now]].u != a)
      pass[++ pcnt] = pre[now], now = e[pre[now]].u;
   pass[++ pcnt] = pre[now];
   reverse(pass + 1, pass + pcnt + 1);
}

inline bool cmp(int a, int b) {return a > b;}

void dp(int x, int fa) {
    f[x] = 0;
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].v != fa && i != tag && (i ^ 1) != tag)
        dp(e[i].v, x);
    gcnt = 0;
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].v != fa && i != tag && (i ^ 1) != tag)
        g[++ gcnt] = f[e[i].v];
    if (!gcnt) return; sort(g + 1, g + gcnt + 1, cmp);
    for (int i = 1; i <= gcnt; ++ i)
      f[x] = Max(f[x], g[i] + i);
}

inline pii solve(int x) {
    tag = pass[x]; dp(a, 0), dp(b, 0);
    return make_pair(f[a], f[b]);
}

inline bool check(pii x) {return x.first <= x.second;}

int main() {
    read(n), read(a), read(b);
    for (int i = 1; i < n; ++ i) {
        int u, v; read(u), read(v);
        add_edge(u, v), add_edge(v, u);
    }
    connect();
    int l = 1, r = pcnt, ans = 1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(solve(mid)))
          l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    pii ans1 = solve(ans), ans2 = mp(-INF, INF);
    if (ans + 1 <= pcnt) ans2 = solve(ans + 1);
    ans = Min(Max(ans1.first, ans1.second), Max(ans2.first, ans2.second));
    printf("%d", ans); return 0;
}

#T4 电路板

因为临近考试，但涉及到了新的科技，就先咕咕咕罢