- 博客(147)
- 收藏
- 关注
RSS订阅
原创 乱七八糟的笔记......（更新中）
有向图最小路径覆盖，二分图最小点覆盖，二分图最大独立集，二分图最大团，最长反链二分图最大独立集（选最多的点，使得两两之间没有边相连）=|V|-最大匹配二分图最小点覆盖（选最少的点，使得每条边都至少有一个点被选）=|V|-最大独立集=最大匹配*二分图最小点覆盖 +二分图 最大独立集 = 总顶点数二分图最大团（一个点集，两两有边直接相连）=补图的最大独立集的顶点数。有向图最小路径覆盖（求出最少的路径使每
2017-03-28 19:42:23
1023
1
原创 回文树(Palindromic Tree)+黑科技 学习笔记
回文树(Palindromic Tree)最基本的回文树在网上用很多资料，在这里做简单的介绍。本文的重点是后面回文树的一些更广泛的应用。注：本文的图片转自http://adilet.org/blog/25-09-14/，所以图中某些变量的定义可能与本文不同，需要注意。定义节点回文树中的每个节点都对应了一个回文串。特别注意在回文树中还有两个特殊的节点分别对应了空串和长度为−1-1的串，是为了添加只有一
2017-03-24 22:48:01
3594
4
原创 fft（快速傅里叶变换）学习草稿，逆dft证明
先上最原始的式子（模nnn意义下）： ci=∑j=0iaj∗bi−jci=∑j=0iaj∗bi−jc_i=\sum_{j=0}^{i}a_j*b_{i-j} 变形一下： ci=∑j∑kaj∗bk∗[−i+j+k==0](1)ci=∑j∑kaj∗bk∗[−i+j+k==0](1)c_i=\sum_{j}\sum_{k}a_j*b_k*[-i+j+k==0](1) 考虑怎么判断一个数是...
2017-02-22 22:36:31
2449
4
原创 学习笔记 后缀平衡树简要小结（附例题）
定义后缀平衡树，简单的说就是动态的维护后缀数组，能做到在O(logn)O(logn)插入，O(1)O(1)查询rankrank，O(logn)O(logn)查询SASA。当然由于后缀平衡树是支持对后缀的操作，所以要求插入操作只能在字符串开头插入字符（相当于插入一个后缀）。离线构造根据定义，后缀平衡树就是把后缀数组构成一棵平衡树，所以只需先构出后缀数组再构后缀平衡树。在线构造由于后缀平衡树只能支持在开
2016-10-05 22:50:05
3443
原创 数论学习笔记 基础数论(未完成)
本文是一些对基础数论的总结。欧几里得 Gcd定义：gcd(a,b)gcd(a,b)即求aa和bb的最小公因数。 求法：根据gcd（a,b）=gcd(b,amodb)gcd（a,b）=gcd(b,a\bmod b)，递归求解知道b=0b=0时，gcd(a,b)=agcd(a,b) = a。 时间复杂度：O(loga)O(loga) 证明：时间复杂度不是很会证，但是算法的正确性还是很好证的。设 k
2016-09-19 21:10:18
1714
7
原创 后缀自动机（SAM）学习笔记
构图及原理定义算法后缀自动机（SAM）就是一个要实现能存下一个串中所有子串的算法，按一般来说应当有O(N2)O(N^2)个状态，而SAM却可以用O(N)个状态来表示所有子串，因为它把很多个本质相似的子串映射到了同一个状态上，从而实现了这个优美的算法
2016-03-30 20:31:38
8328
9
原创 Link Cut Tree（LCT )学习笔记
先来说一说什么是Link Cut Tree在数据结构中有一类问题叫做动态树问题（DynamicTree）（Dynamic Tree），它会要求你对一颗树进行切割和拼接，然后再在上面维护传统的数据结构能维护的值，为了完成这一类问题，就有了很多相应的算法来解决这类问题，Link Cut Tree就是其中一种比较方便实用的算法。本文讲的就是本人对LCT的一些见解。
2016-03-27 13:24:08
3029
5
原创 计算几何 学习笔记
基础知识基本操作基本定义struct Dot { double x, y; Dot(double _x, double _y) {x = _x, y = _y;} Dot() {}};struct Line { Dot p, v; Line(Dot _p, Dot _v) {p = _p, v = _v;} Line();};Dot operator - (Dot a,...
2019-01-15 22:15:48
469
原创 CTSC2017总结
听说今年CTSC不个广东省选冲突，那很妙啊！然后我就去垫底了…Day -1由于早上要报到所以提前一天就去到了北京，听说昨天还在雾霾+沙尘暴？为什么我看到的天这么蓝？这好像还是我第一次来北京（鬼知道我高一联赛拿了几等奖…）去到酒店，刚拿出电脑，突然发现充电线没带，整个人都不好了，因为接下来还有APIO和各种夏令营，没充电线怎么活啊！幸好过几天学校还有人来，并且能借到相同的线，不然就生无可恋了。Day
2017-05-11 00:00:04
2220
1
原创 GDOI2017 AFOING...
由于NOIP比较低，所以这次GDOI的压力会比较大…所以还是比较紧张的。Day 1拿到题，第一题，好像挺简单的，直接暴力KMP就可以了。 第二题，题面好长，读题都读了十多分钟。好像有点麻烦，如果直接算mex，好像有点难合并，那么就考虑每个数出现最左端的位置和最右端的位置。对应的就是一段出现的区间。那么找询问子树对应dfs序中包含的最小的区间就可以了。一开始想到用主席树维护，但是仔细想想好像有问题，
2017-05-03 21:01:19
1472
原创 GDOI2017赛前总结
前言经过了4场模拟后终于要迎来了真正的GDOI2017比赛，之前想着GDOI还有几个月，但是停课之后，每天一场模拟，一天天做下来时间过的特别快。由于NOIP的失利，那就意味着GDOI更大的压力，意味着要更稳定的发挥，要更灵活的思维。而刚刚做完的4场GDOI仿真模拟后虽然发挥更加稳定了，但是也暴露出了很多问题，在比赛中出现一次都是很致命的。所以下面总结出来，靠前提醒自己。注意事项心态和状态：保持心态
2017-04-27 11:48:13
787
原创 GDOI2017模拟 第四场（4.24~4.26）
最后一场模拟了，要认真做啊！还有终于到了真.仿真模拟，终于换机房做题了。Day 1一看题，第一题就是字符串，很爽，想了想两个字串的lcs是SAM的fail树上对应节点的lca，现在求lcp，那么把字符串反一下就可以了，直接dp一下就很水了。看下一题。 这个博弈题，怎么这么熟悉，这似曾相识的感觉…这不是前几天才做过的原题吗！！！但是想不起来怎么做了，花了几分钟重新推了一下，想起来是用bitset维护
2017-04-26 23:01:03
781
原创 GDOI2017模拟 第三场（4.19~4.21）
第三轮… 上一轮问题有点多，这一轮要好好改善！！！Day 1噢，一看题就听到栋爷说是HNOI的题，之前听过富榄说第一天他2个小时AK了，第二天很鬼畜，不知道这是第一天还是第二天… 第一题，一上来就是一个”spaly”，看了好久才把题目看完看懂，想了10多分钟发现它旋转其实就是把最小或做大的节点提到根，树的其他结构不变，然后突然发现有删除…难道要Lct???但是想着想着感觉到根的路径可能会有一些比
2017-04-21 21:42:26
568
原创 GDOI2017模拟 第二场（4.15~4.17）
第二场省选模拟。。。Day 1第一题，找区间最小生成树问题，一看节点才100，那直接每根号个设个关键点，求出两两之间的最小生成树，把边集存下来。每次询问就只有3n√3\sqrt{n}条边，暴力就可以了，感觉不算很难。 第二题，看一眼就感觉是容斥dp，但是对竞赛图不是很熟悉，感觉正解应该要用什么奇怪的性质，就弃掉了。 第三题，跟之前做过的一题很像，正解是fft，但是之前那题用bitset就过了，而
2017-04-17 22:56:55
663
2
原创 GDOI2017模拟 第一场（4.11~4.13）
为了更好的迎接省选，又有了GDOI仿真模拟赛，连续三天，每天一场。Day 1第一题，送分题直接跳了。 第二题，一眼看上去像计算几何题，仔细想想好像并不用，一个直观的思路是提取出关键点然后跑spfa，但是关键点之间的连边比较复杂，有点不可打，正解肯定不是这样，一时间有没什么思路就先去看第三题。 第三题，是有关树上两两路径的题，很直接的想到了点剖上面。但是复杂度太大了过不了，但是感觉我的方法有玄学加
2017-04-13 16:36:33
594
原创 JSOI2017 垫底记 幸好不是自己省选系列...
Day 17:10分闹钟响了，觉得有点困，就又在床上摊了一会儿。到楼下后已经30多了…等早餐的时候，一开始煮面大妈有点断线，差点迟到翻车。本来想买杯咖啡清醒一下，结果常州一中旁边的小卖部居然都没开门…最后不得已在有个文具店的小角落找到了一瓶奶茶顶替，很尴尬。（在我脑海里面之前JSOI的题都不难，所以感觉今天早上还是可以做的很爽的——-flag已立）到机房，刚调好gdb考试就开始了。先看完题目，第三题
2017-04-08 20:37:24
2332
3
原创 ZJOI2017 仙人掌 转化模型后的简单树形dp
题目大意给定一个nn个点，mm条变的无向无自环的连通图，问都多少种加边方案使得加完边的图是一幅没有重边仙人掌。(即满足任意一条边只属于一个简单环中的无向无自环图的连通图) 多组数据。∑n≤5∗105\sum_n \leq 5*10^5 ∑m≤106\sum_m \leq 10^6解题思路首先讨论给定的图是树的情况。（转化一） 要求不能有边存在与两个简单环内相当于我们要加入新的边去覆盖这个树，是
2017-03-26 10:14:23
1588
原创 CodeChef March Challenge 2017 题解
CC XENTASK由于要交替选，所以要不第一个人选位置为奇数的数，第二个人选位置为偶数的数，要不第一个人选位置为偶数的数，第二个人选位置为奇数的数。取最小值即可。#include <cstring>#include <cstdio>#include <algorithm>using namespace std;int n, sum[2][2];void solve() { memset
2017-03-13 20:26:30
1267
原创 NOI2017模拟3.8 总结
先看题目名字A，B，字符串。最后一题居然是字符串题，那就先看最后一题。一开始还以为是套路题，但是发现询问居然都是独立的，而且乍一看是O(qm)O(qm)的，直接爆炸。考虑之前做过一道是要设阈值的题。就尝试往这边想。发现当k≤n√k\leq \sqrt{n}是可以直接O(nn√)O(n\sqrt{n})。但是当k≥n√k\geq \sqrt{n}是就只会O(nn√logn)O(n\sqrt{n}log
2017-03-08 20:19:32
1029
原创 NOI2017模拟3.1 总结
今天的比赛有别的学校的大神一起来做，感觉又要被虐了！ 首先看第一题，n<=50n<=50，感觉分成两个部分，每个部分25的话就比较nice了，但是思考了一下没想出什么东西。那就看第二题，哇，一看就觉得很丧。接着看第三题，又是判圆的包含关系，之前做过类似的，对每个圆的左端点和右端点扫线一下，然后用set判断一下上半弧和下半弧，讨论一下就可以处理出来。设下的就是简单dp了。打完这题回头去搞第一题暴力，
2017-03-01 22:31:06
882
原创 Codeforces Round #397 (Div. 1 + Div. 2 combined) 题解（CF765A，CF765B，CF765C，CF765D，CF765E，CF765F）
A.Neverending competitions（Codeforces 765A）题解：直接判断坐飞机的次数是奇数还是偶数就可以了。#include <cstring>#include <cstdio>#include <algorithm>using namespace std;char h[100];int n;int main() { scanf("%d", &n);
2017-02-21 21:00:58
1135
原创 CodeForces AIM Tech Round 3 (Div. 1) 题解（CF708A，CF708B，CF708C，CF708D，CF708E）
A. Letters Cyclic Shift（CF708A）题解：直接找到第一个不是a的位置i和i后面第一个为a的位置j(如果没有，j=len(s))，那么翻转的肯定就是[i,j]这一段。如果这个字符串都是a，那么就翻转最后一个字符。#include <cstring>#include <cstdio>#include <algorithm>using namespace std;char s
2017-02-21 08:50:32
1338
1
原创 GDKOI2017总结
Day 0早上的时间自由安排，先看了一下GDKOI2016的题目，感觉比起GDOI的难度还是简单一点的，毕竟只是模拟。中午坐车去广州，想着NOIP考挂了，但是市队好像不算NOIP分数，总要进个市队吧…… 晚上可能坐车坐太久了，吃晚饭没吃饱（也有可能是和大妈[5个人！]一张桌子），去买了KFC，发现小时候2块钱的雪糕，现在居然要8块。最坑的是西苑还是没有wifi，一晚上无所事事，就听czz讲猎奇故事
2017-02-20 11:19:30
1082
4
原创 GDOI2017模拟2.16
先看第一题，觉得很眼熟，发现以前做过，然后就没什么好说的了。第二题，60分是裸的背包，100分想了一下发现不能直接用数据结构维护，就先跳过。第三题扫了一眼部分分，有70分，想了10分钟正解，没什么思路就开始想部分分，发现分别是暴力，打线段的前缀和标记，以及一个树形dp，都不难打。最后成绩80+60+70，第一题被卡T了，随便卡了卡长就过了。第二题莫名其妙，还要分类讨论。第三题做法很机智，第一步，对于
2017-02-16 20:55:00
599
原创 GDOI2017模拟2.15
第一题是博弈题，一项博弈不好的我有点慌，对正解没什么想法，看到20分暴力分状压一下就可以了，对于正解感觉两个人的决策方式好难处理就先看第二题。第二题求不经过障碍，不相交路径的方案数，也是一脸懵逼，没什么思路，发现暴力有四十分就打了。第三题…奇怪的期望题，一点思路都没有。最后成绩10+35，第一题要强制在线，有个东西不用异或，少了10分。第二题有种情况处理错了。第一题，只要把边上的权值放到点上就很好想
2017-02-15 22:25:17
892
原创 GDOI2017模拟2.14
首先看第一题，裸的主席树。直接看下一题，第二题觉得要先找循环节，然后按m来分类找最优值，但是发现做不了。重新看了一下题目发现n都是质数，也就是说b数组中的数每个恰好会被选一次，想了一会儿还是不会做，然后就去看第三题，前三个数据容许的误差很小，感觉都可以用高斯消元消掉，就决定打高斯消元加一些骗分。最后成绩100+40+6，第三题骗分把前面30分骗没了…第二题是先把特殊情况特判断后用原根把乘法变成加法。
2017-02-14 20:53:45
645
原创 51nod1577 异或凑数（算法马拉松20） 特殊的线性基构造方法
题目大意从左到右一共nn个数，数字aia_i下标从11到nn编号。 一共mm次询问，每次询问是否能从第LL个到第RR个数中（包括第LL个和第RR个数）选出一些数使得他们异或为KK。n≤5∗105n\leq5*10^5 ai,K<230a_i ,K< 2^{30} m≤5∗105m\leq 5 * 10^5解题思路求一堆数能否异或成kk，一个很显然的思路就是构出这堆数的线性基，然后看一下能不能用
2016-12-08 21:01:45
1710
原创 NOIP2016 总结
今年的NOIP停了3个星期的课，本以为状态不错，可以有良好的发挥，但是考试结束后却因为一些平时没注意到的细节导致考挂了。第一天第一题还是比较符合NOIP的难度，就是一个模拟题。但第二题就开始画风突变了。是一道不那么裸的树上路径问题，本以为也不会太难，但是居然想了5分钟还没有想到正解。就先去看看第三题。居然是期望题，NOIP考期望！说好的不考概率相关呢！想了一下还是有思路的，可以设状态dp，就没往细想
2016-11-26 08:31:18
1861
原创 NOIP2016提高A组集训第18场11.17 总结
比赛过程今天又是由于gdb的问题浪费了20多分钟，略显尴尬。先看第一题，woc不会啊，想了想，还是没什么思路。那就先做第二题，发现用dp的话是从一个三角形中转移，本来以为又要切比雪夫距离转曼哈顿距离，但是转念一想，动态维护一下就可以了。第三题，没什么思路，看到询问类总数不超过500000，虚树？这是noip啊！不可能，又想了想没什么思路就去做第二题了。做完第二题，回头想第一题，直接类似贪心的思路就好
2016-11-17 16:57:00
1053
原创 NOIP2016提高A组集训第17场11.16 总结
比赛过程先看题，第一题就是期望，感觉这套题不会太简单。虽然是期望题，但只考了最基本的应用，不难。第二题，曼哈顿距离转切比雪夫距离后就是一个矩阵覆盖问题了。没多想果断树套树。第三题，肯定要构mst，之后把lca缩起来就行了。居然全都会。就开始打。第一题还好，可是到了第二题，发现好难打，调不出来。想了想，好像不可以用树套树做。第一颗树的标记很难维护。但是有感觉能处理掉，就先放了第三题，可是最后还是发现有
2016-11-16 21:43:19
637
原创 NOIP2016提高A组集训第16场11.15 总结
比赛过程吸取了昨天的教训，今天先把gdb什么的弄好，确保打题的时候不会出现什么奇怪的问题。第一题，第一眼感觉直接去重后三次方。看下一题，没什么好思路，只好果断链剖。第三题，一开始有个思路，似乎可行，就先打前两题。第一题，打完后发现做法有问题，算多了一些三角形。想了想也不难改。花了十多分钟解决的问题。在打第一题时发现键盘的空格键有问题，两边塌了！每次按都要很大力，这就很尴尬了，打题速度被大大减慢了。第
2016-11-15 20:29:50
942
原创 NOIP2016提高A组集训第15场11.14 总结
比赛过程今天，又喜闻乐见的到了一个陌生的机房做题。由于今天是我们年级的校运会，一赶到机房就开始比赛了。看到第一题，第一感觉是直接找单调递增序列，想了想似乎没什么问题。第二题，直接排个序dp就行了。第三题，又是圆，又是最小代价。果断先放一放，先打前两题。打完第二题，想要调试一下，发现环境变量每调好，就去重新设了一下，为了方便直接把原来的删了，重新复制了一个。搞定前两题正解后，想拍一下第一题。但是发现，
2016-11-14 20:12:52
680
原创 NOIP2016提高A组集训第13场11.11 总结
比赛过程一看第一题，什么左视图，主视图的，不懂啊。看后两题，发现第二题是字符串题，以为可以好好思考一下了。没想到是道裸题……再看第三题，也是水题。回头想想第一题，还是很水。果断开始码题。最后成绩 100+100+95=295，第三题挂了一个点，什么鬼。发现有个地方没取模，小数据拍不到。可惜了。小结在打完程序后，还有肉眼调试一遍。看看取模啊，空间啊这些细节。以保证拿到自己能拿的分数。
2016-11-11 19:57:34
848
原创 【NOIP2016提高A组集训第12场11.10】图的半径 解方程找最优解 枚举关键点
题目大意给你一幅nn个点，mm条边的无向图。现在要求你找到一个点，可以在边上。是节点中到达这和点的最大值最小，并且输出这个最小值。n≤200n\leq200 m≤19900m\leq19900解题思路可以直接枚举每条边，找出每条边的最有点，然后再在所有边中找到最有的边。 对于一条连接u,vu,v的边。设aia_i表示从节点ii到uu的最短路bvb_v为节点ii到vv的最短路。这可可以用floyd
2016-11-10 21:57:50
800
原创 NOIP2016提高A组集训第12场11.10 总结
比赛过程第一眼看第一题不会做啊，就去看第二题。第二题由于转移区间有单调性，直接用一个数据结构维护一下就可以了。回头看第一题，发现是一个一次函数，果断上三分。打完拍完前两题，想第三题。瞎做。直接暴力二分答案判断是否可行。最后成绩100+100+20=220，第三题拿的部分分有点少。发现程序有个地方打错了。而且，求两两之间的最短路我居然用了spfa，智障了，直接弗洛伊德就好了……小结前两题做的还是有点慢
2016-11-10 16:12:54
630
原创 NOIP2016提高A组集训第11场11.9 总结
比赛过程第一题，第一眼看上去以为是难题，还要枚举比值。但是仔细想想发现，原来比值一开始就知道了。直接贪心就好了。第二题，主要是判断矛盾的方法比较麻烦，一开始想用平衡树维护区间，但是打着打着发现会错。后来想到了二分答案，判断是否可行，感觉这是对的。第三题题目意思很繁琐，看了看，没什么思路就像回去检查第一第二题，感觉比较难拍就出了几个小数据，过了就没管了。最后成绩 0+100+0=100。第一题都过了，
2016-11-09 15:51:49
926
原创 JZOJ4876. 【NOIP2016提高A组集训第10场11.8】时空传送 拓扑序判断最长路是否合法
题目大意给定一个nn个点，mm条边的有向图无环图，现在要求你删除一个点以及与它有关的边，使得图中的最长路最短。n≤4∗105n\leq4*10^5 m≤106m\leq10^6解题思路首先考虑当必须选某一条边时的最长路怎么算。假设这条边连接u,vu,v。那么我们可以先预处理出fif_i数组表示到ii点的最长路是多长和gig_i表示从ii点往后走的最长路是多长，这两个都可以通过拓扑序O(n)O(n)
2016-11-08 17:28:48
825
2
原创 GDOI2017模拟11.8 总结
做题过程第一题感觉是一个经典的问题，想了想好像有点思路。先看第二题，显然要枚举约数，算了算复杂度，感觉会超，就没有继续想下去。继续看第三题，感觉好恶心，肯定要贪心加分类讨论什么的。还是想想第一题，想了一会，发现虽然感觉离正解很近，但是就是不会做。只好打暴力。第二题暴力分是送的。第三题打了个状压，调了好久。最后10分钟打完第一题暴力。最后成绩40+30+5=75，感觉该拿的分也没拿到。第二题打了几块部
2016-11-08 17:10:21
854
原创 GDOI2017模拟11.7 总结
比赛过程先看第一题，哇计数题，先看下一题；再看第二题，哇又是计数题，再看下一题；最后看第三题，哇还是计数题，什么鬼啊！三个计数题，要命啊！还是绝觉得第一题比较可做，先推了一下式子，感觉那n2dpn^2dp改成矩阵乘法就可以了！不管后两题，打了再说。打着打着，发现有点问题，幸亏只要预处理一下就可以解决，但是细节问题还是调了比较久。导致拍完之后已经只剩一个小时了。而后两题又想不出来。之后打暴力。最后成绩
2016-11-07 22:32:02
621
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人