Run for beerCF 575G 如果直接bfs分层贪心可以做，但是很毒瘤，具体可以参考Gavinzheng的提交 考虑魔改dijkstra 首先，每次拿权值最小的来松弛肯定没有问题，只是怎么表示路径长度 由于边权很小，我们只需要拿 排名 * 10 + w 当权值就可以了。 这里的“权值”是相对的权值，具体可以看代码。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474 ...

曼哈顿距离最小生成树codechef Dragonstone 首先，对于每一个点来说有用的边只有它向它通过 x=0,y=0,y=x,y=-x 切出来的八个平面的最近点。 证明 我不会 反正当结论记住就行了 然后我们就只需要考虑右上这个区间的点（因为看起来最好做） 其他的区间可以通过坐标变换到这个区间，并且因为边是双向的，可以只考虑y=-x切出来的右上的这四个区间。 对于一个点$B(x_1,y_1)$和这里的点$A(x_0,y_0)$B是合法的当且仅当$x_1 > x_0 , y_1 &g ...

CF1208H Red Blue Tree原本应该放在这里但是这题过于毒瘤。。单独开了篇blog 首先考虑如果$k$无限小，那么显然整个树都是蓝色的。随着$k$逐渐增大，每个点都会有且仅有一次变色，我们考虑维护这个变色的时间$t$。如果每个点的变色时间都已经被算出来，那么我们可以轻易解决题目的查询操作和修改$k$， 也就是说修改$k$本身就是个假操作。。只需要考虑的是修改单点颜色。 修改单点颜色，看起来就很$ddp$。树链剖分后，用$f(x) = \{a,b\}$表示点$x$重儿子是 R 时的临 ...

Manthan, Codefest 19A XORinacci显然循环节是3 12345678910111213141516171819#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define MAXN 200006int n , m , t;int A[MAXN];int main() { in ...

51nod 1709 复杂度分析考虑定义$F(x)$为$x$为根的子树所有点与$x$的深度差（其实就是$x$到每个子树内点的距离）的 1 的个数和。 注意，$F(x)$的值不是答案，但是只需要一点树形dp的基础内容就可以变成要求的答案。 对于一个点$u$， 考虑它的一个儿子$v$， 我们此时已经计算出了$F( v )$的值那么怎么统计$v$中所有点对于$u$的贡献呢？首先考虑$F(v)$ 的变化，由于当前的点$u$是$v$的父亲，$v$中所有点到$u$的距离实际上是原来到$v$的路径长度 + ...

CF Edu Round 71A There Are Two Types Of Burgers贪心随便模拟一下 12345678910111213141516171819202122232425262728#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;#define MAXN 200006int n , m;int ...

P4551 最长异或路径挺裸的01trie吧，dfs的时候算一下这个点到根路径异或和，加进trie，查一下和trie里面的异或和最大的。 就当用来存一下基础的01trie的板子吧 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<iostream>#include<algorit ...

CF#581 题解A BowWow and the Timetable如果不是4幂次方直接看位数除以二向上取整，否则再减一 1234567891011121314151617181920#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<set>#include<map>usi ...

ZROI 游记在自闭中度过了17天 挖了无数坑，填了一点坑 所以还是有好多坑啊zblzbl 挖坑总集： 时间分治 差分约束 Prufer序列 容斥 树上数据结构 例题C （和后面的例题） 点分 最大流、费用流、上下界 Hero meet devil(dp套dp) Pollards’ Rho CRT & exCRT BSGS & exBSGS NTT & FFT 以及 分治NTT & FFT （& 原根） Cipolla 算法（二次剩余） Min25 Z ...