Zhayan9QvQ-CSDN博客

原创 Hello world!

#include <cstdio>using namespace std;int main(){ printf("hello world\n"); return 0;}咳咳咳，终于有了自己第一个正式点的博客>.< 所以… 这里Zhayan9QvQ 可撩可勾搭w~(≧▽≦)/~ Q 957714473 hiahiahia 最后推一波我校神犇 [人类智慧巅峰并且手速超神->]

2017-02-08 22:00:48 4294

题意伟大的树上权值第k小。解析在树上建立主席树，每个点的前驱不再是它的前一个点，而是它的父亲结点。我们可以这样来想，序列上的主席树类似于前缀和，用的时候直接序列上差分。而树上也就可以把每个点保存为到根的主席树，查询的时候也类比树上的差分就可以了。记得是Query(rt[x],rt[y]….)。#include <cstdio>#include <algorithm>#define Rep( i ,

2017-07-06 11:51:50 678

原创【Bzoj3732】Network

题意给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).现在有 K个询问 (1 < = K < = 20,000)。每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？解析类似于那啥货车运输，嗯

2017-07-01 19:11:39 694

原创【Bzoj4353】play with tree

题意给你一棵包含N个节点的树，设每条边一开始的边权为0，现在有两种操作： 1）给出参数U,V,C，表示把U与V之间的路径上的边权变成C（保证C≥0） 2）给出参数U,V,C，表示把U与V之间的路径上的边权加上C。但是如果U至V之间路径某条边的边权加上C小于0，那么C=这条边的边权的相反数。你需要统计出每次一操作过后树中边权为0的边有多少条。解析边权树链剖分。对于操作1直接修改，对于操作2，先

2017-07-01 16:15:30 788

原创【Bzoj4336】骑士的旅行

题意给一棵树，每个结点上可能有多个权值，可以每次改变某权值的值或者位置，多次询问一条路径上的前k大值。解析对于每个结点维护一个multiset，因为k很小，所以每次可以把两结点暴力合并，这样就只要把两个队列合并就可以了。#include <set>#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end ) for(i

2017-06-24 22:40:19 818

原创【Bzoj4448】情报传递

题意给一棵树和m个操作(持续m秒)，操作如下 1.给一个点打上标记，被标记的点每秒加1危险度，(被标记时仍为0，后一秒为1)。 2.查询x,y的路径上有多少危险度大于k的点。解析这种每秒增加的标记显然是不好维护的。考虑转化。设某点在t时刻被标记，i时刻提出询问，那么此时它的危险度为i-t。则有i-t>k,t#include <cstdio>#include <algorithm>#

2017-06-20 20:40:08 677

原创【Bzoj1901】Dynamic Ranking

题意给一个序列，每次询问[l,r]区间内第k小的数字。带修改。解析同2B平衡树的操作。操作少可以打得简单一点。#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end ) for(int i=(_begin),i##_END=(_end);i<=(i##_END);i++)#define For( i , _beg

2017-06-15 18:00:02 584

原创【Bzoj2141】排队

题意给一个序列，每次可以交换其中的两个数，每次交换后输出逆序对的数量。解析每次交换考虑x,y之间的数字(x之前,y之后的数字是没有影响的) 那么增加的数字是小于a[y],大于a[x]的那些。减小的是小于a[x],大于a[y]的。区间查rank显然可以树套树解决。然后注意一些特判。#include <cstdio>#include <algorithm>#define Rep( i ,

2017-06-15 17:54:52 600

原创【Bzoj3196】2B平衡树

题意您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数)解析唔…看到这个标题啊啊啊是你吗2B小姐姐！！好了不发神经这是个灰常普通的树套树模板，一般会用线段树套

2017-06-14 21:41:52 714

原创【Bzoj1303】中位数图

题意给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。解析因为数都是不重复的，所以可以把左边小于它的记为+1，大于的记为-1，统计前缀和f。同理，右边大于的记为1，小于的记为-1，统计前缀和g，那么，如果左边某个数出现某次数的方法种数等于右边的，就根据乘法原理统计答案，特别地，f[0]=g[0]=1。数组下标要做一点处理。#

2017-06-10 08:39:37 917

原创数据结构小题

题意给定一个n*m的方格地区，有以下两种操作。 1 x y 从坐标(x,y)的位置向四个方向释放无限长的红雾。 2 x1 y1 x2 y2 询问左上点为(x1,y1)，右下点为(x2,y2)的矩形范围内，被红雾遮盖的地区的数量。注意：释放红雾时脚下没有。　　　两块红雾会抵消对于100%的数据，1<=n,m,q<=100000解析我们可以在横轴和纵轴上分别建立树状数组，(加一，加第二次的话

2017-06-10 07:40:42 458

原创【Bzoj4027】兔子与樱花

题意给一个n个结点的树，每个结点有最大载重m，上面有c[i]朵花，对于每个结点，它的儿子个数和花的朵数不能超过m。现在可以删掉一些结点，每删掉一个，它的花就会给父亲，求最多能删掉多少结点。解析树形Dp+贪心。可以直接Dfs递归实现。显然从权值小的开始删起。#include <cstdio>#include <vector>#include <algorithm>#define Rep(

2017-05-23 22:03:10 402

原创【Bzoj3522】Hotel

题意有一个树形结构，每条边的长度相同，任意两个节点可以相互到达。选3个点。两两距离相等。有多少种方案？解析满足条件的点对一定是“有一个中心点，三个点到中心点的距离相等，且三个点分别在不同子树中”这种情况。(因为如果在同一子树中会被重复统计)。那么枚举中心点，然后遍历子树，统计答案。令cnt[i]表示当前子树中深度为i的点有多少个。 f[i]表示当前点已经遍历过的子树中，深度为i的点有多少个

2017-05-23 21:57:01 348

原创没有上司的舞会

题意某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。解析经典题，dp[i][0]表示不选i时能取得的最大利益

2017-05-23 21:48:30 311

原创【Bzoj1060】时态同步

题意给你一个n个结点的树。每条边上有一个权值，你可以给边加上权值，求最少要加上多少权值才能使根结点到每个叶子结点的权值相同。解析Dfs即可，每个结点的子结点都要加上其与最大子结点的差值。#include <cstdio>#include <cstring>#include <algorithm>#define Rep( i , _begin , _end ) for(int i=(_begin)

2017-05-23 21:45:50 372

原创奇怪的题目

没有题面。现在需要你写一种数据结构，支持以下两种操作。 1. 给出 L R K D，代表给你一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。即：令a[L]=a[L]+K，a[L+1]=a[L+1]+K+D。 2. 给出 L R X，我们设a[R] - a[L]的值为tmp。对于给定的整数x，需要你判断tmptmptmp^{tmp} 的位数是否达

2017-05-20 15:06:53 495

原创【Bzoj4653】区间

题意在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。解析我们用一棵线段树来保存点的

2017-05-01 15:36:33 555

原创【Bzoj1029】建筑抢修

题意给出n个需要抢修的建筑，每个建筑抢修需要t1时间，并且要在t2之前完成抢修，问在时间S内能抢修的建筑最多有多少个。解析贪心，首先按t2排序，能修则修。然后不能的话每当有建筑时判断，如果这个建筑需要用时比之前的短，就替换。#include <queue>#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end ) f

2017-05-01 15:26:24 498

原创【Bzoj3668】起床困难综合症

题意给你n个操作包括按位与，按位或，按位异或。还有一个参数m，请你找0~m中的经过n个操作后最大的数，输出这个最大值。分析首先二进制运算的每一位是相对独立的，可以考虑它的每一位。首先，如果某位经过n次操作能变成1，这一位就要选(如果能选0就选0，使数字尽量小)。如果无论1,0都无法变成1，也选0。(在这一位上填1产生的贡献比在它后面全填上1还要大。能填则填。)#include <cstdio>#i

2017-05-01 14:52:23 466

原创单调栈模板题

题意N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。写一个程序计算出有多少对人可以互相看见。解析维护一个不升的序列(单调栈…？)#include <cstdio>#include <algorithm>#define Rep( i , _begin , _en

2017-04-21 22:24:49 919

原创树状数组求逆序对

…话说这不应该是学语言的时候学的嘛…#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end ) for(int i=(_begin);i<=(_end);i++)#define For( i , _begin , _end ) for(int i=(_begin);i!=(_end);i++)#define Lop

2017-04-21 20:32:04 296

原创【Bzoj1293】生日礼物

题意：小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？

2017-04-21 18:55:36 493

原创【Bzoj4195】程序自动分析

题意给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，让你判断是否矛盾。解析用并查集把相等的并起来，之后判断有没有冲突的。注意要先把所有的都并起来，因为可能有连等。#include <cstdio>#include <algorithm>#include <cstring>#define Rep( i , _begin , _end ) for(int i=(_begin);i<=(

2017-04-03 22:31:46 810

原创【Bzoj1218】激光炸弹

题意给你n个点的坐标xi，yi。求一个边长为k的正方形能覆盖多少点。解析可以枚举。但是要加一个二维前缀和。统计的时候可以画一个图。首先a[i][j]是一个大矩形。之后在旁边切掉两个小矩形，但多切掉了一个重复部分，要把它加上。#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end ) for(int i=(_begin)

2017-04-03 22:16:34 472

原创区间

题意现给定n个闭区间[ai, bi]，1请写一个程序：读入这些区间；计算满足给定条件的不相交闭区间；把这些区间按照升序输出。不知道为啥会刷这个，大概是改题。#include #include #define Rep( i , _begin , _end ) for(int i=(_begin);i<=(_end);i++)

2017-04-03 21:38:43 606

原创【Bzoj2654】tree

题意给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。解析这题直接考虑白边不好做，不过我们可以给白边加上一个值x，而x越大，选取的白边就越少，x越小，选取的白边就越多。所以可以二分x，找到符合条件的解。#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end

2017-04-01 22:00:14 430

原创【Bzoj2151】种树

题意A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。最终市政府给园林部门提供了m棵树苗并要求全部种上

2017-04-01 10:55:40 632

原创【Bzoj1196】公路修建问题

题意给一些边，每边有两种权值v1，v2(v1>v2)。分别表示一级或二级，让你求取了k条一级公路时的最小生成树的最大边权。解析因为边的权值范围不大，所以可以直接枚举边权，然后在边中选权值小于check值的加入。#include <cstdio>#include <algorithm>#define Rep( i , _begin , _end ) for(int i=(_begin);i<=(_e

2017-04-01 09:39:38 567

原创树链剖分总结

树链剖分….等等等等这是题目总结，反正就是把各种水题放到一起。然后数组意义的话，dpt深度，son重儿子，ftr父亲，rnk线段树中编号，size是子树大小，top是重链顶端的结点。【Bzoj1036】树的统计比较裸，维护区间和与最大值就好了。【Bzoj4034】树上操作也是模板，对于子树只要记一个end[x]就行了。【Bzoj4396】软件包管理器安装操作就是将软件包到根全都赋为1，然后输出改

2017-03-26 09:54:13 338

原创【Bzoj3626】LCA

题意给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）解析　　首先发现一个性质，加上depth[LCA(

2017-03-24 20:53:42 445

原创【Bzoj3531】旅行

题意：有n个城市，每个城市有权值和颜色，支持的操作有单点修改权值，单点修改颜色，查询区间同颜色之和，查询区间同颜色最大值。思路：对于每种颜色，放入不同的线段树，但其实整个加起来还是还是n个结点，值得注意的是，这里要使用动态开点，要一步步记录左右儿子的编号，而不能使用2i，2i+1直接去找，而这样建树的话，就可以很方便的查询同颜色的结点了，修改操作啥的把原颜色中的结点改为0，再在现在的颜

2017-03-19 15:43:18 388

原创【Bzoj1034】泡泡堂BNB

类似于田忌赛马的策略，最小的能赢就赢，最大的也是能赢就赢，如果都不满足就用最小的去换对方最大的，然后注意判等于。#include #include #define Rep(i,s,t) for(int i=s;i<=t;i++)using namespace std;const int maxx = 100000 + 25;int a[maxx],b[maxx];i

2017-03-19 11:33:34 425

原创【Bzoj1050】旅行comf

题意：给你一个无向图，N(N算法：最小生成树加枚举，每次连通时更新一次答案，话说codevs的第一道题应该都做过...？代码不贴了，很久之前打的没法看。

2017-03-18 22:16:01 523

原创【Bzoj1607】轻拍牛头

题意：给n个数，求出对于每个数，其它数有几个是它的约数。解析：可以筛一遍，不过最好把一样的数用数组保存，不然可能一个个筛会T。然后就是要注意j要从i而不是2i开始枚举，因为可能存在相同的数字，最后给ans减1就好了。#include #include using namespace std;const int maxx = 1000000 + 25;const

2017-03-18 21:57:26 829

原创【Bzoj1800】飞行棋

题目大意：n段圆弧，求有多少个矩形题解：统计直径就行了，可以采用前缀和，然后答案就是C（x，2）。不过统计直径的时候可能会出现一种情况，比如1,2,3和4,5,6是两段等于半圆的弧，而它们所对的半径是同一条，所以说统计时会有重复，对于这种情况的解决，直接少算一条边就好，比如第一条边不要，然后统计其它的半圆，就能得出答案。#include #include using

2017-03-18 21:35:09 436

原创【Bzoj3083】遥远的国度

题意给定一棵有根树，支持3种操作： 1.把首都修改为id； 2.将p1 p2路径上的所有城市的防御值修改为v； 3.询问以城市id为根的子树中的最小防御值。分析画了一堆图之后终于搞懂了一点点，首先换根的话肯定不是真的换。对于每次询问，设现在的根为root，准备询问的结点为x。来考虑几种情况。 1.root == x ，询问整棵树，直接输出全集。 2.root不为x的子树，则直接考虑x的整棵

2017-03-17 22:39:45 398

原创【Bzoj1876】SuperGCD

pythona = (int)(input())b = (int)(input())while b!=0: t = b b = a%b a = tprint(a)

2017-03-17 20:52:55 614

原创【Bzoj1053】反素数ant

定理：一个数约数个数=所有素因子的次数+1的乘积然后得一个2000000000以内的数字不会有超过12个素因子在一个因子数为n的集合中，这个集合中最小的数就是一个反质数。所以我们只要找出小于n的数中因数个数最多的最小数。#include #include using namespace std;typedef long long LL;const LL

2017-03-17 20:49:07 349

原创【Bzoj1012】最大数

动态开点的线段树。#include #include using namespace std;const int maxx = 200000 + 50;const int Inf = (unsigned)(-1)>>1;int n=200000,m,x,y,flag,mod,pos,t;int T[maxx<<2];char s[2];void Build(in

2017-03-17 20:44:36 362

原创【Bzoj2819】Nim

题意给定一棵树，两个操作： 1.询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略。 2.把堆v中的石子数变为k。作为一个解[ka]决[guo]了这道题的人，来分[kou]析[hu]一下算法，其实正解是Dfs序之后树状数组，但是因为懒就直接写了树剖，每个区间维护区间的异或值。因为异或的性质a^b^c=a^(b^c)。然后Nim游戏有必胜策略，当且仅当所有堆的石子异或起来不等于0，之后

2017-03-17 20:40:58 367

空空如也

空空如也