- 博客(94)
- 收藏
- 关注
RSS订阅
原创 做题时经常发生的错误总结(持续更新中)
唠嗑因为做题训练时常常出锅，所以决定写下这篇文章，将这些错误铭记于心，永不再犯。（逃错误总结字符串哈希。哈希的时候尽量使用双哈希，单哈希的话尽量不要取特别常见的模数，否则被卡掉的几率会大幅度提升。(可能良心出题人会把这些模数卡掉)。模数尽量取大一点，否则根据生日悖论，很容易出现冲突(我感觉哈希这一块我已经烂过很多次了)差分约束系统。如果默认每一个位置的元素大小为非负数，一定要考虑到这个限...
2018-09-25 20:47:59
475
原创 CF1236F Alice and the Cactus 期望
题面题目传送门题解考虑连通块的个数为点数-边数+环的个数，方差的式子显然可以被化成E(x2)−E(x)2E(x^2)-E(x)^2E(x2)−E(x)2(xxx为连通块个数)。E(x)E(x)E(x)很好求，直接计算相应的期望就可以了。然后问题就变成了如何求E(x2)E(x^2)E(x2)，其中x=a−b+cx=a-b+cx=a−b+c，把式子打开有E(x2)=E(a2+b2+c2−2a...
2019-11-04 21:01:02
391
2
原创 LOJ2351「JOI 2018 Final」毒蛇越狱 容斥+子集卷积
题面题目传送门解法暴力显然是枚举???到底填什么，那么单次询问的复杂度为O(2cnt?)O(2^{cnt_?})O(2cnt?)，并没有什么可以优化的地方。不妨考虑一个容斥，将???全部看作是111，然后求子集的权值和。但是我们会将某些位置强制为111却填成000的数算入答案，那么我们还要减去这部分的答案。容斥的复杂度为O(2cnt1)O(2^{cnt_1})O(2cnt1)。可以发...
2019-10-19 15:07:15
375
原创 bzoj 4856 [Jsoi2016]病毒感染 区间dp
题面题目传送门解法首先显然可以发现，某一次回头一定会把之前没有被救过的村庄全都救一遍，那么最后的路径一定是不断向前走然后回头再往前走，直到所有村庄全都被救为止。那么我们可以设f[i]f[i]f[i]表示编号为1−i1-i1−i的村庄全部被救最少的死亡人数。对于转移，可以枚举这一次回头后到达的最后一个村庄，即这一轮最早一开始经过但没有救的村庄的编号jjj，那么便有如下转移：f[i]=m...
2019-04-21 21:37:39
317
2
原创 bzoj 3218 a + b Problem 最小割+主席树优化建图
题面题目传送门解法比较显然的最小割，不妨考虑如何建图。首先将SSS连向每一个点iii，容量为w[i]w[i]w[i]，表示割这条边点iii的颜色为黑色；iii向TTT连容量为b[i]b[i]b[i]的边，表示割这条边点iii的颜色为白色。对于jjj满足1≤j<i1\leq j<i1≤j<i且a[j]∈[l[i],r[i]]a[j]\in [l[i],r[...
2019-03-30 18:14:55
140
原创 bzoj 2732 [HNOI2012]射箭 二分答案+半平面交
题面题目传送门解法半平面交模板题。首先可以二分答案，然后考虑如何检验答案是否合法。现在对于每一个靶子都有一个形如l≤ax2+bx≤rl\leq ax^2+bx\leq rl≤ax2+bx≤r的限制，x,l,rx,l,rx,l,r为常量，那么就可以看成对a,ba,ba,b的限制，转化成半平面交。其实不需要每一次二分的时候都进行一次排序，可以先排序，然后将编号在二分范围内的半平面取出即可...
2019-03-24 19:29:32
160
原创 bzoj 3672 [Noi2014]购票 斜率优化+cdq分治+点分治
题面题目传送门解法先不考虑树的情况，考虑一条链怎么做。显然可以写出dp：f[i]=min(f[j]+(d[i]−d[j])p[i]+q[i])f[i]=min(f[j]+(d[i]-d[j])p[i]+q[i])f[i]=min(f[j]+(d[i]−d[j])p[i]+q[i])。然后把式子稍作展开，可以发现这显然是一个斜率优化的形式。决策的点坐标为(d[j],f[j])(d[j],f...
2019-03-23 16:45:37
148
原创 bzoj 4873 [Shoi2017]寿司餐厅 最大权闭合子图
题面题目传送门解法发现每一种寿司的组合方式都只能被计算一次，并且存在一些依赖关系：比如说选择了[l,r][l,r][l,r]就必须选择它的所有子区间。这启发我们利用最大权闭合子图来解决问题。不妨考虑将所有区间看成点，按照最大权闭合子图的方式来建图。当然，对于区间[l,r][l,r][l,r]我们不一定要连向所有的子区间，只要连向[l,r−1][l,r-1][l,r−1]和[l+1,r][...
2019-03-19 21:49:43
174
原创 bzoj 5252 [2018多省省队联测]林克卡特树 树形dp+凸优化
题面题目传送门解法简化一下题面就是选出不相交的k+1k+1k+1条链，使得边权之和最大。先写写部分分好了。k=0/1k=0/1k=0/1比较简单，求一求直径就好了，具体细节不再赘述(我记得我当初在考场上的时候竟然用两次dfs求直径，然后因为有负数就只有5分……)k=2k=2k=2可能是大分类讨论，表示并不会……考虑k≤100k\leq100k≤100怎么处理。可以考虑树形dp。f[...
2019-03-11 21:03:56
142
原创 bzoj 3836 [Poi2014]Tourism 状压dp+树形dp
题面题目传送门解法状压dp+树形dp好题图可能形成多个连通块，对于每一个连通块单独处理，因为相互之间不影响答案。那么考虑对于一个连通块的答案应该怎么计算。因为整个图满足最长路不超过10，那么就意味着dfs时候建出的搜索树深度不超过10，并且非树边必然为返祖边。我们不妨假设000表示这个点被选择了，111表示这个点没有被选择并且它还没有被覆盖，222表示这个点没有被选择但是已经被覆盖...
2019-03-04 18:38:57
175
原创 bzoj 4305 数列的GCD 容斥原理
题面题目传送门解法显然，恰好有kkk个不相同的位置就意味着恰好有n−kn-kn−k个位置的数是相同的，不妨令k=n−kk=n-kk=n−k，求恰好有kkk个位置相同且满足条件的方案数。可以考虑这样一个容斥：令s[i]s[i]s[i]表示有因子iii的数的个数，那么可以得到f[i]=∑i∣jμ(ji)(s[j]k)(⌊mj⌋−1)s[j]−k(⌊mj⌋)n−s[j]f[i]=\sum_{i...
2019-03-03 21:23:40
190
原创 bzoj 5302 [Haoi2018]奇怪的背包 dp+数论
题面题目传送门解法可以将问题转化成这样一个问题：选出一些数a1,a2,…,ama_1,a_2,\dots,a_ma1,a2,…,am，使得存在这样的x1,x2,…,xmx_1,x_2,\dots,x_mx1,x2,…,xm满足∑i=1maixi≡w(modp)\sum_{i=1}^ma_ix_i\equiv w\pmod p∑i=1maixi≡w(modp)显然需要满足...
2019-03-01 22:12:10
167
原创 LG P5156 [USACO18DEC]Sort It Out dp+树状数组
题面洛谷传送门USACO传送门解法结论应该比较显然，就是相当于找字典序第KKK大的LISLISLIS。考虑怎么证明其正确性。对于一次sort(x)sort(x)sort(x)操作，可以发现除xxx之外的元素的相对位置并不发生改变。那么，现在相当于要找一个最大的集合SSS，使得它们在序列中严格递增。显然∣S∣|S|∣S∣等于LISLISLIS的长度。然后再考虑字典序的问题。最后答案的集合...
2019-02-25 21:44:28
228
原创 bzoj 2597 [Wc2007]剪刀石头布 费用流
题面题目传送门解法简单来说，题意就是确定一些无向边的方向，使得三元环的个数最多。考虑所有边都确定的情况下怎么计算三元环的个数，假设每一个点的度数为d[i]d[i]d[i]，通过容斥原理可以得到(n3)−∑i=1n(d[i]2){n\choose 3}-\sum_{i=1}^n{d[i]\choose 2}(3n)−∑i=1n(2d[i])。那么我们可以将那些没有确定的边按照编号提...
2019-02-17 20:54:39
153
原创 bzoj 5251 [2018多省省队联测]劈配 网络流+二分答案
题面题目传送门解法当年我果然还是太菜了先考虑第一问怎么解决对于每一个选手iii，连接(S,i,1)(S,i,1)(S,i,1)；对于每一个评委jjj，连接(j,T,b[j])(j,T,b[j])(j,T,b[j])。选手按照编号从小到大处理，枚举最后的答案，然后加上相应的边，看是否能够增广就可以了。对于第二问，可以记录一下每一个选手做完之后的残量网络，二分答案即可。【注意事项】...
2019-02-14 20:58:50
112
原创 bzoj 2149 拆迁队 斜率优化+cdq分治
题面题目传送门解法从来没写过这样的……第一问非常简单，能够从jjj转移到iii的条件显然为a[i]−a[j]≥i−ja[i]-a[j]≥i-ja[i]−a[j]≥i−j，移项可得a[i]−i≥a[j]−ja[i]-i≥a[j]-ja[i]−i≥a[j]−j。不妨令x[i]=a[i]−ix[i]=a[i]-ix[i]=a[i]−i，那么在O(nlogn)O(n\log n)O(nlogn...
2019-02-12 19:10:33
245
原创 bzoj 3992 [SDOI2015]序列统计 NTT
题面题目传送门解法先考虑一个最简单的dp：令f[i][j]f[i][j]f[i][j]表示前iii个数的乘积对mmm取模为jjj的方案数，转移比较简单，在这里就不写了。但是我们会发现，转移的时候是乘法，并没有特别好的优化方式。注意mmm是一个质数，一定存在原根ggg。那么，我们就可以用ggg的若干次方表示出[1,m)[1,m)[1,m)中的所有数。现在我们不妨对原来的状态稍作修改，f...
2019-02-04 08:54:35
180
原创 bzoj 1845 [Cqoi2005] 三角形面积并 扫描线+计算几何
题面题目传送门解法不妨将三角形所有的定点和边上的交点全部单独拎出来，然后考虑横坐标相邻的两个点。假设以这两个点的横坐标分别作一条很长的竖直线，那么必然会和一些三角形形成若干个梯形（三角形也可以作为特殊的梯形）。那么现在考虑如何计算中间的那些面积，假设现在两条直线分别为x=x1x=x_1x=x1和x=x2x=x_2x=x2。由一些几何知识可以知道，梯形的中位线长度等于上底与下底之和的...
2019-01-31 21:48:54
187
原创 bzoj 4821 [Sdoi2017]相关分析 线段树
题面题目传送门解法文化课烂了之后回来写数据结构……首先，我们明显可以将分子和分母分开来算。对于分子，我们可以这样展开：∑(xiyi−xˉyi−yˉxi+xˉyˉ)=∑xiyi−xˉ∑yi\sum(x_iy_i-\bar xy_i-\bar yx_i+\bar x\bar y)=\sum x_iy_i-\bar x\sum y_i∑(xiyi−xˉyi−yˉxi+xˉyˉ)=...
2019-01-27 12:55:38
121
原创 Educational Codeforces Round 56 (Rated for Div. 2)
唠嗑这一场题目基本比较模板，所以就稍微写一下题解吧题解A. Dice Rolling有一个色子，六个面为222到777，每一次给定一个数xxx，问可以掷多少次色子使得最上面的数的和为xxx。解法可以发现，尽量用777就可以了，答案显然为⌈x7⌉\lceil\frac{x}{7}\rceil⌈7x⌉。代码#include &amp;lt;bits/stdc++.h&amp;gt;using na...
2018-12-20 11:37:11
196
原创 bzoj 4916 神犇和蒟蒻 杜教筛
题面题目传送门解法杜教筛的模板题首先可以发现，∑i=1nμ(i2)\sum_{i=1}^n\mu(i^2)∑i=1nμ(i2)一定等于1，因为除了i=1i=1i=1的时候μ(i2)=1\mu(i^2)=1μ(i2)=1，其他时候μ(i2)=0\mu(i^2)=0μ(i2)=0。然后考虑怎么求∑i=1nφ(i2)\sum_{i=1}^n\varphi(i^2)∑i=1nφ(i2)，显...
2018-12-02 09:40:56
200
原创 bzoj 4659 Lcm 莫比乌斯反演
题面题目传送门解法还是写得详细一点比较好我们可以比较显然地得出式子：∑i=1n∑j=1nμ(gcd(i,j))2lcm(i,j)\sum_{i=1}^n\sum_{j=1}^n\mu(gcd(i,j))^2lcm(i,j)∑i=1n∑j=1nμ(gcd(i,j))2lcm(i,j)然后下面就是推导过程了：=∑d=1nμ(d)2d∑i=1⌊nd⌋∑j=1⌊nd⌋[gcd(i,j)=...
2018-11-28 22:14:46
194
原创 bzoj 3994 [SDOI2015]约数个数和 莫比乌斯反演
题面题目传送门解法其实很久之前就想写这道题了……首先我们先考虑一下d(ij)d(ij)d(ij)怎么处理。有一个结论：d(ij)=∑x∣i∑y∣j[gcd(x,y)==1]d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]d(ij)=∑x∣i∑y∣j[gcd(x,y)==1]，具体证明可以看这里然后我们就可以把式子写成这样：∑i=1n∑j=1m∑x∣i...
2018-11-25 17:09:32
118
原创 bzoj 3529 [Sdoi2014]数表 莫比乌斯反演+树状数组+离线处理
题面题目传送门解法显然，对于每一个格子(i,j)(i,j)(i,j)，在不管限制的情况下它对答案的贡献为σ(gcd(i,j))\sigma(gcd(i,j))σ(gcd(i,j))（σ(i)\sigma(i)σ(i)表示iii的约数和）。那么我们不妨考虑每一个d=gcd(i,j)d=gcd(i,j)d=gcd(i,j)对整个答案的贡献，应该是σ(d)∑i=1n∑j=1m[gcd(i,j)...
2018-11-25 09:23:21
501
原创 bzoj 1396 识别子串 & bzoj2865 字符串识别 后缀数组+线段树
题面题目传送门双倍经验传送门解法解法全靠yy……显然我们可以先构造出后缀数组。我们令len[i]=max(height[rnk[i]],height[rnk[i]+1])len[i]=max(height[rnk[i]],height[rnk[i]+1])len[i]=max(height[rnk[i]],height[rnk[i]+1])，表示从iii开始长度超过len[i]len[...
2018-11-21 21:25:37
284
原创 bzoj 2754 [SCOI2012]喵星球上的点名 后缀数组+莫队
题面题目传送门解法之前曾尝试用AC自动机暴力水过去，然而T了……AC自动机显然是可以实现的，但是因为字符集太大，所以会导致超时。那么我们考虑后缀数组解决。首先我们可以将所有串整个拼成一个新的字符串。名和姓之间用一种分隔符隔开，不同的字符串之间用另一种分隔符隔开。然后构造出后缀数组。考虑如何求解第一问，显然可以在后缀数组中找到以当前字符串开头的后缀的位置，然后上下二分一下对应的区间[l...
2018-11-18 13:51:13
420
1
原创 bzoj 3473 字符串&bzoj 3277 串 后缀数组
题面题目传送门双倍经验传送门解法我还是太菜了……3277总时限10s，然而T了……首先显然是把这些串拼起来中间用分隔符隔开，然后构造出后缀数组。然后我们枚举子串的开头部分。可以发现，最大能贡献到答案中的长度是满足单调性的，所以我们可以考虑二分这个长度，假设为lenlenlen。那么我们就可以求出这个后缀所在的最长的区间使得这个区间中后缀两两的lcplcplcp不小于lenlenle...
2018-11-17 21:35:55
158
原创 bzoj 3238 [Ahoi2013]差异 后缀数组+单调栈
题面题目传送门解法重新开始学习后缀数组的第一道题……显然，我们只要考虑怎么求∑i∑jlcp(i,j)\sum_i\sum_j lcp(i,j)∑i∑jlcp(i,j)。
2018-11-17 15:58:50
131
原创 bzoj 4653 [Noi2016]区间 线段树
题面题目传送门解法显然，我们只要选出若干个区间，使得某一个位置被至少覆盖了mmm次就可以了考虑将这nnn个区间按照长度从大到小排序，在选择区间的时候显然是选择连续的一段，即使中间某一个区间可能并没有什么用处，但是至少不会使答案变得更劣。那么我们枚举最左边选取的是哪一个区间，然后扫到下一个正好使得所有数出现次数最多的那个出现了不少于mmm次，然后更新答案。类似于two-pointers...
2018-11-07 22:05:24
110
原创 bzoj 2678 [Usaco2012 Open]Bookshelf dp+multiset
题面题目传送门解法显然有一个O(n2)O(n^2)O(n2)的dp：f[i]=min(f[j]+max(h[j+1],…,h[i]))&amp;amp;nbsp;(s[i]−s[j]≤L)f[i] =min(f[j]+max(h[j+1],\dots,h[i]))\ (s[i]-s[j]\leq L)f[i]=min(f[j]+max(h[j+1],…,h[i]))&amp;amp;nbsp;(s[i]−s[j]≤L)。...
2018-11-07 16:06:46
178
原创 bzoj 4777 [Usaco2017 Open]Switch Grass 线段树+multiset
题面题目传送门解法因为我比较菜，离线的做法并不会……显然我们可以发现一个性质：不同颜色的最短距离一定是某一条边。然后我们可以发现，这些答案边一定在最小生成树上，且任意一棵最小生成树都满足。考虑这个为什么是正确的。假设存在一条不在最小生成树上的边(x,y,v)(x,y,v)(x,y,v)满足答案要求，那么同时也一定会与一条xxx到yyy且总长度不超过vvv的路径上存在某一条边满足条件，...
2018-11-06 22:13:01
166
原创 bzoj 2506 calc 离线处理+权值分块
题面题目传送门解法叫权值分块感觉挺诡异的……我们不妨离线处理询问，对于一个询问可以变成求解[1,r][1,r][1,r]中满足条件的个数-[1,l−1][1,l-1][1,l−1]中满足条件的个数。由于权值到10410^4104，无法直接暴力实现。那么我们考虑将这些数分成2部分来实现。对于不超过100100100的模数ppp，记f[i][j]f[i][j]f[i][j]表示当前做到的数...
2018-11-01 22:46:27
149
原创 Educational Codeforces Round 53 (Rated for Div. 2)
比赛链接Educational Codeforces Round 53 (Rated for Div. 2)A. Diverse Substring题面给定一个字符串SSS，求出一个子串满足子串中出现的所有字母出现次数不超过这个子串长度的一半(下取整)，如果不存在输出NO。解法显然，只要不是所有字符都相同，那么这个串一定存在这样的子串。我们只要找到一个长度为2且两个字符不相同的子串就...
2018-10-27 21:15:19
141
原创 bzoj 3697 采药人的路径 点分治
题面题目传送门双倍经验传送门解法这道题的点分治依然比较基础将黑色的边变成1，白色的边变成-1，这样比较容易判定。因为要满足路径中间存在一个点使得这个点可以将这条路径分成两段且长度为0，所以这样就变得不是特别容易处理。考虑在枚举分治重心的时候，已经处理完了前面的子树，假设对于当前的子树中的一点xxx，当前的深度为ddd，那么前面的子树中一定要有一个深度为−d-d−d的点，假设为yyy...
2018-10-20 20:16:44
121
原创 bzoj 2653 middle 二分答案+主席树
题面题目传送门解法其实这道题严格上说并不是主席树，而是可持久化线段树。显然答案满足单调性，假设我们当前二分到的是midmidmid，那么对应的中位数即为a[mid]a[mid]a[mid](a[mid]a[mid]a[mid]表示从小到大排完序之后的第midmidmid小，不是这个序列中的数显然可以不用考虑)。然后将小于它的数变成-1，其他数变成1。然后对于[a,b],[c,d][a,b...
2018-10-18 21:33:37
150
原创 [2018.10.17校内训练] 小报告 KMP+主席树
题面给定一个长度为nnn的序列和一个长度为mmm的序列，问长度为nnn的序列中有多少个长度为mmm的子串离散化后的结果恰好为原先给的长度为mmm的序列，并求出出现的位置。n,m≤105n,m≤10^5n,m≤105解法表示这道题yy了很久……KMP可以和主席树放在一起考察比较诡异……看到要求出现的位置，第一感应该是字符串哈希或者是KMP。但是发现字符串哈希并不是特别好写，所以就考虑如何...
2018-10-17 21:08:00
161
原创 bzoj 1539 [POI2005]Dwu-Double-row 建图+思路
题面题目传送门解法思路还是比较精妙的我们不妨假设a[i]a[i]a[i]表示iii这一列是否交换两行的数然后对于一个数xxx，假设它出现的位置分别为第iii列和第jjj列，如果这两个位置在同一行，那么i,ji,ji,j之间连接一条为111的无向边，表示a[i]≠a[j]a[i]≠a[j]a[i]̸=a[j]，否则在i,ji,ji,j之间连接一条为000的无向边，表示a[i]=a[j]...
2018-10-10 21:39:14
173
原创 bzoj 1535 [POI2005]Sza-Template KMP
题面题目传送门解法花了好久终于把这道题弄懂了……可以发现，满足性质的字符串一定同时是整个串的前缀和后缀首先考虑这样一个时间复杂度为O(n2)O(n^2)O(n2)的做法：对原串进行KMP求出nxtnxtnxt数组，那么我们就可以一个一个枚举同时为前缀和后缀的字符串考虑如何检验答案的合法性，找出该字符串在原串中出现的位置(这里指匹配到的最后一位)，将这些位置标记一下。如果相邻标记点的...
2018-10-02 20:58:03
316
原创 LOJ 2318 「NOIP2017」宝藏
题面题目传送门解法为什么我的状压dp那么丑啊……发现n≤12n≤12n≤12，所以不妨考虑状压dp设f[d][S][rt]f[d][S][rt]f[d][S][rt]表示当前深度为ddd，在根为rtrtrt的子树中有SSS集合内的点的最小代价考虑先枚举rtrtrt的一个儿子是什么，假设为xxx，然后枚举集合S′⊂SS&#x27;\subset SS′⊂S作为xxx的子树部分，...
2018-09-29 20:19:32
254
原创 LOJ 2319「NOIP2017」列队 线段树
题面题目传送门解法想了好久才把这道题真正弄懂……可能还是我太菜了这道题做法比较多，这里讲一个线段树的做法考虑建出n+1n+1n+1棵线段树，前nnn棵线段树维护每一行的情况，最后一棵线段树维护最后一列的情况显然这些线段树一定要动态开点，否则空间肯定爆炸先口胡一下如何处理离队事件，假设在(x,y)(x,y)(x,y)的同学离队：如果y=my=my=m，即这个同学在最后一列，显然只...
2018-09-26 20:50:59
130
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人