10.22 模拟赛T1 染色考虑每个连通块删成一棵树就好了。 mmp场上就我路径压缩写炸。。。。 1f[1<<21],n,m,t;F(x){t=f[x];return x^t?f[x]=!t?x:F(t):x;}main(s){for(scanf("%*d%d",&s);~scanf("%d%d",&n,&m);f[F(m)]=F(n))s-=F(n)!=F(m);exit(!printf( ...

CF Round 594(Div1) （A~D）简要题解开学基本打不了cf了啊。。 A Ivan the Fool and the Probability Theory对于$1 \times n$的情况，稍微推一推式子发现是斐波那契数列的两倍（因为第一个位置可以是0可以是1，就是两倍了，否则是一倍）。 考虑第一行，第一行有两种情况： 如果第一行是 01010… 交错的，那么 0 开头可以看成一种颜色，1 开头可以看成一种颜色。然后就成了一个竖着的$1 \times n$的情况。然后考虑第 1 ...

CSP-J/S 第一轮知识点选讲转载自这里 感谢原博主的大力整理! 信息学史及基本知识一、信息学及计算机史 计算机的顶级奖项：图灵奖、冯·诺依曼奖 图灵奖：由ACM（美国计算机协会）设立于1966年。是“计算机界的诺贝尔奖”。 冯·诺依曼奖：由IEEE设立。 对信息科学做出突出贡献的大神：图灵（所以才有个奖），冯 · 诺伊曼 中国获图灵奖的大神：姚期智（清华就有姚班，就是以他的名字命名的） 世界第一台电子计算机：埃尼阿克（$ENIAC$），于1946年2月14日（够虐狗的）在美国宾夕法尼亚大 ...

10.17 模拟赛T1直接看题解吧，懒得写了，和前天T2的思路差不多 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<iostream>#include&l ...

10.16 模拟赛T1首先，对于全0或者全1可以手推或者打表发现是卡特兰数。 假设从0切换到1或者1切换到0，一定有$a_i \leq b_i \leq b_{i + 1} \leq a_{i + 1}$ 相当于一定把前$i$个位置填完了才会开始填$i + 1$个位置。 所以直接乘起来就好了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555 ...

10.15 模拟赛原题场。 A 石子暑假，概率与期望ppt中的经典例题的一道题。。 考虑令$x_i$表示第$i$堆石头在第几次被取。那么有 $x_1 = \sum_i{ [x_i \leq x_1] } = 1 + \sum_i{[x_i < x_1]}$ 两边同时套一个期望，由期望的线性性 $E(x_i) = 1 + \sum_iE([x_i < x_1]) = 1 + \sum_i{P([x_i < x_1])}$ 然后求的就是第$i$堆石头比第一堆石头先取的概率。 这个可 ...

10.14 模拟赛抱歉咕了一天，前一天晚自习搞oj去了。 A 序列开始看错题了1h20分钟。。。。一场爆炸。。 枚举开头是0还是1，就已经确定了每个数字到哪里（这个贪心显然） 然后我们考虑怎样让字典序变小，我们注意到只有同往一个方向走，且可以第一次的可以覆盖第二次的起点的时候可以任意交换。可以拿一个set或者pq维护一下。 真的毒瘤。。 12345678910111213141516171819202122232425262728293031323334353637383940414243444 ...

10.12 模拟赛T1首先有一个显然可以得到的结论，每次减去最大值一定最优。 只会最无脑的做法。。每次减去最大值，复杂度$O(n)$，虽然减了一些枝但还是显然过不去 其实感觉60分做法就很有意思了。 对于$n \leq 10^{12}$ 考虑分开考虑前六位和后六位，这个时候前六位的变化只有$O(\sqrt n)$次。 考虑当前六位的最大值为某一个值时，后六位分别需要多少次才可以变成负数，以及会变成多少 复杂度是$O(\sqrt n)$ 对于$n \leq 10^{18}$ 也是一个挺奇妙的搞法吧 ...

Peaks ( Gym 100365H )这题nk做法还挺正常的。。后面那个循环就很恶心了 考虑 dp[i][j] 表示长度为i的排列，恰好有k个峰的方案数量。 然后转移就是把 i 插入 i-1 的排列。 i显然是i-1的排列里面最大的数，然后插入就只有两种情况： 插入在峰的左右，由于峰不可能相邻，所以可以插入在 2j 个位置 插入在爬山的时候，那么峰的数量+1 $dp[i][j] = 2j\times dp[i-1][j] + ( i - 2(j - 1) )dp[i-1][j-1]$ 其 ...

一种优化方法，具体例子可以看这里 这里只是存一下手写Bitset的板子 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091struct Bitset{ unsigned a[1600]; voi ...

Sums gym100753M同余最短路模板，然而这个东西貌似也可以做去年D1T2 首先我们选择一个模数作为基准，然后剩下的这样连边： 对于一个面值为 x 的硬币 ，当前在 u 这个点（感性理解一下吧） u + x < Mod 这种情况直接从u向 u + x 连一条长度为0的边，表示我们在 0 * M + (u + x) 的时候就已经可以凑出了 u + x > Mod 这种情况下可以 u 向 ( u + x ) mod Mod 连一条长度为1的边，表示通过x的硬币至少在 1 * ...

Break upCF700C 首先考虑只能删一条边的做法，我们可以找出所有的桥，然后随便跑一条 S 到 T 路径，如果这条路径上有桥就说明可以，否则不行 发现这个做法其实是 O(M) 的 那么可以先随便找一条 N 到 M 的路径，分别尝试删这条路径上的边再套上面做法就好了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606 ...

Cycling City毒瘤题 首先建dfs树，由于是个无向图所有返祖边都是连向祖先的。 判是否有解其实很简单，只要图不是一个仙人掌就有解了。 仙人掌有关可以看这个博客 但是这道题由于要输出路径成功变成了一个一个顶俩的题。。。。。 通过判仙人掌我们确认了一个点，它连向自己父亲的路径至少被两个边所覆盖。 然后我们可以从这个点开始深搜，找到这两个返祖，注意是返向这个点祖先的路径。 于是有起点就是这两个路径下端的lca，终点就是这两个路径上端点最深的一个（画图很好看出来的） 然后有哪些路径就显然了。。 ...

Unique PathAGC 038 D 考虑如果两个点之间只能有一个边它们就把它们缩起来，那么最后缩起来的每一块都只能是一棵树。 如果两个点之间必须不止一个边，并且在一个连通块，显然无解。 首先把所有树给连好，现在的可用的边的数量只有$m - n + c$了。 然后两个连通块之间如果有超过一条边，连通块内部的点显然不只一条路径了。 其他情况，如果我们给连通块连边的时候每个连通块都只一直用一个点来往外连，就可以保证所有连通块都满足要求。 如果不存在两个点之间不只一个边的情况 那么只要可用的边的 ...

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 ...