- 博客(484)
- 收藏
- 关注
RSS订阅
原创 新的开始
先简单介绍一下博主的情况高二省选失败 高考考到北航本以为到了大学可以轻松一点 然而发现可能要高四今天考了场试又备受打击所以打算重新开始 哪怕只有三分钟热度也起码坚持三分钟希望能进个校队吧...
2020-09-20 19:51:49
341
9
原创 Codeforces DP训练
813D：题意：给出长度为nnn的序列，从中找出222个子序列，满足每个子序列相邻两数之间要么相差111，要么同余于777，求这两个子序列的最长长度和。题解：DP优化主要考虑状态的减少和转移的加快，这个题f[i][j]f[i][j]f[i][j]表示分别以iii、jjj为结尾的子序列最长长度和的状态不能减少，考虑优化转移。防止一个位置被重复选择，要强制限制i<
2018-09-29 22:05:14
2267
2
原创 【温故知新】BZOJ复习计划
前言：在BZOJ上也做了不少题了，但是有些题当时在做的时候理解不够深刻，或是时间久了忘记了，都是形同虚设的。那么，有空就多看看自己以前做的题目吧……==============分割线==============1805: [Ioi2007]Sail 船帆： 好题。首先我们要得到贪心的策略，从后往前放旗子，每次选当前行最少旗子的放，若相同则从上往下放，正确性显然。但有了这个还不够，...
2017-12-09 20:56:20
518
3
原创 不想写博客的题目
2017.10.11 BZOJ1225: [HNOI2001] 求正整数 一个普通的搜索，应用了约数和公式，用对数来比较大小的思路很新颖（至少我没有想过）。 2017.10.12 BZOJ4149: [AMPPZ2014]Global Warming 单调栈，这篇题解写得很好点这里 唉，最近几天效率贼低……尤其是理解别人的代码，有时几乎对着打都一堆错，我还是滚去看初赛吧…… 2017...
2017-10-11 19:36:46
966
2
原创 第 45 届ICPC亚洲区域赛（昆明）B Chessboard 上下界费用流 负环处理
Solution:用的是题解的建图（详见出题人知乎回答）。然而上下界费用流为了平衡源汇点的流量，会有一条汇点到源点的边，而负权边的出现会导致原图存在负环。采用以下方法处理：模板参考的是这位大佬。存一下模板。Code#include<bits/stdc++.h>using namespace std;#define LL long long#define pa pair<int,int>const int Maxn=55;const int N=160,M=250
2021-04-07 15:48:08
367
原创 HDU6054 String and String 广义后缀自动机+树状数组套线段树
存一下代码。广义SAM是正版的。Code#pragma comment(paintr, "/STACK:102400000,102400000") #include<bits/stdc++.h>using namespace std;#define LL long long#define pa pair<int,int>const int Maxn=400010,N=390;const int inf=2147483647;const double pi=acos
2021-02-28 16:09:01
244
原创 [BZOJ]5093: [Lydsy1711月赛]图的价值 NTT+第二类斯特林数
Description“简单无向图”是指无重边、无自环的无向图（不一定连通）。一个带标号的图的价值定义为每个点度数的k次方的和。给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。因为答案很大，请对998244353取模输出。Solution考虑每个点的贡献，容易得到如下式子：ans=n×2n(n−1)2−n+1∑i=1n−1Cn−1iikans=n\times2^{{n(n-...
2019-04-25 07:30:42
257
原创 [BZOJ]4160: [Neerc2009]Exclusive Access 2 状压DP+Dilworth定理
Description给出 N 个点M 条边的无向图，定向得到有向无环图，使得最长路最短。N ≤ 15, M ≤ 100Solution大家都知道Dilworth定理的其中一个内容：最小路径覆盖=最长反链。实际上与之相似的是：最长路=最小反链划分数。这个东西虽然比较显然，但是之前没有接触过的话可能还是比较难想到。有了这个，直接状压DP就行了。Code#include<bit...
2019-04-17 12:06:24
360
原创 [AGC028] E - High Elements 思维
Solution考虑知道前面的一段后，怎么判断后面是否合法，这样就可以逐位确定。先上一个结论：令mximx_imxi为原序列111~iii的最大值所在位置，我们称原序列中每个mxi=imx_i=imxi=i的位置为上升位，分割后的序列的新的上升位为新晋上升位，那么若存在一种合法方案，一定可以将其调整为其中一个序列中的所有上升位置都是原序列的上升位。证明可以考虑若两个序列都存在新晋上升位，...
2019-04-16 20:40:50
560
1
原创 [LOJ]#2720. 「NOI2018」你的名字 后缀自动机+主席树
Solution首先讲一下一个68分的水法：建广义SAM，然后每次询问完之后暴力撤销，复杂度未知。这种做法本身复杂度好像就不对，而且也没法扩展，考虑另外的做法。考虑每个询问串前缀的贡献。首先要保证本质不同，所以先求出每个前缀的最短的没有在之前出现过的后缀，这个可以对每个询问串建SAM求。然后要求出每个前缀的最短的没有在SSS出现过的后缀，如果是68分，相当于在SSS的SAM上匹配，求最长匹配...
2019-04-13 17:00:09
376
原创 [Codeforces] 1037 H. Security 后缀自动机+主席树
Solution这题思路还是比较简单的。由于∑∣S∣\sum|S|∑∣S∣较小，所以可以枚举答案前多少位是和给出的串是一样的，再枚举下一位填什么，这样问题就转化为快速判断一个区间中某个字符串是否出现过。把parent树建出来后，就是询问某个点子树中有没有值域在某个范围内的点，可以用主席树解决。需要注意的是，当询问长度为lenlenlen的串是否在[l,r][l,r][l,r]中出现时，询问...
2019-04-11 17:26:48
313
原创 [LOJ]#572. 「LibreOJ Round #11」Misaka Network 与求和 min_25筛+杜教筛
Solution推一下式子，容易得到一个线性做法：∑d=1nfk(d)((2∑i=1⌊ni⌋φ(i))−1)\sum_{d=1}^nf^k(d)((2\sum_{i=1}^{\lfloor{n\over i}\rfloor}\varphi(i))-1)d=1∑nfk(d)((2i=1∑⌊in⌋φ(i))−1)这个东西数论分块加速一下，只需要快速求欧拉函数的前缀和和fff的kkk次方的前缀...
2019-04-09 13:23:09
381
原创 [Codeforces] 1109F. Sasha and Algorithm of Silence's Sounds LCT+线段树
Solution假如要求的不是一棵树而是一个森林那就很好做，直接用一个双指针+LCT就可以对每个右端点维护出没有环的左端点。那么树这个限制怎么解决呢？树也就是连通块只有一个，而连通块数=点数-边数，用一个线段树维护这个东西就行了。Code#include<bits/stdc++.h>using namespace std;#define LL long long#defin...
2019-04-05 13:33:44
202
原创 [Codeforces] 888G. Xor-MST Boruvka算法/分治+01trie
Solution经典的异或最小生成树，我所知道的有两个做法，分别介绍一下。1、最小生成树的Boruvka算法。这个最小生成树算法大概流程是把开始的nnn个点视为nnn个连通块，然后每次每个连通块找到一条连向其他连通块的权值最小的边并连起来，这样每次至少减少一半的联通块数，复杂度为O(nlogn)O(n\log n)O(nlogn)。那么在这题套用这个算法的话，可以建一个所有数的010101...
2019-04-05 12:05:58
495
原创 [LOJ]#2731. 「JOISC 2016 Day 1」棋盘游戏 DP
Solution首先判断无解：四个角没有棋子或者第一、三行连续两个没有棋子。然后通过观察可以发现，按照空格的四连通块来划分的话，每个连通块之间是互不影响的。所以可以对每个连通块分别DP，最后再用组合数把各个连通块给拼起来。设fi,j,0/1f_{i,j,0/1}fi,j,0/1表示第二行的第iii个空格，是当前这个连通块第jjj个填的，填的时候是上下填好还是左右填好，如果上下左右都已经填好...
2019-04-03 07:26:59
224
1
原创 [AGC031]E - Snuke the Phantom Thief 费用流
Solution假设我们一共选了kkk个，那么假如x≤ax\le ax≤a最多选bbb个，那么xxx第b+1b+1b+1大的宝石的xxx必须大于aaa，假如x≥ax\ge ax≥a最多选bbb个，那么xxx第k−bk-bk−b大的宝石的xxx必须小于aaa。也就是说只要枚举选了多少个，那么对于每个宝石的x、yx、yx、y都可以得到一个上下界，可以直接跑上下界费用流，但是其实没有必要。因为上下解...
2019-04-02 19:12:21
583
原创 [HDU]6326 Problem H. Monster Hunter 贪心
Solution回顾一下经典的打怪兽问题。设打死一只怪兽先掉aia_iai血，再回bib_ibi血，那么我们排序策略是：对于ai≤bia_i\le b_iai≤bi，aia_iai小的排在前；对于ai>bia_i>b_iai>bi，bib_ibi大的排在前，前一种情况排在前面，正确性显然。到了树上，并且有了打完父亲才能打儿子的限制，考虑怎么做...
2019-03-25 21:21:50
234
原创 [BZOJ]5259: [Cerc2017]区间 线段树
Description给定一个1到n的排列a1, . . . , an。对于一个区间[l, r]，我们称该区间是连续的，如果将al, . . . , ar排列之后得到的是一列连续的数。（换句话说，如果x,y都在该区间中，那么所有介于x,y之间的数也在该区间中）现在有m(1 ≤ n, m ≤ 100000)个询问，每个询问给出一个区间[xi, yi],你需要找到一个长度最短的连续区间[li...
2019-03-25 19:06:12
354
原创 AtCoder Grand Contest 031 C - Differ by 1 Bit 构造 归纳法
Solution下面基本都是题解的中文翻译。为了方便，称一个数的奇偶性为二进制表示中111个数的奇偶性。首先判掉无解，即AAA与BBB奇偶性相同，因为每次有一位不同，所以每次奇偶性会变。下面用归纳法证明其他情况都是有解的。n=1n=1n=1时显然有解，假设n=kn=kn=k时有解，现在证明n=k+1n=k+1n=k+1时也有解。AAA和BBB至少有一位不同，假设是第xxx位，两个数同时去...
2019-03-17 21:47:41
389
1
原创 [BZOJ]3711: [PA2014]Druzyny 分治+线段树
Description体育课上，n个小朋友排成一行（从1到n编号），老师想把他们分成若干组，每一组都包含编号连续的一段小朋友，每个小朋友属于且仅属于一个组。第i个小朋友希望它所在的组的人数不多于d[i]，不少于c[i]，否则他就会不满意。在所有小朋友都满意的前提下，求可以分成的组的数目的最大值，以及有多少种分组方案能达到最大值。Solution先列出最简单的DP：fi=max{fj+1...
2019-03-15 13:44:35
367
原创 [BZOJ]4730: Alice和Bob又在玩游戏 sg函数+trie
DescriptionAlice和Bob在玩游戏。有n个节点，m条边(0<=m<=n-1)，构成若干棵有根树，每棵树的根节点是该连通块内编号最小的点。Alice和Bob轮流操作，每回合选择一个没有被删除的节点x，将x及其所有祖先全部删除，不能操作的人输。注：树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。比如：1-3-2 这样一条链，1号点是根节点，删除1号点...
2019-03-15 13:02:29
513
原创 [BZOJ]4180: 字符串计数 SAM+矩阵乘法+二分
DescriptionSD有一名神犇叫做Oxer，他觉得字符串的题目都太水了，于是便出了一道题来虐蒟蒻yts1999。他给出了一个字符串T，字符串T中有且仅有4种字符 ‘A’, ‘B’, ‘C’, ‘D’。现在他要求蒟蒻yts1999构造一个新的字符串S，构造的方法是：进行多次操作，每一次操作选择T的一个子串，将其加入S的末尾。对于一个可构造出的字符串S，可能有多种构造方案，Oxer定义构造...
2019-03-14 17:37:06
206
原创 [BZOJ]4844: [Neerc2016]Foreign Postcards 概率DP
Descriptionls是一名集邮爱好者，他专门有一个栈来存放他的所有的邮票，但ls同时也是一名很粗心的人，有一些邮票可能放反了（上下颠倒），有一天他想把他的邮票拿出来向他的妹子炫耀，但因为有一些邮票可能反了，于是ls就想把那些邮票矫正方向，但ls特别懒，他觉得一张一张矫正太费时间了，即使是要给妹子看的，他也不想费太多时间，于是ls就想出了一种奇迹淫巧：1.假设栈中还剩n张邮票，他每次从1到...
2019-03-14 15:20:11
337
原创 [BZOJ]4987: Tree 树形DP
Description从前有棵树。找出K个点A1，A2，…，Ak。使得∑dis(AiAi+1),(1<=i<=K-1)最小。Solution这道题首先要用到一个结论，即ans=最小的包含A1到Ak的连通块中所有边的和×2−这个连通块直径ans=最小的包含A_1到A_k的连通块中所有边的和\times 2-这个连通块直径ans=最小的包含A1到Ak的连通块中所有边的和×2−...
2019-03-13 17:48:55
432
原创 [BZOJ]5068: 友好的生物 放缩
Solution猜到复杂度……却依然不会做……这个方法感觉和不等式证明中的放缩法有点类似，所以我个人这样称呼……先把CiC_iCi乘进去，把式子写出来：∑i=1k−1∣ai−bi∣−∣ak−bk∣\sum_{i=1}^{k-1}|a_i-b_i|-|a_k-b_k|i=1∑k−1∣ai−bi∣−∣ak−bk∣绝对值很烦，考虑怎么去掉它，我们可以直接2k−12^{k-1}2k−1枚...
2019-03-13 17:42:12
139
原创 [BZOJ]4849: [Neerc2016]Mole Tunnels 模拟费用流
Description鼹鼠们在底下开凿了n个洞，由n-1条隧道连接，对于任意的i>1，第i个洞都会和第i/2（取下整）个洞间有一条隧道，第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠，第i只鼹鼠住在第pi个洞内，一天早晨，前k只鼹鼠醒来了，而后n-k只鼹鼠均在睡觉，前k只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的ci均大于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动...
2019-03-13 12:30:39
262
2
原创 [BZOJ]5219: [Lydsy2017省队十连测]最长路径 DP
Description在Byteland一共有n个城市，编号依次为1到n，它们之间计划修建n(n-1)/2条单向道路，对于任意两个不同的点i和j，在它们之间有且仅有一条单向道路，方向要么是i到j，要么是j到i。换句话说，这是一个n个点的竞赛图。Byteasar居住在1号城市，他希望从1号城市出发，沿着单向道路不重复地访问一些城市，使得访问的城市数尽可能多。请写一个程序，帮助Byteasar计算有...
2019-03-11 07:26:48
227
原创 [LOJ]#2736. 「JOISC 2016 Day 3」回转寿司 分块
Solution显然每次操作是要选一个上升子序列， 然后把整体往后推，去掉一个最大值，加入AAA，考虑怎么维护。看见数据范围和时限，大胆猜测是分块。这里采用一种类似线段树中lazylazylazy标记的思想。对于中间的整块，显然是加入AAA之后出来一个最大值，我们每个块用一个堆维护最大值，暂时不管数的顺序。但是对于左右的不完整块，我们必须知道数的位置，用另外一个堆维护这个块有哪些数经过过，然后...
2019-03-07 22:35:19
329
原创 [LOJ]#2472. 「九省联考 2018」IIIDX 线段树+贪心
Solution按照大小关系连边之后得到一棵树，然后肯定是每次填入尽量大的数，如果当前连到第xxx个点，那么就需要知道当前能用的数中最大的一个有sizexsize_xsizex个数大于等于它的数，考虑如何维护这个东西。如果直接维护现在每种数剩下多少个，就很难搞，反正我是没有搞出来，考虑换一个东西，维护大于等于每种数的还有多少个数能用，这样的话每次是一个区间加减，还有一个线段树上二分的操作。注意...
2019-03-07 22:28:23
198
原创 [LOJ]#2773. 「ROI 2017 Day 2」学习轨迹 线段树
Solution如果只上一所学校的课，那么显然要选择这所学校的所有课程。因此，至少有一所学校选择的课程权值超过了这所学校总权值的一半。不妨强制第一所学校要超过，那么设第一所学校第一次前缀和超过总权值一半的位置为ppp，则这个位置一定要被选择。在第二所学校选择了一些课程后，一定是从ppp开始，尽量往两边扩展。枚举第二所学校选择的右端点rrr，那么每次最多会有一个位置不能再被选择。可以用两个单调栈...
2019-03-06 22:34:46
878
原创 [LOJ]#6515. 「雅礼集训 2018 Day10」贪玩蓝月
Solution离线做法很简单，就是线段树分治，不过复杂度是qmodlogqmod\logqmodlog。考虑在线做法，在线段树分治中，我们并没有利用到删除以及加入都只会在两端进行这个性质，我们考虑用两个栈分别维护两端，每次加入一个数就暴力做背包，删除就删除栈顶。当某一个栈被删空了之后，就把现有的数均等分成两份，扔进两个栈中暴力重构。询问的话，一开始也想过分成两段维护，但一直没有办法快速合...
2019-03-05 07:34:18
695
原创 [LOJ]#2838. 「JOISC 2018 Day 3」比太郎的聚会 根号分治
Solution以后不会做题还是要考虑根号分治啊……对于给出点数≥n\ge\sqrt n≥n，直接O(n)O(n)O(n)DP；对于给出点数&lt;n&lt;\sqrt n<n，可以预处理：对于每个点，预处理出离他最远的n\sqrt nn个点，然后更新时可以归并一下，询问时直接查就可以了。Code#include<bits/stdc++.h>us...
2019-03-03 19:37:48
410
原创 [LOJ]#2344. 「JOI 2016 Final」铁路票价 最短路
Solution先BFS一次跑出最短路，然后动态维护每个点现在还有多少个直接连到它的点能够通过最短路走到它就可以了。每个点的值最多只要一次变为000，复杂度是线性的。Code#include<bits/stdc++.h>using namespace std;#define LL long long#define pa pair<int,int>const i...
2019-03-03 19:31:53
391
原创 [BZOJ]5306: [Haoi2018]染色 容斥+NTT
Solution设fif_ifi为至少有iii种颜色出现恰好sss次的方案数，gig_igi为恰好有iii种颜色出现恰好sss次的方案数，那么通过观察或者推导，可以得知容斥系数，那么有：gi=∑j=im(−1)j−iCjifjg_i=\sum_{j=i}^m(-1)^{j-i}C_j^if_jgi=j=i∑m(−1)j−iCjifj把组合数拆开，移项：gi×i!=∑j=im(−1)j...
2019-03-03 17:31:26
208
原创 JXOI2017题解
「JXOI2017」加法先二分答案，求出每个位置需要被覆盖多少次，那么从左往右扫，对于每个位置，如需被覆盖xxx次，那就贪心的选择前xxx个能覆盖到他且覆盖的最远的xxx条线段。随便维护一下即可。Code#include<bits/stdc++.h>using namespace std;#define LL long long#define pa pair<int,...
2019-03-01 08:05:36
329
原创 JXOI2018题解
「JXOI2018」游戏显然只要检查完所有除自己外没有范围[l,r][l,r][l,r]的因数的数就可以使所有办公室开始认真工作，那么只需要求出这种数有多少，后面就随便算了。那么只需要知道最大因数是否在[l,r][l,r][l,r]内，线性筛出每个数的最小质因数就可以知道最大因数了。Code#include<bits/stdc++.h>using namespace std;...
2019-02-28 17:48:05
324
原创 [LOJ]#2553. 「CTSC2018」暴力写挂 边分治+线段树合并
Solution这题搞了好久……不过还是挺有收获的。听说这种多棵树的题大概都是这样的套路？枚举第二棵树的LCA(x,y)LCA(x,y)LCA(x,y)，然后化一下式子可以发现：depthx+depthy−depthLCA(x,y)=12(depthx+depthy+distancex,y)depth_x+depth_y-depth_{LCA(x,y)}={1\over 2}(depth_x+...
2019-02-28 13:42:15
212
原创 [LOJ]#2554. 「CTSC2018」青蕈领主 DP+分治NTT
Solution首先，连续段只会包含而不会相交，而且每个连续段向第一个包含它的连续段连边，就会形成一个树的结构。这个如果无法理解可以看LCA今年营员交流。然后设当序列为1,1,1...n1,1,1...n1,1,1...n的时候的答案为fnf_nfn，每个点的儿子个数为bib_ibi，那么ans=Πi=1nfbi+1ans=\Pi_{i=1}^n f_{b_i+1}ans=Πi=1nfb...
2019-02-27 08:05:05
215
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人