题解 P4461 【[CQOI2018]九连环】   由于各位大佬已经用各种方法,将公式推得我这里便不再过多阐述,我们来谈谈本题的实现~   首先,我们先来看公式:$\lfloor\frac{2^{n+1}}{3}\rfloor$   我们知道,因为n<=1e5，所以$|2^{n+1}|$很小,而且询问也只有10,所以我们如果能较快求出$2^{n+1}$我们再跑个高精除低精便可以通过此题了...   于是现在问题转化到如何快速求$2^{n+1}$,于是,某大佬站出来刷刷刷...快速幂+FFT 对此我只能orzzzzz   由于我太弱,所以懒得打FFT了,但是打高精明显GG啊...这可怎么...

rt。。。

Floyd再思考   ——by ThinkofBlank   一.序言   Floyd,是一个十分常用的图论算法，其作用是在O(n^3)的时间内计算出全源最短路。其实现原理是利用的dp,然而，刚开始接触Floyd的时候，并没有去尝试理解，思路此算法，仅仅记了下打法就跑了，最近无聊时思考了下，得出了些有用的东西，特此来分享   注意:以下说的图都是无负环的，不然，求甚么最短路。。。   当然，给出的图是联通且点的个数至少为3   二.引入   1、路径合成可行性   给定一个图,假设我们已知i->j的最短路径为a1,i->k的最短路径为a2,(a1<a2)，那么j->k的...

题解 CF785E 【Anton and Permutation】   一.闲谈   听说本题分块可以过而且吊打树套树？orz。。。我果然还是太菜了。。。   二.分析   1.求逆序对   简化题目:给出序列1-n，以及m个操作，每次交换两个数，求当前序列的逆序对数   如果,交换的两个数相同，我们直接输出当前答案即可，那么其他的情况呢？   假设，我们知道交换前的逆序对数，那么新序列的逆序对数便等于原逆序对数加上两个数交换后的贡献   那么，我们来考虑如何计算两个数交换的贡献   我们设两个数分别为x和y,我们再设find_max(l,r,x)表示区间l->r内比x大的数的个数，fi...

玉米田迷宫题解   一.背景   x年x月x日，竞赛老师拿此题问我，然后我玄学过了，于是特来写此题。（谁说dijkstra不能过的？？）   二.分析   本题，我们先不考虑有传送阵的情况，发现，其实就是一个最短路(bfs)的模板题，随便弄下就能过，不过，这里多了个传送阵，于是我们就要考虑下怎么做题了。。。   Method 1   考虑bfs。   通过观察发现，本题的边的权已经不止是我们平常所做的只有1的边权了，还多了传送阵之间的0边权，所以，本题存在0、1两种边权，怎么搞呢？   有个东西叫做01bfs，专门处理这种情况，我们把队列修改为双端队列，一个点，如果是被1边权扩展出来的，我们把...

树链剖分，是个很神奇蛇皮的算法，他巧妙的运用了与分块类似的思想，来加速整块代码。不过，对于某些毒瘤题来说，树链剖分很可能会爆栈，如：一本通:染色。不过洛谷还好，不会爆栈。。。   那么这个时候，我们就需要手动模拟来实现非递归版本的树链剖分了。   注意到，整块树链剖分的代码中使用了递归的地方:   1.两次dfs求dfs序   2.线段树   而其中线段树，我们完全不用改。因为，它的运行层数才log(n)层（要改的话可以去学下zkw线段树）   那么，我们着重看两次dfs。   第一次dfs:   这次dfs，需要我们求出所有节点的:   1.父亲   2.层数   3.子树大小(包括自身) ...

本题有两个问，第一个是求最少硬币数，第二个则是求方案(翻译竟然没写。。。)。   首先，我们来解决第一问。   我们可以很容易想出，这是一个dp，我们设dp[i]表示凑出面值i最少需要多少个硬币，然后打个多重背包就好了。。。于是你就T了。。。   对于多重背包，我们通常使用一种手段:二进制拆分(听说还可以使用单调队列优化,但是本弱鸡并不会。。。QwQ)   二进制拆分，它的原理是:任何一个数都可以用2^0^,2^1^,2^2^...2^k^表示(每个最多取1个)。   于是，对于一个物品的个数C，我们把它成:C=2^0+2^1+2^2...+2^k+X(X<2^(k+1)),这我们就能表...