Chester_King-CSDN博客

原创失踪人口

终于有了去年学长们的体验：文化课和竞赛的抉择高一下这个学期感觉过得浑浑噩噩的，整天颓废，不知道自己的路在哪里人的精力终究是有限的，一天六七张试卷也不是开玩笑的接下来还有市统测和学考，失踪人口既定于七月初回归...

2018-06-07 16:38:35 735 4

原创日记（不定期更新）

6.7 今天是中考前的适应性训练第二天，昨天考的数学和社会已爆炸…… 等下还有一门英语，听班主任说考完后还有减压小游戏？wtf？踩气球？还有3天就中考了，每个碰见我的人都会跟我说要加油努力，考上二中…… 谢谢啊…… 哎，自己还是太菜，当初信誓旦旦的说要考二中创新班，现在只能是仰望他们的身影。虽然现在和二中创新班的同学们在一起训练OI，有同样的老师和学长，但是我也明白，我和他

2017-06-07 13:10:33 1323 17

原创【BZOJ】3925 [Zjoi2015]地震后的幻想乡状压+期望DP||定积分

题目传送门这题是真的神仙题……整整花了我两个礼拜来理解这题首先这题据我了解有三种做法：纯OI做法、积分+数学推导、直接积分请做好一定的心理准备，接下来的东西可能有点难理解~~（好像不是一点点的难吧……）~~ 1.纯OI做法首先我们根据期望的线性性，可以得到ans=∑x=0mw(x)×p(x)ans=\sum_{x=0}^mw(x)\times p(x)ans=∑x=0mw(x)×p(x...

2018-10-08 20:55:59 493

原创记一次突击检测

Typora的稳定性令人堪忧啊——把我刚写好的blog给吞了……wqnmlgb 假装重新写一次今天本来是比较平淡的一天，甚至还有些烦闷——毕竟快期末考了，各种试卷和作业，我也就呵呵了晚上还是在机房，结果创新班的同学们都没来，我怕不是要被班主任D死了本来想一个人静静地学一些算法和姿势的，但是心始终静不下来，开黑打比赛的学弟们太吵了，一群嘤嘤怪于是就想起来走走，换换脑子，然后就被学弟...

2018-06-09 21:43:29 375 1

原创【BZOJ】4504 K个串主席树+堆

题目传送门一个晚上就做了这么一道题……好颓啊…… 首先我们可以对于每个aia_i维护一个pre[ai]pre[a_i]表示在它之前与他最近的相同的数的位置。然后对于每个aia_i，在(pre[ai],i)(pre[a_i],i)这个范围内都加上aia_i，可以用主席树。题目要求kk个区间不相同，这就是“超级钢琴”的模型，套上超级钢琴的套路就行了。附上AC代码： #inclu

2018-01-16 21:21:22 233

原创【BZOJ】3993 [SDOI2015]星际战争二分+网络流

题目传送门网络流的用法又涨姿势了——网络流可以用于判断答案的可行性。这题我们首先考虑建图：第ii个机器人向超级汇点连一条流量为aia_i的边。超级源点向第ii个武器连一条流量为??的边。（??表示流量暂时未定）如果第ii个武器可以打到第jj个机器人，就连一条流量为+∞+\infty的边。然后考虑二分一个时间midmid作为答案，这时考虑第2条建图，这时的??就等于bi×mi

2018-01-15 21:08:45 227

原创【HDU】4787 GRE Words Revenge 二进制分组+AC自动机

题目传送门 orz Manchery 多次询问可以按时间分治，但可惜这题强制在线。因而引入了二进制分组，就是把当前字符串的数量二进制拆分。比如说当前有10个字符串，就把这10个字符串分成一组8个和一组2个。这样每个字符串最多被重构AC自动机log2n\log_2n，一种优美的暴力二进制分组适用于那些不支持修改的数据结构，AC自动机算一例，凸包也是。附上AC代码： #i

2018-01-15 21:08:09 419

原创【BZOJ】2124 等差子序列线段树+hash

题目传送门等等……这题好像在哪里做过…… 哦，Codeforces 452F，原题哈…… 为什么我还是不会做啊…… 就当是复习一遍吧，这种想法还是挺好的。 p.s.WA了两发，错在了updata上……好像updata这个地方好容易出错啊。附上AC代码： #include #include #include using namespace std; typedef un

2018-01-12 21:15:31 195

原创【51nod】1486 大大走格子 DP+组合数学

题目传送门很久以前就考过的题目了……但是为什么我一直都不会…… 考虑两个障碍物之间的转移，方案数就是Cx2−x1x2−x1+y2−y1C^{x2-x1}_{x2-x1+y2-y1}。把起点和终点加到障碍物里一起转移，先按坐标升序排序。然后定义f[i]f[i]表示前ii个障碍物只经过第ii个的方案数，f[i]=Cxi−1xi+yi−2+∑jij=1f[j]×Cxi−xjxi−xj+yi

2018-01-12 21:14:22 249

原创【51nod】1407 与与与与 DP+容斥

题目传送门好难懂的一道题啊……%%%sillyf 先把题目转化一下，答案就等于所有组合-and值不为零的组合。定义f[x]f[x]为ai&x==xa_i\&x==x的aia_i的个数，g[x]g[x]为xx转化为二进制后1的个数。f[x]f[x]的求解方法见上一篇blog。容斥一下求and不为零的组合情况： ans=∑x=11000000(−1)g[x]−1×(2f[x]−1) a

2018-01-12 20:55:17 391

原创【51nod】1406 与查询 DP

题目传送门考虑一个数num&x==xnum\&x==x，说明xx在二进制下为1的位置上numnum也为1。定义f[x]f[x]为ai&x==xa_i\&x==x的aia_i的个数。如果y&x==xy\&x==x，即yy是xx的一个子集，那么f[y]f[y]一定对f[x]f[x]产生贡献。这样就可以枚举子集转移了，但是可能会有重复计算，于是从高位向低位转移。 p.s.输入输出数据量

2018-01-12 20:54:45 226

原创【BZOJ】3506 [Cerc2007]robotic sort Splay

题目传送门这好像是两天前的题目了……一直都忘记写blog了…… 其实这题就是一道序列翻转+求区间最小值的位置，直接splay维护序列就行了。 p.s.这是一道双倍经验题，不过3506那题的题目描述极为险恶……（见oj1552）…… 附上AC代码： #include #include #include using namespace std; const int N=1e5+10

2018-01-11 11:55:26 161

原创【BZOJ】3669 [Noi2014]魔法森林 kruskal+LCT

题目传送门一句话题意：求一条路径，使得max(ai)+max(bi)max(a_i)+max(b_i)最小。输出这个最小值。还是ZZK最强了，一眼就秒掉了这道题。首先我们把所有的边按aia_i排序，从前往后加入边，显然当前的边是最大的aia_i，我们只需要用LCT维护一个从1到n路径上的max(bi)max(b_i)就行了。不过LCT好像没法处理边权，那么我们可以换一种建LCT的方

2018-01-09 18:58:01 200

原创【BZOJ】2843 极地旅行社 LCT

题目传送门这题啊，又是一道LCT的裸题，大致上和洛谷的模板差不多吧，直接切掉就好了。附上AC代码： #include #include #include using namespace std; const int N=2e5+10; int n,a[N],m,ch[N][2],f[N],mk[N],sz[N],o,x,y; inline char nc(void){

2018-01-08 20:51:42 195

原创【BZOJ】2002 [Hnoi2010]Bounce 弹飞绵羊 LCT

题目传送门这题的想法挺好的。至少我想不到。考虑每个点向它弹到的点连边，如果在当前点被弹飞，就和n+1n+1号点连边。然后发现这样的建图形成了一棵树，修改操作可以看成删边+加边。一个节点的答案就是该节点到n+1n+1号节点的路径长度-1。附上AC代码： #include #include #include using namespace std; const int N

2018-01-07 20:21:04 272

原创【洛谷】3690 【模板】Link Cut Tree （动态树）

题目传送门一道迟到的模板题。话说在思路清晰的时候敲代码真的爽啊。修改操作可以先访问该节点，然后把它旋转到根，这样只用修改这一个点的权值就好了。询问操作可以把其中一个节点搞成根，然后两点间的权值就变成了另一个节点到根的权值了。这两个想法挺妙。附上AC代码： #include #include #include using namespace std; const i

2018-01-07 20:20:43 237

原创【BZOJ】2049 [Sdoi2008]Cave 洞穴勘测 LCT

题目传送门好吧，有些时候不能盲目地相信板子——LCT的splay和普通的splay有区别的…… 我就是因为直接copy板子而一直TLE，还不知道哪里错…… 直接给出ZZK的blog，还是ZZK最强啦！！！总之LCT的最核心的操作就是access，把一棵树分成很多实链，每条实链对应一棵splay，然后处理两个点之间的关系（连接与断开）就变成了splay的操作。至于时间复杂度，好像也是

2018-01-07 15:49:48 190

原创【BZOJ】1007 [HNOI2008]水平可见直线半平面交(单调栈)

题目传送门半平面交这个名字好可怕啊……但是其实就是一个单调栈。我们把所有的一次函数按斜率降序排序，设ii为当前函数的编号，sk[]sk[]为单调栈，toptop为栈顶指针。定义calc(x,y)calc(x,y)函数为计算两个一次函数的交点的横坐标。如果calc(i,sk[top])>=calc(sk[top],sk[top−1])calc(i,sk[top])>=calc(sk[to

2018-01-05 19:51:37 237

原创【BZOJ】3196 Tyvj 1730 二逼平衡树线段树+平衡树

题目传送门这题除了烦一点，其实也没什么大不了的嘛……就是外层一棵区间线段树，内层套上splay，除了第二个操作需要套一个二分，时间复杂度为O(log32n)O(\log_2^3n)，其他的操作的时间复杂度都是O(log22n)O(\log_2^2n)。主要是细心吧，耐心一点写都能过的吧。p.s.话说内存不够导致TLE什么的好鬼啊……还是ZZK大佬最强了，一眼就看出了问题。附上AC代码：#includ

2018-01-03 20:44:18 279

原创【BZOJ】3932 [CQOI2015]任务查询系统主席树+差分

题目传送门这题嘛，就是主席树吧，把一个任务拆成两部分：任务开始的加入操作和任务结束的删除操作。（好像这就是差分了吧）然后如果两个操作在同一个时间点上发生，就直接对当前时间节点的树根进行修改；否则就在两个操作时间点之间的时间点上覆盖为前一个操作时间点的主席树根。（话说一开始我还不知道为什么要有这个覆盖的……智商已下线）然后就是一些普通的主席树操作了吧，直接写掉就行了。附上AC代码：#include <

2018-01-03 20:43:38 239

原创【Codeforces】600E Lomsat gelral (dsu on tree)

题目传送门优美的暴力什么的太暴力了吧……首先我们证明一下dsu on tree的复杂度，我们挑出一个节点的重儿子，就是树剖里的重儿子，把所有的轻儿子的信息加入到重儿子里，每次的树的大小至少翻倍，所以时间复杂度为O(nlog2n)O(n\log_2n)。dsu on tree也有一定的局限性：1.只能支持子树查询；2.不支持修改修改。个人感觉dsu on tree就是处理树上的轻重儿子关系吧，就是在轻

2018-01-02 21:13:59 284

原创【BZOJ】2120 数颜色莫队

题目传送门观察前两题，莫队算法好像是一种只支持查询的离线算法，但是莫队真的不支持修改吗？答案当然是否定的——莫队是一种支持查询和修改的离线算法。就是一种优美的暴力……考虑在莫队算法中增加一个变量nownow，表示当前有nownow个修改已经修改掉了。并在每一个询问中增加一个变量prepre，表示最近的修改操作的编号。若q[i].pre>nowq[i].pre>now，那么就把剩下的修改全部修改掉；反

2017-12-28 19:54:08 181

原创【BZOJ】3781 小B的询问莫队

题目传送门有了上一题的铺垫，这题就是一道莫队的裸题，直接用和上一题一样的套路搞就行了。附上AC代码：#include <cstdio> #include <cctype> #include <cmath> #include <algorithm> using namespace std;typedef long long ll; const int N=5e4+10; int n,m,k,size,

2017-12-28 19:53:35 211

原创【BZOJ】2038 [2009国家集训队]小Z的袜子(hose) 莫队

题目传送门开坑莫队，个人感觉莫队的操作有点类似于分块，就是把原数组分成O(n√)O(\sqrt n)块，然后对于排序后的询问，移动ll和rr两个指针来计算答案，于是询问之间就有可能有相同的部分，这样就可以节省时间了。至于莫队的时间复杂度为什么是O(n32)O(n^{\frac{3}{2}})，可以参照hzwer大佬的博客。然后这题就是一道莫队的裸题了，还没有修改，直接水掉就行了。附上AC代码：#in

2017-12-27 19:32:37 184

原创【BZOJ】3589 动态树树链剖分+线段树

题目传送门最近心真的有点浮躁啊……连题目都不想好好看了……于是就把“一条树枝其实就是一个从某个节点到根的路径的一段”看成了“一条树枝其实就是一个从某个节点到根的路径”……wqnmlgb……操作1的K≤5K\le5，那么是不是会想到容斥？对两条路径求交？但是分析一下时间复杂度，O(m×log22n×2k)O(m\times\log_2^2n\times2^k)，接近20亿啊……搞毛啊……考虑给每一条路

2017-12-26 20:57:23 260

原创【BZOJ】3991 [SDOI2015]寻宝游戏树形DP+虚树+set

题目传送门其实这题并没有真正的用到虚树，只是用到了虚树的思想。首先考虑暴力树形DP，时间复杂度还是O(n×m)O(n\times m)，必须要优化。然后我们把思路转移到虚树上，发现问题转化为改变一个节点是否为关键点，答案就是虚树上所有边权*2。我们考虑一个节点加入虚树产生的贡献，就是DFS序中和当前节点相邻的节点的路径长度*2，删除同理。那么我们每次维护改变的节点的贡献即可。可以用一个set来维护当

2017-12-24 19:17:59 309

原创【BZOJ】2286 [Sdoi2011]消耗战树形DP+虚树

题目传送门第一眼就是树形DP，然而看到数据范围以后望而却步……O(n×m)O(n\times m)的时间复杂度实在受不了啊……观察数据范围，发现题目给出的是∑ki≤5×105\sum k_i \le 5\times10^5，那我们就要考虑减少每次询问的时间复杂度，不能是O(n)O(n)的，应该和kik_i有关吧。于是我们就想：有没有什么高级的数据结构，可以让我们的时间复杂度降下来，把多余的状态舍去呢

2017-12-24 11:39:39 254

原创【BZOJ】4552 [Tjoi2016&Heoi2016]排序二分+线段树

题目传送门题解真的好机智啊……像我这种蒟蒻只能跪在地上%%%了。简化问题是非常必要的，否则就要用Treap套权值线段树这种（垃圾又恶心的）大数据结构了。有些时候我们会把无序的数据排序来简化问题，但是……你们肯定知道我要说什么的：这题就是把有序的数据进行无序处理来简化题目的……首先我们二分一个midmid来作为最后给定位置上的答案，然后对给出的数列进行无序处理：小于midmid的位置记为00，大于等于

2017-12-19 20:58:00 216

原创【BZOJ】2588 Spoj 10628. Count on a tree LCA+主席树

题目传送门如果是强制在线的话，那就只能用主席树了。这题的主席树建立方法也是挺好的，每个节点向它的父亲节点建立主席树。对于每个询问(x,y)(x,y)，抓住x,y,lca(x,y),father[lca(x,y)]x,y,lca(x,y),father[lca(x,y)]这四个点，初始化这四个点在各自主席树的根部，然后用二分加容斥来更新这四个点在各自主席树上的位置——选择左儿子或右儿子，最后得到答案。

2017-12-18 21:19:30 202

原创【BZOJ】1901 Zju2112 Dynamic Rankings 树状数组+主席树

题目传送门树状数组套主席树什么的真的好迷啊……还是整体二分比较平易近人（大雾）。我们考虑主席树的修改，如果像以前一样前缀动态开点，那么修改一个点就要把后面的主席树全部重建，时间复杂度O(m×n×logn)O(m\times n\times\log n)，和暴力差不多嘛……然后我们考虑在主席树外面套一个树状数组，这样既不会破坏前缀动态开点的性质，同时把时间复杂度降到了O(m×log2n)O(m\tim

2017-12-17 20:30:16 180

原创【BZOJ】3524 [Poi2014]Couriers && 【BZOJ】2223 [Coci 2009]PATULJCI 主席树

BZOJ3524BZOJ2223好久都没有接触主席树了，都已经忘的差不多了……说好的定期复习呢？主席树的还是像以前一样的前缀动态开点，如果当前主席树的左儿子容斥后的sum>r−l+12sum>\frac{r-l+1}{2}，那么答案肯定在左儿子中；否则右儿子也是同样的判断，如果两个儿子都不满足，那么就是00。因为一个区间内出现次数c>r−l+12c>\frac{r-l+1}{2}的数最多只有一个，这

2017-12-17 20:27:15 364

原创【洛谷】3389 【模板】高斯消元法

题目传送门我当高斯消元是什么神奇的算法啊，原来就是小学数学的解方程组……高斯消元的核心思想就是消元……对于第ii个方程，把第ii项的系数变成11，然后对第i+1⇒ni+1\Rightarrow n个方程，通过等式的减法把第ii项的系数变成00。这样一直到第nn行，显然这是的等式就是an=ba_n=b，然后向上回代即可。附上AC代码：#include <cstdio> #include <cmath>

2017-12-17 16:09:10 195

原创【BZOJ】3007 拯救小云公主最短路径

题目传送门题目大意：给定一个矩形和矩形内一些点，求一条左上角到右下角的路径，使所有点和矩形边界到这条路径的最小距离最大。解法1：最小距离最大，想到二分，然后题目就转化成：矩形内有一些圆形障碍，问左上角是否能到达右下角。直接BFS判断即可。（话说这种图好像叫对偶图啊）解法2：考虑两点间距离，如果要通过这两点，最小距离肯定为(xi−xj)2+(yi−yj)2−−−−−−−−−−−−−−−−−√\sqrt

2017-12-17 13:20:11 329

原创【BZOJ】1305 [CQOI2009]dance跳舞网络流

题目传送门又是一道神题……为什么网络流的建图都这么诡异啊……写在前面：互相喜欢什么的……cp都得死！身为单身狗的我手中多出了不知名的火把和汽油考虑把所有的男孩和女孩都拆成两个点，分别表示喜欢点和不喜欢点。对于一对相互喜欢的男孩女孩，男孩的喜欢点向女孩的喜欢点建一条流量为1的边。对于一对不互相喜欢的男孩女孩，男孩的不喜欢点向女孩的不喜欢点建一条流量为1的边。每一个男孩的喜欢点向不喜欢点建一条流量

2017-12-16 10:50:16 243

原创【BZOJ】2982 combination Lucas

题目传送门这题嘛，就是一道Lucas的裸题……暴力水博客.png直接上Lucas就好啦。附上AC代码：#include <cstdio> using namespace std;const int mod=10007; int jc[mod],inv[mod],t,n,m;inline int lucas(int a,int b){ if (a>b) return 0; if (b<

2017-12-14 20:52:39 177

原创【BZOJ】4804 欧拉心算莫比乌斯函数+欧拉函数+数论分块

题目传送门来来来，推式子啦： ∑i=1n∑j=1nϕ(gcd(i,j))=∑i=1n∑j=1n∑d=1n[gcd(i,j)=d]×ϕ(d)=∑d=1n(ϕ(d)×∑i=1⌊nd⌋∑j=1⌊nd⌋[gcd(i,j)=1]) \sum_{i=1}^n\sum_{j=1}^n\phi(gcd(i,j))=\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n[gcd(i,j)=d]\t

2017-12-14 19:56:33 305

原创【CODE[VS]】1228 苹果树树状数组

题目传送门为什么我拿到这题的第一反应是树剖啊……我到底在想些什么啊然而这题被分类在树状数组里，于是我就把想法往树状数组上靠，依然没有任何思路于是我放弃了树状数组的解法，想用树剖暴艹这题。却突然惊讶的发现：树剖你妹啊，这题不就是先序遍历后树状数组维护节点权值吗？被一道傻逼题浪费了一个小时的我表示t有一句mmp不知当不当讲……附上AC代码：#include <cstdio> #include <ccty

2017-12-13 20:44:06 344

原创【BZOJ】3668 [Noi2014]起床困难综合症贪心

题目传送门题目想法好+1，贪心新技能get。把初始值二进制拆分，分三种情况讨论：如果当前位为0，但是经过所有操作后为1，显然这一位为0最优。不满足情况1，如果当前位为1，经过所有操作后还是1，并且答案加上这一位没有超过m，显然这一位为1最优。证明：∑k−1i=12i=2k−1<2k\sum_{i=1}^{k-1}2^i=2^k-1<2^k。前两种情况都不满足，即这一位不管是0还是1经过所有操作

2017-12-12 20:49:12 206

原创【BZOJ】1251 序列终结者 Splay

题目传送门这题其实就是一道Splay的区间修改模板题，太棒啦，又水了一篇blog！其实Splay的区间加上一个值用的就是线段树的延迟标记的思想，实现就和下放区间反转的标记一样。区间求最大值也是类似的。于是这题就是练一下码力的水题。附上AC代码：#include <cstdio> #include <cctype> #include <algorithm> using namespace std;co

2017-12-12 19:28:29 178

原创【计蒜客】「2017 计蒜之道复赛」A.阿里云秘钥池数位DP+莫比乌斯函数

内个……我还没有计蒜客的账号，就先不给题目传送门了……看到数据范围不正常，就想到了数位DP。定义f[i][j]f[i][j]表示从高到底DP到第ii位，第i+1i+1位上的数为jj的方案数。 f[i][j]=∑k=1p−1f[i−1][k]×[(j,k)=1]=∑k=1p−1f[i−1][k]×∑d|(j,k)μ(d)=∑d|jμ(d)∑t=1⌊p−1d⌋f[i−1][d×t] f[i][j]=\

2017-12-10 16:06:37 304

空空如也

空空如也