Ⅰ. 基础模型

A. 01背包

即每个物品要么选，要么不选。我们可以设状态 $f_{i,j}$ 表示考虑前 $i$ 个物品总体积 $\leq j$ 的最大价值，于是状态转移如下：

$$
f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)
$$

前一个表示不选第 $i$ 个物品的情况，后一个表示选第 $i$ 个物品的情况。

初始化：$f_{i,j}=0$ 。

考虑怎么统计方案数。状态定义一样，但是表示的是方案数，于是又有转移方程如下：

$$
f_{i,j}=f_{i-1,j}+f_{i-1,j-w_i}
$$

初始化：$f_{i,0}=f_{0,j}=1$ 。

考虑优化空间，我们发现，每次转移只会用到上一维的状态，于是就可以把DP数组压成一维。代码如下：

1
2
3
4
5

for (int i = 1; i <= n; i++) {
	for (int j = m; j >= w[i]; j--) {
		f[j] = max(f[j], f[j-w[i]]+v[i]);
	}
}

B. 完全背包

就是在01背包的基础上每个物品可以选任意多个。状态设计同01背包，转移如下：

$$
f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)
$$

区别在哪里呢？完全背包可以从当前的 $i$ 的状态转移过来，因为一个物品可以一选再选。

初始化、变形成方案数统计和压空间和上面的01背包大同小异，不过多赘述。贴个优化空间代码：

1
2
3
4
5

for (int i = 1; i <= n; i++) {
	for (int j = w[i]; j <= m; j++) {
		f[j] = max(f[j], f[j-w[i]]+v[i]);
	}
}

C. 多重背包

更好的阅读体验

这道题难点在于建图，建完图之后用 $\text{Dijkstra}$ 或 $\text{Floyd}$ 跑个最小环就行了。

我的建图方法和其他题解所赘述的有所不同（在同机房dalao的指点下想到的）。

建图

我们将题目中读入的边看做点，题目中的边权在这里就是点权，考虑边权的设计。不难发现，当篱笆可以组成环时，将两个点间的边权定义为其点权之和，那么环的权值就是所有边权之和的 $\frac{1}{2}$ （因为每个点权都被加了两次）。

最小环

我用的是 $\text{Dijkstra}$ 跑最小环。大致流程如下：

• 枚举一条边 $(u,v)$ 并删除；

• 从这条边的一个端点 $u$ 开始跑 $\text{Dijkstra}$ 到另一个端点 $v$ ，可以获得一个值 $dis_v$ 表示不经过 $(u,v)$ 时两点的最短路；

• 最后统计全局最小环为 $ans=\min(w(u,v)+dis_v)$ 。在本题中最终答案为 $ans\times\frac{1}{2}$ 。

正确性显然。

一个小问题

有细心的读者会发现，如果我们将边转化成点，会出现一个问题：

按上文的找最小环的方法会找到三条边都交于一点的“环”，这样的答案是不合法的，因此我们要规定找最小环时，必须是从一边入另一边出。可以通过开一个 $flg_{u,v}$ 表示 $u$ 这个点，通往 $v$ 的边是在原图的哪一边。

但是由于我们读入时没有处理，即我们不知道谁的左边是谁的右边，因此在判断时要统一一个公共点来判断，于是在跑 $\text{Dijkstra}$ 时处理一个 $f$ 表示上一个点。具体实现间代码。

代码

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

#include <bits/stdc++.h>
using namespace std;

int n;
int g[101][101];
bool flg[101][101];

struct node{
	int dis, u, f;
	bool operator<(const node& b) const {
		return dis > b.dis;
	}
};
priority_queue<node> q;
int dis[101];
bool vis[101];

int s, t;

bool dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s] = 0;
	q.push({0, s, 0});
	while (!q.empty()) {
		int u = q.top().u, f = q.top().f;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int v = 1; v <= n; v++) {
			if (!g[u][v]) continue;
			if (u == s && v == t) continue;
			if (u == t && v == s) continue;
			if (u != s && flg[u][f] == flg[u][v]) continue;
			if (dis[v] > dis[u]+g[u][v]) {
				dis[v] = dis[u]+g[u][v];
				q.push({dis[v], v, u});
			}
		}
	}
	return dis[t]!=0x3f3f3f3f;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int k, v, n1s, n2s, x;
		cin >> k >> v >> n1s >> n2s;
		for (int i = 1; i <= n1s; i++) {
			cin >> x;
			g[k][x] += v, g[x][k] += v;
			flg[k][x] = 0;
		}
		for (int i = 1; i <= n2s; i++) {
			cin >> x;
			g[k][x] += v, g[x][k] += v;
			flg[k][x] = 1;
		}
	}
	int ans = 0x3f3f3f3f;
	for (s = 1; s <= n; s++) {
		for (t = s+1; t <= n; t++) {
			if (!g[s][t]) continue;
			if (dijkstra()) {
				ans = min(ans, (g[s][t]+dis[t])/2);
			}
		}
	}
	cout << ans;
}

进入博客食用更香！

一道贪心题。

无解

很明显的，当 $n=1$ 时，因为小I先手，小J可以直接收牌，所以小I无法获胜。

策略

Case 1 小 I 手上没有任何能配对的牌

也就是说对于每一对牌总有一张在小I的手上。

此时我们应该先打出对面出牌序列中最后一张牌，随后对面出什么牌我们就跟着出什么牌，确保小J出的牌能被我们立刻收掉。

最后对面出他的最后一张牌把我们出的第一张牌收掉，此时我们手上的牌全是成对的，对方只有一对牌。随便出一张手上的牌把对面的一张牌收掉，对面下次出牌就必输。

Case 2 小 I 贪心每一回合

此时我们手中必有一对牌。我们能用这对牌来干嘛呢？一开始我们埋下这张牌作为保险，如果后面对面想收牌（牌堆里的或是我手上的），我们就打出这对牌的另一张把整个牌堆清空。

我们可以像 $\text{Case 1}$ 一样，对面出牌我们紧跟着收牌 ，考虑以下几种情况（以下 $A_i$ 指我们出的编号为 $i$ 的牌，$B_i$ 指对面出的编号为 $i$ 的牌，$[\cdot\cdot\cdot]$ 表示当前时刻之后的假设情况）：

• $A_?…B_i[…A_i]$ 以及 $A_?…B_i[…B_i]$ 这两种情况都会对我们的策略造成威胁，因此在这个时候应该立即收掉所有牌。

• $A_i…A_iB_j[…]$ 这种情况会使我们误收场上所有牌，导致对方出的 $B_j$ 要么收不掉（这意味着我们要花额外的步数去收这张牌）或是对面会在后面某一时刻清场（这意味着我们要么输，要么步数更多）。

• 其余情况按正常的成对出牌。

基于以上几点对方就不能在任何时刻收牌，因为我们要么快人一步把前面的收了要么把他出的第一张牌直接收了，而此时也会达到步数最小值，不难发现这个步数最小值是 $n$ 。

* 蒟蒻个人理解，可能有些问题欢迎大家指出！

码

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
76
77
78
79

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300010;

int n;
int s[2*MAXN], top, cnts[MAXN];
int mine[MAXN];
int a[MAXN];
queue<int> q;

void pop(int x) {  // 清理公共牌堆
    while (s[top] != x) {
        cnts[s[top]]--;
        mine[s[top]]++;
        q.push(s[top]);
        top--;
    }
    cnts[s[top]]--;
    mine[s[top]]++;
    q.push(s[top]);
    top--;
}

void push(int x) {  // 打牌
    s[++top] = x;
    cnts[x]++;
}

int main() {
    scanf("%d", &n);
    if (n == 1) return printf("-1")&0;  // 无解
    for (int i = 1; i <= n; i++) {
        mine[i] = 2;
    }
    int st = -1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a+i);
        mine[a[i]]--;
    }
    for (int i = 1; i <= n && st == -1; i++) if (mine[i] == 2) st = i;
    for (int i = 1; i <= n; i++) {
        for (int j = mine[i]-(i==st); j >= 1; j--) q.push(i);
    }

    if (st == -1) {  // 没有成对的牌
        printf("%d\n%d", n+2, a[n]);
        for (int i = 1; i < n; i++) printf(" %d", a[i]);
        printf(" %d %d", a[1], a[1]);
        return 0;
    }

    printf("%d\n%d", n, st);
    mine[st]--;
    push(st);
    push(a[1]);
    for (int i = 2; i <= n; i++) {
        int x = a[i];
        if (mine[x] || cnts[x]) {  // 有威胁。清空牌堆
            printf(" %d", s[1]);
            pop(s[1]);
        } else {
            if (q.front() == s[1]) {  // 会误收牌堆
                q.push(q.front());  // 将队首移到队尾
                q.pop();
            }
            int nxt = q.front();
            printf(" %d", nxt);
            if (cnts[nxt]) {
                pop(nxt);
            } else {
                push(nxt);
                mine[nxt]--;
                q.pop();
            }
        }
        push(x);
    }
}

考试总结

Task 1

正解

性质题，找规律。

规律如下：

从 $n=15$ 开始：
$108,188,200,208,288,688,888,1088,1888,2008,2888,8888\dots$

容易发现 $a_n=a_{n-7}\times10+8\quad(n \geq 22)$

前14个要特判。

代码

1

无

关键点

暴力找规律。

死因

20 开头的规律没找到，就是没打暴力找规律。

Task 2

正解

搜索。

优化

这道题可以用 十字链表（Dancing Links X） 加速，但是爆搜就能跑出 $400\text{ms}$ 的好成绩。

别名：双向循环十字链表。

为什么能跑这么快

关键点：

• 对于这种搜索时间最不利的是 $5 \times 6$ 的矩阵，并且是无解的情况。
• 正常来说，如果不要求不能重复走点，时间复杂度最坏为 $O(2^{4} \times 3^{14} \times 4^{16})$ ，即四个角（4个）上的点有两种走法，边上的点（14个）有三种走法，内部的点（16个）有四种走法。
• 但是不能重复走点的情况下，时间复杂度最坏为 $O(1^{4} \times 2^{14} \times 3^{16})$，但是考虑到实际情况，加一个可行性剪枝，最后 $\text{dfs()}$ 函数大概只会运行到 $5 \times 10^6$ 次。
• 爆搜敢冲就能过。

题目来源

《永远的七日之都》

代码

1

无

死因

1

for (int i = 0; i <= n; i++)  // wssb

Task 3

正解

以 $dp$ 为辅助的搜索题。

说真的，这道题不难。一切的思路都是自然而然的，从爆搜到可行性剪枝再到用 $dp$ 完成可行性剪枝，最后实现的代码难度也不高。

关键点

$dp$ 可能不是一道题的全部而是一道题的部分。

思路

• 先想爆搜，同一位按字典序从大到小搜，期望得分：$30-40;pts$。
• 再想剪枝，用 $dp$ 判定后面有没有可能有解，计算一个点后最多能获取到的权值，再加上已经搜到的权值看它能不能 $\geq x$ 。
• 怎么做 $dp$ ？记录 $dp$ 长度和最后一位，预处理 $dp$ 时间复杂度为 $O(4n)$ 。整个算法时间复杂度见课后思考。

课后思考

• 整体时间复杂度是 $O(n+k)$ 还是 $O(nk)$ ？理论分析应该是 $O(n+k)$ 。

代码

1

无

死因

并没有死，打了暴力。还是全场唯一得分点（$30;pts$）。

但是事实上我的暴力打得还有优化空间且有一个小问题。

Task 4

正解

区间 $dp$ 。

思路

• 考虑朴素区间 $dp$ ，对于每个 $l\sim r$ 区间，枚举小区间并转移，时间复杂度 $O(n^4)$ 。
• 但是这种做法会 $\text{WA}$ 掉，因为这样记录状态会有情况没考虑到。所以考虑重设状态 $f_{i,j,max,min}$ 表示区间 $i\sim j$ 内已经通过多次操作后剩下的最大值为 $max$ 、最小值为 $min$ 时，所花的最小代价。而后我们定义 $ans_{i,j}$ 为 $i\sim j$ 这段区间被选空的最终答案（就是题目中说的那个最后输出的答案）。
• 接下来考虑怎么转移。$ans_{i,j}$ 的转移很简单，就是 $ans_{i,j}=max(f_{i,j,max,min}+a+b\times(max-min))$ 。而 $f_{i,j,max,min}$ 的转移，首先应该枚举中间断点 $k$ 就应该有以下三种情况：
  • $min$ 与 $max$ 都在左边，右边被选空：$f_{i,j,max,min}=f_{i,k,max,min}+ans_{k+1,j}$ 。
  • $min$ 与 $max$ 都在右边，左边被选空：$f_{i,j,max,min}=ans_{i,k}+f_{k+1,j,max,min}$ 。
  • $min$ 与 $max$ 左右两边都有：$f_{i,j,max,min}=f_{i,k,max,min}+f_{k+1,j,max,min}$ 。
• 容易发现的是，这样转移肯定不会少考虑情况，接下来就是考虑这么转移是否会多考虑情况？如果多考虑了，对答案有没有影响？
• 【这里不会】（zhw看到了comment一下）
• 结论：会多考虑情况但是这些情况不会比答案更优。
• 注意点：$w_i \leq 1000$ ，需要离散化处理。

来源

THUSC 2016 成绩单

代码

1

无

区间DP总结

• 区间DP是变化之神！
• $\text{Link Start!}$

通过例题看看区间DP的一些套路和新的思路。

不如按题目分类来说。

A~E 普通/模板区间DP

• 能量项链——普通区间DP
• 石子合并（加强版）——四边形不等式优化（不要求掌握）
• 【USACO 3.3.5】A Game游戏 IOI’96——带了博弈论的区间DP（个人觉得有点意思）
• 做错的作业——括号匹配类型的区间DP
• 【CQOI 2007】涂色——涂色类型区间DP

F,G 凸多边形区间DP

这一类型的DP特点是建立模型比较难。

要点梳理：

• 无论从哪一个点开始都一样，因此不必拆环成链。
• 状态定义为：$f_{i,j}$ 表示将 $i\sim j$ 这一段点的区间转化为三角形的最小价值。
• 状态转移为：$f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k,j}+\text{cost}(i,j,k))$ ，即 $k$ 是两个子区间的公共端点， 而将他们合并后能组合出新的三角形 $\Delta A_iA_jA_k$ ，因此要加上这个新三角形造成的权值。

H 字符串折叠

我认为这道题的思路是捋得最清的，因为这道题真的很简单。

大致思路就是有两种转移：一是组合两段已压缩的区间，二是将这段区间压缩，时间复杂度大致为 $O(n^4)$ ，能刚刚好卡着过（据说用预处理或哈希或KMP找最长重复子串的长度能够将这道题卡到 $O(n^3)$ 的时间复杂度，然鹅我不会）。

R 压缩

这也是一道压缩字符串的题目。

但是这里对 $M$ 和 $R$ 的处理要更为复杂。

具体而言，这道题的 $f_{i,j,k}\quad(1\leq i\leq j\leq n,k\subset{0,1})$ 多了一维，用于标记 $i\sim j$ 这段区间内是（$1$）否（$0$）存在 $M$ 。

状态转移：

• $f_{i,j,0}=f_{i,k,0}+j-k$
• $f_{i,j,1}=\min(f_{i,k,0},f_{i,k,1})+\min(f_{k+1,j,0},f_{k+1,j,1})$
• $f_{i,j,0}=f_{i,mid,0}+1\quad\text{when }[i,j]\text{ can compress}$

J 表达式的亿种可能性

最有意义的题目之一。

维护的 $f_{i,j}$ 就是答案所求，关键就在转移。

弄清楚以下几点：

• $\times$ 的转移不需要别的东西，只需要 $f_{i,j}=f_{i,k}\times f_{k+1,j} \times\text{val}$
• $+$ 和 $-$ 的转移需要考虑左边的括号个数和右边的括号个数（详见第一次提交内的代码推导），最终转移式为：$f_{i,j}=((j-k-1)!f_{i,k}+(k-i)!f_{k+1,j})\times\text{val}$
• 但是以上转移式只考虑了先放完左边的括号再放右边的括号，然而，我们可以左右交替来回放，并且，左边内括号的顺序已经是我们在 $f_{i,k}$ 中内定好的了。因此 $\text{val}=\frac{(j-i-1)!}{(k-i)!(j-k-1)!}$ 作为系数。

M 有味道的数字

最具有启发性的一题。

这道题有几个性质需要搜索搜出来——只有 $3$ 和 $7$ 无法表示，表示 $5000$ 以内的数字最多只会用到长度为 $11$ 的前缀。

$f_{i,j}$ 表示 $i\sim j$ 这段区间内能表示出来的值（是个数组）这种思想有个很NB的名字叫做 **离散_____**（人话：打表）。

即用 $\text{vector}$ 存储值，单次转移时间复杂度就是 $O(nm)$ （ $n,m$ 表示合并的两个 $\text{vector}$ ） ，玄学下降！

而转移嘛……人人都会。

Q 单调栈

搜索最上牌面的一题。

这道题思路没什么好说的，只是注意一下有的时候记忆化搜索比循环区间DP好写。

区间DP的一点小知识

我个人一般会这么打区间DP：

1
2
3
4
5
6

for (int len = 2; len <= n; len++) {
	for (int i = 1; i+len-1 <= n; i++) {
		int j = i+len-1;
		// ...
	}
}

然而这么打常数是比较大的，优化写法：

1
2
3
4
5

for (int j = 2; j <= n; j++) {
	for (int i = j-1; i >= 1; i--) {
		// ...
	}
}

据说这样能优化很多。

我认为区间DP还有一类很重要的题，典型例题：关路灯

区间DP的特征

• 在操作中需要将两端区间合并，合并时存在固定的转移关系。
• 在操作中需要将子区间转移。

怎么看需不需要多开维数

很明显，当目前的状态定义会出现明显重复统计或是限制条件不够时要多开空间。

十一月

开这个坑已经是月底了，记录一下几个题目。

Atcoder Beginning Contest 330 E - Mex and Update

我认为这是一道不错的性质题。

当时在考场上看出了这道题有性质，但是并没有推导出性质。性质主要就是对于一个长度为 $n$ 的数组，其 $\text{mex}$ 一定是在 $0$ 到 $n$ 内的，至于怎么证明……简单抽屉原理。

然后就是怎么维护这个 $\text{mex}$ ，可以用 $\text{set}$ 记录没有在数组中的 $0$ 到 $n$ 的数的集合，因为 $set$ 可以自动排序，所以查询就是 $\text{set.begin}$ ，维护时还需要维护每个数在数列中的出现次数，不然会误加元素进 $\text{set}$。没了。

Codeforces 1900 E - Transitive Graph

最考码力の一题。

首先还是有个性质（还没严格证明）：如果一堆点在原图SCC内，那么最后它们一定能化成一个完全图——这个SCC内每个点，都能直接互相到达。

因此，我们可以先缩点，然后对于缩出来的点建DAG跑拓扑排序，答案也可以在拓扑过程中更新。That’s all.

果果要求掌握的东西当然是要掌握的咯。

最终形式

$$
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
$$

证明

$$
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
$$

解释一下，首先，这里的 $\gcd(j,n)$ 一定是只有一个值，不可能说有两个不同的值来自同一个 $\gcd(j,n)$ ；其次，为什么这一坨东西等于 $n$ 呢，因为其一说的每个 $\gcd$ 都有唯一确定的值，因此我们只需要枚举 $\gcd$ 的每种可能并枚举所有 $n$ 以内的正整数就必然有且仅有一种可能的 $d$ 满足每组 $\gcd(j,n)=d$ 。

换句话说，因为一个 $\gcd(j,n)$ 只对应唯一一个 $d$ ，这里我们把所有可能的 $\gcd$ 的值和所有的 j 都枚举了自然其值也就等于 $n$ 了（主要就是说明一个不重也不漏）。

$$
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
$$

这里没什么好说的，目的是把 $\gcd$ 的值化为 $1$ 后能转化成欧拉函数的形式。

$$
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
$$

$$
\large\therefore n=\sum_{d|n}{\varphi(d)}
$$

这里是因为每个 $\frac{n}{d}$ 和 $d$ 是对应的，所以能如此转化。

例题

• 多组数据，每组数据给出一个数 $n$ ，求 $\sum_{i=1}^{n}{\gcd(i,n)}$ 。

利用欧拉反演，改变题目公式如下：

$$
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
$$

拆开 $\gcd$ 得：

$$
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
$$

改变循环顺序得：

$$
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
$$

化简得：

$$
\sum_{d|n}\varphi(d)\frac{n}{d}
$$

关于推导式子就没了。这时只需将 $\text{phi}$ 预处理，每次询问 $\sqrt{n}$ 复杂度。

• CF1900D Small GCD

先排序，可得以下原公式：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
$$

带入欧拉反演如下：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
$$

化简：

$$
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
$$

其中我们可以边枚举 $i$ 边处理 $cnt_d$ ，并预处理 $\varphi(x)$ 。因此总时间复杂度为 $O(M+TN\sqrt{M})$ ，$M$ 表示 $a_i$ 的值域，还会有一些小常数，会有点卡常。

果果要求掌握的东西当然是要掌握的咯。

最终形式

$$
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
$$

证明

$$
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
$$

解释一下，首先，这里的 $\gcd(j,n)$ 一定是只有一个值，不可能说有两个不同的值来自同一个 $\gcd(j,n)$ ；其次，为什么这一坨东西等于 $n$ 呢，因为其一说的每个 $\gcd$ 都有唯一确定的值，因此我们只需要枚举 $\gcd$ 的每种可能并枚举所有 $n$ 以内的正整数就必然有且仅有一种可能的 $d$ 满足每组 $\gcd(j,n)=d$ 。

换句话说，因为一个 $\gcd(j,n)$ 只对应唯一一个 $d$ ，这里我们把所有可能的 $\gcd$ 的值和所有的 $j$ 都枚举了自然其值也就等于 $n$ 了（主要就是说明一个不重也不漏）。

$$
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
$$

这里没什么好说的，目的是把 $\gcd$ 的值化为 $1$ 后能转化成欧拉函数的形式。

$$
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
$$

$$
\large\therefore n=\sum_{d|n}{\varphi(d)}
$$

这里是因为每个 $\frac{n}{d}$ 和 $d$ 是对应的，所以能如此转化。

例题

• 多组数据，每组数据给出一个数 $n$ ，求 $\sum_{i=1}^{n}{\gcd(i,n)}$ 。

利用欧拉反演，改变题目公式如下：

$$
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
$$

拆开 $\gcd$ 得：

$$
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
$$

改变循环顺序得：

$$
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
$$

化简得：

$$
\sum_{d|n}\varphi(d)\frac{n}{d}
$$

关于推导式子就没了。这时只需将 $\text{phi}$ 预处理，每次询问 $\sqrt{n}$ 复杂度。

• CF1900D Small GCD

先排序，可得以下原公式：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
$$

带入欧拉反演如下：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
$$

化简：

$$
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
$$

其中我们可以边枚举 $i$ 边处理 $cnt_d$ ，并预处理 $\varphi(x)$ 。因此总时间复杂度为 $O(M+TN\sqrt{M})$ ，$M$ 表示 $a_i$ 的值域，还会有一些小常数，会有点卡常。

〇. 前置知识

• 四边形不等式（几何意义上）

  对于任意一个凸四边形（如图1），四个顶点分别为 $A,B,C,D$ ，其对角线交于点 $O$ ，则有 $AD+BC>AB+CD$ 以及 $AD+BC>AC+BD$ .

  证明：

  $\because AO+BO>AB\text{ and }CO+DO>CD$ （三角形两边长之和大于第三边）

  $\therefore (AO+DO)+(BO+CO)>AB+CD$ （联立两不等式）

  $\therefore AD+BC>AB+CD$

  （同理可得 $AD+BC>AC+BD$）

• 四边形不等式（DP意义上）

  这边主要都是些定义，因此不会有什么 针对定义的证明 。

  • 定义1

    设 $w$ 是定义在整数集合上的二元函数，对于任意整数 $i \leq i’ \leq j \leq j’$ ，若有 $w(i,j)+w(i’,j’) \leq w(i,j’)+w(i’,j)$ ，则称 $w$ 满足四边形不等式.[^1]

    什么叫做定义在“整数集合上的二元函数”？就是 $w$ 函数有两个参数，它的值和参数均为整数.

    但是，这似乎跟四边形没有半点关系吧.我们不如形象一点，对于刚才的定义，我们将 $i,i’,j,j’$ 表示在一个不太严谨的数轴上，这个数轴上 $a,b$ 两点的距离是 $w(a,b)$，然后，将中间的两个点，也就是 $i’$ 和 $j$ 向上抬升一点（如图2），这个四边形（在 $i’=j$ 的情况下是三角形）就出来了.

    

  • 定义2

    这是 定义1 的特殊情况。

    对于任意整数 $i < i+1 \leq j < j+1$ ，若有 $w(i,j)+w(i+1,j+1) \leq w(i,j+1)+w(i+1,j)$ ，则称 $w$ 满足四边形不等式.[^1]

    没啥好说的。。。

  • 单调性

    设 $w$ 是定义在整数集合上的二元函数，对于任意整数 $i \leq i’ \leq j \leq j’$ ，若有 $w(i,j’) \geq w(i’,j)$ ，则称 $w$ 具有单调性.[^1]

一. 证明四边形不等式定理

• 四边形不等式定理

  如果 $w(i,j)$ 满足四边形不等式和单调性，则使用动态规划计算 $f$ 数组的时间复杂度为 $\Theta(n^2)$ .

  • 引理1

• 1

二. 引用

[^1]: 参考 罗勇军的博客——算法竞赛专题解析（10）：DP优化(1)–四边形不等式

[^2]:F. Frances Yao原论文

• $\text{I don’t know this person is 2B or not 2B.}$

Day $-1$

回想起了初赛S组的难度以及一个卡分数线过的我。我感觉第二天的考试要炸，思前想后感觉这种时候可能也做不了什么知识性的事了，于是就把文件快读的模板背了一下（虽然不知道明天是否有用）。无论如何，这天奇迹般地睡了个好觉。

Day $0$

Backroom

Day $1\frac{1}{3}$

$8:30$

上J组考场，VS Code能正常用！J组的AB两道题都比较简单——新时代的大水题！其中 $\text{T1}$ ，一开始看的时候没什么思路，盯着电脑想了十几分钟，还是决定从部分分拿起，打完第一问后一分多钟第二问就出来了，$\text{T1}$ 就拿下了。打完后测过大样例觉得有点后怕，还是把文件快读加上了。然后开 $\text{T2}$ ，看到标题一瞬间想到之前做过的一道题（尽管题面并不一样），看完题面后想到了贪心并且觉得应该一段一段的考虑，略加调试，就通过了样例。之后有一段时间对着大样例调试，发现之前没用完的油要接着考虑，再次修改代码，结束 $\text{T2}$。

$\text{T1}+\text{T2}=70\text{min}$

$9:(3\sqrt{5})^2$

发现 $\text{T3}$ 是一道大模拟，然后飞快看了眼 $\text{T4}$ 并断定不会，于是就老老实实打 $\text{T3}$ 了。$\text{T3}$ 是我唯一一道打了表的题，这是我在正式考试中头一次使用打素数表这种不光彩的方法，打起来感觉比之前我所写过的大模拟舒服得多，大样例也给得毫不吝啬，帮助我发现了许多bug，例如最大的解为 $0$ 的情况。总之，最后通过了大样例，$\text{T3}$ 宣告结束了！

这里是考后视角，虽然目前没有发现任何bug，但是小*灵和*斗都只拿到了 $80$ 分，$\text{I don’t know Y}$ ，唯有洛谷给出了 $100$ 分的佳绩，希望得到洛谷的hack数据，希望CCF的样例和洛谷一样水！！！

然后就去打 $\text{T4}$ ，想了想有了正解的思路，最后打了个 $\text{dfs}$ ，思路是在深搜过程中记录要求最严苛的点，最后加到 $ans$ 里面一起统计答案去。

在洛谷上取得了 $35$ 分的好成绩，在小*灵上取得了 $15$ 分的成绩，再次衷心祝愿CCF数据出水点！然而，考后我把深搜改成了广搜，并且把记录内容从最严苛的点变成了最晚出发时间，然后 $35\rightarrow 90$ （真的想吐）。最关键的是，但凡我是一个正常人，我看完这道题后就应该记录最直接的数据二分这种垃圾玩意！虽然正解是二分+同余最短路，但是以我对CCF的最后一丝幻想，我觉得CCF不会在普及组出这么恶心的东西，而且，二分起始时间的思路似乎已经被同机房的大佬hack了，因此我厚颜无耻地认为“我的思路是正解”。

Day $1\frac{7}{12}$

$14:00$

打提高组，然后寄了。

除了 $\text{T1}$ 以外其他题都大寄特寄！

整个过程没什么好说的，$\text{T1}$ 打完（$1\text{hour}$）之后的所有时间都去打 $\text{T2}$ 去了，然后 $\text{T2}$ 只打了个区间DP，比赛就结束了。

考后震惊地发现 $\text{T3}$ 打太急了甚至没有编译，导致编译错误，但是我会自我安慰——即使没有CE也会爆零。我谢罪！

更好的阅读体验

本蒟蒻的第一篇题解。

这道题我看大家都是用一维 DP 做的，本蒟蒻今天在考场上写了种二维 DP 的做法。我个人认为这种可能理解起来会简单一些（虽说写起来麻烦了点），于是就有了这篇题解。

思路

当时（考场上）想了半天没想出来怎么使用一维 DP 解决这道题，便想了一种二维 DP 的做法。

我们定义 $f[0][i]$ 表示以 $i$ 作为一段的头部时是否可行，$f[1][i]$ 表示以 $i$ 作为一段的结尾是否可行。并且在原序列中添加两个点：$0$ 和 $n+1$。

状态转移（以下 $i$ 均指当前考虑的位置）：

• 头的转移

1. 如果上一个位置可以作为尾，那么这个位置就可以作为头。
   也就是 $f[0][i] = f[1][i-1]$
2. 如果当前位置作为头，那么下一段的头的位置也可以作为头。
   也就是 $f[0][i+a[i]+1] = f[0][i]$

• 尾的转移

1. 如果上一段的尾的位置可以做尾，则当前位置可以做尾。
   也就是 $f[1][i] = f[1][i-a[i]-1]$
2. 如果这一段的头的位置可以做头，那么当前位置也可以做尾。
   也就是 $f[1][i]=f[0][i-a[i]]$

注意：写代码的时候要注意下标不能越界。

根据以上的转移（可能有点乱），我们能知道初始状态为：
$$
f[1][0] = f[0][1] = 1
$$

而最后我们只需要判断第 $n$ 个位置能否做尾或第 $n+1$ 个位置能否做头就好。

代码

（供群众批判）

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

#include <bits/stdc++.h>
using namespace std;

int n;
int a[200010];
bool f[2][200010];
/*
  0: 作为头
  1: 作为尾
 */

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		memset(f, 0, sizeof f); // 多测不清空，爆零两行泪
		f[1][0] = 1;
		f[0][1] = 1;
		for (int i = 1; i <= n; i++) {
			// i作为头
			// 从上一个是尾转移
			f[0][i] |= f[1][i-1];
			// 隐藏情况：之前有人帮它更新了
			// 更新下一个可能作为头的
			if (f[0][i] && i+a[i]+1 <= n+1) f[0][i+a[i]+1] = 1;
			// i作为尾
			if (i-a[i]-1 >= 0) f[1][i] |= f[1][i-a[i]-1];
			if (i-a[i] >= 0) f[1][i] |= f[0][i-a[i]];
		}
		if (f[1][n] || f[0][n+1]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Lambda表达式

首先，Lambda读作 [‘læmdə]。

好，接下来我们步入正题。就我个人认为，Lambda表达式是一种能让一些不会经常调用的 简单函数 写得更简单的方法，其中最典型的例子就是sort自定义排序函数。
假设我们有一个结构体node如下：

1
2
3

struct node{
	int x, y;
}points[114514];

一般来说，我们会写一个cmp函数如下：

1
2
3
4

bool cmp(node &a, node &b) {
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

或者更高级一点，使用operator重载运算符：

1
2
3
4
5
6
7

struct node{
	int x, y;
	const bool operator<(const node &b) const {
		if (x == b.x) return y < b.y;
		return x < b.x;
	}
}points[114514];

但是，这些写法都是需要额外再开一个函数的，并且对于先按某规则排序再按另一种规则排序这种情况的处理并不好（第二种写法甚至不能在这种情况下使用）。于是我们需要一种更简单的方法来写排序函数——Lambda表达式。先看效果，它写出来大概长这样：

1

sort(points+1, points+n+1, [](node a, node b) -> bool { return (a.x==b.x?a.y<b.y:a.x<b.x); });

* 还能再简单点吗？
* 可以，那么就是这样：（下面代码中的-> bool被省略了）

1

sort(points+1, points+n+1, [](node a, node b) { return (a.x==b.x?a.y<b.y:a.x<b.x); });

这只是其中一种使用方法。借此，我们还可以把局部变量当做“全局”变量来用（并不是真的全局，但是在Lambda表达式的函数内可以使用这些局部变量），具体实现方法是 捕获 （这东西我还没想到在OI中的应用），也就是在那个[]内部做文章，实现可以参考参考资料。

upd 20231130

除此之外，Lambda表达式还可以在函数内部定义函数，例如，我们可以在 main 函数里定义一个 add 函数用来给链式前向星加边：

1
2
3
4
5
6
7
8
9
10
11
12
13

struct node{
    int nxt, to;
}g[200010];
int head[200010], tot;

int main() {
    function<void(int, int)> add = [](int u, int v){
        g[++tot] = {head[u], v};
        head[u] = tot;
    };
    add(1, 2);
    return 0;
}

而这个函数也是受“变量”的定义域所影响的，例如下面在 test 函数中调用 add() 函数将出现 $\text{CE}$ ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct node{
    int nxt, to;
}g[200010];
int head[200010], tot;

void test() {
    add(1, 2);
}

int main() {
    function<void(int, int)> add = [](int u, int v){
        g[++tot] = {head[u], v};
        head[u] = tot;
    };
    test();
    return 0;
}

不仅如此，我们甚至可以在这基础上写递归（以 Tarjan 为例）：

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

struct node{
    int nxt, to;
}g[200010];
int head[200010], tot;

int dfn[200010], low[200010], cnt;
int st[200010], top;
bool inst[200010];

int scc[200010], sc;

int main() {
    function<void(int)> tarjan = [&tarjan](int u) {
        dfn[u] = low[u] = ++cnt;
        st[++top] = u, inst[u] = 1;
        for (int i = head[u]; i; i = g[i].nxt) {
            int v = g[i].to;
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inst[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            sc++;
            while (st[top] != u) {
                scc[st[top]] = sc;
                inst[st[top]] = 0;
                top--;
            }
            scc[st[top]] = sc;
            inst[st[top]] = 0;
            top--;
        }
        return ;
    };
    return 0;
}

其主要就是一个 function 的实现，语法是 function<返回值类型(参数类型1, 参数类型2, ...)> = [捕获](传参){函数主体} ，而要递归就只用在捕获处引用这个函数（就像上面的例子）。

auto (C++11新语法)

先说怎么启用C++11或其他新版本，对于Dev-C++，在编译选项中的“在编译时添加这些参数”添加-std=c++11，这里的 11 可以换为其他版本如：-std=c++23。
auto 可以自动匹配变量类型，但是没多大用（除非使用迭代器iterator这种难写的类型），具体而言可以这么写：

1
2

auto i = 1ll;
auto j = mp.begin();  // mp是一个map<int, int>

(值得一提的是，使用迭代器遍历map遍历出来的是pair类型的东西)
并且，auto还有一些可以减少代码量的用法，例如遍历vector:

1
2
3
4
5
6
7

for (int i = 0; i < (int)vec.size(); i++) {
	cout << vec[i] << endl;
}
// 等价于
for (auto &i : vec) {
	cout << i << endl;
}

同理，其他能使用迭代器的容器都可以如此遍历（但是，栈和队列都不行）。

using

这个语法很简单，应用只有一个——using ll = long long 。
它能定义 ll 为 long long 并且还不能批量替换 int 。
如果要把代码中所有 int 替换为 long long，请使用 #define int long long （虽然这是未定义行为）.

模块化思想 与 类和对象

将代码中实现不同功能的代码封装成函数，这会对 debug 有极大的帮助。
对象嘛，不是你想的那个对象，你可以使用 namespace 或 class。
给个例子：

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

#include <bits/stdc++.h>
using namespace std;

namespace work1{
	string main(string t) {
		return t+t+"adwe";
	}
	void print(string t) {
		cout << main(t) << endl;
	}
};

class work2{
private:
	string main(string t) {
		return t+t+"adwe";
	}
public:
	void print(string t) {
		cout << main(t) << endl;
	}
};

int main() {
	// 使用namespace的方法
	work1::print("1abc");
	cout << work1::main("2abc") << endl;
	// 使用class的方法
	work2 *p = new work2;  // 新建一个类
	p->print("3abc");
	p->main("4abc");  // 无法编译
}

调试常用

离线比赛常用：cerr

因为离线比赛中需要进行文件输入输出，但是每次开关文件很麻烦，而 cerr 可以不受文件输入输出流影响，往标准输入输出流里进行输出，但代价是每次输出都会清理一遍缓冲区，时间消耗极大，所以调试完后一定一定要把所有 cerr 语句删除。

啥都能用的 assert

位于头文件 cassert 中，如果不用万能头要把头文件导入。

在代码中可以写 assert(a <= n && 1 <= a); 来判断 a 是否在给定的范围内，如果不在程序将立即终止运行并输出错误所在的行号等信息，准确来说，只要 assert 语句中的表达式的值为 false ，就会返回报错。

可以使用宏 #define NDEBUG 即可一次性禁用所有 assert 语句。

值得注意的是，在洛谷中，如果 assert 返回报错会显示 RE ，并返回错误信息：

1
2

Runtime Error.
Received signal 6: Aborted / IOT trap.

参考资料

Lambda表达式

• 官方文档
• zhihu