跃迁引擎启动

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

A Eating Soup

B Cat Party

给定序列 $a$，求一个最长前缀，满足删除一个数后，剩下每种数的出现次数相同。

维护每种数的出现次数，每种出现次数的出现次数。

显然，有答案时，出现次数的种类最多为 $2$，分类讨论判断一下即可。

C Power Transmission

给定 $1000$ 个点，两两连着直线，求有多少直线相交，重合的直线只算一次。

只需要将直线去重即可，对于每种斜率，统计即可。

把直线转化为一般方程去重即可。

D Mysterious Code

有一个未知串 $p$，两个模式串 $s$ 和 $t$，要求最大化 $p$ 串中 $s$ 串出现次数减去 $t$ 串出现次数。

对 $s$ 和 $t$ 串建出 $fail$ 指针，记 $dp[t][i][j]$ 表示 $p$ 串前 $t$ 个匹配到两个串 $i$ 和 $j$ 位置时的最大值。对于每个新字符，如果是通配符就跑所有字母的转移，转移就是在两个 $fail$ 指针上找到下一个位置，并更新计数值。

阅读全文 »

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

模板

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
int main() {
    scanf("%d", &n);
    vector<int> st;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", h + i);
        while (!st.empty() && h[st.back()] > h[i]) {
            r[st.back()] = i - 1;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && h[st.back()] > h[i]) {
            l[st.back()] = i + 1; st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (!r[i]) r[i] = n;
        if (!l[i]) l[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, 1ll * h[i] * (r[i] - l[i] + 1));
    }
    printf("%lld\n", ans);
    return 0;
}

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

模板

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

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]$ 也能类似的考虑，注意转移之间的影响。

阅读全文 »