__故人__

分类

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

2020牛客国庆集训派对day2 C 来自专栏

题意从个位置中选出两两不相邻而且元素尽可能多的方案数。分析我们可以考虑递归有序列这个时候如果我们在末尾添加了新的元素，那么我们就可以在第或者第个选择一个。那么我们就有递推式。在时。特判一下就好了。最后输出因为我们对于最后一个元素可以选择也可以选择。代码 #...

2020-10-14

5 500

[ZJOI2006]物流运输

分析我们可以对于每一天考虑，如果有一天改了道，那么贪心的选择也应该是最短路，而不是其它的路径。这个还是比较显然的。那么现在考虑一个线性。令表示考虑从第天的最小代价和。那么转移为。这里引入了一个的数组。这里表示从第天到第天的合法的最短路。那么我们可以先预处理总的复...

2020-10-14

6 668

2020牛客国庆集训派对day2 B 来自专栏

分析很套路的一道题，但是初始值初始时有点搞心态。主要是考虑到，很自然的想到用状压去维护。定义为当前节点在，已经过了的节点状态为。那么我们的转移也比较简单。那么我们只需要预处理即可。代码 #include<bits/stdc++.h> using namesp...

2020-10-13

6 655

2020牛客国庆集训派对day2 A 来自专栏

题意给你两个整数，要求求出约瑟夫问题中最后一个人是谁。分析总所周知，约瑟夫问题有模拟，线性。这里解释一种的解决方法。考虑到我们每次走个删一个，那么在一圈以内我们可以删掉个。我们可以模拟这个过程递归求解。由于每次递归问题规模变为。通过归纳验证时间复杂度大概是代码...

2020-10-13

4 846

Garland

分析我们对于每个子树的答案是可以预先知道的，那么如果那么一定无解。之后我们可以直接遍历整个树得到的节点。那么当这样的节点个数超过的时候，这个树就是合法的，输出两个非树根的节点就可以了。那么总的复杂度为。代码 #include<bits/stdc++.h> usin...

2020-10-13

5 628

多项式求ln 来自专栏

关于多项式的操作，我会慢慢补充的。多项式求ln 前置公式，和。前置知识，多项式点值表示，多项式求逆。给你一个多项式，要求求出一个多项式满足。考虑积分和求导。我们考虑是和复合。那么那么，左右同时积分。那么就做完了。代码 #include<b...

2020-10-13

4 611

筱玛爱线段树

分析我们主要考虑如何处理的操作又重新做一次，这个我们考虑区间加，定义为第次操作要执行的次数。那么这个我们可以通过差分做到。最后处理区间加。这个一样可以用差分来做，那么最后的复杂度为。差分，我们定义数组，如果原值为。那么满足。那么给全部等同于。这样我们对...

2020-10-12

11 688

关于Bell的指数型生成函数推导来自专栏

必要公式首先我们知道根据第二类斯特林数和贝尔数的定义很容易证明。第二类斯特林数的通项公式，可以根据容斥定理枚举空的盒子得到。我们知道这个是在处的展开。而，因此得证。这个是最简单的二项式展开了。不多说明。推导那么现在。是不是很神奇，神奇就点个...

2020-10-10

4 944

Angry Cows(Silver)

分析我们可以考虑一个合法答案，那么，则也是一个合法答案。那么这个满足单调性，我们可以考虑二分，如何判断是否是一个合法解。我们考虑贪心，从左向右考虑，每次考虑最靠左而且没有被现在的区间覆盖的点。对于这个点也可以二分，好像直接做也没有问题。那么最后判断是否就可以了。代码中所有二...

2020-10-10

3 685

牛客练习赛71 C 来自专栏

分析我们可以假象一个假的限制记录前个条件都满足，但第个条件不满足的方案数，考虑之间的数随便排列，，然后第个条件不满足，前个条件都满足，乘；对于不同的，方案是不相交的，且计算了所有不应该在中计数到的方案数所以。思路来源与不知名的大佬。我这里只是分享一下做法...

2020-10-10

9 552