跃迁引擎启动

发表于 分类于 阅读次数：

模板

线段树优化建图 + 拓扑排序。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 998244353;
const int maxn = 500000 + 5;

vector<int> edge[maxn];
int n, b[maxn], a[maxn], pos[maxn], id[maxn], deg[maxn];

void build(int l, int r, int rt) {
    pos[rt] = -1;
    if (l == r) {
        id[l] = rt; pos[rt] = l;
        return ;
    }
    int m = (l + r) >> 1;
    edge[rt << 1].push_back(rt);
    edge[rt << 1 | 1].push_back(rt);
    deg[rt] += 2;
    build(lson); build(rson);
}
void link(int L, int R, int p, int l, int r, int rt) {
    if (L <= l && r <= R) {
        edge[rt].push_back(p); 
        deg[p]++;
        return ;
    }
    int m = (l + r) >> 1;
    if (L <= m) link(L, R, p, lson);
    if (R > m) link(L, R, p, rson);
}

int main(){
    scanf("%d", &n); 
    for (int i = 0; i < n; i++) scanf("%d", b + i);
    build(0, n - 1, 1);
    for (int i = 0; i < n; i++) {
        if (b[i] % n == i) continue;
        int s = b[i] % n;
        if (s < i) link(s, i - 1, id[i], 0, n - 1, 1);
        else {
            link(s, n - 1, id[i], 0, n - 1, 1);
            if (i) link(0, i - 1, id[i], 0, n - 1, 1);
        }
    }
    int last = 0;
    priority_queue<PII,vector<PII>,greater<PII> > pq;
    for (int i = 0; i < n; i++) {
        if (deg[id[i]] == 0) pq.push({b[i], id[i]});
    }
    while (!pq.empty()) {
        PII t = pq.top(); pq.pop();
        if (t.first != -1) a[last++] = t.first;
        for (int& v: edge[t.second]) {
            deg[v]--;
            if (deg[v] == 0) {
                if (pos[v] == -1) pq.push({-1, v});
                else pq.push({b[pos[v]], v});
            }
        }
    }
    for (int i = 0; i < n; i++) printf("%d%c", a[i], " \n"[i == n - 1]);
    return 0;
}

发表于 更新于 分类于 阅读次数：

A Darker and Darker

给定一个 $n\times m$ 的 $01$ 矩阵，求 $01$ 之间的最大曼哈顿距离。

$KD-Tree$ 询问最近点（误

把黑点加进去 $BFS$ 扩展即可。

B LRUD Game

有 $n\times m$ 的地图，有一个棋子一开始在 $(x,y)$ 处，有两个 LRDU 操作序列 $S,T$，两人分别用这两个操作序列移动棋子，在 $i$ 轮，第一个人可以选择是否用 $s$ 的第 $i$ 个操作，第二个人选择是否用 $t$ 的第 $i$ 个操作，第一个人要将棋子移出地图，第二个人组织第一个人，求第一个人是否能获胜。

其实上下左右四个方向是独立的，分成 $4$ 个方向贪心即可，注意边界。

C Removing Coins

给定一棵无根树，每个结点上有一枚硬币，两人轮流操作。操作是将一个有硬币的结点上所有硬币拿走，然后其他所有结点上的全部硬币向选择的这个点的方向移动一步，判断是否先手必胜。

考虑一个操作，如果选择当前的直径的端点，那么直径长度减一，否则选择任何其他点，都会导致直径长度减二。

因此，我们只需要关注直径的变化即可。每次操作实际上是从 $n$ 个石子里面，要么选 $2$ 个，要么选 $1$ 个。特别地，$2$ 个石子时只会选 $1$ 个。

也就是说，$1$ 是必胜态，$2$ 是必败态，$3$ 必胜态，$4$ 转移到 $2$，$5$ 转移到 $3$ 和 $4$，因此归纳易得，$n$ 模 $3$ 余 $2$ 时是必败态。

阅读全文 »

发表于 更新于 分类于 阅读次数：

模板

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
ll qpow(ll x, ll n) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return r;
}
ll Inv(ll x) {
    return qpow(x, mod - 2);
}

ll fac[maxn], a[20], inv[maxn];
struct Lagrange {
    // 1-based
    ll cc[20]; int n;
    void build(int nn) {
        n = nn;
        for (int i = 1; i <= n; i++) {
            cc[i] = Inv(fac[i - 1] * fac[n - i]) * a[i] % mod;
            if ((n - i) % 2 == 1) cc[i] = (mod - cc[i]) % mod;
        }
    }
    ll get(ll x) {
        if (x <= n) return a[x];
        ll ans = 0, tmp = 1;
        for (int i = 1; i <= n; i++) tmp = tmp * (x - i) % mod;
        for (int i = 1; i <= n; i++) {
            ans += tmp * inv[x - i] % mod * cc[i] % mod;
            if (ans >= mod) ans -= mod;
        }
        return ans;
    }
} f;
阅读全文 »

发表于 更新于 分类于 ， 阅读次数：

A Inscribed Figures

B Ugly Pairs

C Match Points

给定序列 $a$，求最多能匹配多少对差值绝对值大于 $z$，一个位置不能匹配多次。

显然，排序。我们不能对于每个数贪心的选最小的匹配，但是我们注意到答案最大是 $[{ n\over 2}]$，从前后一半选显然最优。

对于前一半，在后一半匹配一个最小的即可。

D 0-1-Tree

给定一棵带 $01$ 权值的无根树，求多少条形如 $111\dots 111$， $000 \dots 000$ 和 $000\dots000111\dots111$ 的路径。

并查集维护 $1$ 边连接和 $0$ 边连接的点集，枚举每个点作为第三种路径分界的情况，即 $1$ 和 $0$ 的联通块大小减一的乘积。

E Special Segments of Permutation

给定一个 $1$ 到 $n$ 的排列，求有多少对 $(l,r)$，满足 $a[l]+a[r]=\max_{i=l}^r a[i]$。

考虑枚举最大值位置，左右两边选择一对能够凑成最大值，只需要枚举短的一边，判断配对的另外一个数是否在另外一边。

复杂度证明类似于启发式合并，$O(n\log n)$。

阅读全文 »

发表于 更新于 分类于 ， 阅读次数：

A Reverse a Substring

B Game with Telephone Numbers

C Alarm Clocks Everywhere

D Beautiful Array

给定一个序列，允许将一个连续区间内所有数乘 $x$，求最大连续子段和。

考虑 $dp[i][3]$，前 $i$ 个位置的答案，最后一次用 $x$ 的最大值以及从来没用过 $x$ 的最大值。

E Guess the Root

猜一个 $10$ 次多项式在模意义下的根，最多询问 $50$ 次多项式在某点的取值。

$11$ 次询问插出多项式，暴力枚举即可。

阅读全文 »

发表于 更新于 分类于 阅读次数：

A Love “A”

B Hate “A”

C Tree Diameter

给一棵 $100$ 个点的树，询问 $9$ 次，每次询问两个点集之间的最大距离，猜树的直径。

按照线段树类似的分治结构，每层的左区间放在一边询问，右区间放在另一边询问，层数最大为 $9$ 层。

D Frog Jumping

青蛙在数轴上跳，每次正方向跳 $a$ 步或者反向跳 $b$ 步，记 $f(x)$ 表示青蛙跳在 $[0,x]$ 区间内最多能走到多少个点。

求 $\sum_{i=1}^m f(i)$。

显然当 $x$ 很大时，所有 $\gcd(a,b)$ 的倍数都可以被跳到，贡献可以枚举右端点。

考虑这个分界线可能会在哪，发现 $x \ge a+b$ 时，所有 $\gcd(a,b)$ 的倍数都跳到了。

证明：

对于任意一个可能跳到的位置 $p=ax-by$ 且 $0 \le p \le a+b$。

若 $p \ge b$，则它肯定可以往回跳 $b$。

若 $p \le b$，则它肯定可以往后跳 $a$。

于是，由于初始位置 $0$ 可以被跳到，那么这里面所有位置都可以被跳到。

回到原题，对于在 $[0,a+b)$ 内范围的点对答案贡献，只要暴力模拟出每个位置的第最近位置，若回到一个去过的地方则停止。

对于 $[a+b,m]$ 的贡献，考虑一个公差为 $\gcd(a,b)$ 的等差数列，求和即可。

E Hot is Cold

给定一个序列，有 $q$ 次操作，每次操作将 $ > x $ 或 $ < x$ 的数变成相反数。

对正值域维护线段树，维护区间赋值和区间翻转标记，以及单纯的区间翻转标记。

以大于为例，大于正的就是区间赋值，大于负的就是一部分区间翻转，一部分区间赋值。

注意打标记的细节。

F Leaf Partition

将一颗有根树的叶子划分到几个不相交的子图中，子图为包含叶子的最小子图，求方案数。

考虑树形 $dp$，一个点 $u$ 划分为 $3$ 种不相交的状态，$u$ 不在儿子中的任何一个子图，$u$ 在儿子中的子图内，但是只连了一条边，不满足最小子图条件，$u$ 和儿子连成子图，依次为 $dp[u][0,1,2]$。

初始状态为 $dp[leaf][2]=1$，否则 $dp[u][2]=0$。

考虑状态转移，假设对于 $u$ 已经计算了 $dp[u][0,1,2]$，枚举到下一个儿子。

对于 $dp[u][2]$，假如结点 $v$ 连接到 $u$ 上，那么可以和 $dp[u][1]$ 和 $dp[u][2]$ 的状态连接，$v$ 的状态也是 $dp[v][1]$ 和 $dp[v][2]$，假如 $v$ 没有连接到 $u$ 上，那么就是用 $dp[u][2]$ 的状态和 $v$ 不连接上来的状态合并，也就是 $dp[v][0]$ 和 $dp[v][2]$。

对于 $dp[u][1]$ 和 $dp[u][0]$ 也能类似的考虑，注意转移之间的影响。

阅读全文 »

发表于 分类于 阅读次数：

真 nm 自闭（呲牙。

A Maxim and Biology

B Dima and a Bad XOR

给定一个 $n \times m$ 的矩阵，每一行选一个，构造一种异或和不为 $0$ 的情况。

枚举每个二进制位，统计有多少个位置必选 $1$，其他位置可选 $1$ 的，选上使得 $1$ 的总数为奇数。

C Problem for Nazar

D Stas and the Queue at the Buffet

给定 $n$ 对数 $(a_i,b_i)$，为这些数字重新安排位置，假设 $i$ 在位置 $j$ 上，他的权值是 $(j-1)\cdot a_i + (n-j) \cdot a_i$，求最小权值和。

先假设所有每个位置都选上了 $a_i$，只要在选 $b_i$ 时把 $a_i$ 的影响消除即可。

注意到越小的数系数应该越小，对 $b_i-a_i$ 排序，乘上贡献即可。

E Number of Components

给定 $n$ 个在 $[1,n]$ 范围内的数，记 $f(l,r)$ 表示，选出所有范围在 $[l,r]$ 内的数，剩下的数组成了多少条线段。求 $\sum_{l=1}^n \sum_{r=l}^n f(l,r)$。

考虑每个点作为一个线段左端点的贡献。

如果 $a_i \ge a_{i-1}$，那么左端点的范围是 $[a_{i-1}+1,a_i]$，右端点的范围是 $[a_i,n]$，否则类似的计算贡献。

F Sonya and Informatics

给定一个 $01$ 序列，做 $k$ 次操作，每次等概率选一对数交换，求最后排成不减序列的概率。

显然，顺序不影响，只要前面都是 $0$，后面都是 $1$ 即可，设有 $m$ 个 $0$，考虑 $dp[i]$ 表示前面 $m$ 个有 $i$ 个 $0$。

于是有转移方程

状态数只有 $100$，转移次数很大，注意到转移矩阵是固定的，矩阵快速幂即可。

阅读全文 »

发表于 分类于 ， 阅读次数：

注意不要忘记原点变成缩点后的新点。

模板

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
int cnt, bel[maxn]; // important!
namespace Tarjan {
    int tot, dfn[maxn], low[maxn], st[maxn], top, vis[maxn];
    void clear(int n) {
        tot = top = cnt = 0;
        for (int i = 1; i <= n; i++) {
            edge[i].clear(); dfn[i] = vis[i] = bel[i] = 0;
        }
    }
    void dfs(int u, int f) {
        dfn[u] = low[u] = ++tot;
        st[++top] = u; vis[u] = 1;
        int k = 0;
        for (int& v: edge[u]) {
            if (v == f && !k) {
                k++; continue;
            } 
            if (!dfn[v]) {
                dfs(v, u); low[u] = min(low[u], low[v]);
            } else if (vis[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            cnt++; int t = 0;
            do {
                t = st[top--];
                bel[t] = cnt;
                vis[t] = 0;
            } while (t != u);
        }
    }
    void scc(int n, vector<int> * g) {
        for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan::dfs(i, 0);
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i <= n; i++) {
            int u = bel[i];
            for (int& x: edge[i]) {
                int v = bel[x];
                if (u != v) {
                    g[u].push_back(v);
                }
            }
        }
    }
}
阅读全文 »