Day24h

分类

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章（共131篇）

树状数组树链剖分

其实树状数组和线段树写树剖都差不多，只是换了一种储存数据的方式，一种占用空间小，但是相对耗时，一种占用空间大，但是很快。模板题：树链剖分用树状数组会 tle 但是这也是一种思路 // Created by CAD on 2019/8/11. #include <bits/...

树状数组树链剖分

2019-08-12

0 444

线段树树链剖分

模板题：树链剖分参考博客：树链剖分详解（洛谷模板 P3384）前置技能：线段树 #define lson (p<<1) #define rson (p<<1|1) 建树的时候需要注意的： void build(int s,int t,int p...

树链剖分

2019-08-12

0 464

Compress Words

E. Compress Words 直接套 KMP 即可（那为什么打 cf 的时候没有想到...），求出后一个单词（word）的前缀数组，然后从前面已得的字符串的末尾 - word. length () 开始查询利用前缀数组进行优化即可代码: // Created by CAD o...

字符串 KMP 前缀函数

2019-08-12

0 430

White Lines

D. White Lines 主要思路就是利用差分对于行：如果在某一个点上，向右下角涂掉 k*k 的矩形能够使得新出现一行 “B” 那么就在这个点上 +1（这里的加 +1 需要利用差分来完成）列同理，如果有现成的空白行，记录一下即可，最后直接加上代码： // Created b...

差分

2019-08-12

0 335

差分

差分的还原操作千万不能记错，是 ch[i][j]+=-ch[i-1][j-1]+ch[i-1][j]+ch[i][j-1] 模板： int ch[10][10]; /*修改（标记储存）*/ void change(int x1, int y1, int x2, int y2) { ...

差分

2019-08-12

0 330

线段树

参考:线段树模板题:线段树模板写线段树需要注意的几点： build和update的时候最后记得加和！（d[p]=d[p<<1]+d[p<<1|1]） lazy标记下传后记得把父节点的清除！（laz[p]=0）变量 co...

线段树

2019-08-11

0 429

Color

C - Color 参考：CF GYM 100548 Color（2014ACM西安现场赛Problem F） Codeforces Gym 100548F Color (组合数＋容斥) 思路：可以参考第一个博客的思路，很容易理解需要注意的地方：因为数据很大所以一不...

容斥原理组合数逆元

2019-08-11

0 388

Co-prime

B - Co-prime 参考：HDU 4135 Co-prime (容斥原理) 这个题利用的是容斥原理，同时也利用到了求质数个数的一个技巧—— 1~m 内与 n 不互质的个数为 m/n 个： prime.clear(); for(ll i=2;i*i<=n;++i) ...

容斥原理二进制质数

2019-08-10

0 359

Misha and Permutations Summation

A - Misha and Permutations Summation 首先这个 mod n! 因为数量级上的差别最多只会对康拓展开的第一项起作用所以这个题并不需要把 ord (p) 和 ord (q) 的具体值算出来，因为最后还需要进行康托逆展开所以用一个数组来储存对应的值即可然后利用...

逆康托展开树状数组二分进制

2019-08-10

0 387

You Are Given a WASD-string...

C. You Are Given a WASD-string... 主要看的还是思维，分别求出在上下左右四个方向移动的最大幅度（ mov_up, mov_down, mov_right, mov_left ）然后对于垂直方向如果 mov_up == mov_down 那么 robot 最后的...

思维

2019-08-09

0 487