__故人__

分类

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

/ 注册

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

30篇文章 847人学习

22篇文章 1707人学习

全部文章（共169篇）

牛客小白月赛28 B 来自专栏

分析对于博弈问题我们可以把从一个必胜状态和必败状态进行推导。我们已经知道是个必败节点，那么则是必胜节点，从而可以得到也是必败节点。把图画出来，我们发现出现了一个很显然的分形结构，而最小单元是个的图，把表打出来就可以了，时间复杂度为。代码 #include<bits/st...

2020-09-21

6 652

牛客小白月赛28 A 来自专栏

分析我们可以求出单次抛出的概率为，所以赢的概率为，那么输掉的概率为，快速幂计算，时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char...

2020-09-21

4 645

[BZOJ 3028] 食物来自专栏

分析刚学生成函数，来试试水。我们先把每一种的生成函数写出来，并转化为封闭性式。全部相乘之后。如何转化为幂级数的形式。因为所以所以最后的答案为。代码 #include<bits/stdc++.h> using namespace std; cons...

2020-09-21

3 605

[TJOI/HEOI2016] 求和来自专栏

[TJOI/HEOI2016] 求和所以我们现在可以求出了。因为后面的式子已经是卷积形式了了。代码 #include<bits/stdc++.h> using namespace std; const int p = 998244353,Gi = 3,N = 1e6 +...

2020-09-19

4 626

多项式乘法逆来自专栏

多项式乘法逆给你多项式，寻找一个多项式满足。考虑倍增求解。如果我们已知，而根据。那么显然 ,两式相减那么 ,左右相减。考虑左右都乘上一个，那么移项。那我们的递归出口为。代码 #include<bits/stdc++.h> using name...

2020-09-19

5 710

[HNOI2017]礼物来自专栏

分析我们发现，对于一个序列进行旋转操作，其实可以等同于只对一个序列进行操作。然后加上改变量所以题意其实就是要我们求。我们先把中间的式中拆开。变成了这个式子。那么我们可以考虑枚举。那么现在就只有是没法很快求出来的了。可以令一个数组，保证，那么现在，就是要求，这个就是个标...

2020-09-19

5 0

[SCOI2009]游戏

分析我们先引入一个概念，置换。这里我简单的说一下，就是把个元素的其它排列与原排列的映射关系。可以用一个数组表示。而这个道题就是给出一个置换，求有多少个不同的循环。为什么置换存在循环。不难发现，如果把每个数字看作一个节点，那么每个节点都有一个后驱节点和一个前驱节点，所以出度和入度都为 ...

2020-09-18

9 1450

牛客挑战赛42 F

分析分析题意，我们可以发现它就是要让求。而是可以线性筛求出来的。所以现在问题就是如何维护矩阵中的。因为，所以可以考虑二维莫队这样的时间复杂度为。这道题卡空间，要注意线性筛时可以不用额外数组记录。后话关于牛客挑战赛42的题就算补完了，可以说这套题还是不错的，只是有些题面稍...

2020-09-18

4 535

牛客挑战赛42 E

分析令为以结尾的最小代价。，后面的可以前缀和优化一下。。令为的决策点，那么可以化简为。那么这个就是个一次函数。其中，所以为了让最小，那么我们显然要让最小。那么现在就是要求的最小值，放在坐标轴上，就是求直线与所有一次函数的最小值，这个可以李超线段树来求...

2020-09-17

3 571

联合权值

分析每条边的边权为，由于输入的图是一颗树，那么之间有且仅有一条简单路径，所以合法的点对中间只会有一个点。所以考虑枚举中间的节点。令表示节点为中间节点的权值之和，那么。因为，所以可以先考虑有序点对的值最后再就好了。所以，表示在为中间点，为当前考虑点，已...

2020-09-17

7 795