2022.12.01杭州集训Day3 考试记录

2022秋 2022杭州集训

---

考场成绩：

T1	T2	T3	Sum
15	100	10	125

T1 Card

考点：???

用时：???

得分：$15pts$

Description

给定单调递增的序列 $A$，共有 $n$ 个数。$q$ 次询问，每次询问给定 $(x,y)$ 满足 $|x-y|\le 1$，两个人 $A,B$ 轮流取数，$A$ 取距离 $x$ 最近的未被去过的数，$B$ 取离 $y$ 最近的，直到取完。请求出 $A$ 取出数字之和。

$n\le 5\times 10^4,A_i< 2^{17},q<2^{18}$

Solution

我会双指针模拟！期望得分 $15pts$

T2 划分

考点：观察性质，缩点，树形DP

用时：???

得分：$100pts$

Description

给定 $n$ 个结点的树，$m$ 种颜色，点有颜色或无色。你需要找到一种划分方案使得每种颜色恰好只出现在同一种连通块中。求方案数，保证存在合法方案。

$n,m\le 3\times 10^5$。

Solution

观察一些性质，由于每个连通块恰好只有一种颜色

所以我们可以对于每种颜色，找到把该颜色所有点包含的最小联通块，容易发现如果有解，则这些连通块互不相交。

我们把这些连通块缩起来，就形成了 $m$ 个有颜色的点以及不再任何一个结合的无颜色点的树。

考虑树形DP求方案，我们要做的是把那些无颜色点分进各个集合中，设：$f[i][0/1]$ 表示第 $i$ 个点在 他的子树/他的祖先集合中的答案。

分类讨论一下：

$col[x] = 0$：

$$f[x][0] = \prod_{y}{(f[y][0] + f[y][1])}$$

$$f[x][1] = \sum_{y_0}{\frac{f[y][1]\times f[x][0]}{f[y][0] + f[y][1]}}$$

$col[x] = 1$

显然不存在 $f[x][0]$

$$f[x][1] = \prod_{y}{(f[y][0] + f[y][1])}$$

然后简述一下缩连通块的方式：

我们把点按颜色分类，把他们拉成序列，然后维护前缀的LCA，每次加入一个点，让之前的LCA和当前点暴力向上跳，注意：跳到相同颜色的点即可提前结束。

这样就可以知道哪些点要被染色，此题解决。

Summary

性质很好观察，DP也很基础。

一道码量较大的签到题。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 5 * 1e5 + 5, mod = 998244353;
int n, K;
int a[maxn], Dep[maxn], Father[maxn][25], Top[maxn], f[maxn][2];
vector <int> Col[maxn];
unordered_map <int, int> mapp[maxn];
struct Map {
    struct node {
        int v, nex;
    }edge[maxn << 1];
    int head[maxn], len;
    inline void make_map(int u, int v) {
        len++;
        edge[len].nex = head[u];
        edge[len].v = v;
        head[u] = len;
    }
}Edge, Tree;
inline int Ksm(int A, int B) {
    int res = 1;
    while(B) {
        if(B & 1) res = res * A % mod;
        A = A * A % mod, B >>= 1;
    }
    return res;
}
inline void Deal_First(int x, int fa) {
    Dep[x] = Dep[fa] + 1, Father[x][0] = fa;
    for(register int i = 1; i <= 20; ++i) Father[x][i] = Father[Father[x][i - 1]][i - 1];
    for(register int i = Edge.head[x]; i; i = Edge.edge[i].nex) {
        int y = Edge.edge[i].v;
        if(y == fa) continue;
        Deal_First(y, x);
    }    
}
inline int Get_LCA(int x, int y) {
    if(Dep[x] < Dep[y]) swap(x, y);
    for(register int i = 20; i >= 0; --i) {
        if(Dep[Father[x][i]] >= Dep[y]) x = Father[x][i];
        if(x == y) return x;
    }
    for(register int i = 20; i >= 0; --i)
        if(Father[x][i] != Father[y][i]) x = Father[x][i], y = Father[y][i];
    return Father[x][0];
}
inline bool Jump(int x, int y, int col) {
    while(x != y) {
        if(a[Father[y][0]]) return a[Father[y][0]] == col;
        y = Father[y][0], a[y] = col;
    }
    return 1;
}
inline void Paint() {
    for(register int i = 1; i <= K; ++i) {
        int Siz = Col[i].size();
        if(!Siz) continue;
        int now = Col[i][0];
        for(register int j = 1; j < Siz; ++j) {
            int LCA = Get_LCA(now, Col[i][j]);
            if(!Jump(LCA, now, i)) { printf("0\n"); exit(0); };
            if(!Jump(LCA, Col[i][j], i)) { printf("0\n"); exit(0); }
            now = LCA;
        }
        Top[i] = now, f[Top[i]][1] = 1;
    }
}
inline void Remake() {
    for(register int i = 2; i <= Edge.len; i += 2) {
        int y = Edge.edge[i].v, x = Edge.edge[i ^ 1].v;
        int f1 = (a[x] ? Top[a[x]] : x), f2 = (a[y] ? Top[a[y]] : y);
        if(!a[x] || !a[y]) {
            if(!mapp[f1][f2] && !mapp[f2][f1]) Tree.make_map(f1, f2), Tree.make_map(f2, f1);
            mapp[f1][f2] = mapp[f2][f1] = 1;
        }
        else if(a[x] != a[y]) {
            if(!mapp[f1][f2] && !mapp[f2][f1]) Tree.make_map(f1, f2), Tree.make_map(f2, f1);
            mapp[f1][f2] = mapp[f2][f1] = 1;
        }
    }
}
inline void Search(int x, int fa) {
    int Cnt = 1;
    for(register int i = Tree.head[x]; i; i = Tree.edge[i].nex) {
        int y = Tree.edge[i].v;
        if(y == fa) continue;
        Search(y, x);
        Cnt = Cnt * (f[y][0] + f[y][1]) % mod;
    }
    if(!a[x]) f[x][0] = Cnt;
    else f[x][1] = Cnt;
    for(register int i = Tree.head[x]; i; i = Tree.edge[i].nex) {
        int y = Tree.edge[i].v;
        if(y == fa) continue;
        if(!a[x]) f[x][1] = (f[x][1] + Cnt * Ksm((f[y][0] + f[y][1]) % mod, mod - 2) % mod * f[y][1] % mod) % mod;
    }
}
signed main() {
    freopen("partition.in", "r", stdin);
    freopen("partition.out", "w", stdout);
    n = read(), K = read(), Edge.len = 1;
    for(register int i = 1; i <= n; ++i) a[i] = read(), Col[a[i]].emplace_back(i);
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read();
        Edge.make_map(u ,v), Edge.make_map(v, u);
    }
    Deal_First(1, 0), Paint();
    Remake(); int Root = (Top[1] ? Top[1] : 1ll);
    Search(Root, 0);
 f[i][1]);
    printf("%lld\n", f[Root][1]);
    return 0;
}

T3 打表

考点：状压

用时：???

得分：10pts

Description

有 $k$ 种颜色的棋子，每种颜色的棋子有两个。求在 $n\times n$ 的棋盘内放置这 $2k$ 个棋子的方案数，满足一个位置最多放一个棋子，且同种颜色的两个棋子都不在同一行或同一列。

$n,k\leq 40$

Solution

我会暴力！期望得分 $10pts$