这是一道并不复杂的状压dp，隐藏在复杂的题面下面的是简单的思维。
首先根据题意，一个人能不能打饭，是一个状态，所有的状态总和是\(2^n\)个，显然过于多了。然后一个什么时候打饭，只和后方的7个人有关系，所以可以考虑将当前这个人前面的所有状态压缩起来。于是设f[i][j]表示1i-1个人已经打到饭，ii+7打饭的状态是j。
再对照题目，我们还需要知道上一个打饭的人是哪一位，那加上一维，成为f[i][j][k]，k表示于i的相对位置。
然后就可以枚举每一个i,j,k了，将f[i][j][k]作为旧状态，去更新新的状态，这样也方便计算忍耐度。 我们有 对于st&1==1： \[f[i + 1][st >> 1][8 + k - 1], f[i][st][8 + k]\] 其他情况，从没有打饭的人里面，找一个打饭： \[f[i][st + (1 \lt\lt l)][8 + l], f[i][st][8 + k] + cal(i + k, i + l)\]
1 | #include <bits/stdc++.h> |
这道题在我的题目列表里躺了好久，一直不会做，今天终于做出来了。 思路：
\(f_i\)表示i时间的还没有买机器人的最大价值。
由于要计算一系列复杂的东西，这道题的\(O(n^3)\)算法并不适合用填法来做，适合用刷法。
详细的参考代码，枚举ijk即可。中间求和过程可以预处理，也可以记录下上一次的状态，直接计算。
这道题可以用单调队列把k消掉，不过要转换为填法，这里不再赘述。 ## 代码
1
f[i+k] = f[i-1] + \sum^{k}_{kk = 0} {a[i+kk][j + kk]} - c[j]
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#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, p;
int w[N][N];
int f[N];
int c[N];
int main()
{
cin >> n >> m >> p;
for (int i = 0; i < n; ++i)
for (int j = 1; j <= m; ++j)
cin >> w[j][i];
for (int i = 0; i < n; ++i)
cin >> c[i];
memset(f, 0xa0, sizeof f);
f[0] = 0;
for (int i = 1; i <= m; ++i)
// time
{
for (int j = 0; j < n; ++j)
// pos
{
int ans = -c[j] + f[i-1];
for (int k = 0; k < p && i + k <= m; ++k)
// step
{
int t = (j + k) % m;
ans += w[i + k][t];
f[i + k] = max(f[i + k], ans);
}
}
}
cout << f[m] << endl;
}
看了半天题解，发现：这不就是一道01背包嘛 ## 公式 f[i]
表示当前队伍1，花费i的时间的总最短时间 ## 代码
1
2f[j] = min(f[j], max(f[j - a[i].x], j + a[i].y)); //排在队伍1
f[j] = max(f[j], sum[i] + a[i].y - j); //排在队伍21
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#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
struct node
{
int x, y;
bool operator<(const node &n2)
{
return y > n2.y;
}
} a[N];
int sum[N];
int f[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + a[i].x;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = sum[i]; j >= 0; --j)
{
if(j >= a[i].x) f[j] = min(f[j], max(f[j - a[i].x], j + a[i].y));
f[j] = max(f[j], sum[i] + a[i].y - j);
}
for (int j = 0; j <= sum[i]; ++j)
cout << f[j] << " ";
cout << endl;
}
int ans = 1e9;
for (int j = sum[n]; ~j; --j)
{
ans = min(ans, f[j]);
}
cout << ans << endl;
}
经过这几年的学习信息奥赛，现在此写下我的感受。
更新：2019年，NOIP取消，我成为了最后一界NOIP选手。以此纪念我三年的信息奥赛生涯
贪心算法指： 求解某一问题时，做的某一个策略一直是局部最优解。每次将问题规模减少，直至减少到基础情况。
对于无法直接贪心的题目，配合随机化，将贪心步骤打乱，可能会产生更优的解，以此更新最优答案。
有些题目的正解是贪心+调整，每一步都采取贪心策略，将然后剔除部分不是最优的解，这样下去可能会产生最优解。
动态规划是一种依据子问题来确定当前问题的最优解的过程，一般是一种自底向上的做法。 通常来讲，正解是贪心的题目一定有动态规划的做法，正解是动态规划的题目一定有搜索做法。 通常递推的做法也可以算作动态规划。 动态规划的核心是状态转移方程，每个状态只由已知的状态推导出。
常见的题目描述是，给定一个长度为n的序列，他们有xxx属性，要求某个全局最优解。通常按照合并区间的方法进行DP，以石子合并为例，有方程\[f_{i,j}=\min \{f_{i,k}+f_{k+1,j}\}+sum[i][j]\] #### 线性DP 常见的题目有求两个字符串的最长公共子串、子序列、编辑距离等，也有求一个序列的最长上升子序列，还有一些算法，比如线性筛算法，也可以规划到线性DP中（虽然比较少见） #### 树上DP 这一类DP是在树上进行的，利用DFS的顺序进行转移，通常状态多而杂，很容易写错，但这类题目的正解一般只有这一种。 例题有：没有上司的舞会、树型依赖背包问题 #### 背包DP 背包DP是比较常见的一类DP，有01背包、完全背包、多重背包、有依赖关系的背包、分组背包、最后是泛化背包，这些将在后面讲解。 #### 状压DP 利用数字的性质，将某种状态转换为整数来存储，在此基础上DP #### 环形DP 一般这种情况可以复制一份，转换成线性DP或区间DP，然后在新的数组上DP。 #### 方案DP 如果一个题目要求求出方案数，可以将初始状态设为0，直接+=。 #### 数位DP 针对某些数据范围极大的数学题，求具有某些特点的数字的个数 #### 图上DP 可以利用拓扑序dp，也可以用jarjan算法缩点后，建立一棵树再进行dp #### 插头DP Q:什么题目使用插头dp? A:关键词：超小数据范围，网格图，连通性。 Q:什么是“插头”？ A:一个格子通过某些方向与另一个格子相连，这些连接的位置叫做“插头”。形象地理解，网格图上每一个格子是一块拼图，那么两块拼图的接口就叫做“插头”。
对于一些和状态无关的变量，可以进行预处理，比如前缀和，做到\(O(1)\)查询。
对于一些形如\[f_i = \sum \limits_{j\lt i}\{f_j\} + a_i\]的转移方程，可以用树状数组、线段树来加速转移，使时间复杂度由\[O(n^2)\]降低到\[O(n \log n)\] 一些求最大最小值的状态转移方程，可以用优先队列优化，复杂度同上。
对于\[f_i = \max \limits_{a\le j\le b \lt i}\{f_j\} + a_i\]形式的转移方程，可以采用单调队列优化，每次直接取出最优解，再维护最优解。具体来说，这应该维护一个单调递减的单调队列，每次取队尾，如果队尾元素过期，则将它出队。更新当前状态后，要将队头的非最优元素出队。 时间复杂度是\(O(n)\)的
对于一些带有平方项的状态转移方程，状态是关于\(i,j\)两项的，这时就不能直接利用数据结构优化了。不过还是有优化的方法的。
首先进行一波公式推导，发现对于当前状态\(i\),有\(j,k\)两个状态可以转移，其中\(j\)更优的条件是 \[ \frac{a_j-a_i}{j-i} \lt \frac{a_k-a_i}{k-i}\]则可以在单调站内维护一个下凸包，每次取出最优解，入栈时维护单调站的性质来加速转移。
很多问题都可以转换成背包问题，背包问题的描述是这样的：
给定一些物品，编号1-n，有价值和体积。现在有一个容量为V的背包，求怎样装可以做到价值最大、或者求符合要求的方案数。
几乎所有背包问题都是用DP来做的。 ### 01 背包和完全背包
有状态转移方程\[f_j=
f_{j-w_i}+v_i\]，j是体积，阶段i隐藏在转移过程中，表示当前的背包装填了1-n的若干物品，用了j容量的最大价值。
区别是，01背包要从后向前转移，为了避免当前阶段的决策对当前阶段其他状态的影响；而完全背包没有这个限制，甚至需要这个“副作用”。
时间复杂度\[O(NV)\]，空间复杂度\[O(V)\] ### 更大体积的01背包
这一类问题的特征是，\[n \approx
40\]，\[j\]更大，甚至达到1e9，显然传统的做法是没法做的，直接枚举选择物品会超时。这时可以将物品分为两部分，每部分约20个。之后枚举一组的所有情况，存到一个map中，然后对另一组做同样处理。处理好之后，对第一组的每一个可以选的状态，在第二组里查找可行解，组合、记录最优解。
时间复杂度\[O(2^{\frac n 2}\log 2^{\frac n
2})=O(2^{\frac n 2})\] 可见，它和体积无关。 ### 分组背包
对于一个分组，只能选择一样物品，那么就把这些物品捆绑起来，枚举怎样选择，就可以了。
### 多重背包
每个物品有k件，求体积限制内最大价值。可以枚举件数，也可以二进制拆分成\[\log a_i\]件单一物品，一般这就足够了。
另外有剩余类的单调队列优化，对于某一个状态\[f_i\]，它只会被用来更新\[f_{i+kv_i}\]，所有\[i \mod
v_i\]构成一个剩余类，我们开多个单调递减队列，分别维护每个剩余类的最大值，再转移就好了。时间复杂度\[O(NV)\] ### 依赖背包
给定多个物品，其中每个物品可以被选择，仅当某一个特定的物品被选择，就限定体积内的最大价值。形象的理解是”进化树“
这样的题目有 津津的存储计划， 访问艺术馆等
津津的存储计划这道题，每个物品只能被两个物品依赖，依赖关系只有一层，更优的做法是，将每个被依赖的物品拆成4个，然后进行01背包的求解。
访问艺术馆就没这么简单了，它需要实打实地进行依赖背包的dp。思路是，把每一个物品都看做一个背包，对于每一个体积，都有特定的价值，然后问题成了给定若干个背包，要求按顺序合并这些背包。合并中的需要处理的地方有、如果某个背包是被依赖的，合并它的子物品所代表的背包时，要加入一个容量上的偏移，这个偏移就是主件的体积。
再建立一个虚拟物品0，所有物品都依赖它，然后0背包的解就是答案了 ###
多重依赖背包 这种DAG背包问题有两种，一种是 魔兽地图
类型的，经过预处理后，可以转换为传统的背包问题；另一种是”科技树“、”软件包管理器“类型的，无法转换为传统背包问题。
第一种无非码量大一些，预处理后按照常规方法可以解决。
第二种是无法在多项式时间内处理出来的，因为它具备后效性。如果试图转换成图来做，节点数目也是\(O(2^n)\)级别的，边的数目会更多。所以只能搜索或者枚举，参考更大体积的01背包
几乎任何题目都是可以通过搜索或穷举做出来的。缺点是复杂度极高。 搜索的复杂度可以称玄学\(O(\frac {n!} {XuanXue})\)，但是通常不会跑满 ### 技巧 没有后效性的搜索，可以通过记忆化来实现，这和DP是等价的。有时候因为思维难度低，复杂度跑不满，也非常优秀。复杂的状态可以通过哈希来存储，略微有些冲突一般不会影响到答案。 剪枝是很有必要的，有些题目没有图论、结论、Dp、贪心做法，就只能搜索。剪枝的优秀性和数据强度决定了搜索算法的分数。
多用结构体，多写函数。模拟时要按照题意来，不要偷懒，也不要理解错误，别的没什么好说的。
最短路是图论里最经典的题目。
| 算法名称 | 适应条件 | 时间复杂度 |
|---|---|---|
| Dijkstra | 不存在负权边、在稠密图上性能良好、求单源最短路 | \(O((V+E)\log E)\) 或\(O(E + V \log V)\) |
| SPFA-- 队列优化的BellmanFord | 稀疏图、单源最短路 | \(O(kn)\)到\(O(n^2)\) |
| Floyd | 稠密图、多源最短路 | 稳定\(O(n^3)\) |
最小生成树的性质有：两点之间的边权最大值最小，在连通的所有子图中，所有边权之和最小
| 算法名称 | 适应条件 | 时间复杂度 |
|---|---|---|
| Prim | 稠密图中表现良好 | \(O(Elog V)\) |
| Kruskral | 稀疏图中表现良好，实现简单，常数小 | \(O(Elog E)\) |
常用算法有tarjan算法。tarjan可以做的事情有很多，比如求强连通分量、缩点、求割点、求割边。 通过tarjan算法，可以将一个图转换成DAG，进而可以进行拓扑排序，这是tarjan非常重要的应用。
欧拉回路指，经过所有边恰好一次的一条路径。做法很简单，dfs即可。确定入点后，遍历完一条边后标记一下，dfs退栈时将当前点加入一个栈中，最后将栈内元素取出就是经过的路程。
二分图匹配是什么，自己百度吧…有一些题目是需要用二分图匹配的做法的，比如某些棋盘放置，求方案的问题，用二分图匹配的复杂度远低于搜索。
## 数论1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18bool dfs(int u,int vistime) {
/*
*vistime为时间戳
*具体的，对于点u，如果dfn[u]<>vistime
*则点u在本轮匹配中还没有被匹配到
*/
for(rg int i=hd[u];i;i=edge[i].nxt) {
int &to=edge[i].to;
if(dfn[to] != vistime) {
dfn[to]=vistime;
if((!mch[to]) || (dfs(mch[to],vistime))) {
mch[to]=u;return true;
}
}
}
return false;
}
关于求素数、欧拉函数的算法参考我之前的文章。 ### 最大公约数
简单的欧几里得算法就可以解决\[\gcd(a, b)= b==0?a : \gcd (b,a\mod b)\]
有公式\[lcm(a,b)=\frac {ab} {\gcd(a,b)}\]
拓展欧几里得算法如下：
扩展欧几里德算法的应用主要有以下三方面： 1. 求解不定方程 \(ax+by=c\) > gcd(a,b) = gcd(b, a%b) >
ax+by=gcd(a, b) > =>bx+(a%b)y=gcd(b,a%b) > b = 0时，x = 1, y =
0 > 然后就可以回溯回去了 2. 求解模线性方程（线性同余方程） 3.
求解模的逆元1
2
3
4void gcd(ll a,ll b,ll &d,ll& x,ll& y){
if(!b){ d=a, x=1, y=0; }
else{ gcd(b,a%b,d,y,x); y-=x*(a/b); }
}
写了一下午一晚上，好累
同学在做这道题，我就一起做了，没想到比他A得还要早。这是一个考试中比较实用的做法。
首先针对nm比较小的情况，由于
1 | "必胜情况存在，当且仅当存在策略，使对手不存在必胜情况" |
然后我们就得到了dp公式递推公式
时间复杂度\(O(mn)\) ## 对于更大的情况
### 70分做法 我们发现绝大多数情况都是可以必胜的，直接输出1
当然出题人不会这么轻易放过你的，所以只能拿70分 ### 100分做法
我们把打的表格放出来，发现存在一个规律，即必败的点在两条直线上，而且经过原点，这就是规律。
至于为什么在两条直线上，是因为nm是可以互换的。
然后我们求出斜率的平均值，最后判断一下就好了。
判断的时候直接相等肯定是不行的，因为这是浮点数比较，还是我们估计的浮点数，所以我们需要一个eps。这个eps，可以用统计的方法算出来。
#### 求斜率和eps 首先剔除n>m情况的数据
设\(k\)为我们的估计的斜率，有\[k=\sum \frac{y}{x}\] 然后有 \[eps = \frac {\sum |k'-k|} n\]
其中\(k'\)是实际的斜率
在\(|\frac nm - slope| \le
eps\)的情况下，极大概率是必败的。当然也要考虑mn颠倒的情况。 ##
源程序
1 | #include <bits/stdc++.h> |
1 | #!/usr/bin/python3 |
原题考的数据范围比较小，标程给了\(O(nm \log (n+m))\)的做法。实际上可以做到严格\(O(nm)\)，另外还有\(O(n^2m^2)\)（暴力预处理）、\(O(nm\log nm)\)（Dijkstra）、\(O(nm\alpha (nm))\)(并查集维护连通性)的做法。
预处理的思路是多源bfs，是本题得分的关键。然后可以枚举答案，可以通过原题。发现答案有单调性，于是可以二分，也可以上优先队列，就有了那两个带有log的做法。实际上严格\(O(n^2m^2)\)的做法是通过Dijkstra的做法优化而来的，具体实现是用多个桶，维护多个解，然后按照limit减小的方向更新，权值为历史路径和当前点的最近距离取min，可以证明不会出现比limit更大的权值。每个节点都会遍历一次，所以是严格\(O(n^2m^2)\)的。
另外有一种常熟较小的Dijkstra的做法，即将到路径上最近值的最大值作为第一关键字，距离终点的距离作为第二关键字，用的是A*的思想，不过没有实现。
这道题的标程有问题，被我hack掉了，原因是读入时没有和下表对齐。
做法有很多，比如枚举每一行的排列，随机化+卡时等，这些期望是20分的。 更好的做法有：预处理出right数组，排序后用单调栈找最大矩形，或者二分长度，找最大出现次数，这些分别是\(O(mn\log n)\)、\(O(mn\log m)\)的，能过70分的点。 标程是在预处理出right数组，排序后用单调栈找最大矩形的基础上，用计数排序，压缩掉了log的复杂度，是严格\(O(mn)\)的
这道题的问题是，为了保险，写部分分的解时，5000*5000的数组开了7个，导致MLE。
题意：每条边有两个权值x,y，给定a,b，求将所有点联通时的最小化的代价。代价为\[max{x}\times a + max{y}\times b\] 一种做法是暴力枚举所有加边方式，复杂度\(O(m!)\)。 60分做法是枚举x，找最小的y，利用并查集维护连通性，复杂度为\(O(m^2)\) 标程是\(O(mn)\)的做法，每次加边时，在环上将最坏的边去掉，link-cut-tree或者暴力都可以，标程应该是暴力。
这道题的m开小了，导致RE一片
这是一道水题，用桶计数，每次分配桶内元素的个数+1作为第x个排列，最后桶内元素需要非严格递减，才是由排列构成的，否则就不是。 这道题看错了题意，以为排列只能向后弄，只拿了10分样例分。
部分分有搜索+剪枝，正解的dp很难想，也有情况无法处理，只拿了20分。 ## T6 正解是并查集或树套树，大概是。//TODO
原理是替换掉了默认的cin 和 cout，可以自行改为更为高效的实现
1
2
3
4
5
6
7struct myinput{ operator bool() const { return !feof(stdin); } }cin;
struct myoutput{}cout;
struct myendl{}endl;
myoutput &operator<<(myoutput &myoutput, int s) { printf("%d", s); return myoutput; }
myoutput &operator<<(myoutput &myoutput, myendl en){ printf("\n"); return myoutput; }
myoutput &operator<<(myoutput &myoutput, const char *s) { printf("%s", s); return myoutput; }
myinput &operator>>(myinput &myinput, int &s){ if(myinput) scanf("%d", &s); return myinput; }
大家的都太长了，发一个比较短的代码，洛谷上测的时间为800ms。思路大概是，暴力枚举，还有一些剪枝。用了一些奇技淫巧，没有删除调试代码，也没有压行。可以注意一下预处理的方式。
1 | #include <bits/stdc++.h> |
今天考试内容比较没有头绪，第一道题看样子是序列上的dp，好像又有后效性，就很无奈。干脆写了随机化，最后拿了50分。正解确实是dp，裸的dp能拿50分，如果用Lowerbound和线段树来初始化，用线段树转移状态，就能拿到满分。时间复杂度为\(O(n\log_2n)\)，要注意一些细节，改了很久。
顺便一提，bool operator<(const T &o)在某些环境下是无法编译通过的，但是在某些环境上却可以编译通过，与-std=c++98选项无关，与警告无关。(T){xxxx}也是一样，但是c++11标准是明确支持的，这两个可能会导致CE。为了避免CE，还是手动写一个struct的构造函数为好，最好是以额外的函数形式写。
第二题同样是没有什么头绪，也写了随机化算法，拿到了30分，但是花费了不少时间。第二题解决方法有二：枚举中间节点，跑最小生成树，或者附加状态的dp，或者叫状压dp。
第三题的暴力，可以枚举根节点，跑树状背包。正解是树分治，可惜没有学。
距离NOIP还有30天，需要加倍努力，进省队还是有希望的。
T1 第一题是简单的模拟，首先预处理出\(s[i] = min\{x_j\}(j \le i)\)，设p指向数组末端，从p向前查找第一个大于\(x_i\)的位置，然后把这个位置改为0，重复这个步骤，直到处理完所有输入，或者\(p == 0\)，然后输出\(p\)即可。
T2 这一道题的正解是排序+贪心+并查集，首先将所有的海拔从低到高排序，然后取出其中最低的一个，如果是属于A城市，则连向周围的遍历过的一个点，重复这个步骤，直到所有的A城市的点都于其他点合并了起来。考试的时候没有什么好的思路，于是随机化+卡时，好像拿了30分。
T3 这一题的做法有很多，暴力分能到70甚至90分，常见的做法是：数链剖分、dfs序+数据结构，都可以树状数组/线段树来做。还有做法是利用并查集的路径压缩思想，可以过90分的点。
T4 正解是枚举从左边切的最大次数，然后按照上下左右的顺序切割，直到完成任务。这些做完之后，将图翻转90°，重复。当时写了个有些问题的贪心，只有20分。
今天考了分治，但是几道题都没有用分治做。 - 第一题是栅栏涂色，没有想到怎么写，甚至连贪心都没有写出来，是个失误。正解是考虑[L,R]，高度>H的一段，要么这一段竖直涂色，要么全部水平涂色，然后就求水平涂色的上方的一段。 - 第二题的思路是，二分最大价格，利用所有价格小于它的边建最小生成树，直到所有有冲突的点都被连接起来。瓶颈在找有冲突的点，相当于找平面最近点对。 - 第三题是求\(k^s\mod m\)，其中s非常大，一个方法是利用拓展欧拉定理，将s转成longlong来操作，另一个方法是直接将s看做n进制数，然后进行快速幂，这个不容易出错。 - 第四题不妨称为斐波那契图，20分的数据是\(n,m\le10\)，50分的数据是\(n\le16, m \le 1e5\)，当时只想到了50分的做法，没想到成了最高分。只是递推出了第n张图，然后直接跑最短路，但这样是\(O(Vm)\)的，不过可以离线处理，复杂度降到了\(O(V^2)\)，踩了题解中的50分做法。标程是首先与处理出每张图的第一个点第一个点到最后一个点的距离，然后得出u,v到最近的割点的距离，再计算割点之间的距离，不需要建图，能过n<1000的点。（但是实际上，它不处理n>80的部分，因为再向上就会爆longlong。
事情是这样的，今天第二次做"关押罪犯”一题，奇迹般的MLE了4个点。
一开始想要优化并查集点写法，不想费事初始化，于是有了以下代码
看着没有什么问题。1
2
3
4
5
6
7
8
9
10
11int f[N];
int find(int x)
{
if(f[x])
return f[x] = find(f[x]);
return x;
}
void merge(int x, int y)
{
f[find(x)] = find(y);
}
后来发现把代码改成这样就没有问题了。
但是这样又违背了初衷，感觉很奇怪。 ## 事情的解决
在十几篇博客中的某篇博客的注释中，发现了我的问题所在：如果1
2
3
4
5
6
7int find(int x)
{
if(f[x] != x)
return f[x] = find(f[x]);
return x;
}
//加初始化merge(i,i)，也就是在同一棵子树上的两个节点，再find(i)，就会认为某个节点是子节点，它的父节点也是自己，造成死循环/无限递归，至于是M还是T，取决于时间空间限制。做如下改动就行了
1
2
3
4
5void merge(int x, int y)
{
int rx = find(x), ry = find(y);
rx != ry ? f[rx] = find(ry): 0 ;
}