Quack_quack-CSDN博客

原创 CQOI2016游记

前情提要：我是丝薄，noip405的丝薄，所以这次省选特别虚 day0 上午随便切了两个题，背了下版。下午看考场，环境还好，键盘也不错，评测姬非常好，就是人和人之间有点近，我回去买了耳塞(虽然并没有用上晚上回去一边看板一边纠结，想自己万一进不了队怎么办，熬到十一点过终于睡了。我心态果然还是不够好啊，应该什么都不想的。 day1 上午六点半就起来了，七点到学校，开车过去七点四十就到了重

2016-04-10 23:06:44 1510 5

原创 HDU5519 Kykneion asma (指数生成函数+快速数论变换模任意数+启发式合并思想)

先说一下，这个不是正解。但是也可以过。题意：有5个数字——0,1,2,3,4，每个数字分别有a0,a1,a2,a3,a4个。问这些数字能组成多少个n位数？数据范围：a<=30000,n<=15000 时限：6s 分析：首先n位数肯定是排列，每种数字有很多个，就是多重集，这个就是多重集的排列问题。显然是指数生成函数可以做的。关于指数生成函数可以看看我前面的生成函数这个课件。现在

2016-02-26 12:14:19 2150

原创数位DP小结

数位DP的模式一般是从L到R有多少满足条件的数。写记忆化搜索不错，模式性很强而且好写。省略了不少无效状态。比较难想的是状态的优化和表示。 SPOJ - BALNUM Balanced Numbers 给出区间[L,R]问在区间中有多少数字满足其某一位是奇数的位数有偶数个，某一位是偶数的位数有奇数个。考虑状态压缩，0-9这9个数，每个数3个状态，0代表没使用，1代表用了奇数个，2代表

2016-02-18 23:00:44 537

原创插头DP小结

插头DP一般都是棋盘模型，找路径或者环路最值或者方案数。插头：说白了就是两个联通的格子，一个走向另一个，那么这里就有一个插头。轮廓线：DP逐格DP，那么轮廓线可以分开DP过的格子和未DP的格子。轮廓线的长度明显是m+1。插头垂直于轮廓线。转移：轮廓线在换行的时候要位移，这个画画图就出来了。然后具体问题具体讨论。比如任意多个环路，不考虑方向，那么就是eat the trees，用最

2016-02-18 22:34:46 4936

原创生成函数

自己做的PPT，放博客上，希望对你有点帮助w

2016-02-18 20:36:16 1171 1

原创快速傅里叶变换

自己写的课件公式太多不好弄上来，还是算了。贴两个模板。一个FFT一个NTT，都是UOJ#34的。#include<iostream>#include<cstdio>#include<cmath>using namespace std;const double pi=acos(-1.0);struct complex{//建议手封一个复数，比系统自带快400ms以上 double

2016-02-01 18:23:26 1260

原创 WC2016酱油记

DAY -1 听说picks要讲introduction to polynomial？于是看了看他的博客然后给其他人讲了下fft DAY 0 坐动车跑到绵阳了。中午到的。车站那个乡村基给差评，太慢了而且咖喱酱太稀了。志愿者妹子领我们到大巴上然后到南山中学。妹子挺热情的，点赞。然后领了一堆资料下午听我们一个同学讲了下cdq分治。晚上有个开幕式，感觉学校强行宣传233，其

2016-02-01 14:17:25 1443

原创 UVALive 5131 Chips Challenge 费用流

题意：有一个芯片，芯片上有N*N（1≤N≤40）个插槽，可以在里面装零件。有些插槽不能装零件，有些插槽必须装零件，剩下的插槽随意。要求装好之后满足如下两条要求： 1、第 i 行和第 i 列的零件数目必须一样多（1≤i≤N）。 2、第 i 行的零件数目不能超过总的零件数目的 A/B（1≤i≤N，0≤A≤B≤1000，B≠0）。求最多可以另外放多少个零件（就是除掉必须放的）。如果无解

2016-01-21 11:25:11 1339

原创网络流总结

1.最大流有一个有向图，u到v的有向边表示水可以从u流向v 边上有容量，表示水最多流过去的量有一个源点一个汇点，从源点这倒水，水通过流网络流向汇点，问这个流网络最多可以承受多少倒进去的水这个问题就是最大流在解决实际问题时主要还是建模比较考思维有几个现成的例子比如二分图跑最大流，或者由最大流可以解决最小割而引出的最大密度子图这些还有一个分支就是平面图最大流（狼抓兔子）考到了平

2016-01-04 00:00:48 895

转载【转】Codeforces GoodBye2015 New Year and Three Musketeers Codeforces 611E（贪心）

http://blog.csdn.net/gengmingrui/article/details/50441328

2016-01-02 12:21:45 559

原创 HDU 2825 Wireless Password AC自动机+状压DP

题意：给出密码的长度n，可能含有密码字串的个数m和密码至少含有密码字串的个数k，求有多少种情况。分析：因为这个题不是问的密码字串必须全部包含，所以不能矩阵加速= = 果然n的大小变得很小只有25 可以用状压DP来做，具体是每个AC自动机内的节点都编个号，然后getfail的时候像以前矩阵加速getfail一样，假设当前节点的编号是2^k，当前节点的fail指向的点的编号是2^j，那么

2015-12-30 22:06:55 466

原创 Codeforces Round #337 (Div. 2) 战报

这次CF很难得是白天比赛= =于是果断现场赛了 A Pasha and Stick 题意：给出总的木棍长度，求把木棍拆成一个矩形的方案数，不含正方形。这个水题直接给代码了。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,ans;int m

2015-12-29 00:42:01 413

原创两个AC自动机+矩阵的题

POJ 2778 DNA Sequence 题意：给出n个匹配串，已知原串的长度为m，求原串中不包含任何一个匹配串的情况数。先把n个匹配串建成AC自动机，然后根据trie图建矩阵，最后矩阵快速幂求解。建AC自动机要注意这些矩阵的题，next数组必须有值。初始值为-1方便更新。建矩阵的时候要注意trie图只是根据next数组来建的，和fail半毛钱关系都没有。那么为什么要用AC自动机呢？

2015-12-25 00:18:48 547

原创 ZOJ 3430 detect the virus AC自动机

#include<stdio.h>#include<iostream>#include<cstring>#include<queue>using namespace std;int n,m,alen,blen,a[5100],b[5600];struct ACatuomata{ int next[55600][256],fail[55600],idx[55600],last[55

2015-12-23 21:25:38 389

原创 HDU 3065 病毒侵袭持续中 AC自动机

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>using namespace std;char key[1010][52],s[2000010];int ans[1010],n;struct ACautomata{ int next[50010][26],fail[

2015-12-23 21:17:01 345

原创 HDU 2896 病毒侵袭 AC自动机

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>using namespace std;struct ACautomata{ int next[100010][127],idx[100010],fail[100010],last[100010],num,root;

2015-12-23 21:11:25 325

原创 AC自动机模板

#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;char s[1000010];struct ACautomata{ int next[500010][26],fail[500010],cnt[500010],last[500010],num,root;

2015-12-23 20:58:19 370

原创回文树笔记

1.回文树的next[charset]指针： b->aba 那么就这样表示：b.next[a]=aba 当然树里面肯定不能存字符串，于是就直接用下标标号代替了 2.回文树的fail指针：跟ac自动机类似，fail指针指向当前节点的最大回文后缀没有就指向根 3.回文树的根有2个根，一个单根就是往下连回文串长度为奇数的节点，本身长度为-1 还有个双根就是往下连回文串长度为偶数的

2015-12-21 23:01:42 797 2

原创 manacher模板

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int len,maxid,ans,p[4000010];char c,s[4000010];int main(){ s[len++]='@'; while(~(c=getchar())&&c!='\n')s[len++]='$'

2015-12-19 11:51:29 455

原创后缀数组模板

bool cmp(int *y,int a,int b,int l){ return y[a]==y[b]&&y[a+l]==y[b+l];}void pd(int n,int m){ int i,j,p,*x=prnk,*y=psa; for(i=0;i<m;++i)bucket[i]=0; for(i=0;i<n;++i)++bucket[x[i]=s[i

2015-12-19 11:48:40 338

原创 BestCoder Round #66 (div.2) 战报（误）

一场优秀的涨rating比赛。。 1.GTW likes math 问题描述某一天，GTW听了数学特级教师金龙鱼的课之后，开始做数学《从自主招生到竞赛》。然而书里的题目太多了，GTW还有很多事情要忙（比如把妹），于是他把那些题目交给了你。每一道题目会给你一个函数f(x)=ax^2+bx+c求这个函数在整数区间[l,r]之间的最值。题解注意到这个数据范围[l,r]最长只有200，因此可

2015-12-13 16:22:39 387

原创 Codeforces Round #335 (Div. 2)战报（误）

A. Magic Spheres 题意：你有a,b,c个不同种类的球，两个同种类的球可以合成一个其他种类的球，问你能否使得自己有x，y，z个不同种类的球。题解：如果a>x那么就有(a-x)/2个多余的球，否则就有(x-a)个缺少的球。其他两种球也这么分析。最后看总数是多余还是缺少。当时秒了这个水题。#include<cstdio>#include<algorithm>#include<cs

2015-12-12 14:18:52 383

原创 lct模板

from popoqqq 指针版 BZOJ 2049洞穴勘测#include<cstdio>#include<algorithm>using namespace std;struct node{ node *fa,*lc,*rc; bool rev; node(); void pushdown();}*null=new node,tree[10010];n

2015-12-08 22:17:34 1088

原创莫队算法笔记

莫队算法用于解决不带修改的离线区间问题。其主要思想是这样的：先已知区间[L,R]的答案为ans，如果求出区间[L+1,R],[L-1,R],[L,R-1],[L,R+1]的时间均为alpha()，那么就可以在alpha()的时间内转移一个单位区间，求出答案ans’。因此，我们可以通过安排查询的顺序来使得转移次数尽量少。可以用平面最小曼哈顿距离生成树来确定查询顺序，不过有一个更好写的方

2015-12-08 22:06:20 1440

原创 POJ 2887 Big String(块状链表)

先建块状链表，然后插入操作就是把块内元素位置在pos后的全部后移一位，再插入新的元素，如果元素个数大于2000就split 这样写不用merge。。。 find就是先找到块再找到位置输出来#include<iostream>#include<cstring>#include<cstdio>using namespace std;struct blocklist{ struct b

2015-12-08 21:32:46 579

原创二次同余方程模合数的一般解法

0.不讨论复杂情况的解释对于一般的二次同余方程形如可以通过配方化为下式可通过换元，得到解出X的取值，然后用2ax+b回带，用扩展欧几里得解线性同余方程就可以得到方程本来的解注意上式得到了一般二次同余方程的形式，即下文讨论上式的一般解法，并给出代码进行解释1.朴素的二次同余方程的解法因为，因此很明显可以直接枚举。时间复杂度，如果m稍微大一些效率就会很低2.对

2015-12-05 20:50:29 12400 1

原创可持久化线段树笔记

可持久化数据结构主要解决有查询历史版本或者返回历史版本的操作。可持久化线段树就是一种可持久化数据结构。最简单的可持久化线段树的方法是对于不同的时间，都建一棵新线段树，当前时刻的线段树可以由前一时刻复制来，然后在当前时刻的线段树上面进行修改。然而这样的可持久化线段树非常耗费内存，有一种感性的想法，就是如果当前时刻的线段树和前一时刻的线段树有共用的节点，这样这些节点就可以不用复制，直接把要修

2015-11-28 20:59:29 4173 2

原创树链剖分笔记

树链剖分是维护树上路径的一种有力工具。支持以下操作：修改：单点改权，单边改权，从u到v的简单路径上的点或边改权等等修改权值的方式可以是加/减/乘/除一个值。查询：单点查询，单边查询，查询从u到v的简单路径上的点或边权值之和/最大值/最小值等等树链剖分的主要步骤： 1、找到重儿子son，顺便维护出树的fa，size等等。重儿子就是当前节点的所有儿子中size最大的那个； 2、根据重儿子

2015-11-23 23:53:23 567

原创高次同余笔记（三）:离散对数和原根

我们来看这个方程： a，b，c在int内，c是质数。求x在[0,c-1]内所有的解。这个怎么搞？那我们换个方程：这个方程的解很明显是但是我们换个角度，因为开根号这个操作数论里面不好搞。这样有通过这个式子可以算出这样x就是一个指数式子，不含根号了。但是e这个东西数论里面没有啊。注意到这个底数的选取是任意的，那么随便选一个底数记作G。

2015-11-23 00:10:56 1247

原创 POJ 3580 SuperMemo（区间树）

唯一一个要说的就是REVOLVE操作。别的在笔记上有。可以发现REVOLVE就是把一段区间砍下来然后接在一个点后面。那么先把这个区间砍下来（rotateto（l-1,0）rotateto（r+1,root）），然后pushup，然后找到那个点（rotateto（x,0）rotateto（x+1,root）），然后插入回去。最后pushup。#include<iostream>#includ

2015-11-22 16:28:22 553

原创 BZOJ3224普通平衡树splay，SBT代码

splay#include<iostream>#include<cstdio>#include<cstring>using namespace std;int v[100010],fa[100010],ch[100010][2],sz[100010],tot[100010],rt,n,op,x,cnt,pred,succ;char c;inline void GET(int &n){

2015-11-22 16:22:45 568

原创 splay学习笔记及模板

splay很灵活的，它既可以作为一棵二叉查找树又可以作为一棵区间树，不过不能共存。因此从两方面来说splay。一、splay的rotate，splay操作 splay不是特别平衡。不过splay还算是平衡树吧，是有维护平衡的方式的。 splay维护平衡的方式就是提根。查询完了某个节点，就把这个节点提根。这样经过证明每次操作是均摊log(n)的。提根就是不停旋转，一次旋转，目标节点总可

2015-11-22 16:19:09 1644 2

原创高次同余笔记（二）:extended-baby-step-giant-step算法

终于稍微有点空了。。我们来看这个方程： a，b，p为常数且在int内。注意到这次p可以为合数。先来说说p为质数或者合数有什么问题。对于a与p互质，那么有a^phi(p)=1(mod p)，对于p是素数phi(p)==p-1，所以x的取值只要在0->n-2之中取就可以了.然而如果p为合数，phi(p) < p-1，这个范围不明确，就不好分块了。而且解是否存在，有几个，也很麻烦。

2015-11-20 00:41:14 861

原创 SBT笔记和模板

一、SBT维护平衡的方式 SBT靠维护size来维护平衡。对于以r为根的子树，SBT必须满足以下性质： 1.r的左儿子的size大于等于r的右儿子的左右儿子的size 2.r的右儿子的size大于等于r的左儿子的左右儿子的size SBT维护size很简单，就是插入++size，删除–size 维护平衡依靠maintain函数。具体看论文。我想写这个和AVL的相似的地方。首先

2015-11-19 17:26:29 586

原创 AVL树笔记（二）:maintain,delete

先是maintain操作，它可以维护AVLTree的平衡。有了maintain，AVLTree的insert和delete就可以不马上维护平衡，而是操作完再维护平衡了。void maintain(int &r){ if(tree[tree[r].lc].h==tree[tree[r].rc].h+2) { int t=tree[r].lc; if

2015-11-17 22:50:38 502

原创高次同余笔记（一）:baby-step-giant-step算法

我们来看这个方程： a，b，p为常数且在int内。、p是质数。这个怎么搞？首先x的取值肯定在0到p-1之间。暴搜？肯定超时啊。优化暴搜？用meet-in-the-middle？先来说说meet-in-the-middle怎么做。就是找一个点把[0,p-1]这个区间分成两半（一般找中点），算出前一半塞到hash表里面，再算后一半看看hash表里面有没有。复杂度大概是上

2015-11-17 00:35:30 2951 1

原创 AVL树笔记（一）:zig-zag,insert,find,predecessor,successor

AVL树就是一棵平衡的二叉查找树。其维护平衡的方式是：维护一个平衡因子h，即子树高度，如果左子树高度和右子树高度相差2，那么就旋转把它弄平衡。旋转是怎么转的这就不细说了，每个PPT都写了。这个二叉树明显不平衡，可以发现全部左偏，于是右旋。右旋就是当前节点的左儿子的右儿子是当前节点。如果当前节点有右儿子，怎么办？那么把这个右儿子拆下来然后装在当前节点的左儿子上。如图

2015-11-16 22:35:32 2030

原创 NOIP四校联训Round8小结

这次考得一般。第一题A了，不说了。第二题主要是抓到一个性质，然后也A了。主要问题在时间分配上面，一二题的AC花费了我不少时间和精力，我第三题没怎么想直接输出-1了。回来想想，代码不长，思路就是二分+贪心，其实还是可以一试。主要是没时间了。第一题我求稳写了3个数据范围的代码。第二题找性质也花了不少时间。因为到得晚，我的考试策略是全力12题第三题骗分，没想到别的人考得更好，最后结果也

2015-10-31 21:11:06 577

原创 NOIP四校联训Round7小结

这次考试思路好点了，就是实现上面有偏差，导致最后结果不好。时间也有点匆忙，因为难度比较大。第一题就有一些难度。一开始想了个O（nm）的40分算法，最后是11:20倒回来想的，想了个O（p^2logp）的算法觉得差不多了没仔细继续想，其实是有O（p^2）的算法的。跑去写第二题的线段树了。得了80. 第二题线段树一开始也没想到，写的O（n^2）的60分算法。时间不多了我去想第三题了，结果发现第三题

2015-10-26 21:51:15 511

原创 NOIP四校联训Round6小结

这次考得很差。。第一题不知道怎么回事WA了。这题有点难，考试的时候想了一会，结果竟然写WA了。当时也没什么时间仔细检查了。教训还是很重的。毕竟第一题如果爆0了的话就回家养猪了。我想了一下，有这么些方法可以尽量避免这种事情。 1.思考的时候注意时间，不要想太久了，因为这个是一个整体，当然如果后面的题也不会还是回来写这个吧= = 2.这个题n^2的代码可以拿60分。而且比较好写。可以

2015-10-20 00:09:19 562

lucas定理扩展论文

NOI2015试题

空空如也