- 博客(92)
- 收藏
- 关注
RSS订阅
原创 【递推】常见的递推关系
背景：基于对于昨天的考试暴毙的反思就写了这篇博客，总结之前所有学过的递推关系以及一些比较有常见的数列，这其实就是针对于T1的出题范围，很有可能是这些公式的简单应用。所以就把它们打个包直接全放在这个专题的博客里面了，一是方便复习，二是方便再用，，（写这个的时候，，胳膊还是废了的，，，觉得打字都是左中右轻，，（再也不打羽毛球了，，，/(ㄒoㄒ)/~~））前置黑科技：组合数：Cnm=(nm)=...
2019-10-17 16:39:16
3047
原创 传送门
—————OJ—————洛谷POJHDUOJBZOJCDOJACM_ICPCUSAcodeforcesUVAAcwing————刷题工具————图论画图谷歌翻译————大佬博客————------网上的巨佬-------hzwer自为风月马前卒qscqeszezbtrsyiqzqhehe-------同校巨佬-------Cydiaterxwch...
2019-06-16 13:01:52
450
原创 再见，OI
这是最后一篇博客，OIOIOI 生涯就此画上句号，尽管最后不是怎么圆满，没有很好的结果或者回报，没有沉甸甸的掂在自己手里的那个证书或者奖牌，我还是觉得，真的，自己尽管现在两手空空，既没有文化课，也没有竞赛的奖牌，我依然觉得自己收获了很多，而且一个人掂在手里沉甸甸的，很满的那种感觉，而且很感谢能有这次竞赛的机会，出现在我的生命中，感谢上天能给我在高中，在我这么小的时候就给我这么大的感悟，这种感悟，说...
2019-11-18 09:34:01
901
4
原创 模板
模板现在距离 2019CSP2019CSP2019CSP 不到 242424 小时了，积攒了很多的模板，为了不发最后一片学术博客进行记录，还可以算是给萌新 OIOIOI 一个总结吧，（这是最后这几天敲的，可能不会很全，希望评论多给扩充，应该仅限于今天吧，明天就上刑场了）大佬们，都发说说纪念了，我就发个博客吧（嘻嘻）搜索：dfs：void dfs()//深搜{ if() retur...
2019-11-15 08:42:16
260
原创 动归杂题冲刺三十题
背景：在被DP一顿捶打的悲惨经历之后，我打算开始反击了！！！不能让DP对我再痛下杀手了！要起义了，，，（假装很大声）所以我准备了40道DP题目，（先立个小目标，在11月之前刷完，然而现在已经24号了，，，，）希望能唤起我对于写DP的灵感，毕竟CSP历年来考的重点在于DP和图论啊，（表示学了半年的数据结构，，哭死），为了记录和监督自己，决定写博客进行记录！题目：T1:随风而逝的都是属于昨天的...
2019-10-29 12:23:45
619
原创 【模拟赛】10.15—10.17
背景：继国庆自闭四联考之后，确实，是很自闭，还做了些比较疯狂的事情，然后顿悟了很多，然后刚知道怎么去努力，刚知道努力的方法和方向就赶快滚回来写博客了，毕竟是在将近考试的时候出现了问题，还是赶快狗回来重要，，，不多扯了，毕竟都写好多了，而且今天任务有些重，就好好写吧，（还要吐槽一下，，，不知道是谁说的，这套题适合我的，，，，，，我**）题目：Day1:T1:煎蛋的疑惑(excatalan...
2019-10-18 11:28:17
388
原创 10.02 T3题解
题目：简化题目：在一个图中删一条边，然后再跑此刻图中最短路，有时间的限制，存在每条边都可以在任意时刻删。求删完后的最短路径长。题解：（这个题我赶了一下午，跟G-hsm大佬一起讨论，多亏大佬的细心讲解，我才大概能懂，再次感谢！）（这个题，输出 −1-1−1 即可有15分，输出样例就可以20分了，这样的题我觉得20分就够，，，因为这个题的暴力是在是不好调还不好写。尽管让我在台上讲了这个题，但...
2019-10-04 17:31:01
160
原创 【模拟赛】2019.9.23—2019.9.24
背景：模拟赛定下来了，，周一周二周五，周三讨论，这晚自习占的，一看课表发现周三周四是语文和英语晚自习，这还是不停课吗？？？白天的课，能（想）上的就上（主要上理科和数学，，语文英语基本没上过，，，结果就被KK怼回去上文化课了，结果发现好多不好补回来，但是没有大片的空白，就是那些老师拓展的东西没有学到，有点亏了，还有作业，基本没写，就是偶尔自己闲了就写写题当做休息，，这样怎么可能提高文化课，，，）这...
2019-09-26 09:01:26
186
原创 【模拟赛】2019.9.15—2019.9.16
背景：这次的模拟赛啊，，是真的自闭，自闭到家了，，(ㄒoㄒ)这次是Cydiater出的题，真的是很有水平，跟历年noip的题目难度差不多，但是很不好想的那种，然后就考了个Day1，Day2，结果，，，如果交了的话就是两百分左右（打的太菜了，就没交，但是回过头来想了想，以后还是好好交吧，不管考了多少，这样的话，至少在之后老师记录的折线图中至少就可以看到自己每次考试的进步和退步了，要是总不交或者是只...
2019-09-18 12:44:23
276
原创 【数据结构】水题集合
（好不容易从大神那里拿来的复习巩固的数据结构题目，，然后就，，，看到这些题，，，两个小时六道，，然后就大模拟赛了，，所以好几天了，这样的话，我就一不小心就断更了，，）（都是UVA的题，，，ACM制的害我一顿好调的，，）这篇博客可能有点长，总共十道题，从初级数据结构到高级数据结构的事情。题目1：题目链接：UVA11995 I Can Guess the Data Structure!题解...
2019-09-11 20:57:13
211
原创 【模拟赛】2019.9.5
题意：随机生成一个 m + 1 个数的数列，第一个数为 0, 生成第 i个数时，在前 i − 1 个数中等概率选择一个数 k, 则第 i 个数为k + 1。每个数均有一个对应的权值，求数列权值和的期望。回想一下正睿老师讲期望与概率的套路。。。SSS：数列的权值和XiX_iXi：第i个数的权值（X1X_1X1为定值0，所以忽略不计）S=∑i=2m+1Xi根据期望的线性性有S=\sum_...
2019-09-06 15:33:53
241
原创 【分块】[LUOGU 弹飞绵羊] 分块
题目：题目链接：[LUOGU 弹飞绵羊] 题解：这个题就是一个LCT的模板题，但是呢，作为一个菜鸡，LCT，，还是不会的了，那我就好好写分块吧，就好好写分块就好了，，，，这个题用分块的写法就是比较简单了，开两个数组记录一下就好了，一个是记录这只绵羊跳多少步才能跳出他自己所在的块，再开一个记录一下他跳出去之后跳到了哪个点上就好。这样的话就很好去用分块进行维护了。，，代码：#include...
2019-09-03 21:31:51
125
原创 [LUOGU 哈希冲突] 巧妙根号算法
题目：题目链接：[LUOGU 哈希冲突] 题解：一看到是rxz大佬的题目，，就上去做了做，但是，，为什么挂出来分块的标签，但是呢，，，，跟分块，，一点关系都没有啊！！！！!不瞎扯了，，，进入正题，，，先解释一下题面：就是给你一串数，对于标号进行操作，标号取模得x的，把他给的数的劝权值进行取和。就是nnn\sqrt{n}nn进行预处理，之后的可以O(1)O(1)O(1)处理n\sqr...
2019-09-03 21:10:59
141
原创 【分块】[LUOGU 旅行规划] 分块+二分+凸包优化
题目：题目链接：[LUOGU 旅行规划] 题解：先解释一下题面的意思：就是一个区间加的操作，再加上一个代码:
2019-09-03 20:33:45
110
原创 【线段树】ZKW线段树浅谈
（学了学一般的线段树，还学了学线段树合并还有扫描线什么的，然后就就看到有一个比较有意思的线段树，，就学了一下）这里，，警告！zkw这东西，犹如鸡肋之令，食之无味，弃之可惜，没有太大的作用，本菜鸡就是敲一下板子了解一下即可。。。。。进入正题，，，，安利博客：洛谷日报，SinGuLaRiTy，Judge 关于zkw线段树zkw线段树，就是从底到上建线段树，抛弃掉之前的由上到下不断递归的建树...
2019-09-03 19:12:02
603
原创 【分块】[LOUGU 作诗] 正偶次分块
题目：题目链接:[LOUGU 作诗]题解：题目就是让求区间的正偶次个数，这里可以仿照区间众数的做法，整体下来进行分块就比较复杂，还需要考虑衔接块和大整块，但是还是比较好思考的。（重点看注释）代码：// luogu-judger-enable-o2//有是不挺的TLE，，又是要卡常，，，开O2过的#include<bits/stdc++.h>using namespac...
2019-09-02 19:35:39
137
原创 【线段树】[LUOGU 会场预约] 线段树染色
题目：题目链接：[LUOGU 会场预约]题解：（这个可以用BIT写，这个是比较短的，可是蒟蒻这个数据结构还需要加强，，，，）线段树染色，就是对于每次的区间覆盖的时候进行染色处理，再记录一下是否被删除过的数 ，这样不用再进行真实的删除操作了，懒标记为颜色的标号。安利大佬博客：传送门（好不容易写完的题，反复TLE，，，索性一个O2，，，结果就过了，，，，不知道我的常数为何如此之大，，，，）...
2019-09-02 18:57:30
127
原创 【分块】[LUOGU 教主的魔法] 分块模板
题目：题目链接：[LUOGU 教主的魔法] 题解：（才发现我的分块再洛谷上交的题比较少都是在别的OJ上写的比较多，所以就打算补补。。。）这个题就是个分块的模板题，，，，这里还是也要补充一下数组和vector的比较：vector：不定长的数组，但是是动态的，相对于数组来说会比较慢（毕竟是STL），但是比较好排序，以及比较由于是不定长的所以就不用管它的长度。数组：比较固定是静态的，由于是...
2019-09-02 17:18:27
140
原创 【线段数】[LUOGU 上帝造题的七分钟2 / 花神游历各国] 线段树/分块 区间开方
题目：题目链接：[LUOGU 上帝造题的七分钟2 / 花神游历各国] 题解：这个题其实在之前我写的数列分块中的有一道题很一样，几乎一模一样了，也是让区间开方，分块写就很好理解，然后现在用线段树写其实大体上的解是一样的但是呢，就是套路不是很一样，，，这个题重要的就是在一点，对于要好多次开方的数，你会发现，一个在1e9之内的数你对它开最多开方（下取整）六次即可开到1,或者是0，这样的话如果是开...
2019-09-02 16:38:18
122
原创 【线段树】[LUOGU 守墓人] [LUOGU 维护序列] 线段树模板题
题目：题目链接：守墓人题解：线段树单点修改，区间修改，单点查询，区间查询，一系列线段树基本操作，模板打就好。（回头再补一个分块和树状数组的这种板子题，就是用分块和树状数组再写一遍，，练练手用）代码：#include<bits/stdc++.h>#define LL long long#define lk (k<<1)#define rk (k<<...
2019-09-02 16:15:28
173
原创 【线段树】[POJ Atlantis] 线段树扫描线
题目：题目链接：[POJ Atlantis] 题解：（这个题作为学习线段树的尾巴，，，结果还是学了好长时间）先安利一下sdau_blue大佬的优秀博客，太有用了。这个题就是有许多的矩形进行随意放置在二维平面内，重叠的面积只算一次，求总面积。在这里就是离散化处理横坐标，对于纵坐标进行结构体处理一下，然后再以横坐标作为线段(区间)，对横坐标线段进行扫描，扫描的作用是每次更新下底边总长度和下...
2019-08-29 16:27:45
164
1
原创 【线段树】[LUOGU [湖南集训] 谈笑风生]线段树合并
题目:题目链接：[LUOGU [湖南集训] 谈笑风生]题解：由于是要求符合条件的三元组，那么可以分成两段来写，第一段：如果b在a的上面的时候在这一段中c就可以是a的子树大小，而b的话就是min(deep[a]−1,K)min(deep[a]-1,K)min(deep[a]−1,K)，这一部分的答案就是size[a]∗min(deep[a]−1,K)size[a]*min(deep[a]...
2019-08-29 06:23:20
121
原创 【线段树】[LUOGU [Vani有约会]雨天的尾巴] 树上差分+线段树合并
题目：题目链接：[LUOGU [Vani有约会]雨天的尾巴]题解：这个题，，，就是线段树合并的板子，加上一个树上差分操作即可。至于怎么树上差分，可以先想一下在序列中差分，因为这里是赋值的操作了，所以在序列中啊，就是在序列的首位出加一减一就可。这样的思想转化到树上对于树上的距离就是重在四个点上，xxx,yyy,lca(x,y)lca(x,y)lca(x,y),fa[lca(x,y)]fa[lc...
2019-08-28 21:53:57
114
原创 【线段树】[LUOGU NOIP2016 天天爱跑步] 线段树合并+树上差分
题目：题目链接：[LUOGU NOIP2016 天天爱跑步]题解：（这个题，，真的，其实学这个权值线段树的知识，就是为了写这道题的，，，但是，尽管半个小时码完了代码，但是，，，调了一下午，，，，o(╥﹏╥)o）不扯了，还是好好写题解吧：这道题其实就是个加强版的雨天的尾巴（树上差分+线段树合并），可以先做一下这道题。这个题中的链中，如果可以被观察员发现的话，需要满足两点：第一点：xxx...
2019-08-28 21:42:16
138
原创 【线段树】[LUOGU [USACO17JAN]Promotion Counting晋升者计数] 线段树合并
题目：题目链接：[LUOGU [USACO17JAN]Promotion Counting晋升者计数]题解：这是个线段树合并的板子题，，，可以主席树写，可以树状数组（竟然还有莫队优化+BIT的写法，，，菜鸡我竟然没想到），甚至是Splay也可以写，，但是我偏要写线段树合并，，o(´^｀)o，，在前面处理一下点权，这里的点权可以用比较巧妙的一个小trick即可，然后这个线段树合并就非常的板子...
2019-08-26 21:36:46
155
原创 【线段树】[LUOGU [HNOI2012] 永无乡] 并查集+区间第k小 [线段树合并]
题目：题目链接：[LUOGU [HNOI2012] 永无乡]题解：代码：#include<bits/stdc++.h>using namespace std;inline int read(){ int s=0,w=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar()...
2019-08-26 06:18:51
101
原创 【线段树】[LUOGU CF600E Lomsat gelral] 区间众数和 [线段树合并]
题目：题目链接：[LUOGU CF600E Lomsat gelral]题解：这个题就是个（动态开点）权值线段树的板子题，就是在每个点上建立一个取值线段树，记录区间众数和，不断是合并权值线段树就行，在up里面就进行对于众数的判断即可。这里再说一下权值线段树，之前说过，这就是个桶，但是桶只能查找到权值等于xxx这个值的个数，但是权值线段树可以查找到权值在xxx，yyy之间的的个数。代码：...
2019-08-25 18:45:34
929
原创 【线段树】[LUOGU [POI2011] ROT-Tree Rotations] 线段树合并
题目：题目链接：[LUOGU [POI2011] ROT-Tree Rotations]题解：（这此是真的线段树合并，上次是，，失误）这个题，从权值线段树开始学，又学了动态开点，最后才学的线段树合并，，，，（我说之前我连题解都看不懂呢，，，）先说一下动态开点，我认为它就是个比较好的思想，在之前我写的线段树是中规中矩的，开满满的二叉树，还要开4倍的空间，这样的话其实是比较浪费空间的，那么就...
2019-08-25 06:23:06
151
原创 【线段树】[LUOGU USACO08FEB 酒店Hotel ] 区间连续最大
题目：题目链接：[LUOGU USACO08FEB 酒店Hotel ]题解：这个题，就是XOR的艺术和Glass Carving的结合，就是求长度为x的最小房间号的连续0，这样的话就是和Glass一样进行线段树的合并，再想XOR的艺术一样进行修改。代码：#include<bits/stdc++.h>#define lk (k<<1)#define rk (k&...
2019-08-22 13:37:30
107
原创 【线段树】[LUOGU Glass Carving] 区间连续最大
题目：题目链接：[LUOGU Glass Carving]题解：仔细想一下，纵着切和横着切是互不影响的。这样就是可以用线段树维护横坐标和纵坐标就行，，所以这个题的关键就是在段树合并，现在节点的最大值就是左边最大值，右边最大值，以及左边中从右边开始的0+右边中从左边开始的0的和，这样就是在up中解决一下就行了。代码：#include<bits/stdc++.h>#defin...
2019-08-22 12:32:32
150
原创 【线段树】[LUOGU XOR的艺术] 区间异或+区间询问
题目：题目链接：[LUOGU XOR的艺术]双倍经验：[USACO08NOV 光开关Light Switching]三倍经验：[LUOGU [TJOI2009] 开关]题解：异或操作，区间和即可。代码：#include<bits/stdc++.h>using namespace std;inline int read(){ int s=0,w=1;char ch=...
2019-08-22 11:01:34
150
原创 【线段树】[LUOGU 方差] 线段树+数学技巧
题目：题目链接：LUOGU 方差题解：（其实最近写线段树的题还有一部分原因是因为这个题，，，码了半个多小时，调了一两天，，，/(ㄒoㄒ)/~~，因为这个题，三个人一起改，，，还是没改出来，，，之后我还去学了Dev的单步跟踪，，，结果，，单步跟踪挂掉了，，一些玄学错误不好调了，完了，，，就只好重新码一遍，结果还好重构之后就是过了，，，不容易啊(〃＞＿＜;〃)）还是 进入正题吧，，，这个题其实...
2019-08-22 10:10:31
145
原创 【线段树】[P1816 忠诚] 询问区间最小
题目：题目链接：P1816 忠诚题解：（要不是被一个小可爱催着睡觉，，，一晚上就写完了，，，，￣へ￣）这个题，看着比较简单，用线段树写比较好写，用分块就更好写了，，但是既然是练习线段树，就用线段树写吧。代码：#include<bits/stdc++.h>#define lk (k<<1)#define rk (k<<1|1)using name...
2019-08-22 09:22:30
126
原创 【线段树】[POJ A Simple Problem with Integers] 区间加
A Simple Problem with Integers【http://poj.org/problem?id=3468】P1816 忠诚方差XOR的艺术(三道)Glass CarvingP2894 [USACO08FEB]酒店Hotel
2019-08-22 09:06:36
109
原创 [LUOGU 可怜的狗狗] 主席树 单点修改+区间查询
题目：题目链接：LUOGU 可怜的狗狗题解：这个题啊，真的是，，，一个完全可以用莫队写的题，我偏偏写了主席树，，唉，还不是被怼只会写莫队分块，，， 就好好学了主席树，但是，主席树，尽管是名义上的可持久化线段树，但是它的代码和线段树一比就知道还是主席树代码短，主要是因为看它是可持久化的只需要对于把几棵树串起来来回修改就好，线段树还是要遍历整颗树，，，这个题就是主席树的模板，直接套上就好，离散...
2019-08-22 08:38:31
229
原创 【二分图】[LUOGU P2055 假期的宿舍] 最大匹配
题目：题目链接：[LUOGU P2055 假期的宿舍]题解：最大匹配板子题，就是巧妙在建图上，有床留校者则连即可，最后处理判断是否完全匹配即可。代码：#include<bits/stdc++.h>using namespace std;const int sea=200;int T,n,a[sea][sea],g[sea][sea],pre[sea],v[sea],ff[...
2019-08-13 23:08:06
107
原创 【二分图】[LUOGU P4298 祭祀] 最长反链+输出方案
题目：题目链接：[LUOGU P4298 祭祀] 题意：求最长反链的长度并输出方案。题解：最长反链=最小点覆盖数=最小路径覆盖数=总点数-最大匹配重点看注释，，，#include<bits/stdc++.h>using namespace std;inline int read(){ int s=0,w=1;char ch=getchar(); while(ch&...
2019-08-12 23:55:56
260
原创 【二分图】[LUOGU 长脖子鹿放置] 最大独立集+奇偶建边
题目：题目链接：LUOGU 长脖子鹿放置题解：这个题，我刚看上去就像是搜索吧，然后就往搜索优化，剪枝，A*什么的想了，然后看到题目上的一句话：然后，，，，（无语）转变了想法，直接想建图，，但是确实不是很会建，就看了看题解，按照奇偶性建边，，，我**，想不到啊，按照思路画了画图，下面是样例2，按照奇偶建边，可以铺满整个图的（重复的就画了框外线，而且只画了前两行）所以直接按照奇偶性建边...
2019-08-12 13:43:29
241
原创 【二分图】[LUOGU P4589 智力竞赛] 二分图最独立集+二分答案
题目：题目链接：[LUOGU P4589 智力竞赛]题意：就是给出一个带权有向图，选出n + 1条链，问能否全部点覆盖，如果不能，问不能覆盖的点权最小值最大是多少题解：发现题目要求的就是可相交的最小路径覆盖，再求一下Floyed传递闭包，可以求出每个点能到达的点集，二分答案，check里面用栈存一下判最大匹配即可。二分图的相关总结：点覆盖：点集合使得任意一条边至少有一个端点在集合中。...
2019-08-12 11:23:12
112
原创 【二分图】[LUOGU P1155 双栈排序] 二分图染色+栈模拟
题目：题目链接：LUOGU P1155 双栈排序题解：按单栈的规则建图，如果不能再同一个栈就连边，所以总共分成三种情况：1.单栈直接就可以解决的2.双栈排序连成二分图才能解决3.双栈排序时连不成二分图，无解在建二分图的时候，运用二分图染色，把图染成黑白两种色，这样用来表示二分图，然后判断是否是二分图即可，最后输出答案的时候进行对栈的模拟即可。代码：#include<bits...
2019-08-12 10:30:28
118
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人