IED98-CSDN博客

原创本站的最后一篇博客

明天就要坐车去杭州参加NOI2015了，做OIer的这两年我很学到了很多知识，学到了很多道理，也失去了很多。感谢OI将我带入一个神奇的世界。感谢YL的同学给我带来的无数欢笑，与你们一起训练的那段时光是最快乐，也是最有效率的。作为一个D类，能走到这里我已经很开心了。感谢众多帮助过我的神犇，感谢母校给我一个出去看一眼世界的机会。NOI结束，我就正式退役了，再也不能在机房里来几套变态的模拟题了，再也不能

2015-07-14 22:37:02 968

原创一些POI的简单题解(2)

1436: Poi2003 Trinomial直接上lucas1510: [POI2006]Kra-The Disks单调栈，看被卡在哪里1529: [POI2005]skaPiggy banks很明显，是个有向图，很显然同一个scc中的点只需要摔一次。1531: [POI2005]Bank notes二进制优化背包。2095: [Poi2010]Bridges

2015-07-14 12:57:05 1388

原创一些POI的简单题解

WJMZBMR说过：“连POI都不会还搞个屁OI”，早就听说过POI，然而一直没有勇气去刷。几个月前才发现，POI的题目几乎都是趣味性很强的思维题。初学者如果要锻炼思维的话可以去刷一刷。由于NOI吧里都可以找到资源，所以我在这里就简要讲一下我做了的题目里面比较经典的思路和细节(不要怪博主懒，明天就去NOI了，怎么也赶不赢啊。。。。。)（题目序号都是bzoj上的）1097: [POI2007

2015-07-14 12:01:51 2470

原创 bzoj2333: [SCOI2011]棘手的操作线段树+离线

网上都是可并堆在线搞，其实直接离线处理处每个联通块，然后把他们放一起，然后点更新，区间询问就可以了。#include #include #include #include using namespace std;#define INF 100000000#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define get

2015-07-13 12:54:15 1447

原创 bzoj2588: Spoj 10628. Count on a tree 主席树+dfs序

hzhwcmhf讲过，这个题是主席树，然后我当时说按树链剖分那样弄，被否掉了，后来才发现，是dfs序，虽然没有很大差别，但仔细想想，树剖那样搞完全是多余。。。。以前的我太弱了。#include#include#include#include#include#define inf 0x7fffffff#define ll long long#define N 100005#de

2015-07-13 12:49:29 585

原创 bzoj2594: [Wc2006]水管局长数据加强版

离线处理后不难发现就是一个LCT询问两点间最大值最小值之类的，然后就上模板#include #include #include #include #include using namespace std;int getint(){ char ch = getchar(); for ( ; ch > '9' || ch < '0'; ch = getchar());

2015-07-13 12:47:25 1048

原创 bzoj3110: [Zjoi2013]K大数查询树套数

写了个主席树套线段树数据小，所以就过了23333#include #include #include #include #include using namespace std;int getint(){ int res;char c; while(c=getchar(),c'9'); res=c-'0'; while(c=getchar(),c>=

2015-07-13 12:45:39 659

原创 bzoj3629: [JLOI2014]聪明的燕姿搜索好题

题目大意：令f(x)=Σi (i|x) 给定n，求所有的x，使f(x)=n首先约数和公式令n=p1^a1*p2^a2*...*pk^ak则f(n)=(1+p1+p1^2+...+p1^a1)*(1+p2+p2^2+...+p2^a2)*...*(1+pk+pk^2+...+pk^ak)于是我们枚举质数p，采取DFS的方式求出所有值#include #include #inclu

2015-07-13 12:41:08 580

原创 bzoj3931: [CQOI2015]网络吞吐量网络流

经典题目改版，直接求完最短路上最大流就行了。#include #include #include #include #include #include using namespace std;typedef long long sint;sint INF=(1LL<<42);#define maxn 222222int getint(){ char c;int r

2015-07-13 12:38:23 660

原创 bzoj3932: [CQOI2015]任务查询系统主席树

niabby讲过，不过niabby之后就退役了。。。。。。这个题离线后就是裸的主席树了(连删除操作都没有。。。)。然后怎么搞还要我说？空间要开这么大我也是醉了#include #include #include #include #include using namespace std;typedef long long sint;#define ss printf("orz\n")

2015-07-13 12:35:03 575

原创 bzoj3323: [Scoi2013]多项式的运算 splay

对于多项式的每一项我们可以建一个节点记录其系数。然后这题就成了裸地模板题。求值操作直接o（n）搞。#include #include #include #include #include using namespace std;#define maxn 1000000+100#define maxm 100000+100#define INF 0x3f3f3f3f#defi

2015-07-13 12:29:55 594

原创 bzoj3242: [Noi2013]快餐店树形dp+线段树

对于不是环上的点我们可以用树形dp解决，剩下的就是在一个环上找距离最远的两点。我们可以拆环，几下每个点第一大和第二大的距离这样最长链就是max{sum[j]-sum[i]+dis[i]+dis[j]}。于是用两颗线段树分别维护max{sum[j]+dis[j]}和max{dis[i]-sum[i]}。然后更新答案。#include #include #include #inc

2015-07-13 12:21:22 1270

原创 bzoj3043: IncDec Sequence 差分

明显要求最后差分数列除第一项都是0的情况。然而为什么答案是只用统计上升和下降的差分呢？？？？有个比较牵强的说法，>0的差分其实是指后面连续一段降的话只需要上升的差分这么多。而如果你升高的话只能连续升高，或下降的话只能连续下降。因为上升的话后面所有的数都上升了，如果你再下降的话，就会有重复的多余操作。下降同理。#include#include#include#include#

2015-07-13 12:09:21 668

原创 bzoj2877: [Noi2012]魔幻棋盘树套数+差分

神题，只能膜拜题解。然后发现了差分这个东西，所谓差分就是sigma{a[i]}=b[i]; a[i]=b[i]-b[i-1];(是不是和辗转相减很像。。。。。)我们再来看一下二维的怎么做。。然后我们换一种维护的方法。因为题目要求一定会查询到守护者a[x, y]，所以我们以(x, y)为原点，建立直角座标系。二维的一样是得差分，对于第四象限的点：b[i, j] = a[i, j] - a[i-1

2015-07-13 11:41:18 1360

原创 bzoj2875: [Noi2012]随机数生成器裸矩阵乘法

裸题，注意细节就可以了，不再赘述。#include #include #include #include #include using namespace std;typedef long long sint;struct matrix{ sint a[2][2]; void cl() { memset(a,0,sizeof(a));

2015-07-13 11:29:16 511

原创 bzoj2876: [Noi2012]骑行川藏拉格朗日插值

大神题，依然不知道lyp讲的贪心+调整是怎么搞的。所以还是拉格朗日插值+牛顿迭代求解搞，不懂拉格朗日插值的同学请自行百度，估计NOI再不会考这种结论这么强的题目，所以了解一下就好。还有牛顿迭代法，这个可以学一学，还是蛮好用的，精度也很高。#include #include #include #include using namespace std;#define maxn 11000d

2015-07-13 11:13:20 1299

原创 bzoj1040: [ZJOI2008]骑士 dp

这题是pxr讲过的题，我又想起了那段日子。刚刚转到4班(壮哉我大四班)。当时和1023一样，听懂后就没有管了。前几天做了几个拆环的dp，所以就想到还有这个题，于是就过来把它切了。不知道pxr出国准备得怎么样了。这个题就是拆环，然后像没有上司的舞会那样进行一次dp就好了。注意，这个题是多个块。。。。。#include #include #include #include using

2015-07-13 11:07:18 850

原创 bzoj1063: [Noi2008]道路设计树形dp

这题太神了，所以直接看了题解 http://www.cnblogs.com/jianglangcaijin/archive/2013/12/06/3462328.html 将狼踩进讲得很详细。公式变换太美我不敢看。还有取模的时候要判书不是0，有数据刚好是mod的倍数。。。。。#include #include #include #include using namespace std;#

2015-07-13 11:03:00 586

原创 bzoj2434: [Noi2011]阿狸的打字机 trie+线段树

我们可以先按题目描述建出一个trie树，然后得到fall树，我们可以发现，fall树的子树里有#include #include #include #include using namespace std;#define maxn 110000#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define getmid int

2015-07-13 10:55:01 642

原创 bzoj2432: [Noi2011]兔农快速幂+数论

不难发现，这个题就是求斐波那契数列改化，由于有一个很强的结论，斐波那契数列取模是一个周期数列，所以我们可以去找循环节，然后找到循环节后把这第一个循环节处理出来。其实vfk说的很详细了，注意这里mod的数不一定是个质数，我们只能用拓展欧几里得求逆元。。。。http://vfleaking.blog.163.com/blog/static/174807634201341721051604/#

2015-07-13 10:14:23 1921

原创 bzoj1407: [Noi2002]Savage

这个题，把式子列出来，就不难发现是个拓展欧几里得求线性解，然后分类讨论一下解得情况就可以了。#include #include #include #include #include using namespace std;int gcd(int a,int b){ if(a<0) a=-a; if(b<0) b=-b; if(b==0) {

2015-07-13 10:01:56 794

原创 bzoj1415: [Noi2005]聪聪和可可记忆化搜索

由于猫每次都走最短路，我们可以把老鼠所在每个点时猫会怎么走给处理出来。若i==j 则f[i][j]=0若p[i][j]==j||p[p[i][j]][j]==j则f[i][j]=1否则令temp=p[p[i][j]][j]，则有其中degree[j]表示j的连边数量#include #include #include #include #include #in

2015-07-13 09:49:37 560

原创 bzoj2891: 匹配难题压状dp

由于人很少，我们可以用longlong进行位运算记录每个人匹配的状态，根据hall定理我们可以知道很多状态都是不成立的，所以我们先预处理出每种状态之间的关系，把位数太大的数进行hash，然后就跑压状dp了。#include #include #include #include using namespace std; #define n 105#define m 400

2015-07-13 09:41:39 793

原创 bzoj2850: 巧克力王国 kd-tree

裸kd-tree，注意估价函数的写法，每个点记个sum。#include #include #include #include using namespace std;#define ll long long#define maxn 60000int read(){ int x=0,f=1;char ch=getchar(); while(ch'9'){if(c

2015-07-13 09:29:39 861

原创 bzoj1941: [Sdoi2010]Hide and Seek KD-tree

裸地kd-tree，所谓kd-tree就是暴力优化，把二维或多维德空间分块，然而树的形态可能会随着加点而退化，这时我们重建一下kd-tree就可以了。#include #include #include #include #include using namespace std;#define ll long long#define maxn 600000#define inf

2015-07-13 09:26:02 604

原创 bzoj2006: [NOI2010]超级钢琴贪心+堆

由于他已经把顺序给排好了，一开始以为是乱序然后要你找。。。。。。。既然顺序已经排好了，值一开始又都大于0,那么题目就变成了找k个不同的连续子串，使得和最大。所以一开始把所有长度为l的丢进堆里，每次把值最大的取出来再分裂。#include #include #include #include #include #include #include using namespace

2015-07-13 09:19:10 558

原创 bzoj2653: middle 主席树+线段树

主席树经典问题 cxlove讲得很详细了 http://blog.csdn.net/acm_cxlove/article/details/8566093#include #include #include #include using namespace std;#define pii pair#define mp make_pair#define maxm 2560005#d

2015-07-12 21:45:19 600

原创 bzoj1146: [CTSC2008]网络管理Network 树套树

我还是太弱了，第一次碰主席树带删除的操作。首先我们按题目要求建一棵主席树(主席树只会是记前缀和)，然后像COT那样用dfs序来维护，接着删除操作只是在树状数组上进行，树状数组只是记录每个点在原值的基础上加或减了多少。我们可以开个数组把子树都记下来，然后在二分的时候一边二分一边向下走就可以了。#include #include #include #include #include us

2015-07-12 21:32:09 569

原创 bzoj2179: FFT快速傅立叶 FFT裸题

FFT可以看具体数学和ACdreamer的博客。模板果然还是黄学长的短#include #include #include #include #include #include using namespace std;#define maxn 1000000#define pi acos(-1.0)typedef complex E;int n,m,L;char ch[m

2015-07-12 21:29:57 799

原创 bzoj3176: [Coci 2012]Sort

我们不难发现，第一次操作之后序列就会变成一段上升，然后突然降下来，再不断上升的一个序列，然后序列每次就只能交换相邻两个错位的数，然后就成了统计逆序对的裸题。 #include#include#define LL long long#define maxn 210000using namespace std;int n;int a[maxn];int b[maxn];LL ans;

2015-07-12 21:26:20 890

原创 bzoj3810: [Coci2015]Stanovi 记忆化搜索

膜拜了网上神犇的题解，得知是记忆化搜索之后感觉整个题就傻逼了。然而我作死得把大数组开在前面，然后就被卡常数了(这种卡常还真是233333)。主要思路就是一个矩形房间可以分为多个小矩形，然后递归处理。#include #include #include #include using namespace std;#define sint long long#define INF

2015-07-12 20:46:55 1253

原创 bzoj3992: [SDOI2015]序列统计 NTT+快速幂

第一次自己切NTT,感觉NTT就是FFT的取模版本，具体可以看 http://blog.csdn.net/acdreamers/article/details/39026505 讲得很清楚然后系数本来是可以预处理出来，时间可以缩很多，但我为了模板的简洁还是在想求系数了。说了那么多废话，下面我们进入正题：题目最简单的dp可以设做dp[i][j]:前i位积mod m 为j的方案数。由于乘法再

2015-07-12 20:05:54 3177

原创 A04在Yaliの生态(下)

我久久坐在电脑前，不知这也许是我最后一篇的博客该怎么写。2015的省选，如梦如幻正如我所说网络流和树剖+主席树永远是我心中的痛......HN的小伙伴们也都被弄醉了，似乎我认识的人几乎都跪了......也许一切自有天意。看了看武大的排名也已经那么前，也许我的命运只能在那里。THU和PKU的确只是梦。说到生态，我只记得暴力出奇迹。与mx logic lyy wxr niabby sb

2015-05-03 21:24:49 841 4

原创 A04在Yaliの生态(上)

作为一个蒟，必定得去犇的集散地去。于是在3月2日向老师递交了最后浪一次的请假条后，xwlj的一个月过去了复习了好多好多，知识点学了好多好多。然后题目刷了好多好多。总之整个人就好多好多了。记得是在3月中左右？看到了vijios（湖南师大附中）の培训企划，所以天真地以为又可以去浪一把。然后得知在我认识的人里面就rausen去.......又得知了其他几个傻逼也会去。所以就放弃了vijiosの培训企

2015-04-15 16:10:38 595

原创 bzoj2132: 圈地计划最小割

继续套公式，第一次写公式的时候漏掉了都是0的情况，然后就又陷入不理解中。如果按01表示每个点转态的话很明显两个相邻的不同很难处理(其实不难处理，可是这个题把公式变成min的时候就成了-，+的话直接相互连边就可以了)于是考虑黑白染色，然后直接套公式。套公式的确是一点技术含量都没有虽然慢但可以过。。。#include #include #include #include #inclu

2015-03-26 19:56:52 644

原创 bzoj2127: happiness 最小割

Description高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。Input第一行两个正整数n，m。接下来是六个矩阵

2015-03-26 14:09:47 520

原创 bzoj1468: Tree 点分治

今天考试,依旧打暴力咯。一看第一题绝壁是个虚树之类的东东。就是给你一棵树每次选几个点,给定几个点的控制范围，统计有多少点被控制。正解是离线+点分治+虚树。搞得我整个人都BB了。不过这场真是暴力出奇迹，竟然混到rank9 我也是醉了，网络赛就是水。。。。。说正题：学习了一下点分治，我们从最基本的问题入手。LCT男人八题。不知不觉搞完一半了。。。。。点分治的思想和分治差不多就是把一个东西分块，

2015-03-25 19:03:28 962

原创 bzoj3566: [SHOI2014]概率充电器 dp

原文改自yzf的博客首先普及一个概率公式 P(A+B)=P(A)+P(B)-P(AB)题意：一些充电元件和导线构成一棵树，充电元件是否能充电有2种情况，1、它自己有qi%的概率充电2、与它相邻的元件通过导线给它充电（导线有p%的概率导通）求最终充了电的元件的期望题解：首先可以将元件能否充电分成3种情况考虑，1、它自己给自己充好了电2、

2015-03-24 19:28:06 691

原创 bzoj2836: 魔法树树链剖分

就是上题中我说过得类似的操作。。。本题只有加和询问操作。#include #include #include #include #include using namespace std;#define ss printf("orz\n");#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define INF 0x3f3

2015-03-23 21:49:20 552

原创 bzoj2157: 旅游树链剖分模板题

今天考试碰到一个树链剖分的模板题，由于脑抽一时忘记了整个子树是怎么修改的。。。。其实就是加上个siz。。。。然后就找了一个操作比较全的树链剖分切了。。。。#include #include #include #include #include using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<

2015-03-23 20:49:55 826

空空如也

空空如也