Description

Link.

概括什么好麻烦哦 w。

Solution

生成函数裸题。

把所有情况罗列出来:

kkk:

金: $1+x^6+x^{12}+\dots=\frac{1}{1-x^6}$

木: $1+x+x^2+\dots+x^9=\frac{1-x^{10}}{1-x}$

水块: $1+x+x^2+\dots+x^5=\frac{1-x^6}{1-x}$

火: $1+x^4+x^8+\dots=\frac{1}{1-x^4}$

土: $1+x+x^2+\dots+x^7=\frac{1-x^8}{1-x}$

lzn:

金: $1+x^2+x^4+\dots=\frac{1}{1-x^2}$

木: $1+x=\frac{1-x^2}{1-x}$

水: $1+x^8+x^{16}+\dots=\frac{1}{1-x^8}$

火: $1+x^{10}+x^{20}+\dots=\frac{1}{1-x^{10}}$

土: $1+x+x^2+x^3=\frac{1-x^4}{1-x}$

凉心出题人友好的卡了精度并且顺便卡了pypy。所以，人生苦短，Ruby用我

n = gets.to_i
print (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24

Description

Link.

给你一棵树，放置守卫在某个点上面需要一定代价和一定的有效范围。让你覆盖若干指定点，求最小代价

Solution

算法标签：

$\ \ \ \ \ \ \ \ \ $ 树DP

DP状态定义:

$\ \ \ \ \ \ \ \ \ $ 说实话这道题定状态不好定。

$\ \ \ \ \ \ \ \ \ $ 那么我们从头来看，当 $d =0$ 的时候，我们就是在求树的最大独立集，定义显而易见。

$\ \ \ \ \ \ \ \ \ $ $d\neq 0$ 我们可以照搬原来的定义，把它扩展一下。

$\ \ \ \ \ \ \ \ \ $ $f_{i,j}$ 表示以 $i$ 为根结点的子树已经完全被覆盖让然后还能向上覆盖 $j$ 层的最小代价

$\ \ \ \ \ \ \ \ \ $ $g_{i,j}=$ 表示以 $i$ 为根结点的子树还有 $j$ 层没有覆盖的最小代价

$\ \ \ \ \ \ \ \ \ $ 需要注意的是 $j$ 本质上是带有方向性的，可以类比向量的概念。

$\ \ \ \ \ \ \ \ \ $ 边界条件很显然，$f_{i,0}=val_{i}$ 此时当前结点需要被覆盖。

$\ \ \ \ \ \ \ \ \ $ 其他情况：

$$ \begin{cases} f_{i,j}=val_{i},j\in [1,d] \\ \displaystyle f_{i,j}=\infty,j=d+1 \end{cases} $$

$\ \ \ \ \ \ \ \ \ $ 状态转移方程倒是比较好想，这里就不再赘述。

#include <cstdio>
#include <algorithm>
#include <queue>

char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is_number (ch >= '0' && ch <= '9')

template < typename Type >
void read(Type& a) {
    a = 0; bool f = 0; char ch;
    while (!(ch = gc(), is_number)) if (ch == '-') f = 1;
    while (is_number) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
    a = (f ? -a : a);
}

template < typename Type, typename... Args >
void read(Type& t, Args&... args) {
    read(t), read(args...);
}

int val[500005], f[500005][25];
int g[500005][25], vis[500005];
int n, m, d, tot, head[500005];
int nxt[1000005], to[1000005];
std::vector < std::vector < int > > G(500005);

void add(int x, int y) {
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
    G[x].push_back(y);
    G[y].push_back(x);
}

void DP(int x, int fa) {
    if (vis[x]) g[x][0] = f[x][0] = val[x];
    for (int i = 1; i <= d; ++i) f[x][i] = val[x];
    f[x][d + 1] = 0x3f3f3f3f;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y ^ fa) {
            DP(y, x);
            for (int j = d; j >= 0; --j)
                f[x][j] = std::min(f[y][j + 1] + g[x][j + 1], f[x][j] + g[y][j]);
            for (int j = d; j >= 0; --j)
                f[x][j] = std::min(f[x][j + 1], f[x][j]);
            g[x][0] = f[x][0];
            for (int j = 1; j <= d + 1; ++j)
                g[x][j] += g[y][j - 1];
            for (int j = 1; j <= d + 1; ++j)
                g[x][j] = std::min(g[x][j - 1], g[x][j]);
        }
    }
}

signed main() {
    read(n, d);
    for (int i = 1; i <= n; ++i) read(val[i]);
    read(m);
    for (int i = 0, x; i < m; ++i) read(x), vis[x] = 1;
    for (int i = 1, x, y; i < n; ++i) read(x, y), add(x, y), add(y, x);
    DP(1, 0);
    printf("%d\n", g[1][0]);
}

Description

Link.

在一个数轴上给你三个点，移动方法是彼此为中点进行跳跃，不能同时越过两颗棋子。

给出初始状态和目标状态，问能否从初始状态跳到目标状态。若能，输出最少步数。

棋子之间互相没有差别。

Solution

这道题是我们去年学倍增的时候LF给我们放的一道题（实际上和倍增没有半毛钱的关系。

啊对我就是一道题从去年做到今年（我不管做出来了就是我的题量XD/xyx

不扯了说正事儿。

其实拿到这道题我是很懵的，完全不知道该怎么入手。

然后我们拿出传统手艺手玩数据。我们可以发现对于一个三元组 $(x,y,z)$ 只有三种移动的方案：

（啊对了，说一下这里的三元组表示的是一种位置关系，即 $x$ 在左 $y$ 在中间 $z$ 在右）

中间往两边跳

1. $y$ 以 $x$ 为中点进行跳跃，三元组变为：$(x-(y-x),x,z)\implies(2x-y,x,z)$
2. $y$ 以 $z$ 为中点进行跳跃，三元组变为：$(x,z,z+(z-y))\implies(x,z,2z-y)$

两边往中间跳

这里方便讨论我们不妨设 $dis_{1}$ 为 $x$ 和 $y$ 之间的距离，$dis_{2}$ 为 $y$ 和 $z$ 之间的距离。

当 $dis_{1} > dis_{2}$

3. $x$ 以 $y$ 为中点进行跳跃，三元组变为：$(y,y+dis_{1},z)\implies(y,2y-x,z)$

当 $dis_{1} < dis_{2}$

3. $z$ 以 $y$ 为中点进行跳跃，三元组变为：$(x,y-dis_{2},y)\implies(x,2y-z,y)$

当 $dis_{1}=dis_{2}$

无法继续跳，也就是我们的边界。

好，现在把所有我们已知的条件串起来看：这不就是一棵二叉树吗？

对呀，这就是一棵二叉树（我在说什么

为什么这一定是一棵树呢？想一想就明白了，就像数学中的收敛一样，最后一定会出现 $dis_{1}=dis_{2}$ 的情况。

而且这棵树是唯一确定的。

那么这道题的答案是什么就很明确了。

首先判断YES或NO的情况我们只需要判断初始状态和目标状态是否在统一棵状态树上即可。

最小的步数就是他们两个在树上的距离。

暴力肯定是不可取的。

但是我们可以通过模拟暴力的情景来得到优化的策略。

比如我们思考一个数据：$x,y,z$。

其中 $y$ 是一个 远大于 $x$ 的数。

方便起见我们令 $z=y+1$

暴力此时会不停的让 $z$ 以 $y$ 为中点跳。

此时我们回顾一下题面：

棋子之间互相没有差别。

没错，每颗棋子之间其实是没有任何差别的。

打个比方说，现在 $z$ 以 $y$ 为中点进行了跳跃，其本质就是 $z$ 和 $y$ 一起往左平移了 $z-y$ 步。

这就意味着，我们不需要老老实实的每次都跳，我们可以直接获得 $z$ 跳跃的次数即 $(y-x)\div(z-y)$ 次。

再推一下就是欧几里得最大公约数的形式了，也就是说我们在 $log_{2}$ 的复杂度解决了这个问题。

最后二分一下到LCA的距离，这道题就被你暴切啦

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int a, b, c;
int x, y, z;

void sort(int& x, int& y, int& z) {
    vector < int > vec;
    vec.push_back(x);
    vec.push_back(y);
    vec.push_back(z);
    sort(vec.begin(), vec.end());
    x = vec[0], y = vec[1], z = vec[2];
}

void Initialization() {
    scanf("%d %d %d", &a, &b, &c);
    scanf("%d %d %d", &x, &y, &z);
    sort(a, b, c);
    sort(x, y, z);
}

int GetRoot(int& x, int& y, int& z) {
    int dis1 = y - x;
    int dis2 = z - y;
    if (dis1 ^ dis2) {
        int temp;
        if (dis1 < dis2) {
            temp = dis2 / dis1;
            if (!(dis2 % dis1)) --temp;
            x += temp * dis1;
            y += temp * dis1;
        }
        else {
            temp = dis1 / dis2;
            if (!(dis1 % dis2)) --temp;
            z -= temp * dis2;
            y -= temp * dis2;
        }
        return temp + GetRoot(x, y, z);
    }
    else return 0;
}

void ArriveK(int& x, int& y, int& z, int key) {
    int dis1 = y - x;
    int dis2 = z - y;
    if (dis1 < dis2) {
        int temp = dis2 / dis1;
        if (!(dis2 % dis1)) --temp;
        if (temp >= key) {
            x += key * dis1;
            y += key * dis1;
        }
        else {
            x += temp * dis1;
            y += temp * dis1;
            ArriveK(x, y, z, key - temp);
        }
    }
    else {
        int temp = dis1 / dis2;
        if (!(dis1 % dis2)) --temp;
        if (temp >= key) {
            z -= key * dis2;
            y -= key * dis2;
        }
        else {
            z -= temp * dis2;
            y -= temp * dis2;
            ArriveK(x, y, z, key - temp);
        }
    }
}

signed main() {
    Initialization();
    int a0 = a, b0 = b;
    int c0 = c, x0 = x;
    int y0 = y, z0 = z;
    int rt1 = GetRoot(x0, y0, z0);
    int rt2 = GetRoot(a0, b0, c0);
    if (a0 ^ x0 || b0 ^ y0 || c0 ^ z0) return puts("NO") & 0;
    if (rt1 < rt2) ArriveK(a, b, c, rt2 - rt1);
    else ArriveK(x, y, z, rt1 - rt2);
    int l = 0, r = min(rt1, rt2);
    while (l < r) {
        int mid = (l + r) >> 1;
        a0 = a, b0 = b, c0 = c;
        x0 = x, y0 = y, z0 = z;
        ArriveK(x0, y0, z0, mid);
        ArriveK(a0, b0, c0, mid);
        if (x0 == a0 && y0 == b0 && z0 == c0)
            r = mid;
        else
            l = mid + 1;
    }
    printf("YES\n%d\n", max(rt1, rt2) - min(rt1, rt2) + (l << 1));
    return 0;
}

Description

Link.

联赛原题应该都读过吧……

Solution

Part 0

大致思路

主要的思路就是逐个打破，研究特殊的数据得到普通的结论。

Part 1

暴力的部分分

暴力的部分分很好拿，我们可以直接把全排列，然后 $\Theta(n)$ 判断更新答案。

恭喜您拿到赛场满分

namespace SubtaskForce {
    int cmp[MAXN], ans[MAXN];
    bool vis[MAXN];
    void dfs(int now) { // 全排列
        if (now == n) { // 更新答案
            for (R int i = 1; i <= n; ++i) cmp[id[i]] = i;
            for (R int i = 1; i <= n; ++i) {
                if (cmp[i] < ans[i]) {
                    for (R int j = 1; j <= n; ++j) ans[j] = cmp[j];
                    break;
                }
                if (cmp[i] > ans[i]) break;
            }
            return ;
        }
        for (R int i = 1; i < n; ++i) {
            if (!vis[i]) {
                vis[i] = 1;
                swap(id[nodes[i].x], id[nodes[i].y]);
                dfs(now + 1);
                swap(id[nodes[i].x], id[nodes[i].y]);
                vis[i] = 0;
            }
        }
    }

    void main() { // 初始化
        for (R int i = 1; i <= n; ++i) vis[i] = 0;
        for (R int i = 1; i <= n; ++i) ans[i] = n - i + 1;
        dfs(1);
        for (R int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
}

Part 2

菊花图的部分分

就这道题而言，菊花图其实是比链的数据好想一些的。

我们称菊花图中度数为 $n-1$ 的结点为 $rt$ 罢。

我们可以发现在菊花图上删除边一定是某个结点和 $rt$ 之间。

也就是说无论我们按怎样的顺序删边，最后都会变成一个环。

我做了一个动图演示，如果洛谷博客不支持gif的话就直接到这个网址 Click Here

有了环这个结论，就有一个很显然的贪心构造环的方法：

按照 $1,2,\cdots,n$ 的顺序每个数字选择环上自己的下一个点。

在编写代码的时候还需要注意还没有连到 $Y_{n}$ 就提前自毙自闭封闭的情况。

namespace SubtaskAss { // 菊花的单词太长了，就取了个差不多的/xyx
    bool vis[MAXN];
    int ans[MAXN];
    struct UninoFindSet {
        int fa[MAXN];

        void init(int limit) {
            for (R int i = 1; i <= limit; ++i)
                fa[i] = i;
        }

        int find(int x) {
            if (x ^ fa[x]) fa[x] = find(fa[x]);
            return fa[x];
        }

        void merge(int x, int y) {
            x = find(x);
            y = find(y);
            if (x ^ y) fa[x] = y;
        }
    } ufs;

    void main() {
        ufs.init(n);
        for (R int i = 1; i <= n; ++i) vis[i] = 0;
        for (R int i = 1; i <= n; ++i) {
            for (R int j = 1; j <= n; ++j) {
                if (!vis[j] && (i == n || ufs.find(j) != ufs.find(id[i]))) {
                    vis[j] = 1;
                    ans[i] = j;
                    ufs.merge(j, id[i]);
                    break;
                }
            }
        }
        for (R int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
}

Part 3

链的部分分

说实话链的部分分其实也挺好拿的，但是还是比菊花图难想一些。

首先，用dfs序把链拍成树是固定操作了。

链有一个性质，就是每个结点(两端点除外)的度数都有且只有二。

也就是说除端点外，每个结点都有两条边。而且这两条边的被删除时间一定不一样（废话

也就是说每个结点的两条边被删除的情况一共有三种。

我们定义 $order_{i}$ 为结点 $i$ 的左右两边的删除情况：

• 0：0表示这个结点的左右边都还没被删除
• 1：1表示这个结点的左边先被删除
• 2：2表示这个结点的右边先被删除

现在我们假设左边的结点 $u$ 要跑到右边的结点 $v$ 那里去，那么在 $u$ 和 $v$ 之间的结点一定是左边先被删除，所以 $order_i=1,i\in (u,v)$

对于 $u$ 和 $v$ 两个结点，一定是右边先被删除，否则就不知道跑哪里去了

所以 $order_{u}=order_{v}=2$

至于从右跑到左就完全同理了。

答案则同样是从小枚举到大(我是从小枚举到大的/xyx)

比如说我们当前枚举到了结点 $x$，我们希望它能去尽量小的一个点

假设当前 $x$ 在 $P_{x}$，我们直接暴力枚举一个 $P_{y}$。

判断一个方案是否可行只需要判断它与前面的删边顺序冲突即可。

这样做是 $\Theta(N^3)$ 的。我们可以在dfs的时候标记，这样就是 $\Theta(n^2)$ 了。

namespace SubtaskChain {
    int rnk[MAXN], ans[MAXN], dfn[MAXN];
    int sbc_tot, order[MAXN], vis[MAXN];

    void dfs(int x, int fa) {
        rnk[dfn[x] = ++sbc_tot] = x;
        for (R int i = head[x]; i; i = nxt[i])
            if (to[i] ^ fa) dfs(to[i], x);
    }

    void mark_node(int p1, int p2, int tg) {
        if (p1 != 1 && p1 != n) order[p1] = tg + 1;
        if (p2 != 1 && p2 != n) order[p2] = tg + 1;
        for (R int i = (tg ? p1 + 1 : p2 + 1); i < (tg ? p2 : p1); ++i) order[i] = ((tg ^ 1) + 1);
    }

    int iterate(int x, int tg) {
        int res = n + 1;
        if (order[dfn[x]] == tg + 1) return res;
        for (R int i = dfn[x] + (tg ? -1 : 1); tg ? (i >= 1) : (i <= n); i += (tg ? -1 : 1)) {
            if (order[i] == (tg ^ 1) + 1) {
                if (!vis[i]) res = min(res, rnk[i]);
                break;
            }
            if (!order[i] && !vis[i]) res = min(res, rnk[i]);
        }
        return res;
    }
    int inver_id[MAXN];
    void main() {
        for (R int i = 1; i <= n; ++i) rnk[i] = 0;
        for (R int i = 1; i <= n; ++i) dfn[i] = 0;
        for (R int i = 1; i <= n; ++i) vis[i] = 0;
        for (R int i = 1; i <= n; ++i) order[i] = 0;
        for (R int i = 1; i <= n; ++i) inver_id[id[i]] = i;
        sbc_tot = 0;
        for (R int i = 1; i <= n; ++i) {
            if (in[i] == 1) {
                dfs(i, 0);
                break;
            }
        }
        for (R int i = 1; i <= n; ++i) {
            int left = iterate(inver_id[i], 1);
            int right = iterate(inver_id[i], 0);
            if (left < right) mark_node(dfn[inver_id[i]], dfn[left], 0);
            else left = right, mark_node(dfn[inver_id[i]], dfn[left], 1);
            ans[i] = left;
            vis[dfn[left]] = 1;
        }
        for (R int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
}

Part 4

正解

拼凑出的正解

（我能说这剩下的40pts我看题解都看了半天吗）

剩下的40pts是我看了这篇题解才会的Click Here

其实会了链的数据基本就离成功不远了。

仔细想想，我们在处理链的时候，规定了与一个结点的边的删除顺序的数值。

如果放到一般的情况来看，我们可以确定一个类似于拓扑序的删除顺序，即某一条边需要在某一条边删除过后才能被删除。

比如下图：

当我们把这一删除顺序写出来，就可以发现这其实构成了一个链。

对吧！对吧！

假设我们现在需要把 $x$ 删到 $y$ 结点上。

那么判断法则如下：

不合法的情况：

• 有一个数已经从 $x$ 出去过了
• 有一个数已经到过 $y$ 这里了
• 有一个数从相同方向过了 $x$ 的一条出边
• 有一个数从相同方向过了 $y$ 的一条出边
• 出/入边任意一条被别的数字从相同方向走了一次
• 加上当前数构成的链 $x$ 有任意一边出边不在上面
• 加上当前数构成的链 $y$ 有任意一边出边不在上面
• 加上当前数后，经过 $x$ 的数字自闭了(形成了一个环)
• 加上当前数后，形成了一条链，$x$ 有任意一条出边不在上面

合法的情况

• 排除以上所有情况即合法

直接贪心会死得很惨烈。

我们可以通过dfs找出编号最小的作为本轮的答案。

namespace SubtaskRandom {
    int mark[MAXN][MAXN], inver_id[MAXN];
    int lave_unwalked[MAXN], fa[MAXN];
    int lave_in[MAXN], lave_out[MAXN];
    int node_from[MAXN], node_to[MAXN];
    int header[MAXN][MAXN], footer[MAXN][MAXN];
    bool vis[MAXN];

    void dfs(int x, int rt) {
        for (R int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            if (y ^ fa[x]) {
                fa[y] = x;
                vis[y] = 1;
                if (x ^ rt) {
                    if (mark[x][y] == x || mark[fa[x]][x] == fa[x]) vis[y] = 0;
                    if (mark[x][y] == 0 || mark[fa[x]][x] == 0) vis[y] = 0;
                    if (header[x][fa[x]] == node_to[x] && footer[x][y] == node_from[x]
                        && lave_out[x] + lave_in[x] + (lave_unwalked[x] << 1) > 2) vis[y] = 0;
                    if (footer[x][y] == fa[x]) vis[y] = 0;
                }
                else {
                    if (mark[x][y] == x) vis[y] = 0;
                    if (mark[x][y] == 0) vis[y] = 0;
                    if (node_from[x]) {
                        if (footer[x][y] == node_from[x] && lave_unwalked[x] + lave_in[x] + lave_out[x] != 1)
                            vis[y] = 0;
                    }
                }
                vis[y] &= vis[x];
                dfs(y, rt);
            }
        }
        if (rt ^ x) {
            if (node_from[x]) vis[x] = 0;
            if (node_to[x]) {
                if (footer[x][node_to[x]] == fa[x] && lave_unwalked[x] + lave_in[x] + lave_out[x] != 1)
                    vis[x] = 0;
            }
        }
        else {
            vis[x] = 0;
        }
    }

    void main() {
        for (R int i = 1; i <= n; ++i) node_from[i] = 0;
        for (R int i = 1; i <= n; ++i) node_to[i] = 0;
        for (R int i = 1; i <= n; ++i) lave_in[i] = 0;
        for (R int i = 1; i <= n; ++i) lave_out[i] = 0;
        for (R int i = 1; i <= n; ++i) lave_unwalked[i] = 0;
        for (R int i = 1; i <= n; ++i) inver_id[id[i]] = i;
        for (R int i = 1; i < n; ++i) {
            lave_unwalked[nodes[i].x]++;
            lave_unwalked[nodes[i].y]++;
            mark[nodes[i].x][nodes[i].y] = -1;
            mark[nodes[i].y][nodes[i].x] = -1;
            header[nodes[i].x][nodes[i].y] = nodes[i].y;
            header[nodes[i].y][nodes[i].x] = nodes[i].x;
            footer[nodes[i].x][nodes[i].y] = nodes[i].y;
            footer[nodes[i].y][nodes[i].x] = nodes[i].x;
        }
        for (R int i = 1; i <= n; ++i) {
            for (R int j = 1; j <= n; ++j) fa[j] = 0;
            vis[inver_id[i]] = 1;
            dfs(inver_id[i], inver_id[i]);
            int res = 0;
            for (R int j = 1; j <= n; ++j) {
                if (vis[j]) {
                    res = j;
                    break;
                }
            }
            printf("%d ", res);
            node_from[res] = fa[res];
            while (fa[res] ^ inver_id[i]) {
                if (~mark[fa[res]][res]) {
                    mark[fa[res]][res] = mark[res][fa[res]] = 0;
                    lave_in[res]--;
                    lave_out[fa[res]]--;
                }
                else {
                    mark[fa[res]][res] = mark[res][fa[res]] = fa[res];
                    lave_unwalked[res]--;
                    lave_out[res]++;
                    lave_unwalked[fa[res]]--;
                    lave_in[fa[res]]++;
                }
                int t = res;
                res = fa[res];
                header[res][footer[res][t]] = header[res][fa[res]];
                footer[res][header[res][fa[res]]] = footer[res][t];
            }
            if (~mark[fa[res]][res]) {
                mark[fa[res]][res] = 0;
                mark[res][fa[res]] = 0;
                lave_in[res]--;
                lave_out[inver_id[i]]--;
            }
            else {
                mark[fa[res]][res] = fa[res];
                mark[res][fa[res]] = fa[res];
                lave_unwalked[res]--;
                lave_out[res]++;
                lave_unwalked[inver_id[i]]--;
                lave_in[inver_id[i]]++;
            }
            node_to[inver_id[i]] = res;
        }
        puts("");
    }
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is() (ch >= '0' && ch <= '9')
#define R register

template < class Type >
void read(Type& a) {
    a = 0; bool f = 0; char ch;
    while (!(ch = gc(), is())) if (ch == '-') f = 1;
    while (is()) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
    a = (f ? -a : a);
}

template < class Type, class... Args >
void read(Type& t, Args&... args) {
    read(t), read(args...);
}

const int MAXN = 2000 + 5;
int T, n, max_in, id[MAXN];
int head[MAXN], nxt[MAXN << 1];
int tot, in[MAXN], to[MAXN << 1];
struct EdgeNode {
    int x, y;
} nodes[MAXN];

EdgeNode make_edge(int x, int y) {
    EdgeNode res;
    res.x = x;
    res.y = y;
    return res;
}

void add(int x, int y) {
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

namespace SubtaskForce {
    int cmp[MAXN], ans[MAXN];
    bool vis[MAXN];
    void dfs(int now) {
        if (now == n) {
            for (R int i = 1; i <= n; ++i) cmp[id[i]] = i;
            for (R int i = 1; i <= n; ++i) {
                if (cmp[i] < ans[i]) {
                    for (R int j = 1; j <= n; ++j) ans[j] = cmp[j];
                    break;
                }
                if (cmp[i] > ans[i]) break;
            }
            return ;
        }
        for (R int i = 1; i < n; ++i) {
            if (!vis[i]) {
                vis[i] = 1;
                swap(id[nodes[i].x], id[nodes[i].y]);
                dfs(now + 1);
                swap(id[nodes[i].x], id[nodes[i].y]);
                vis[i] = 0;
            }
        }
    }

    void main() {
        for (R int i = 1; i <= n; ++i) vis[i] = 0;
        for (R int i = 1; i <= n; ++i) ans[i] = n - i + 1;
        dfs(1);
        for (R int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
}

namespace SubtaskAss {
    bool vis[MAXN];
    int ans[MAXN];
    struct UninoFindSet {
        int fa[MAXN];

        void init(int limit) {
            for (R int i = 1; i <= limit; ++i)
                fa[i] = i;
        }

        int find(int x) {
            if (x ^ fa[x]) fa[x] = find(fa[x]);
            return fa[x];
        }

        void merge(int x, int y) {
            x = find(x);
            y = find(y);
            if (x ^ y) fa[x] = y;
        }
    } ufs;

    void main() {
        ufs.init(n);
        for (R int i = 1; i <= n; ++i) vis[i] = 0;
        for (R int i = 1; i <= n; ++i) {
            for (R int j = 1; j <= n; ++j) {
                if (!vis[j] && (i == n || ufs.find(j) != ufs.find(id[i]))) {
                    vis[j] = 1;
                    ans[i] = j;
                    ufs.merge(j, id[i]);
                    break;
                }
            }
        }
        for (R int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
}

namespace SubtaskChain {
    int rnk[MAXN], ans[MAXN], dfn[MAXN];
    int sbc_tot, order[MAXN], vis[MAXN];

    void dfs(int x, int fa) {
        rnk[dfn[x] = ++sbc_tot] = x;
        for (R int i = head[x]; i; i = nxt[i])
            if (to[i] ^ fa) dfs(to[i], x);
    }

    void mark_node(int p1, int p2, int tg) {
        if (p1 != 1 && p1 != n) order[p1] = tg + 1;
        if (p2 != 1 && p2 != n) order[p2] = tg + 1;
        for (R int i = (tg ? p1 + 1 : p2 + 1); i < (tg ? p2 : p1); ++i) order[i] = ((tg ^ 1) + 1);
    }

    int iterate(int x, int tg) {
        int res = n + 1;
        if (order[dfn[x]] == tg + 1) return res;
        for (R int i = dfn[x] + (tg ? -1 : 1); tg ? (i >= 1) : (i <= n); i += (tg ? -1 : 1)) {
            if (order[i] == (tg ^ 1) + 1) {
                if (!vis[i]) res = min(res, rnk[i]);
                break;
            }
            if (!order[i] && !vis[i]) res = min(res, rnk[i]);
        }
        return res;
    }
    int inver_id[MAXN];
    void main() {
        for (R int i = 1; i <= n; ++i) rnk[i] = 0;
        for (R int i = 1; i <= n; ++i) dfn[i] = 0;
        for (R int i = 1; i <= n; ++i) vis[i] = 0;
        for (R int i = 1; i <= n; ++i) order[i] = 0;
        for (R int i = 1; i <= n; ++i) inver_id[id[i]] = i;
        sbc_tot = 0;
        for (R int i = 1; i <= n; ++i) {
            if (in[i] == 1) {
                dfs(i, 0);
                break;
            }
        }
        for (R int i = 1; i <= n; ++i) {
            int left = iterate(inver_id[i], 1);
            int right = iterate(inver_id[i], 0);
            if (left < right) mark_node(dfn[inver_id[i]], dfn[left], 0);
            else left = right, mark_node(dfn[inver_id[i]], dfn[left], 1);
            ans[i] = left;
            vis[dfn[left]] = 1;
        }
        for (R int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
}

namespace SubtaskRandom {
    int mark[MAXN][MAXN], inver_id[MAXN];
    int lave_unwalked[MAXN], fa[MAXN];
    int lave_in[MAXN], lave_out[MAXN];
    int node_from[MAXN], node_to[MAXN];
    int header[MAXN][MAXN], footer[MAXN][MAXN];
    bool vis[MAXN];

    void dfs(int x, int rt) {
        for (R int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            if (y ^ fa[x]) {
                fa[y] = x;
                vis[y] = 1;
                if (x ^ rt) {
                    if (mark[x][y] == x || mark[fa[x]][x] == fa[x]) vis[y] = 0;
                    if (mark[x][y] == 0 || mark[fa[x]][x] == 0) vis[y] = 0;
                    if (header[x][fa[x]] == node_to[x] && footer[x][y] == node_from[x]
                        && lave_out[x] + lave_in[x] + (lave_unwalked[x] << 1) > 2) vis[y] = 0;
                    if (footer[x][y] == fa[x]) vis[y] = 0;
                }
                else {
                    if (mark[x][y] == x) vis[y] = 0;
                    if (mark[x][y] == 0) vis[y] = 0;
                    if (node_from[x]) {
                        if (footer[x][y] == node_from[x] && lave_unwalked[x] + lave_in[x] + lave_out[x] != 1)
                            vis[y] = 0;
                    }
                }
                vis[y] &= vis[x];
                dfs(y, rt);
            }
        }
        if (rt ^ x) {
            if (node_from[x]) vis[x] = 0;
            if (node_to[x]) {
                if (footer[x][node_to[x]] == fa[x] && lave_unwalked[x] + lave_in[x] + lave_out[x] != 1)
                    vis[x] = 0;
            }
        }
        else {
            vis[x] = 0;
        }
    }

    void main() {
        for (R int i = 1; i <= n; ++i) node_from[i] = 0;
        for (R int i = 1; i <= n; ++i) node_to[i] = 0;
        for (R int i = 1; i <= n; ++i) lave_in[i] = 0;
        for (R int i = 1; i <= n; ++i) lave_out[i] = 0;
        for (R int i = 1; i <= n; ++i) lave_unwalked[i] = 0;
        for (R int i = 1; i <= n; ++i) inver_id[id[i]] = i;
        for (R int i = 1; i < n; ++i) {
            lave_unwalked[nodes[i].x]++;
            lave_unwalked[nodes[i].y]++;
            mark[nodes[i].x][nodes[i].y] = -1;
            mark[nodes[i].y][nodes[i].x] = -1;
            header[nodes[i].x][nodes[i].y] = nodes[i].y;
            header[nodes[i].y][nodes[i].x] = nodes[i].x;
            footer[nodes[i].x][nodes[i].y] = nodes[i].y;
            footer[nodes[i].y][nodes[i].x] = nodes[i].x;
        }
        for (R int i = 1; i <= n; ++i) {
            for (R int j = 1; j <= n; ++j) fa[j] = 0;
            vis[inver_id[i]] = 1;
            dfs(inver_id[i], inver_id[i]);
            int res = 0;
            for (R int j = 1; j <= n; ++j) {
                if (vis[j]) {
                    res = j;
                    break;
                }
            }
            printf("%d ", res);
            node_from[res] = fa[res];
            while (fa[res] ^ inver_id[i]) {
                if (~mark[fa[res]][res]) {
                    mark[fa[res]][res] = mark[res][fa[res]] = 0;
                    lave_in[res]--;
                    lave_out[fa[res]]--;
                }
                else {
                    mark[fa[res]][res] = mark[res][fa[res]] = fa[res];
                    lave_unwalked[res]--;
                    lave_out[res]++;
                    lave_unwalked[fa[res]]--;
                    lave_in[fa[res]]++;
                }
                int t = res;
                res = fa[res];
                header[res][footer[res][t]] = header[res][fa[res]];
                footer[res][header[res][fa[res]]] = footer[res][t];
            }
            if (~mark[fa[res]][res]) {
                mark[fa[res]][res] = 0;
                mark[res][fa[res]] = 0;
                lave_in[res]--;
                lave_out[inver_id[i]]--;
            }
            else {
                mark[fa[res]][res] = fa[res];
                mark[res][fa[res]] = fa[res];
                lave_unwalked[res]--;
                lave_out[res]++;
                lave_unwalked[inver_id[i]]--;
                lave_in[inver_id[i]]++;
            }
            node_to[inver_id[i]] = res;
        }
        puts("");
    }
}

signed main() {
    for (read(T); T; --T) {
        read(n);
        for (R int i = 1, x; i <= n; ++i) read(x), id[x] = i;
        for (R int i = 1; i <= n; ++i) head[i] = in[i] = 0;
        tot = 0, max_in = 0;
        for (R int i = 1; i < n; ++i) {
            int x, y;
            read(x, y);
            add(x, y);
            add(y, x);
            ++in[x], ++in[y];
            nodes[i] = make_edge(x, y);
            max_in = max(max_in, max(in[x], in[y]));
        }
        if (n <= 10) SubtaskForce::main();
        else if (max_in == n - 1) SubtaskAss::main();
        else if (max_in == 2) SubtaskChain::main();
        else SubtaskRandom::main();
    }
}

NOI-Online-T1-序列

其实这道题是全场最难的……

我这里给出一种并查集的做法。

首先我们把操作2中的 $u$ 和 $v$ 合并

对于操作1我们可以把他转化为操作2来做。

比如我们针对操作1给出 $(u,v)$ 和 $(v,t)$ 两条边，对 $(u,v)$ 进行同增，对 $(v,t)$ 进行同减。

这样就变成了 $u++,t--$ 了。

然后我们把操作2缩点，然后把操作1的边连到操作2缩的点上。

然后对操作1合并。

此时，图中的每个点的度数最多为一。

那么对于一条边 $(x,y)$ 如果 $a_{x}-b_{x}=a_{y}-b_{y}$ 那么就是YES；

对于一个自环 $(x,x)$ 如果 $(a_{x}-b_{x})$ 为偶数，那么就是YES；

对于一个度数为零的点 $x$ 如果 $a_{x}=b_{x}$ 那么就是YES；

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p2 == p1 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is_number (ch >= '0' && ch <= '9')

template < typename Type >
void read(Type& a) {
    a = 0; bool f = 0; char ch;
    while (!(ch = gc(), is_number)) if (ch == '-') f = 1;
    while (is_number) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
    a = (f ? -a : a);
}

template < typename Type, typename... Args >
void read(Type& t, Args&... args) {
    read(t), read(args...);
}

const int MAXN = 2e5 + 5;
int T, n, m, vis[MAXN];
int u[MAXN], v[MAXN];
int a[MAXN], b[MAXN];
int nxt[MAXN], to[MAXN];
int head[MAXN], tot;
struct UnionFindSet {
    int fa[MAXN];

    void init(int n) {
        for (int i = 1; i <= n; ++i)
            fa[i] = i;
    }

    int find(int x) {
        if (x ^ fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }

    void merge(int x, int y) {
        int u = find(x);
        int v = find(y);
        if (u ^ v) {
            fa[v] = u;
            a[u] += a[v];
            b[u] += b[v];
        }
    }
} ufs;

void add(int x, int y) {
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

signed main() {
    for (read(T); T; --T) {
        read(n, m);
        tot = 0;
        memset(head, 0, sizeof head);
        ufs.init(n);
        for (int i = 1; i <= n; ++i) read(a[i]);
        for (int i = 1; i <= n; ++i) read(b[i]);
        for (int i = 1, opt; i <= m; ++i) {
            read(opt, u[i], v[i]);
            if (opt ^ 1) vis[i] = 1, ufs.merge(u[i], v[i]), --i, --m;
        }
        for (int i = 1; i <= m; ++i) {
            add(ufs.find(u[i]), ufs.find(v[i]));
            add(ufs.find(v[i]), ufs.find(u[i]));
        }
        for (int i = 1; i <= n; ++i) {
            int t = ufs.find(to[head[i]]);
            for (int x = nxt[head[i]]; x; x = nxt[x])
                ufs.merge(t, ufs.find(to[x]));
        }
        for (int i = 1; i <= n; ++i) {
            if (head[i]) {
                int x = ufs.find(i);
                int y = ufs.find(to[head[i]]);
                if (x ^ y) {
                    if ((a[x] - b[x]) ^ (a[y] - b[y])) {
                        puts("NO");
                        goto there;
                    }
                }
                else {
                    if ((a[x] - b[y]) & 1) {
                        puts("NO");
                        goto there;
                    }
                }
            }
            else if (ufs.fa[i] == i) {
                if (a[i] ^ b[i]) {
                    puts("NO");
                    goto there;
                }
            }
        }
        puts("YES");
        there: ;
    }
}

NOI-Online-T2-冒泡排序

这道题我在考场上的做法很玄，本来是奔着40pts的部分分去的，结果爆零了(至今没找到原因)

我们设

$$bigger_{i}=\sum_{j=1}^{i-1}[a_{j}>a_{i}]$$

显然逆序对数量为 $\sum bigger$

于是问题就转化为了动态维护 $bigger$。

手玩几组数据后我们可以发现，每轮冒泡 $bigger$ 都会有一下的变化：

$$bigger_{i}=\max\{bigger_{i}-1,0\}$$

于是树状数组维护即可

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is() (ch >= '0' && ch <= '9')
template < typename Type >
void read(Type& a) {
    a = 0; bool f = 0; char ch;
    while (!(ch = gc(), is())) if (ch == '-') f = 1;
    while (is()) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
    a = (f ? -a : a);
}

template < typename Type, typename... Args >
void read(Type& t, Args&... args) {
    read(t), read(args...);
}

using namespace std;

const int MAXN = 2e5 + 5;
int n, m, bigger[MAXN], bucket[MAXN], a[MAXN];
long long bit[MAXN], init_inver_tot;

void Update(int x, long long y) {
    for (; x <= n; x += x & -x) bit[x] += y;
}

long long GetAnswers(int x) {
    long long res = 0;
    for (; x; x -= x & -x) res += bit[x];
    return res;
}

signed main() {
    read(n, m);
    for (int i = 1; i <= n; ++i) read(a[i]), init_inver_tot += (bigger[i] = i - 1 - GetAnswers(a[i])), bucket[bigger[i]]++, Update(a[i], 1);
    memset(bit, 0, sizeof bit), Update(1,  init_inver_tot), init_inver_tot = 0;
    for (int i = 0; i < n; ++i) init_inver_tot += 1LL * bucket[i], Update(i + 1 + 1, init_inver_tot - n);
    for (int i = 0, op, x; i < m; ++i) {
        read(op, x);
        if (n - 1 < x) x = n - 1;
        if (op ^ 2) {
            if (a[x + 1] > a[x]) {
                swap(a[x], a[x + 1]);
                swap(bigger[x], bigger[x + 1]);
                Update(1, 1);
                Update(bigger[x + 1]++ + 2, -1);
            }
            else {
                swap(a[x], a[x + 1]);
                swap(bigger[x], bigger[x + 1]);
                Update(1, -1);
                Update(--bigger[x] + 2, 1);
            }
        }
        else printf("%lld\n", GetAnswers(x + 1));
    }
    return 0;
}

NOI-Online-T3-最小环

全场最水的一道题，但是可怕的心理作用还是让我放弃了这道题。

首先有一个显然的结论，我们需要把这 $n$ 个数分为 $\gcd(n,k)$ 个环。

虽说是显然但是不画画图还真的玩不动

给一下图示意一下：

图中那个看起来像个五角星的东西其实就是个环

这个图中有 $\gcd(n,k)$ 个环，这就是我们的结论。

具体到实现，我们采用的是预处理出所有答案。

还有 $k=0$ 的情况需要特殊处理一下

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 5e5 + 5;
vector < int > integer(MAXN);
vector < long long > ans(MAXN);

int gcd(int x, int y) {
    return !y ? x : gcd(y, x % y);
}

signed main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &integer.at(i)), ans.at(0) += (long long)integer.at(i) * (long long)integer.at(i);
    sort(integer.begin() + 1, integer.begin() + 1 + n);
    for (int i = 1; i <= (n >> 1); ++i) {
        if (!(n % i)) {
            int t = n / i;
            vector < int > process(MAXN);
            int tot = 0;
            for (int j = 2; j < t; j += 2) process.at(++tot) = j;
            process.at(++tot) = t;
            for (int j = t - 1 - (t & 1); j > 0; j -= 2) process.at(++tot) = j;
            for (int j = t + 1; j <= n; ++j) process.at(j) = process.at(j - t) + t;
            for (int j = 1; j <= n; ++j)
                if (!(j % t)) ans.at(i) += (long long)integer.at(process.at(j)) * (long long)integer.at(process.at(j + 1 - t));
                else ans.at(i) += (long long)integer.at(process.at(j)) * (long long)(integer.at(process.at(j + 1)));
        }
    }
    for (int i = 0, x; i < k; ++i) scanf("%d", &x), printf("%lld\n", ans.at(x ? gcd(n, x) : 0));
    return 0;
}

总结

（其实我不是很会写这玩意儿）

果然心理素质还是不行……错过了T3这样的水题。

总体来说，把握住机会，把题目都当作大白菜（雾）。

然后就是多去做题吧，题量多少都不嫌多。

就这样（

普及组口胡

说了是口胡所以没代码不保证正确/xyx

至于题目难度这是NOIOL不是NOIpOL给了搬出题人放飞自我的空间。

T1：普通NOIp普及难度，各位巨佬随便切

T2: 基础多项式，会的人就很套路。不会的话就n方dp骗骗分

T3: 这道题我不太确定，应该是Floyd+矩阵。

完结撒六花