状压dp入门 状态压缩嘛，就是把连续的一坨可以用01表示的状态，搞进个整数里，然后用位运算来进行检查、转移等操作。 例题 [SCOI2005]互不侵犯 每行国王分布的情况可以用01表示，这样就可以把每一行的状态用一个整数表示。 先预处理出一行里面没有会打架的的所有情况，和该情况对应的国王数量 f[i][j][k]为第i行的状态为第j种时，一共用了k个国王的方案数 那么f[i][j][k...

N0lP 2018 货币系统 划水一周就写了个这玩意儿？ 题目 传送门 货币种数为 nnn、面额数组为 a[1..n]a[1..n]a[1..n]的货币系统记作 (n,a)(n,a)(n,a)。 两个货币系统$ (n,a)$ 和$ (m,b)是等价的，当且仅当对于任意非负整数是等价的，当且仅当对于任意非负整数是等价的，当且仅当对于任意非负整数x$，它要么均可以被两个货币系统表出，要么不...

经过了一周的划水，我终于搞懂了cdq分治。 总的来说，cdq分治处理偏序问题就是 先把左边和右边当成一个完整的问题处理 然后把左边对右边的影响合并到右边 例题 园丁的烦恼 传送门 求静态区域内的点数，二维偏序模板题。 #include<cstdio> #include<algorithm> const int MAXN = 500000 * 5 + 5;...

Dijkstra嘛，就是每次从最短路未固定的点中找到已知最短路最短的点，然后将它固定，并更新这个点连接的其他点的最短路。最开始时，源点到源点的最短路为0。 所以，复习了一遍Dijkstra然后发现了几个函数 make_heap (first, last, comp) : 把一个数组搞成一个堆 push_heap (first, last, comp) : 让数组末尾的数浮到堆中正确的位置...

强连通分量 染色为搜索树根节点编号： void tarjan (int p) { dfn[p] = low[p] = ++tim; v[p] = 1; s.push(p); for (int i = head[p]; i; i = e[i].nex) { int y = e[i].to; if (!dfn...

题目 为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择． 每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若...

洛谷P3387 【模板】缩点 当我对比大佬的代码调出错误之后，我不禁觉得我之前能过那么多个点简直就是个奇迹 题面 给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。 输入格式： 第一行，n,m 第二行，n个整数，依次代表点权 第三至m+2行，每行两个整数u...

[USACO18DEC]Fine Dining 咕咕咕。。。 什么？前几次考试？ 。。。有空就补（放心你没空的） 题目 漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。农场由N片牧场组成（2≤N≤50,000），方便起见编号为1…N。所有奶牛都要前往位于牧场N的牛棚。其他N?1片牧场中每片有一头奶牛。奶牛们可以通过M条无向的小路在牧场之间移动（1≤M≤100,000）。第i条小路连接牧...

题目 （翻译太水了所以用英文） Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the “Submit” button twice when selecting extra features for the car, and as a result ...

题目 给一个函数 f，f 在一开始会传入 x 的初始值。f 有一些指令，指令分三种： for n - 循环 end - 每个循环的终止符。每个配对的 for n 和 end 之间的代码都要被运行 n 次。保证每个 for n 指令都能与一个 end 指令配对。 add - 将 x 增加 1。 做完所有操作后 x 被当做返回值返回。 在中途的运算中，x 可能会大于 232?12^{3...