louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解 | 信息学奥赛一本通有趣的数列

思路我们将按次序填入,填入未填的,编号最小且为奇/偶数的项.也就是说,位置必须在之后再填.因为,任何时候已填的奇数项不能少于偶数项.这样子可以看成一个栈,填入一个奇数项表示一个元素进栈,填入一个偶数项表示栈顶弹出.所以答案就是卡特兰数第项.复杂度大概为. 代码 #include<bits/s...

卡特兰数

2019-09-01

0 584

题解 | 信息学奥赛一本通序列统计

思路不降的话先改成严格上升,也就是第个数加上,范围就是.然后长度为的序列个数为(选任n个,然后排序,第i项减i还原成不降序列).总答案就是,也就是.用卢卡斯定理求解即可.复杂度. 代码 #include<bits/stdc++.h> using namespace std; #defi...

排列组合

2019-09-01

0 718

题解 | 信息学奥赛一本通数三角形

思路选任意不同的三个点方案数为.然后需要减去共线的三个点的方案数.首先横纵方向.然后考虑枚举每个向量(也就是斜率和长度相同的线段同时枚举),该向量起始位置和中间的某个点为一种方案,那么对于向量,贡献为.上下翻转也是可行的,贡献再乘2.这样子复杂度就是. 代码 #include<bits/st...

排列组合

2019-09-01

0 656

题解 | 信息学奥赛一本通 2^k 进制数

思路跑动态规划.表示第位的数位,前位已经确认的数的个数.转移应该挺好转移的,需要用前缀和优化一下.内存可能比较大,需要滚动数组.最后把满足要求的答案全部加起来就可以了.复杂度为,看起来比较大,实际上基本上跑不满,还是可以过的. 代码 #include<bits/stdc++.h> us...

高精度动态规划

2019-09-01

0 699

题解 | 信息学奥赛一本通樱花

思路先考虑.也就是.考虑..因为互质,所以.所以当且仅当且时满足条件.考虑把质因数分解,每个质因数分给和,或者和,或者全部给.形式化地,,.改成也就是.复杂度.(反正复杂度都这样了还写线性筛干嘛qwq). 代码 #include<bits/stdc++.h> using namespa...

约数质数

2019-09-01

2 542

题解 | 算法竞赛进阶指南圆桌骑士

思路先建反图,也就是说,没有憎恨关系的骑士之间连边,这样问题就变成了求有多少个骑士不在任何一个奇环中.很明显一个奇环的所有点都在同一个v-DCC(点双连通分量)中,因此先tarjan找出所有v-DCC.如果一个v-DCC中有一个奇环,那么该v-DCC所有点都在某一个奇环上.为什么呢?假设有一个奇环...

tarjan 缩点

2019-08-31

0 809

题解 | 信息学奥赛一本通聪明的燕姿

思路一个数的约数和为(你们都会).很明显约数和肯定大于该数,也就是答案也不会超过.可以先处理出以内的质数,然后DFS构造出所有满足条件的答案.依次枚举每个质数以及该质数的幂,除去,答案就乘.当为或者为质数且大于当前枚举的质数,就计入答案序列.这个复杂度不好证明啊qwq,感觉上限大概是级别的.也不用...

构造约数

2019-08-31

0 684

题解 | 信息学奥赛一本通 X-factor Chain

思路一种简单的构造方法就是将作为最后一个数,之前每个数是后一个数除以任意一个因子,这样构造一定是最优的.因此第一个答案就显而易见了,就是的质因子个数.(这里若,算个质因子)如果不是任何质数的平方的倍数,那么方案就是每次除以的因子的全排列.如果,的排列会有重复,也就是说会重复计算.因此若,第二个答案...

约数

2019-08-31

2 836

题解 | 算法竞赛进阶指南生日礼物

思路该题可以转换为数据备份.首先,根据贪心,如果按正负将所有数分成若干连续的段,每一段的正负号相同(这里出现0似乎没什么卵用,你过滤掉也好,看做正数也好,都没有什么问题),那么每一段要么全选,要么都不选.这个很好理解,因为如果是正数段,能选当然一起选最优,如果是负数段,选该段的负数肯定是因为要将两...

堆贪心

2019-08-29

0 582

题解 | 算法竞赛进阶指南数据备份

思路显而易见的一点是,选取相连的任意两栋办公楼肯定是相邻的,于是我们先将距离两两相减得到序列,最后答案即为序列中选个元素,选的任意两个元素不能相邻.如果只有一个数,直接选这个数即可.如果有三个数,要么选中间的,要么选两边.这样一直推下去可以得到一种做法,每次选最小的数,但是实际答案并不一定选该数,...

堆贪心

2019-08-29

0 988