- 博客(214)
- 收藏
- 关注
RSS订阅转载 《长安十二时辰》愿你看尽世间百态，心中仍有热血
在西安的古城墙下，在古都的余晖中读完了70万字的《长安十二时辰》。有人说《长安十二时辰》是《刺客信条·天朝大都》，有人说《长安十二时辰》是《长安：反恐24小时》。但在读完原著后，深深感到这才是一个有着中国内核的故事。记得黄仁宇先生在《万历十五年》开篇：“这一年是24岁的万历皇帝登基的第15个年头，元辅张居正去世的5周年，……其实这一年大明王朝并没有发生什么惊天动地的大事，所以不为一般...
2019-07-20 19:22:00
593
转载 洛谷 [P1337] 平衡点
模拟退火练手一道模拟退火的好题结果一定势能最小与模拟退火思路高度一致#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <cmath>#includ...
2018-11-08 14:35:00
313
转载 洛谷 [P3496] BLO
割点首先 tarjan 求割点,对于不是割点的点, 答案是 2 * (n-1) 有序，所以要乘 2对于是割点的点, 答案是删去该点后所有连通块的个数加上 n-1 在乘 2#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include...
2018-05-27 07:59:00
219
转载 洛谷 [P2341] 受欢迎的牛
强连通分量一个结论: 在有向图中, 一个联通块能被所有点遍历当且仅当图中只有一个连通块出度为零#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm&...
2018-05-24 16:23:00
164
转载 洛谷 [P3723] 礼物
FFThttps://www.luogu.org/problemnew/solution/P3723重点在于构造卷积的形式#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include...
2018-05-24 09:56:00
152
转载 洛谷 [P3338] 力
FFT\[E_i = F_i / q_i = \sum_{i<j} \frac {q_j} {(i - j)^2} - \sum _{ i > j} \frac{q _ j} {(i - j)^2}\]设 \(p _ i = q_{n - i}\) \(g(i) = \frac 1 {i^2}\)则 \(E_i = \sum_{j=1}^{i-1} q _ i g(j ...
2018-05-24 08:43:00
156
转载 FFT与NTT
讲解:http://www.cnblogs.com/poorpool/p/8760748.html递归版FFT#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>#include &l...
2018-05-23 16:50:00
192
转载 洛谷 [P2051] 中国象棋
DPorz__stdcall首先要想出来，每行最多只能放两个棋子，这是显然的于是决策就是一行一行地处理30分的做法就是裸的枚举，暴搜，枚举这一行放哪里，放几个然后想到了压位dp，按3进制表示当前棋盘的状态，即某一列没有棋子，或者有一个，两个棋子，能过50分接着可以发现，棋子的顺序是无所谓的，并不需要准确知道当前棋盘的状态于是有了100分做法：dp[i][j][k]表示放了前...
2018-05-22 19:35:00
181
转载 洛谷 [P2577] 午餐
DP + 贪心我们发现,如果只有一个窗口,贪心即可解决,吃饭时间长的人一定要先打饭有两个窗口的时候,这条性质依然满足,但是两个窗口如何分配,需要 01 背包#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <a...
2018-05-22 14:28:00
126
转载 洛谷 [P3620] 数据备份
贪心神题首先我们发现一个显然的贪心策略,连接相邻两个写字楼总是更优.所以本题就变成了数轴上一堆点,要选 k 个彼此不相邻的区间,使得区间长度最小对于 10000 的数据来说,我们可以用 DP 解决,f[i][j]表示考虑前i个点，已经形成j对点的最小距离，num[i]表示第i个点的坐标。如果这个点不与其他点组成一对，那么f[i][j]=f[i-1][j]。否则这个点只能和前面...
2018-05-03 20:09:00
215
转载 洛谷 [P3623] 免费道路
有 k 条特殊边的生成树我们发现有一些边是必须的,如果把所有的水泥路都加入并查集,再枚举鹅卵石路,如果这条路能再次加入并查集,说明这条路是必须的水泥路同样这样就把必需边求出来了,剩下就可以随意加边了#include <iostream>#include <cstdio>#include <cstdlib>#include <algo...
2018-04-28 11:37:00
220
转载 洛谷 [P1552] 派遣
树型DP + 可并堆非常清楚的想到是树型DP, 但是如何维护最小值, 于是就去新学了可并堆#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>#define ll long long...
2018-04-27 21:20:00
106
转载 洛谷 [P3377] 左偏树(可并堆)
可并堆,就是可以合并的堆注意并查集不能路径压缩,不然删除根节点时会出错#include <iostream>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstdio>using na...
2018-04-27 20:03:00
128
转载 洛谷[P3622] 动物园
状压DP发现本题中,每个小朋友是否高兴仅取决于其后五个动物的情况,我们可以用状压DP解决本题首先已处理 num[i][s] 表示对于位置 i ,状态为 s 时有多少在 s 的同学满意转移方程很好写dp[i][s] = max(dp[i - 1][(s&15)<<1], dp[i - 1][(s&15)<<1|1]) + num[i][s];...
2018-04-25 20:53:00
168
转载 洛谷 [P3381] 最小费用最大流模版
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <queue>using namespace std;c...
2018-04-04 10:09:00
88
转载 洛谷 [P1608] 最短路计数
最短路计数模版本题要注意重边的处理#include <iostream>#include <cstdio>#include <algorithm>#include <cstdlib>#include <cmath>#include <queue>#include <cstring>usi...
2018-04-03 19:44:00
145
转载 HDU [P3849]
tarjan 求 无向图的割边 (桥)边 (x,y) 是桥当且仅当, 对于 x 的子节点 y ,low[x] < dfn[y]对于连向父节点的边要特殊处理#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <...
2018-04-02 15:01:00
141
转载 洛谷 [P3388] 割点模版
tarjan 求无向图的割点割点,即割去此点后原图可变为两个或多个独立的联通块一个点 x 是割点,当且仅当存在一个x 的子节点 y ,使得 low[y] >= dfn[x]对于根节点来说,需要两个满足的节点#include <iostream>#include <cstdio>#include <cstring>#include &...
2018-04-02 10:44:00
106
转载 POJ 1741 Tree
点分治非常巧妙的实现, 复杂度 O(n * log ^2 n)https://www.cnblogs.com/GXZlegend/p/6641720.html#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <...
2018-04-01 16:44:00
116
转载 洛谷 [P4301] 新Nim游戏
线性基 +博弈论先手必胜当且仅当先手取完之后留下的序列无论如何组合，异或和都不为 0也就是剩下的整数线性无关,所以我们对所有整数排序,由高往低的贪心的插入线性基,无法插入的就有先手取出,容易发现,先手必胜#include <iostream>#include <cstdio>#include <cmath>#include <alg...
2018-03-30 21:21:00
144
转载 HDU [P5015] 233 Matrix
矩阵快速幂按列递推#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <cstring>#define ll long longusing namespa...
2018-03-30 19:40:00
122
转载 POJ 3233
矩阵分治注意不要用 (*this) 会改变原值#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <cstdlib>using namespace std;...
2018-03-30 15:37:00
93
转载 洛谷 [P3629] 巡逻
树的直径树的直径有两种求法1.两遍 dfs 法, 便于输出具体方案,但是无法处理负权边2.DP 法,代码量少,可以处理负权边#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#inc...
2018-03-29 16:43:00
169
转载 POJ 2728 Desert King
最优比率生成树01 分数规划与MST的结合,注意总成本与总长度比值最小,不等价于总长度与总成本比值最大#include <iostream>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <algori...
2018-03-29 15:09:00
85
转载 洛谷 [P2886] 牛继电器Cow Relays
最短路 + 矩阵快速幂我们可以改进矩阵快速幂,使得它适合本题用图的邻接矩阵和快速幂实现注意 dis[i][i] 不能置为 0#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#inc...
2018-03-28 19:33:00
211
转载 POJ 1734 Sightseeing trip
floyd求无向图最小环 +输出路径注意保存原来的边, 求最小环的时候要用#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstdlib>#include <vector>#includ...
2018-03-28 15:18:00
121
转载 洛谷 [P3008] 道路与航线
最短路因为有负权边,所以不能 dijkstra ,本题数据还卡 SPFA但是我们发现,有负权的都是有向边,而且如果把无向边连成的联通块看成一个点的话,有向边就连成了一个 DAG,所以我们可以对所有的联通块用dij求最短路在 DAG上用拓扑序求最短路注意:堆优化的 Dijkstra 在定义的结构体重载运算符的时候注意相反因为存在负权边,所以两点不可达,不等价于两点间的距离 ==...
2018-03-27 21:21:00
262
转载 洛谷 [P1948] 电话线
二分答案首先,最大值最小,就是二分答案#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstdlib>#include <cstring>#include <queue>u...
2018-03-27 16:31:00
133
转载 洛谷 [P3455] ZAP
莫比乌斯函数#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#define ll long longusing namespace std;const int MAXN = 500...
2018-03-27 09:33:00
106
转载 CF 451E Devu and Flowers
可重集的排列数 + 容斥原理对于 \(\{A_1 * C_1, A _2 * C_2, \cdots, A_n * C_n\}\)这样的集合来说,设 \(N = \sum_{i = 1} ^ n A_i\), 要在这个集合中取出 \(M\) 个元素来,这样的方案数是:\[ C _ {N+M-1}^{N-1} - \sum _ {i =1} ^ n {C_{N+M-A_i - 2}^...
2018-03-26 20:50:00
117
转载 tyvj 2002 扑克牌
期望DP本题递推比较麻烦,可以记忆化搜索注意搜索的边界条件以及每一次转移#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>using namespace std;double dp...
2018-03-26 15:17:00
152
转载 tyvj 2020 rainbow 的信号
期望被精度坑惨的我注意:能开 long long 尽量开, 先除后乘, int 转 double 的时候 先转换在做运算本题与位运算有关,位与位之间互不影响,所以我们可以分开考虑#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#i...
2018-03-25 21:43:00
147
转载 POJ 2976 Dropping tests
01 分数规划利用实数域下的二分答案来解#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define eps 1e-5using namespace std;int T, n, ...
2018-03-25 20:04:00
85
转载 洛谷 [P2480] 古代猪文
卢卡斯定理注意特判底数和模数相等的情况http://www.cnblogs.com/poorpool/p/8532809.html#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#d...
2018-03-24 09:41:00
108
转载 卢卡斯定理
当 p 为质数时\[c_m^n \equiv c_{m\%p}^{n\%p} * c_{m/p}^{n/p}\pmod p\]模版,注意这其中的逆元求法#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <c...
2018-03-23 20:25:00
109
转载 LFYZOJ 104 Counting Swaps
题解#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#define ll long longusing namespace std;const int MOD = 1e9 + 9, ...
2018-03-23 14:46:00
160
转载 POJ 2893 M × N Puzzle
逆序对n 数码问题的扩展对于一个n * m 的问题来说,结论和 列数 m 奇偶有关对于 m 是奇数来说 , 两个局面互相可达,当且仅当这两个局面按顺序写成一个数列,这个数列的逆序对数的奇偶性相同对于 m 是偶数来说, 两个局面互相可达,当且仅当这两个局面按顺序写成一个数列,这个数列的逆序对数的差与空格所在的行数差的奇偶性相同(证明 ,不存在的)#include <ios...
2018-03-22 19:41:00
110
转载 POJ 2411 Mondriaan's Dream
状压DP#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define ll long longusing namespace std;const int MAXN = 3000;...
2018-03-22 14:52:00
99
转载 洛谷 [P2859] 摊位预定
贪心#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int MAXN = 50005;int init() { int r...
2018-03-21 15:10:00
151
转载 洛谷 [P2887] 防晒霜
贪心首先以 miSPF 为关键字降序排列,然后对于每一头奶牛寻找满足范围的 SPF 值最大的防晒霜用,我们发现,因为已经按最小值降序排列,所以对于下界来说若当前奶牛满足,之后的奶牛肯定满足,对上界来说,对于 SPF[x] < SPF[y] 来说,只可能 x,y 都满足, x,y 都不满足, 或 x 满足 y 不满足.所以选最大的肯定更优#include <iostre...
2018-03-21 11:32:00
218
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人