louhc - 个人主页动态

2019-09-01 20:31

已编辑

思路 选任意不同的三个点方案数为.然后需要减去共线的三个点的方案数.首先横纵方向.然后考虑枚举每个向量(也就是斜率和长度相同的线段同时枚举),该向量起始位置和中间的某个点为一种方案,那么对于向量,贡献为.上下翻转也是可行的,贡献再乘2.这样子复杂度就是. 代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL C3( LL x ){ return x * ( x - 1 ) * ( x - 2 ) / 6; } LL gcd( LL x, LL y ){ return y ? gcd( y, x...

0 点赞评论收藏

2019-09-01 12:37

已编辑

浙江省义乌中学 C++

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

思路 跑动态规划.表示第位的数位,前位已经确认的数的个数.转移应该挺好转移的,需要用前缀和优化一下.内存可能比较大,需要滚动数组.最后把满足要求的答案全部加起来就可以了.复杂度为,看起来比较大,实际上基本上跑不满,还是可以过的. 代码 #include<bits/stdc++.h> using namespace std; #define MAXL 505 struct bignum{ int len, a[MAXL]; bignum(){ memset( a, 0, sizeof a ); len = 1; } friend bignum operator + ( bignum ...

0 点赞评论收藏

2019-09-01 12:23

浙江省义乌中学 C++

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

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

0 点赞评论收藏

2019-08-31 22:27

浙江省义乌中学 C++

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

思路 先建反图,也就是说,没有憎恨关系的骑士之间连边,这样问题就变成了求有多少个骑士不在任何一个奇环中.很明显一个奇环的所有点都在同一个v-DCC(点双连通分量)中,因此先tarjan找出所有v-DCC.如果一个v-DCC中有一个奇环,那么该v-DCC所有点都在某一个奇环上.为什么呢?假设有一个奇环上的两个点,该奇环外一个点,因为在同一个v-DCC上,肯定在同一个环上.路径中,因为在同一个奇环上,至少有两条路可以走,并且这两条路的奇偶性不同,因此不管怎样都可以找到一个包含的奇环.这样思路就很清楚了,先跑tarjan找v-DCC,然后在每一个v-DCC里二分图染色,如果染色失败,那么该v-DCC...

0 点赞评论收藏

2019-08-31 21:27

浙江省义乌中学 C++

是不是搞错了什么

我怎么记得Hankson 的趣味题不是这样的qwq

0 点赞评论收藏

2019-09-01 20:32

已编辑

浙江省义乌中学 C++

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

思路 一个数的约数和为(你们都会).很明显约数和肯定大于该数,也就是答案也不会超过.可以先处理出以内的质数,然后DFS构造出所有满足条件的答案.依次枚举每个质数以及该质数的幂,除去,答案就乘.当为或者为质数且大于当前枚举的质数,就计入答案序列.这个复杂度不好证明啊qwq,感觉上限大概是级别的.也不用过于纠结,这样构造一般都是很容易退出的,答案序列也不会很多,复杂度就当做吧. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b...

0 点赞评论收藏

2019-09-01 20:32

已编辑

浙江省义乌中学 C++

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

思路 一种简单的构造方法就是将作为最后一个数,之前每个数是后一个数除以任意一个因子,这样构造一定是最优的.因此第一个答案就显而易见了,就是的质因子个数.(这里若,算个质因子)如果不是任何质数的平方的倍数,那么方案就是每次除以的因子的全排列.如果,的排列会有重复,也就是说会重复计算.因此若,第二个答案就是.很简单吧.复杂度是. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )...

0 点赞评论收藏

2019-08-29 21:34

浙江省义乌中学 C++

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

思路 该题可以转换为数据备份.首先,根据贪心,如果按正负将所有数分成若干连续的段,每一段的正负号相同(这里出现0似乎没什么卵用,你过滤掉也好,看做正数也好,都没有什么问题),那么每一段要么全选,要么都不选.这个很好理解,因为如果是正数段,能选当然一起选最优,如果是负数段,选该段的负数肯定是因为要将两边的正数连起来,否则选它干嘛?我们先把所有正数段加起来作为答案,将所有负数标记并转换为绝对值,此时对于标记过的段,取它表示原该段要选,未标记过表示原该段不选,这两种操作都是将答案减去整段的和.而且我们发现,相邻的两段(一正一负)一定不能同时取,并且每取一段,都会使方案中选的段数减少一段(除了最两边的...

0 点赞评论收藏

2019-08-29 12:44

浙江省义乌中学 C++

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

思路 显而易见的一点是,选取相连的任意两栋办公楼肯定是相邻的,于是我们先将距离两两相减得到序列,最后答案即为序列中选个元素,选的任意两个元素不能相邻.如果只有一个数,直接选这个数即可.如果有三个数,要么选中间的,要么选两边.这样一直推下去可以得到一种做法,每次选最小的数,但是实际答案并不一定选该数,根据贪心,如果最小的数不选,它两边的数一定要选(否则哪边选就改成不选,改为选中间的数,结果一定更优),于是可以将当前最小的数与两边合并,变成(表示左右两边的数),然后删去即可.这样做次,每次最小值加起来就是答案.用二叉堆优化复杂度就是的. 代码 #include<bits/stdc++.h&g...

0 点赞评论收藏

2019-08-28 22:12

浙江省义乌中学 C++

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

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

0 点赞评论收藏

2019-08-28 21:47

浙江省义乌中学 C++

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

写在前面  表示的子串.这里的下标从1开始.i的上一个匹配:一个位置j,满足.下面黑线表示字符串,其中红框中包含的字符相等(这是自然，同一个字符串嘛).j还要满足(注意啦 两条黑线表示同一个字符串，只是位置不同)(其实这也算是KMP的复习吧...)下面图中红框中都表示相同.  算法 KMP.由于这不是KMP学习笔记,不仔细讲,请先学会KMP. 思路 这题也可算是"拍大腿"系列了吧?其实你看看下面代码,真的很简单,关键就是如何推出这个结论.(我不用next/fail,用了f做数组名,希望大家不要看不习惯,意思是一样的)粉色部分也表示相同.这很明显，因为字符是一一对应的嘛(同一个字符串位置相同,长...

0 点赞评论收藏

2019-08-28 21:31

浙江省义乌中学 C++

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

思路 根据贪心,从开始,该块能增加一个数就再加一个数,直到不合法为止,然后开下一块.如果暴力做的话随随便便就能卡到,肯定过不去.所以要用倍增,每次能加个数就加,不然.这样复杂度为,有点危险.我们可以只对新增的数排序,然后与当前块已有元素归并,复杂度就变成了. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #pragma GCC optimize("Ofast") #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #de...

0 点赞评论收藏

2019-08-28 19:36

浙江省义乌中学 C++

题解 | 算法竞赛进阶指南可持久化并查集

思路 说是可持久化并查集,实际上就是把并查集使用的数组变成可持久化数组.当然,可持久化并查集路径压缩不现实,这样可能总共需要修改个值,空间复杂度可能不好过去.想象当初学并查集时使用的优化,出了路径压缩,还有按秩合并.这样一次只需要修改个值,而且复杂度基本一样.这样子时间复杂度为,空间复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define MAXN 200005 int N, M; int f[MAXN], s[MAXN]; int T[MAXN], L[MAXN * 80], R[MAXN * 80], v_f[M...

0 点赞评论收藏

2019-08-28 13:17

已编辑

浙江省义乌中学 C++

题解 | 算法竞赛进阶指南最大异或和

思路 可持久化入门题.首先,如果不是区间,而是整体询问的话,我们可以直接建,从高位到低位枚举,答案的这一位能是1就为1,不然只能为0.区间询问的话其实相差不大.使用可持久化树,这样就知道每个前缀序列构成的树.还需要记录每个节点总共经过了几次.然后在两棵树上跑,这里判断是否有节点作差即可(类似于前缀和的思想).算法时空复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define MAXN 300005 #define len 25 int N, M; int T[MAXN<<1]; int tr[MAXN * ...

0 点赞评论收藏

2019-08-28 13:08

浙江省义乌中学 C++

题解 | 算法竞赛进阶指南普通平衡树

FHQ Treap FHQ Treap （%%%发明者范浩强年年NOI金牌）是一种神奇的数据结构，也叫非旋Treap，它不像Treap zig zag搞不清楚（所以叫非旋嘛），也不像Splay完全看不懂，而且它能完成Treap与Splay能完成的所有事，代码短，理解也容易。  基本操作 FHQ Treap和Treap很像，都是给每个节点一个随机的权值，使它满足堆的性质。建议先了解Treap（没必要实现，懂得原理即可）。不过，如果有两个节点值相同，FHQ Treap不会用一个数组cnt记录个数，而是直接再开一个节点。 FHQ的基本操作只有两个：Split与Merge。 Split表示把一棵树分成...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：