louhc

题解

未归档(78)

/ 注册

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

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

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

高精度动态规划

2019-09-01

0 690

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

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

约数质数

2019-09-01

1 528

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

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

tarjan 缩点

2019-08-31

0 786

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

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

构造约数

2019-08-31

0 680

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

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

约数

2019-08-31

2 824

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

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

堆贪心

2019-08-29

0 570

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

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

堆贪心

2019-08-29

0 980

题解 | 算法竞赛进阶指南荷马史诗

思路先不考虑的长度,就是一个叉哈夫曼树.题中要求没有是的前缀恰好对应了这一点,因为所有单词编码都是叶子节点,不会出现某字符串是另一字符串前缀的情况.因为需要的长度尽量小,我们在合并的时候尽量选深度小的即可. 代码 #include<bits/stdc++.h> using namesp...

堆贪心

2019-08-28

0 716

题解 | 算法竞赛进阶指南 Period

写在前面表示的子串.这里的下标从1开始.i的上一个匹配:一个位置j,满足.下面黑线表示字符串,其中红框中包含的字符相等(这是自然，同一个字符串嘛).j还要满足(注意啦两条黑线表示同一个字符串，只是位置不同)(其实这也算是KMP的复习吧...)下面图中红框中都表示相同. 算法 KMP.由于这不...

KMP

2019-08-28

0 578

题解 | 算法竞赛进阶指南 Genius ACM

思路根据贪心,从开始,该块能增加一个数就再加一个数,直到不合法为止,然后开下一块.如果暴力做的话随随便便就能卡到,肯定过不去.所以要用倍增,每次能加个数就加,不然.这样复杂度为,有点危险.我们可以只对新增的数排序,然后与当前块已有元素归并,复杂度就变成了. 代码 #include<bits/...

倍增

2019-08-28

0 612