本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-14 14:25:10

CF1353E

• Difficulty: $\color{purple}\text{1900}$
• sol1:
  可以枚举最后一个灯的所在位置，进行 dp。
  设 $dp_i$ 表示最后一个灯在位置 $i$，且只考虑前 $i$ 个位置的最优解。
  显然，对于转移，一种情况是前面全是 $0$，只有这一位是 $1$；另一种情况，是位置 $i-k$ 为 $1$，$i-k+1$ 到 $i-1$ 都是 $0$，从$dp_{i-k}$ 转移过来。
  复杂度 $O(n)$
  提交记录
• sol2
  这些灯可以存在的位置模 $k$ 同余。
  所以可以用 $O(k)$ 的时间枚举灯可选的位置。
  由题目可知，除了选出了的一些相邻的模 $k$ 同余的位置是 $1$，其余位置都得是 $0$。
  也就是说选出了一个位置使其为 $1$，如果原来就是 $1$，可以少改变一次，如果原来是 $0$，就要多变一次。
  现在就是选出一些连续的模 $k$ 同余的位置使得最终改变的次数最小。
  成经典贪心题了。
  复杂度 $O(k \cdot \frac{n}{k}) = O(n)$
  提交记录
  然后发现和第一份做法都是 93ms，复杂度一样常数也一样。。。。。

CF1403C

• Difficulty: $\color{black}\text{3}\color{red}\text{200}$
• sol:

CF3A

• Difficulty: $\color{gray}\text{1000}$
• sol:
  本质上就是可以一次操作中可以改变单个坐标一次，也可以横纵坐标一起改一次。
  贪心是很显然的。
  提交记录

CF1396C

• Difficulty: $\color{orange}\text{2300}$
• sol:
  设 $dp_i$ 表示解决完前 $i$ 关的最小代价。
  对于每一关，显然都分两种情况：一次解决所有怪；解决所有的小怪后，逃跑，再回来打死 Boss。
  想一下，移动路线必然是从 $1$ 到 $n$（最后一步可能还有个 $n$ 到 $n-1$）。
  对于一次解决所有怪（即不逃跑再回来打）的情况，从 $dp_{i-1}$ 转移。
  对于需要逃跑一次的情况，最优的方法是移动到相邻的关卡，相邻两关互相横跳再继续往后走（总体上是向后走的，一些关卡因为要打两遍，为了减少时间消耗只往前走一个关卡，然后回来继续向后走）。
  所以这种情况也从 $dp_{i-1}$ 转移。
  注意走到了 $i-1$ 再回来， $i-1$ 和 $i$ 这样下来都能打两遍，也就是说还可以从 $dp_{i-2}$ 转移过来，计算 $i-1$ 和 $i$ 打两遍的代价。
  总体说完了，一些细节要处理。
  注意如果是 $n-1$ 和 $n$ 互相横跳的话，由于不存在没访问过的点了，$n$ 可以直接解决所有怪然后跳到 $n-1$，不再回去，这个要特判。
  复杂度 $O(n)$。
  提交记录

ABC176F

• Difficulty: $\color{red}\text{2912}$
• sol:

ZOJ2113

• Difficulty: Unknown
• sol:

CF498E

• Difficulty: $\color{red}\text{2700}$
• hint: 矩阵乘法
• sol:

ABC144F

• Difficulty: $\color{orange}\text{2189}$
• sol:

CF8E

• Difficulty: $\color{red}\text{2600}$
• sol:

CF1140E

• Difficulty: $\color{orange}\text{2200}$
• sol:
  显然只需要分别计算每段连续 $-1$ 的方案数，然后乘起来就行了。
  进行一些模拟发现，每段连续 $-1$ 的方案数和左右两边的值没有关系，有关系的是左右两边的值是否相等。
  可以 dp 预处理长度为 $i$ 的连续 $-1$ 段的方案数。
  $dp_{i,0}$ 表示长度为 $i$ 且左右两边的定值不相等的 $-1$ 连续段。
  $dp_{i,1}$ 表示长度为 $i$ 且左右两边的定值相等的 $-1$ 连续段。
  把 dp 状态对应的图画出来（如 $dp_{i,0}$ 对应 $a,-1,-1,\cdots,-1,b$），就能列出转移方程，即：
  $dp_{i,1} = dp_{i-1,0} \cdot (k-1)$
  $dp_{i,0} = dp_{i-1,0} \cdot (k-2) + dp_{i-1,1}$
  复杂度 $O(n)$。
  提交记录

CF1782E

• Difficulty: $\color{orange}\text{2300}$
• sol:

vjudge Kattis-tetris

• Difficulty: unknown
• sol:

CF1699E

• Difficulty: $\color{red}\text{2600}$
• sol:

acmicpc.net 12610

• Difficulty: unknown
• translation：
  题意：
  一年有 $N$ 天，其中有 $T$ 场比赛。
  每一场比赛分为很多轮，且每一轮都分布在比赛开始后的第 $\cdots$ （不知道）天。
  这些比赛的开始时间随机分布在一年中的一些天。
  设一年中一天同时有 $S$ 轮，那么这一天所带来的快乐值贡献为 $S^2$。
  求这一年快乐值期望总和（如果某些轮到了下一年，不算）
  输入格式：
  第一行有一个整数 $C$，代表有 $C$ 组数据。
  每组数据第一行是两个整数 $N,T$。
  接下来 $T$ 行，第 $i$ 行描述第 $i$ 场比赛。
  每行第一个整数 $m$，代表这场比赛有 $m$ 轮，接下来是 $d_2,d_3,d_4,\cdots,d_m$，$d_i$ 代表第 $i$ 轮在比赛开始之后的第 $d_i$ 天进行（第一轮都是在比赛开始的第一天进行，所以没给出）
  输出格式：
  每组数据输出一行，每行输出一个最简形式的带分数，代表答案（具体看原文）。
• sol:

POJ3623

• Difficulty：unknown
• hint: 贪心利用后缀数组优化
• sol:

CF295D

• Difficulty: $\color{red}\text{2400}$
• sol:

CF533D

• Difficulty: $\color{black}\text{3}\color{red}\text{000}$
• sol:

CF1418D

• Difficulty: $\color{orange}\text{2100}$
• sol:
  首先，如果点数小于等于 $2$，不用进行操作。
  否则，画图可知，答案为最大坐标减最小坐标，再减去（相邻两个点位置差的最大值）。
  加上了括号方便断句。
  最大坐标和最小坐标用 set 维护就行了，接下来要想的是如何维护相邻两个点位置差的最大值。
• sol.1
  用 multiset 维护相邻两个点位置差的最大值。
  考虑插入删除操作的影响到底是什么。
  对于插入，设插入在位置 $x$，$x$ 左边最近的点为 $l$，$x$ 右边最近的点为 $r$，相当于删除区间 $[l,r]$ 的影响，加入区间 $[l,x],[x,r]$ 的影响。那只需要在 multiset 里面删掉一个 $r-l$，加入一个 $x-l$ 和一个 $r-x$。
  对于删除，和插入差不多，只不过反过来了。
  一个技巧：如果不想分类讨论，可以先插入两个点，分别是 $+ \infty$ 和 $- \infty$。
  复杂度 $O((n+q) \log n)$。
  提交记录
• sol.2
  用线段树维护相邻两个点位置差的最大值。
  $[1,10^9]$ 的坐标范围，先离散化。
  合并区间的时候，就是左子区间的答案，右子区间的答案，和（右子区间最靠左的点的坐标）减去（左子区间最靠右的点的坐标） 取 max 作为当前区间的答案。
  所以线段树需要维护三个值，即当前区间答案，当前区间最靠左的点的坐标，当前区间最靠右的点的坐标。
  复杂度 $O((n+q) \log n)$。
  提交记录

Luogu P4066

• Difficulty: $\color{purple}\text{省选/NOI}$
• sol:

CF1520G

• Difficulty: $\color{orange}\text{2200}$
• sol:
  一定只使用一次传送门。
  证明：设使用两次或以上的传送门能达最优效果，第一次使用传送门的起点为 $s$，最后一次使用传送门的终点为 $t$，显然直接从 $s$ 到 $t$ 更优。
  现在分两种情况统计答案，第一种是不使用传送门，第二种使用一次传送门。
  第一种很简单，第二种也只需要找出走的距离和跳的代价总和最小的两个点就行了。
  复杂度 $O(nm)$。
  我不知道开了 Ofast 为啥还跑这么慢，提交记录。

POJ1151

• Difficulty: unknown
• sol:

CF845E

• Difficulty: $\color{red}\text{2400}$
• sol:
  二分答案，然后离散化所有矩形，看空隙之间距离就行了。
  离散化的时候要把矩阵四个顶点旁边的点也加入离散化，否则空隙可能会被离散化凭空消失掉。
  Codeforces 提交记录
  这样复杂度 $O(k^2 log_{n})$，是最劣解。
  为了优化复杂度，可以采用扫描线。
  扫描线题解

CF1635F

• Difficulty: $\color{red}\text{2800}$
• sol:

CF1284D

• Difficulty: $\color{orange}\text{2100}$
• sol:
  本质上是问是否不存在两个会议，使得在一个会议场不发生冲突，另一个发生冲突。
  一个简单的套路就是对每个会议分配一个随机权值，然后对每个会议，在两个会场分别记录与其不发生冲突的会议的权值的异或和，看两个会场所得结果是否一样就行了。
  计算不发生冲突的会议的权值的异或和，前后缀异或和预处理就行了。
  这样是复杂度是 O(值域) 的，过不去。
  考虑实际上只关心区间端点的相对大小，可以离散化。
  复杂度是离散化的 $O(n \log n)$。
  提交记录

CF1132F

• Difficulty: $\color{purple}\text{2000}$
• sol:
  我不会比洛谷题解说得清楚。

acmicpc8081

• Difficulty: unknown
• sol:

CF ACM sguru442

• Difficulty: unknown
• sol:

CF482C

• Difficulty: $\color{red}\text{2600}$
• sol:

https://coursera.cs.princeton.edu/algs4/assignments/baseball/specification.php

• Difficulty: unknown
• sol:

UVA1086

• Difficulty: unknown
• sol:

ABC210F

• Difficulty: $\color{orange}\text{2632}$
• sol:

HDU-3062

• Difficulty: unknown
• sol:

POJ-3281

• Difficulty: unknown
• sol:

POJ-1149

• Difficulty: unknown
• sol:

POJ-2391

• Difficulty: unknown
• sol:

CF1009G

• Difficulty: $\color{red}\text{2400}$
• sol:
  贪心思想。
  从前到后枚举每一位的字母。
  优先保证前面的小。
  当一位枚举了一个字母之后，可以通过网络流判断后面位是否存在合法方案。
  关于网络流：
  搞成二分图的形式，左部点是位置，右部点是 $6$ 个字母。
  右部点向超级汇点连权值为该点在原串中出现次数的边。
  当然这不是真正的二分图，可以这样转化成二分图：把每种字母拆成该字母在原串中出现次数个点。
  然后枚举右部点 $6$ 个字母的子集，hall 定理判定即可。
  提交记录

ARC076F

• Difficulty: $\color{red}\text{2819}$
• sol:
  只考虑一个段点限制，然后贪心得计算右端点。

CF808F

• Difficulty: $\color{red}\text{2400}$
• sol:
  二分等级。
  质数除了 $2$ 都是一奇一偶组成的，而 $2 = 1+1$，也就是说只能有一个 $1$。
  把 $1$ 处理掉之后形成了一个以奇偶分类的二分图，超级源点向左部点连权值为能量的边，右部点向超级汇点连权值为能量的边，然后求最小割。
  CF 提交记录

loj3379 【CSP-S2020 儒略日】

• Difficulty: $\color{green}\text{普及+/提高}$
• sol:

CF Gym100722

这个 gym 比较特殊，可以查看他人代码，只有看数据需要 Coach Mode。
在 UVA/SPOJ/BZOJ 有原题。

• Difficulty: unknown
• B:
  把集合编上号，模拟。
• D:
  最小斯坦纳树。
• E:
  排序，然后 dp。