grade

感谢这场比赛,让我暴露出很多问题。

题解

A 仓鼠的石子

n 个环。每个环大小为 a_i。两个人博弈,分别涂红色和蓝色,每次能选某个未被涂色的点涂上自己的颜色,要求任意时刻都不能有同色点相邻。不能操作者为输。

判断是否先手必胜。

n \leq 10^3, a_i \leq 10^9


结论:一个环先手必胜,当且仅当大小为 1

证明非常简单,最后的情况一定是颜色交替出现的,并且最后填的颜色和第一个不一样。所以一定填了偶数个。所以后手必胜。

特判掉 1 就好。

然后把先手必败的换看作转换胜负状态的节点。统计有多少个先手必败的环。

void solve() {
    IO::read(n); int cnt = 0;
    rep(i, 1, n) {
        int x; IO::read(x);
        if (x == 1) cnt++;
    }
    if (cnt & 1) puts("rabbit");
    else puts("hamster");
    return ;
}

B 乘法师

给出由非负整数组成的序列 A 与非负整数 v,求有多少个子段,满足所有数乘积大于 v

|A| \leq 10^5,\ A_i, v \leq 10^9


先将序列被 0 分成若干个子段。

显然可以二分的,可惜 long long 存不下。

对于每个子段,尺取一下。

具体见代码。

void work() {
    ll curval = 1;
    int ridx = 0;
    rep(i, 1, cnt) {
        curval /= table[i - 1];
        while (ridx < cnt && curval < V) curval *= table[++ridx];
        if (curval < V && ridx == cnt) break;
        ans += (cnt - ridx) + 1;
    }
}

void solve() {
    table[0] = 1;
    cnt = ans = 0;
    IO::read(n), IO::read(V);
    rep(i, 1, n) {
        IO::read(arr[i]);
        if (arr[i] == 0) work(), cnt = 0;
        else table[++cnt] = arr[i];
    }
    if (V == 0) return printf("%lld\n", 1ll * n * (n + 1) / 2), void();
    if (cnt) work();
    printf("%lld\n", ans);
}

感觉还是像之前一样,我不太能做得出这种说不出 topic 的东西。反而总是想要把问题复杂化后归约到说得出 topic 的东西(

C 乃爱与城市拥挤程度

给出一棵树与正整数 k,求对于每个点 u

  • 一个点 v 是好的,当且仅当 \text{dis}(u, v) \leq k
  • 求出有多少个点是好点。
  • \text{cnt}(v) 表示 v 在多少条好点到 u 的路径上。求 \displaystyle\prod_{\text{v 是好点}} \text{cnt}(v)

考虑 up and down。状态分别为 f(u, k)g(u, k)。分别表示 u 的子树内与 u 的距离不超过 k 的点形成的树,与 u 的子树外面(注意 u 的子树包括 u)与 u 的距离不超过 k 的点形成的树。

函数对于某个状态 S\text{size}(S) 表示 S 的大小,\text{val}(S) 表示该树的答案(第二问)。

先考虑 \text{size}(f(u, k))

只需要处理出恰好距离为 k 的,然后前缀和一下就是答案。

接下来是 \text{val}(f(u, k))

发现 \forall v \in \text{son}(u),他的子树内的拥挤程度与 f(v, k - 1) 相同。

只有考虑 u 的拥挤程度,显然就是 \text{size}(f(u, k))

所以

\text{val}(f(u, k)) = \text{size}(f(u, k)) \times \prod_{v \in \text{son}(u)}\text{val}(f(v, k - 1))

然后是 \text{size}(g(u, k))

从上向底地更新。分为两部分:在父亲子树外的和兄弟节点。

\forall(u, v) \in E,若 u 是爸爸,则

\text{size}(g(v, k)) = \text{size}(g(u, k - 1)) + \text{size}(f(u, k - 1)) - \text{size}(f(v, k - 2))

最后是较为困难的 \text{val}(g(u, k))

\forall(u, v) \in E,假定 u 是爸爸。

还是分为两个部分:在父亲子树外的与兄弟节点,以及单独一个父亲。

在父亲子树外的就是 \text{val}(g(u, k - 1))

对于兄弟节点(不含父亲),本来是 \text{val}(f(u, k - 1)),即:

\text{size}(f(u, k - 1)) \times \prod_{s \in \text{son}(u)}\text{val}(f(s, k - 2))

因为我们要去掉 v 所在的这棵子树和 u 自己的贡献,所以应该是:

\prod_{s \in \text{son}(s) \land s \neq v}\text{val}(f(s, k - 2))

这一部分的贡献为 \text{val}(f(u, k - 1)) / \text{size}(f(u, k - 1)) / \text{val}(f(v, k - 2))。注意要取模,得乘逆元。

最后是爸爸 u 的拥挤程度。不难发现是 \text{size}(f(u, k - 1)) - \text{size}(f(v, k - 2)) + \text{size}(g(u, k - 1))

全部乘起来就好。

最后考虑如何合并的 f, g\text{size} 就直接加,对于 \text{val}(f(u, k))\text{val}(g(u, k)),还是考虑 u 以外的贡献乘上 u 的贡献。

\text{val}(f(u, k)) \times \text{val}(g(u, k)) / \text{size}(f(u, k)) \times (\text{size}(f(u, k)) + \text{size}(g(u, k)))
typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXK = 10 + 10;
const int P = 1e9 + 7;

int n, K;

int head[MAXN], ecnt;
struct Edge { int nxt, to; } e[MAXN << 1];
void add(int u, int v) { e[++ecnt].nxt = head[u], e[ecnt].to = v, head[u] = ecnt; }

int qpower(int a, int x) {
    int ret = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
    return ret;
}

int f[MAXN][MAXK][2], g[MAXN][MAXK][2];
void dfs1(int u, int fr) {
    f[u][0][0] = f[u][0][1] = 1;
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == fr) continue;
        dfs1(v, u);
        rep(k2, 1, K) f[u][k2][0] += f[v][k2 - 1][0];
    }
}
void dfs2(int u, int fr) {
    rep(k2, 0, K) f[u][k2][1] = f[u][k2][0] ? f[u][k2][0] : 1;
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == fr) continue;
        dfs2(v, u);
        rep(k2, 1, K) f[u][k2][1] = 1ll * f[u][k2][1] * f[v][k2 - 1][1] % P;
    }
}

void dfs3(int u, int fr) {
    g[u][1][0] = !(u == 1), g[u][1][1] = 1, g[u][0][1] = 1;
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == fr) continue;
        rep(k2, 2, K) g[v][k2][0] = g[u][k2 - 1][0] + f[u][k2 - 1][0] - f[v][k2 - 2][0];
    }
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == fr) continue;
        rep(k2, 2, K) g[v][k2][1] = 1ll * g[u][k2 - 1][1] % P *
                                    f[u][k2 - 1][1] % P * qpower(f[v][k2 - 2][1], P - 2) % P *
                                    qpower(f[u][k2 - 1][0], P - 2) % P *
                                    (f[u][k2 - 1][0] - f[v][k2 - 2][0] + g[u][k2 - 1][0]) % P;
    }
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == fr) continue;
        dfs3(v, u);
    }
}

int main() {
    IO::read(n), IO::read(K);
    rep(i, 1, n - 1) {
        int u, v; IO::read(u), IO::read(v);
        add(u, v), add(v, u);
    }
    rep(i, 1, n) rep(k2, 0, K) f[i][k2][1] = g[i][k2][1] = 1;
    dfs1(1, 0);
    rep(i, 1, n) rep(k2, 1, K) f[i][k2][0] += f[i][k2 - 1][0];
    dfs2(1, 0);
    dfs3(1, 0);
    rep(i, 1, n) {
        int tmp = 0;
        printf("%d ", f[i][K][0] + g[i][K][0]);
    }
    puts("");
    rep(i, 1, n) {
        int tmp = 1;
        printf("%lld ", 1ll * f[i][K][1] * g[i][K][1] % P * qpower(f[i][K][0], P - 2) % P * (f[i][K][0] + g[i][K][0]) % P);
    }
    return 0;
}

up and down 的常见转移方式:父亲以外、兄弟、父亲三部分。

小 w 的魔法扑克

k 张牌,每张牌有 2 个数字。数字都属于 [1, n]。每次询问能否选出一些牌,使得这些牌上的数字(每张牌只能选一个数字)取遍 [l, r]

n, k, q \leq 10^5


考虑建图(感觉这个有点难以想到)。边对应牌,向两个数字连边。询问为,能否选择一些边,使得所有点都被覆盖到。

考虑到一个大小为 s 连通块,如果其边数大于 s - 1,则一定能选出边,使得点都被覆盖到。否则一定会有一个点不会被选到。

那么考虑哪些边数为 s - 1 的连通块,即树。如果这个树中的某个点不属于询问的 [l, r],那么不选就是了。

所以我们把树变成若干个线段,线段的左右端点分别是树上点编号的最小最大值。询问就是看是否完全覆盖了某个线段。

即是否存在 i,满足 l \leq l_i, r_i \leq r_i。这就是一个二维数点的问题。排序+BIT 搞搞就好。

typedef pair<int, int> pii;

const int MAXN = 1e5 + 10;

int n, k, q;

struct union_find_set {
    struct Node { int fa, sz, mn, mx; bool is_tree; } node[MAXN];
    union_find_set() { rep(i, 1, MAXN - 1) node[i].fa = node[i].mn = node[i].mx = i, node[i].sz = 1, node[i].is_tree = true; }
    int gf(int x) { return node[x].fa == x ? x : node[x].fa = gf(node[x].fa); }
    void merge(int x, int y) {
        int fax = gf(x), fay = gf(y);
        if (fax == fay) return node[fax].is_tree &= false, void();
        if (node[fax].sz < node[fay].sz) swap(fax, fay);
        node[fax].sz += node[fay].sz, node[fax].is_tree &= node[fay].is_tree;
        node[fax].mn = min(node[fax].mn, node[fay].mn), node[fax].mx = max(node[fax].mx, node[fay].mx);
        node[fay].fa = fax;
    }
} dsu;

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

struct Querys { int l, r, idx; bool operator <(const Querys& _) { return r < _.r || r == _.r && l > _.l; } };
struct Segs { int l, r; bool operator <(const Segs& _) { return r < _.r || r == _.r && l > _.l; } };
vector<Querys> querys;
vector<Segs> segs;
int ans[MAXN];

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, k) {
        int u, v; IO::read(u), IO::read(v);
        dsu.merge(u, v);
    }
    rep(i, 1, n) {
        if (dsu.node[i].fa == i && dsu.node[i].is_tree) {
            segs.push_back((Segs){dsu.node[i].mn, dsu.node[i].mx});
        }
    }
    IO::read(q);
    rep(i, 1, q) {
        int l, r; IO::read(l), IO::read(r);
        querys.push_back((Querys){l, r, i});
    }
    sort(segs.begin(), segs.end()), sort(querys.begin(), querys.end());
    int curidx = 0;
    for (auto q : querys) {
        while (curidx < segs.size() && segs[curidx].r <= q.r) bit.add(segs[curidx].l, 1), curidx++;
        ans[q.idx] = bit.query(q.l);
    }
    rep(i, 1, q) puts(ans[i] ? "No" : "Yes");
    return 0;
}

两个关键点:

  • 建图
  • 树中有一个点不在 [l, r] 里面 \Leftrightarrow 最小值或最大值不在 [l, r] 里。

复盘

开场没读完题,看了 T1 觉得很 easy。

15 min 写出来 T1。

事实上写假了,手玩大小为 3 的环的时候玩错了。不知道为什么这个都会错。其实只要我随便检查一下都能发现。

总之 100 \rightarrow 20

看 T2,非常兴奋,以为是个 sb 题。拿 set 维护了一个前缀积。

写了 20 min。

结果发现看漏了数都是非负数,有 0 的话我的做法是假的。

想了想,发现可以把序列拆成若干个由 0 划分出的子区间,主席树搞一波。

然后写了 45 min,调了 12 min,过了小样例。发现大样例没过。

拿之前的 set 暴力跑了一下大样例,和我主席树是一个答案,都是错的。

然后懵逼了,开始乱调,调了 30 min,发现 10^510^9 的数相乘会爆 long long

是的,我花了 90 min 才发现这题不能维护前缀积!这种一眼能发现的事情我花了 90 min

现在过去了 2h。如果是在 CSP 场上发生这种事情我估计心态会爆炸。

然后又花了点时间写暴力,然后暴力也写错了。

因为我暴力没有分段(

2h - 3h 这 60 min 我不知道在干啥,还在纠结 T2,可是啥都没纠结出来。因为思路已经陷进去了。

还剩 40+ min,赶紧 rush T3,发现很可做,up and down 一下就行。然后没搞清楚转移,大体思路是对的,最后还是错了。

最后也没时间检查 T1,光荣挂 0。

这场有几个错误:

  • 开场没看完题
  • T1 太着急了,写完没检查,最后也没检查。
  • T2 没认真看数据范围,拿着半边就跑,耽误了至少 2h。
  • 开场应该读完所有题,T3 T4 都还算是很可做,尤其是 T3,推推式子就出来了。

本来有几个翻盘点:

  • T1 检查一下。
  • T2 发现 set 不行的时候再认真看看数据范围。
  • T2 发现爆 long long 应该立刻从头开始考虑这题,不要继续再错。
  • 实在不行也应该看看 T3 T4。

以后应该:

  • 无论如何,开场读完题。就算 4 道全是 A+B 也读完题。
  • 开始想题的时候看好数据范围!!
  • 一个思路实在不行应该立刻换掉。

仅有一条评论

  1. bark bark

    总结的好!牢记于心!下场看还会犯错吗?加油

10-26 赛后题解
上一篇 «
国庆 Day 5 模拟赛赛后题解与总结
» 下一篇