段三园的小迷弟

题解

心得(37) 未归档(1) 模板题(7) 读书笔记(2)

/ 注册

全部文章 / 题解（共110篇）

p4409 皇帝的烦恼，二分+dp

圆邻相异，满足最小易知如果n个勋章满足，那么n+1+1+....肯定满足那么我们就要找到最小的满足，二分勋章颜色种数，检查是否满足，从中找到最小的可以满足的勋章数量这里ma【i】表示第i个将军在与第i-1个将军不冲突的情况下，手中勋章与第1个将军颜色同的最多个数 mi【...

二分 dp

2020-04-20

0 651

蓝桥杯芯片测试，思维题

一开始想用并查集，如果双方都认为对方是好的就放在一块，最后把最大的块输出但看了别人的题解发现思维题一道，因为好芯片多，所以只要认为这个芯片好的坏的多，那么这个就是好芯片 #include<bits/stdc++.h> using namespace std...

思维题

2020-04-19

0 571

P3200HNOI2009有趣的数列，卡特兰数

首先看到2n，两个一组（a2i-1<a2i）可以想到卡特兰数设奇数组的是（，偶数组的是），这就转化成了卡特兰数模型这里用 C（2e6,1e6）大概有1e6位，但有mod p 一开始想*逆元（p不一定素数，exgcd）来搞定除数，但是逆元要求a和mod必须...

因数约数卡特兰数

2020-04-15

0 599

P2532 树屋阶梯，卡特兰数+高精度

先用dp的想法来思考这个问题设f【i】表示i层的方法数如何用x之前的f来表示f【x】我们可以把阶梯以某一层分成两块，这两块都在x~x-1层之间所以x层就被分层了i，1，n-1-i三个部分则f【n】=f【i】+f【n-1-i】（分的方法总和），遍历i：1...

高精度卡特兰数

2020-04-15

0 647

p4981父子， prufer序列->cayley定理

n点无根树的选择方法是n^(n-2) 一个无根树有n个点选作根，方法数=n^(n-2)*n=n^(n-1) #include<bits/stdc++.h> using namespace std; typedef long l...

prufer序列

2020-04-10

0 663

p1976鸡蛋饼，卡特兰数+逆元

（2n个点，就要联想到卡特兰数）从第一个开始操作点开始编号，1,2,3。。。。我们发现如果如果连接奇数-奇数，那么必定会有一个偶数点没办法满足题目的连接（即必会交叉）所以我们一定是奇数-偶数这样连再深挖下，我们发现交叉都是在始点1-终点1中的点中，有始点的终点>...

卡特兰数逆元

2020-04-10

0 565

p1044栈，卡特兰数

设f【i】表示i个数的方法数最后出来的数是i的方法数f【i-1】*f【n-i】，（这里i-1+n-i=n-1就可以大致判断出事卡特兰数）有n个数的方法数等于每个数最后出来的方法数的和即：，第一个数是0 一个数最后出来的方法数是1——f【0】=1 二个数最后出来的方...

卡特兰数

2020-04-10

0 630

牛客练习赛60a大吉大利，二进制+组合

把所有的数转成二进制，然后统计每一位1的个数，然后每一位内部组合，注意组合a&b==b&a且视为2组最后再加上每个数自己和自己组合，即累和如1,10,11,100,101（1-5），20位累计3（C（3,2）*2*20），21位累计2（C（2,2）*2*21）,22累...

二进制排列组合

2020-03-28

4 667

牛客练习赛60d斩杀线计算大师，exgcd

把x遍历一遍，然后把转化为关于y，z的yb+zc=（k-xa）的二元一次方程（exgcd模板题），exgcd求解用exgcd求出的是y0，然后转成y（放大（k-xa）/gcd倍），这里的t是y的最小增幅 #include<bits/stdc++.h> using&n...

exgcd

2020-03-27

7 806

牛客小白月赛23f美丽的序列I，数学+分类

一个不降序列本身度是1，要分成若干不降，那么每降的地方就分割一次，所以就转变成求序列有多少前>后——分割次数一个确定数列的美丽度=1+分割次数 1是每个数列都要加的，分割次数不确定（可能为0）所有的1的和=可以排成的数列方案数分割次数和=（遍历每两个相邻数）ai&...

数学分类排列组合

2020-03-23

3 750