Run For Beer CF575G
Run for beerCF 575G 如果直接bfs分层贪心可以做,但是很毒瘤,具体可以参考Gavinzheng的提交 考虑魔改dijkstra 首先,每次拿权值最小的来松弛肯定没有问题,只是怎么表示路径长度 由于边权很小,我们只需要拿 排名 * 10 + w 当权值就可以了。 这里的“权值”是相对的权值,具体可以看代码。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474 ...
阅读更多
曼哈顿距离最小生成树 codechef Dragonstone
曼哈顿距离最小生成树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
CF1208H Red Blue Tree原本应该放在这里但是这题过于毒瘤。。单独开了篇blog 首先考虑如果$k$无限小,那么显然整个树都是蓝色的。随着$k$逐渐增大,每个点都会有且仅有一次变色,我们考虑维护这个变色的时间$t$。如果每个点的变色时间都已经被算出来,那么我们可以轻易解决题目的查询操作和修改$k$, 也就是说修改$k$本身就是个假操作。。只需要考虑的是修改单点颜色。 修改单点颜色,看起来就很$ddp$。树链剖分后,用$f(x) = {a,b}$表示点$x$重儿子是 R 时的临界值 ...
阅读更多
Manthan, Codefest 19 题解
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 复杂度分析
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 71
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 最长异或路径
P4551 最长异或路径挺裸的01trie吧,dfs的时候算一下这个点到根路径异或和,加进trie,查一下和trie里面的异或和最大的。 就当用来存一下基础的01trie的板子吧 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<iostream>#include<algorit ...
阅读更多
CF#581 (div2)题解
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 2019 暑期游记
ZROI 游记在自闭中度过了17天 挖了无数坑,填了一点坑 所以还是有好多坑啊zblzbl 挖坑总集: 时间分治 差分约束 Prufer序列 容斥 树上数据结构 例题C (和后面的例题) 点分 最大流、费用流、上下界 Hero meet devil(dp套dp) Pollards’ Rho CRT & exCRT BSGS & exBSGS NTT & FFT 以及 分治NTT & FFT (& 原根) Cipolla 算法(二次剩余) Min25 Z ...
阅读更多