比较显然，从根节点出发，并不方便做题，所以要颠倒关系，然后就有了树型dp。
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
using namespace std;
const int N = 1e6+5;
struct edge{
int t, w;
};
vector<edge> g[N];
int tot;
int dfs(int i, int fa)
{
int mmax = 0;
for(edge &e : g[i])
{
if(e.t == fa) continue;
e.w += dfs(e.t, i);
mmax = max(mmax, e.w);
}
for(edge &e : g[i])
{
if(e.t == fa) continue;
tot += mmax - e.w;
}
return mmax;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int s;
cin >> s;
for(int i = 1; i <= n - 1; ++i)
{
int a, b, w;
cin >> a >> b >> w;
g[a].push_back(edge{b, w});
g[b].push_back(edge{a, w});
}
int ans = dfs(s, 0);
cout << tot << endl;
}
关于老旧浏览器提示证书错误的问题
Posted on
Edited on
经过测试，在xp ie8和Nokia 按键手机的浏览器环境下，访问部分网站提示证书网址不匹配。测试后，发现原因是服务器上有多个证书，有属于自己服务器的证书，也有不属于自己服务器的证书（通常是服务器提供商的默认证书），部分老旧浏览器不支持自动识别，于是报错。 其他浏览器没有测试。 可以看这个网站：这里
[SDOI2009]学校食堂 题解
Posted on
Edited on
这是一道并不复杂的状压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> |
道路游戏 题解
Posted on
Edited on
写在前面
这道题在我的题目列表里躺了好久，一直不会做，今天终于做出来了。 思路：
\(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;
}
[ZJOI 2005]午餐 题解
Posted on
Edited on
看了半天题解，发现：这不就是一道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;
}
NOIP知识点 总结
Posted on
Edited on
这里是OI知识点的总结
经过这几年的学习信息奥赛，现在此写下我的感受。
更新：2019年，NOIP取消，我成为了最后一界NOIP选手。以此纪念我三年的信息奥赛生涯
贪心算法
贪心算法指： 求解某一问题时，做的某一个策略一直是局部最优解。每次将问题规模减少，直至减少到基础情况。
- 时间复杂度 \(O(n)\)~\(O(n\log n)\)甚至更高
- 空间复杂度 \(O(1)\)~\(O(n)\)或者更高
适合使用贪心算法的条件
- 具有最优子结构： 一个题目的最优解，一定包含当前的局部最优解。这可以通过数学方法证明。
- 无需具有可后撤性
- 题目的数据范围极大，甚至无法用\(O(n\log n)\)算法拿满分
- 想不出正确的DP做法，试图通过奇怪的贪心拿部分分
适合配合使用的算法
随机化
对于无法直接贪心的题目，配合随机化，将贪心步骤打乱，可能会产生更优的解，以此更新最优答案。
调整
有些题目的正解是贪心+调整，每一步都采取贪心策略，将然后剔除部分不是最优的解，这样下去可能会产生最优解。
不适合使用贪心算法的情景
- 求解方案数
- 全局最优解和局部最优解极度不相关
- 数据范围较小，这种题目的正解显然不是贪心
动态规划
动态规划是一种依据子问题来确定当前问题的最优解的过程，一般是一种自底向上的做法。 通常来讲，正解是贪心的题目一定有动态规划的做法，正解是动态规划的题目一定有搜索做法。 通常递推的做法也可以算作动态规划。 动态规划的核心是状态转移方程，每个状态只由已知的状态推导出。
适应于动态规划的题目
- 问题可以分解为若干子问题，子问题之间没有干扰， 不具备后效性，做出一个决策只和当前状态有关，不会影响后续的状态
- 具有最有子结构，全局最优解一定是由局部最优解构成
- 子问题具有重叠性，每个子问题都是一样的。
不适应于动态规划的题目
- 数据范围较大，不适合\(O(n^2)\)的时间复杂度。这一点有例外，将在后来讲。
- 决策具有后效性，当前的决策会影响后来的决策，或其他子问题的决策。这一点可以通过拓扑排序或dfs序排序来消除。如果不能消除，则不存在有效的动态规划做法。
- 过于复杂的题目，动态规划做法很难写对，这属于个人问题。
- 显然存在贪心做法的题目
- 各种数据结构题
动态规划的题型
区间DP
常见的题目描述是，给定一个长度为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); }
}
数据结构
树状数组
线段树
平衡树
STL
堆
队列
堆
PS
写了一下午一晚上，好累
洛谷P2252 取石子游戏 题解
Posted on
Edited on
同学在做这道题，我就一起做了，没想到比他A得还要早。这是一个考试中比较实用的做法。
对于\(mn \le 5000^2\)
首先针对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 |
今日考试存在的问题
Posted on
Edited on
2018-10-29~2018-10-30
T1 逃离
原题考的数据范围比较小，标程给了\(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掉了，原因是读入时没有和下表对齐。
T2 求最大01子矩阵，行可以交换。
做法有很多，比如枚举每一行的排列，随机化+卡时等，这些期望是20分的。 更好的做法有：预处理出right数组，排序后用单调栈找最大矩形，或者二分长度，找最大出现次数，这些分别是\(O(mn\log n)\)、\(O(mn\log m)\)的，能过70分的点。 标程是在预处理出right数组，排序后用单调栈找最大矩形的基础上，用计数排序，压缩掉了log的复杂度，是严格\(O(mn)\)的
这道题的问题是，为了保险，写部分分的解时，5000*5000的数组开了7个，导致MLE。
T3 两个限制的最小生成树
题意：每条边有两个权值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一片
T4 permutation
这是一道水题，用桶计数，每次分配桶内元素的个数+1作为第x个排列，最后桶内元素需要非严格递减，才是由排列构成的，否则就不是。 这道题看错了题意，以为排列只能向后弄，只拿了10分样例分。
T5 zuma
部分分有搜索+剪枝，正解的dp很难想，也有情况无法处理，只拿了20分。 ## T6 正解是并查集或树套树，大概是。//TODO
某个快读算法
Posted on
Edited on
原理是替换掉了默认的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; }
[NOI 2005] 智慧珠游戏 题解
Posted on
Edited on
大家的都太长了，发一个比较短的代码，洛谷上测的时间为800ms。思路大概是，暴力枚举，还有一些剪枝。用了一些奇技淫巧，没有删除调试代码，也没有压行。可以注意一下预处理的方式。
1 | #include <bits/stdc++.h> |