- 博客(101)
- 收藏
- 关注
RSS订阅
原创 模板和学习笔记
-----------------------------------点分治一般步骤：1.找到树的重心（避免当树退化成链时复杂度升高）2.从重心出发分治统计路径分治过程：统计当前节点子树中的符合条件的路径数加到ans中标记当前点避免重复减去当前节点子树节点中的符合条件的路径数（这样剩下的就是经过当前节点的路径数，不会重复了）在当前节点的子树中分别找到重心继续分治解决bzoj1468#include
2017-07-10 17:37:49
1165
原创 BZOJ 4504:K个串 [主席树][贪心]
题意给出一个长度为nn的数列an{a_n},一个区间[l,r][l,r]的和定义为其中的数字之和,相同的数字不重复算求第k大的和题解首先怎么求一个区间的和.对于aia_i维护它之前最近的与它相同的数的位置pre[ai]pre[a_i]对于固定的右端点维护每一个左端点到它的和,可以用线段树则从左往右扫描对于右端点ara_r只要把pre[ar]+1pre[a_r]+1到rr
2018-01-15 18:01:47
254
原创 Codeforces 600E. Lomsat gelral [dsu on tree]
题解传送门新姿势dsu on tree 模板题#include#include#include#define N 100005#define LL long longusing namespace std;vectorint>e[N];int n,c[N],sz[N],son[N],num[N],mx;LL ans[N],sum;bool vis[N];inli
2018-01-15 17:59:35
282
原创 HDU 4787 GRE Words Revenge [二进制分组][AC自动机]
题意维护支持插入和询问的AC自动机,强制在线题解二进制分组(可以百度xhr的答辩论文)对于每一个分组单独建立AC自动机,合并分组时暴力重构还有一个细节是对于重串,要直接踢掉,可以用set或者hash判一下因为一样的串在不同的AC自动机里出现还是当一次算代码又慢又长…大概是string的读入拖慢速度,用时倒数…//按我的打法原本AC自动机的初始状态各个用来模拟指针
2018-01-15 07:30:37
229
原创 洛谷 P3796 【模板】AC自动机（加强版）
题面传送门题解随便统计一下每个单词出现的次数详见代码#include#include#include#include#includeusing namespace std;int n,size,pos[155];struct node{ int fail,lk[26],sum; bool mark;}ac[11000];char s[155]
2018-01-15 07:28:48
318
原创 BZOJ 3932: [CQOI2015]任务查询系统 [主席树]
题意给出nn个由三元组(si,ei,pi)(s_i,e_i,p_i)表示的区间,si,eis_i,e_i表示头尾(包括头尾),pip_i表示这个区间的权重给出mm个询问,询问包含位置xx的按权重排序前kk小的区间的权重和输入先给出所有三元组,询问强制在线题解主席树的权值线段树按照pip_i来搞,因为值域比较大,要离散一下所有三元组先读入,拆成两个端点每个端点维护两个
2018-01-11 14:46:19
200
原创 BZOJ 4140: 共点圆加强版 [二进制分组][凸包]
题意支持在平面直角坐标系内进行操作:1.加入一个圆心在(x,y)(x,y)且过原点的圆2.询问点(x,y)(x,y)是否被之前加入的所有圆包含(在圆内或圆心上)强制在线题解询问即判断(X−xi)2+(Y−yi)2≤x2i+y2i(X-x_i)^2+(Y-y_i)^2\leq {x_i^2}+{y_i^2}是否成立整理一下式子,得−X/Y∗xi+(X2+Y2)/(2∗
2018-01-11 10:00:39
463
原创 BZOJ 3527: [Zjoi2014]力 [卷积][FFT]
题意即求Ei=∑i−1j=1(qj/(j−i)2)−∑nj=i+1(qj/(j−i)2)E_i=\sum_{j=1}^{i-1}(q_j/(j-i)^2)-\sum_{j=i+1}^{n}(q_j/(j-i)^2)题解令f(x)=qx ,g(x)=1/x2f(x)=q_x\ ,g(x)=1/x^2则Ei=∑i−1j=1f(j)g(j−i)−∑nj=i+1f(j)g(j−i)E_
2018-01-11 09:59:33
310
原创 洛谷 P3803 【模板】多项式乘法（FFT）
题面题解fft模板题单向膜拜:从多项式乘法到快速傅里叶变换FFT 学习笔记大致理解为将多项式从系数表示法转化为点值表示法然后再变回系数表示法#include#include#include#define N 2621450#define pi acos(-1.0)using namespace std;int n,m,len,R[N];struc
2018-01-11 09:58:10
483
原创 POJ 2891 Strange Way to Express Integers[中国剩余定理(非互质)][扩展欧几里得]
题意给出n个一元一次同余方程X≡ai(modX≡a_i(mod ri)r_i)求最小的XX,模数不一定互质题解模数非互质不能直接上中国剩余定理任意找两个式子出来:{X≡a1(mod r1)X≡a2(mod r2)\left\{\begin{array}\\X≡a_1(mod \ r_1)\\{X≡a_2(mod\ r_2)}\end{array}\right. 可以
2018-01-11 09:57:06
173
原创 POJ 1006 Biorhythms [中国剩余定理]
题意给出a,b,c,d,求最小的SS满足:S≡a(modS≡a(mod 23)23) S≡b(modS≡b(mod 28)28) S≡c(modS≡c(mod 33)33) 输出S-d题解orz zzk 中国剩余定理直接求这个方程组就好了#include#include#define T 21252using namespace std;int
2018-01-11 09:54:06
170
原创 BZOJ 3196: Tyvj 1730 二逼平衡树 [树套树]
题解不会写,标记一下,抄的是同学的板子#include<cstdio>#include<algorithm>#define N 50010#define M N*30using namespace std;int n,m,sz,ans,a[N],root[M],size[M],fa[M],ch[M][2],v[M];inline char nc(){ static char buf[
2018-01-09 19:01:43
160
原创 codeforces449D&&51nod 1407 与与与与 [dp][容斥原理]
中文题面题解设f[x]f[x]为&x==x的数的个数,g[x]g[x]为x转化为二进制以后1的个数转化一下,求等于0的组数即 所有组合情况-含有位为1的组合数容斥求一下含有位为1的组合数∑x=1220=(−1)g[x]−1∗(2f[x]−1)\sum^{2^{20}}_{x=1}=(-1)^{g[x]-1}*(2^{f[x]}-1)2的幂减一是因为不能一个都不选,
2018-01-09 18:58:07
324
原创 51nod 1406 与查询 [dp]
题面传送门题解一个数&x==x的条件可以理解为转换为二进制后,x为1的位要对应为1设f[x]f[x]为范围内与&x==x的数的个数若yy转换为二进制后的所有1位x都有(yy为xx的子集),则对f[x]f[x]有贡献的数一定对f[y]f[y]有贡献所以可以枚举子集转移,但是这样算会有重复,于是从高位向低位转移,想象一下把xx拆几个1掉就可以变成yy了记得加输入输出优化
2018-01-09 18:56:19
236
原创 51nod 1486 大大走格子[容斥原理]
题面传送门题解好早以前就考过,当时根本不会O(nm)O(nm)的dp很简单,但是不够用啊。考虑通过障碍物转移
2018-01-09 18:54:53
269
原创 cf582B&&51nod 1566 重复的最长不下子序列
题意给出一个长度为n的循环节,问有t个这样循环节的数列的最长不下降子序列题解若要让一个循环节的所有元素都出现则最多要n个循环节,若有相同的应该更少,因为n不大,直接构造长度为n×nn \times n的数列做最长不下降子序列.若剩下还有没用上的,一定是选择出现次数最多的元素插在n×nn \times n的数列中,不到n节的话直接做肯定是不会错的…貌似还有矩阵加速的方法,不太会
2018-01-08 20:39:58
290
原创 BZOJ 1251: 序列终结者 [splay]
题意现在需要你维护一个长度为n的序列,需要支持三种操作:1.区间加 2.区间翻转 3.区间求最大值题解很明显splay裸题,复习了一下splay,感觉忘得一干二净按下标建splay树对于区间加和区间翻转:把l-1 splay到根,把r+1 splay到根的右儿子,然后直接对根的右儿子的左儿子打标记做起来习惯把[0,n+1][0,n+1]转到[1,n+2][1,n
2018-01-08 13:02:44
185
原创 莫队初步
参考blog了解学习了一下莫队,果然是个很好用的东西啊,我为什么现在才学…用途处理一些离线的区间问题一般来说,令ansi,jans_{i,j}表示询问区间[i,j][i,j]的答案,则ansi,jans_{i,j}可以在常数的复杂度内由ansi−1,jans_{i-1,j}或ansi+1,jans_{i+1,j}或ansi,j−1ans_{i,j-1}或ansi,j+1ans_
2018-01-03 21:07:58
166
原创 BZOJ 2124: 等差子序列 [树状数组][hash]
2124: 等差子序列题面传送门题解只要找有没有长度为3的等差子序列是一个排列,用一个辅助数组b[i]=0/1b[i]=0/1记录ii有没有出现过按顺序修改bb,如果数为xx,则查找是否有以xx为等差中项的数对(l,r)(l,r),并且这对数应该是一个出现了另一个没出现(b[l]==1b[l]==1&&b[r]==0 b[r]==0)可以用树状数组或线段树维护bb的hash值,正着一个反着一个,判断
2017-12-25 21:13:37
285
原创 BZOJ 1911: [Apio2010]特别行动队 [斜率优化dp]
1911: [Apio2010]特别行动队题意给出一个常数a,b,c和数列{xnx_n},将其分成若干段每一段至少有一个数,并且每一段将产生一个贡献为a∗x2+b∗x+ca*x^2+b*x+c找到一种分组方案使贡献和最大解题报告前两天写的没来得及写博客现在找不到推式子的草稿纸了…只好再推一遍…斜率优化设置状态fif_i表示分到第ii个数,且以这个数为当前最后一组结尾的最大贡献和转移时若有j<kj<k
2017-12-25 21:08:57
201
原创 BZOJ 1927: [Sdoi2010]星际竞速 [最小费用最大流]
1927: [Sdoi2010]星际竞速题面传送门题解类似DAG上的最小路径覆盖最小费用流,建图 令源点为SS,汇点为TT:S向所有入点连容量为1,费用为0的边S向所有出点连容量为1,费用为aia_i的边所有出点与T连容量为1,费用为0的边对于有边的(ui,vi)(u_i,v_i)其中ui<viu_i<v_i,从uiu_i的入点连向viv_i的出点容量为1,费用为wiw_i的边理解一下:相当于如果要
2017-12-25 21:08:01
165
原创 BZOJ 2150: 部落战争 [二分图匹配][最小路径覆盖]
2150: 部落战争题面传送门题解直接连边然后做最小路径覆盖最小路径覆盖=原图点数-新图最大匹配数#include<cstdio>#include<vector>#include<algorithm>using namespace std;vector<int>e[2500<<2];int n,m,r,c,cnt,mark,vis[51*51],lnk[51*51],map[55][55];
2017-12-25 21:06:35
233
原创 BZOJ 4552: [Tjoi2016&Heoi2016]排序 [二分][线段树]
题意： 给定一个数列{ana_n},然后进行mm次操作,每次操作是对一个区间进行升序或降序排序,要求所有操作后位置qq上的数解题报告： 不会树套树，只能膜线段树题解
2017-12-20 19:56:48
269
原创 BZOJ 3072: [Pa2012]Two Cakes [dp][记忆化搜索]
题意：原题很清楚了.考虑暴力dp dp[p][q]dp[p][q]表示第一只手在p另一只手在q的最短时间 1.若a[p]==b[q] 则dp[p][q]=min(dp[p−1][q],dp[p][q−1])+1dp[p][q]=min(dp[p-1][q],dp[p][q-1])+1 2.若a[p]!=b[q] 则dp[p][q]=min(dp[p−t][q−t])+t−1dp[p][q
2017-12-20 19:38:13
235
原创 BZOJ 2186: [Sdoi2008]沙拉公主的困惑 [欧拉函数][逆元]
题意:给定n,m(n≥m)n,m(n \geq m),求[1,n!][1,n!]和m!m!互质的数的个数
2017-12-19 19:20:07
370
原创 51nod 1204 Parity[并查集]
脑补一个前缀和数组pre 对于给出的[l,r][l,r]的区间和的奇偶性: 若为odd(奇数):转化为pre[r]pre[r]和pre[l−1]pre[l-1]的奇偶性不同 若为even(偶数):转化为pre[r]pre[r]和pre[l−1]pre[l-1]的奇偶性相同 用并查集维护.[1,n][1,n]表示奇偶性相同,[n+1,2∗n][n+1,2 \ast n]表示奇偶性不同#incl
2017-10-26 21:04:40
427
原创 51nod 1461 稳定桌[线段树]
跟风打道题 枚举最长的长度,那么当前的长度全部不砍肯定最优 长度比这个大的一定要砍,可以直接求和 如果数量没到总共的一半,就从比当前长度小的桌腿里砍掉一些来满足题设,可以用线段树维护 (用堆也行,移步jz大佬的博客)#include<cstdio>#include<algorithm>#include<vector>#define N 100000#define LL long lo
2017-10-25 21:06:13
374
原创 51nod 1611 金牌赛事&&cf115E [线段树]
感觉思路很清晰 想到dp,按比赛所需的道路右端点排序 f[i]表示举办第i场比赛为止能获得的最大利润 然后按顺序把每场比赛的收益加入线段树求个最值即可维护最大获利#include<cstdio>#include<algorithm>#define N 200000#define LL long longusing namespace std;struct node{ int l
2017-10-24 21:17:47
406
原创 51nod 1378 夹克老爷的愤怒[贪心][树形dp?]
假如是链上的话就直接贪心搞,每隔2∗k2*k放一个守卫 现在搞到树上 f[i]表示节点i的子树已经全受控制,还可以向上控制f[i]个单位 那么假如当前节点和它的子树节点已经相差为2*k个单位则要加一个家丁 如果当前节点的子树之间可以互相覆盖也是要考虑进去的…假如不能覆盖就要用当前最小的那个了… //感觉叙述不清啊…反正我自己知道怎么做就好了,5个点头盾看题解换10个还是很值的#includ
2017-10-24 21:06:45
301
原创 51nod 1199 Money out of Thin Air[线段树]
题面 把树按dfs序搞成序列然后直接线段树维护就好了#include<cstdio>#include<vector>#define N 50000#define LL long longusing namespace std;vector<int>e[N+5];int n,m,fa[N+5],xl[N+5],size,L[N+5],R[N+5];LL sum[N*4+5],lazy[N
2017-10-24 13:34:12
192
原创 51nod 1122 机器人走方格 V4[矩阵快速幂]
题面 计算到达从某个点到某个点的方案数,考虑构造矩阵:给四个格子编号,构造可达矩阵 然后快速幂计算完把合法的答案累计一下就好了#include<cstdio>#include<cstring>#define N 4#define P 1000000007#define LL long longusing namespace std;const int p[N][N]={ {0,
2017-10-24 13:31:09
229
原创 51nod 1288 汽油补给[贪心][st表][单调栈]
题面 考虑走到第i个城市,接下来,如果在装满油箱的情况下能走到的城市中,有油价比城市i低的城市:就加油到可以到这个城市为止然后过去 否则在当前城市加满油继续 对于油价可以用st表维护最小值 每个城市可以到的城市可以用单调栈预处理出来#include<cstdio>#include<cmath>#define N 100000#define LL long longusing name
2017-10-24 13:27:46
304
原创 51nod 1274 最长递增路径[dp]
题面 题意:给定一张有重边有自环的无向图,求一条最长的路径使路径的权值严格单调递增把边从小到大排序后直接推 注意一下边权相同的就好了#include<cstdio>#include<algorithm>#define N 50000using namespace std;struct edge{ int x,y,z; bool operator < (const edge
2017-10-23 13:56:49
233
原创 51nod 1597 有限背包计数问题[dp][阈值]
居然是读阈(yu第四声)值… 对于大小≤n√\leq \sqrt n的物品做多重背包(前缀和优化O(n)O(n)) 对于大小≥n√\geq \sqrt n的物品完全背包魔改一下:g[i][j]表示用i个物品体积为j的方案数g[i][j]g[i][j]表示用i个物品体积为j的方案数g[i][j] g[i][j]=g[i][j−i]+g[i−1][j−n√−1](前i个物品体积都加1,加入一个体积
2017-10-20 21:06:59
320
原创 BZOJ 1999: [Noip2007]Core树网的核[dfs]
1.对于树中的任意一点，距离其最远的点一定是树的直径的某一端点 2.同一棵树的直径的中点相同(题目里给出来的,虽然不知道怎么用) 3.要求的一定在直径上,并且越长越好(不在直径上的点到端点的距离≥\geq直径上的点到端点的距离,都取较大的那个) 4.任意搞一条直径求出来的偏心距是一样的随意求一条直径,然后抠出来枚举头尾处理一下 当前的这条链到别的点中最长的距离为max(到两端点的距离,到不在
2017-10-20 18:25:42
239
原创 CF 717E[dfs]
题意:给定一棵树,每个节点初始有颜色,共两种颜色.你一开始在点1,走到哪个点就把它的颜色改变.输出一种合法的方案使最终的树颜色都变为11.dfs构造 对每个节点如果当前为-1就从它到父亲节点走一遍 如果当前是root为-1没有父亲就随便找个儿子走一遍再走到那个儿子上(因为是dfs处理它的儿子都已经是1了)#include<cstdio>#define N 200005using namesp
2017-10-20 18:07:35
277
原创 51nod 1494 选举拉票&&cf458C
中文题面 考虑把所有人的票分别从大到小排序之后可以看做n条线段 枚举自己的票数为i,所以每条线段超过i的部分必须收买,如果还不够就到前面挑不够的 0≤b[i]≤1040 \leq b[i] \leq 10^4求前k小想到权值线段树(应该是类似的东西)#include<cstdio>#include<algorithm>#include<vector>#define N 100000
2017-10-18 17:57:16
356
原创 51nod 1624 取余最长路[set]
注意到只有三行,两个拐弯的位置 假设拐弯的位置为x,yx,y 则ans=(sum[3][n]−sum[3][y−1])+(sum[2][y]−sum[2][x−1])+sum[1][x]=(sum[3][n]−sum[3][y−1])+sum[2][y]+(sum[1][x]−sum[2][x−1])ans=(sum[3][n]-sum[3][y-1])+(sum[2][y]-sum[2][x-
2017-10-18 17:41:10
197
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人