Devil_Gary-CSDN博客

原创搬家啦~~

新博客地址:http://www.cnblogs.com/devil-gary/

2018-04-19 19:52:02 300

原创 BZOJ5217: [Lydsy2017省队十连测]航海舰队

被FFT的空间卡了半天后来发现根本不用开那么大…首先可以把包含舰艇的那个小矩形找出来将它一行一行连接成一个串T 其中舰艇位置为1其他位置为0 将大矩形也连成串S 其中礁石为1其他为0 两个串匹配起来如果某一位两个串是1和1 则礁石与舰艇会在同一位置不可能到达那么这个匹配所对应的图中的位置就不成立因为要确定每个位置可以想到将T翻转后做FFT后每一位(每一位代表了一个小矩形的匹配情况...

2018-03-30 08:25:20 610

原创 BZOJ3473 字符串广义后缀自动机

今天主攻了下SAM 好多东西以前都没理解到对于这道题我们建一个自动机存所有串每个穿last从1开始对于自动机上每个点额外记一个cnt 表示能匹配到这个点的不同串个数建完对每个串在自动机上匹配把到的每个点x和par[x],par[par[x]]…的cnt++ 然后就从父亲往儿子传递一下这样每个点i就存了所有≤" role="presentation" style

2018-02-07 17:01:57 408

原创 BZOJ2716 KD-Tree

好久没写博客了回去赶了好久文化课颓欲见长突然翻到fc爷的KD-Tree板子来切了到裸题对于一开始的数据我们可以先预处理具体的排序方式见板子其实就是我们对每次选定的一块选一个维度来排序啦这里算了下方差选最大的那一维来分下去 #include#define bug(x) cout#define ll long long/*char *TT,*mo,but[(115)+

2018-02-06 09:17:09 684

原创 BZOJ5137[Usaco2017 Dec]Standing Out from the Herd

看了半天题不知道怎么用SAM维护于是借（chao）鉴（xi）的一发神犇的只要判断这个子串之前被标记的记号（也就是他属于第几个串）和这次转移到的是否相同如果不同就说明该子串属于多个串直接标记-1 依次转移就好咧最后统计就是ans[f[i]]+=sam[i].mx−sam[par[i]].mx;f[i]ans[f[i]]+=sam[i].mx-sam[par[i]].mx; f[i]就是

2018-01-12 18:18:40 502

原创非旋Treap 学习笔记

今天学习了一下非旋TreapTreap 听说效率很高而且可持久化(一脸懵逼QAQQAQ) 非旋Treap主要是两个操作splitsplit和mergemerge 下面简单描述一下(得先会TreapTreap啊 ) valval:点的值 keykey:randrand的值 splitsplit : 就是我们把原TreapTreap拆成两个TreapTreap x,y x,y 比如以valu

2018-01-10 15:32:16 379

原创 BZOJ3598[Scoi2014]方伯伯的商场之旅数位DP

看到数据范围很容易想到数位DPDP 然后就很容易想到枚举每一位作为最优点我们可以发现对于一个数字如果他的最优点确定了那离最优点花费越高我们可以先将所有的数字全合并到第一个点(用数位DP求) 然后依次枚举从i−>i+1i->i+1 更优的数字有多少个在这里我们只需要求出他对答案的贡献即可从i−>i+1i->i+1 前ii位都要多走一次（加上）后面都要少走一次（减去）我

2018-01-06 16:57:12 357

原创 BZOJ1025 [SCOI2009]游戏 DP

题意可以理解为给定N 将其拆为pα11∗pα22∗pα33⋅⋅⋅pαmmp_1^{α_1}*p_2^{α_2}*p_3^{α_3}···p_m^{α_m}的形式其中pp为素数且 ∑pαii≤n\sum p_i^{α_i}\leq n 求lcm(pα11∗pα22∗pα33⋅⋅⋅pαmm)的不同个数lcm(p_1^{α_1}*p_2^{α_2}*p_3^{α_3}···p_m^{α_m})的不同个

2018-01-03 15:58:04 299

原创 BZOJ4566 [Haoi2016]找相同字符 SAM+拓扑

学了几天SAMSAM学了这道题总算是领会到了些许对parentparent树有了更深的理解但是我还是不能表述出来太菜了大家可以去百度CLJ神犇的PPT 讲的很好附一个百度文库的网址我们可以先跑出两个串的SAMSAM 对于每一个节点记录到达此节点的串的数目这时候要用到拓扑因为对于一个节点ii 如果有两个串能在i匹配则他一定能下parent[i]parent[i] 匹配所以到拓扑将每

2017-12-25 20:17:50 771

原创 BZOJ1823: [JSOI2010]满汉全席 2-sat

裸的2-sat 选（hi,mj）（hi,mj）的话就连(i′,j)(j′,i)(i',j )( j',i) 特别的（hi,mi）（hi,mi）不用连最近集训被吊打啊好蒻打算扎实学习一阵总觉得在知识和实践之间有着一道无法跨越的鸿沟#include<bits/stdc++.h>#define bug(x) cout<<(#x)<<" "<<(x)<<endl#define cl(x) me

2017-12-22 20:20:40 531

原创 BZOJ3505 [Cqoi2014]数三角形数学

总数是ans=C3n∗m−m∗C3n−n∗C3m−斜着的总数ans=C_{n*m}^3-m*C_n^3-n*C_m^3-斜着的总数斜着的可以用gcd枚举对于一个长i宽j的矩形计算出他的对角线有s个整数点则该对角线的贡献是s-2 再计算出只总有多少的这么大的矩形求和就好啦#define bug(x) cout<<(#x)<<" "<<(x)<<endl#define ll long l

2017-12-13 16:01:20 570

原创 BZOJ2820 YY的GCD 莫比乌斯反演

∑isprime(p)∑na=1∑mb=1gcd(a,b)==p∑isprime(p)∑_{a=1}^n∑_{b=1}^mgcd(a,b)==p ∑isprime(p)∑⌊np⌋a=1∑⌊mp⌋b=1gcd(a,b)==1∑isprime(p)\sum_{a=1}^{⌊\frac n p⌋}∑_{b=1}^{⌊\frac m p⌋}gcd(a,b)==1 ∑isprime(p)∑⌊np⌋a=1∑

2017-12-13 15:08:04 317

原创 BZOJ3237: [Ahoi2013]连通图 cdq分治+并查集

首先连通图问题用并查集维护很显然看到k的范围铁铁的nlognnlogn 因为是离线询问我们很容易就能想到用cdq分治来维护并查集对于两个集合s1,s2s1,s2 我们可以把不属于s1,s2s1,s2的边都先存到并查集里将s1s1中不属于s2s2的边加进去这时候就可以判断s2s2这个集合是否满足了之后我们将之前加进去的边删掉再加入s2s2中不属于s1s1的就又可以做s1s1啦

2017-12-06 11:27:59 609

原创 BZOJ1978 [BeiJing2010]取数游戏建图+拓扑序

很容易想到在可以满足L≤gcd(i,j)L\leq gcd(i,j)的i,ji,j之间连边但是暴力n2n^2枚举肯定过不了啦考虑枚举每一个大于L的公因数我们对于每个数根号n枚举他的因子对每一个因子建一个vectorvector来存然后每一个vectorvector里的i和i+1连边 yy一下这样连就保证了L≤gcd(i,j)L\leq gcd(i,j)的点(i,j)(i,j)可以到达通过

2017-12-05 18:07:37 496

原创 BZOJ2750[HAOI2012]Road 最短路

想了半天只知道对于每个边求起点到他的方案数*他到终点的方案数不知道怎么枚举起点终点搜了搜题解涨了些姿势原来Dij可以在求出单元最短路的同时将每个点到源点的距离排序这样的话我们就可以枚举起点按照Dij得到的距离顺序进行转移具体的看代码吧有点困写不动了代码来自Bloodline#include<bits/stdc++.h>#define rep(i,l,r) for(int i=

2017-12-05 10:26:35 532

原创 BZOJ3944 Sum 杜教筛

看完题一副不可做的样子默默点开了题解发现是杜教筛就花了半天学习了一下先说下杜教筛可以在优于线性的复杂度内求出积性函数的前缀和下求∑ni=1f(i)\sum_{i=1}^nf(i) 令F(i)=∑ni=1f(i)F(i)=\sum_{i=1}^nf(i)我们可以再引入一个积性函数g(i)g(i) 则∑ni=1f(i)∗g(i)=∑ni=1∑d|if(d)∗g(id)=∑ni=1∑⌊

2017-12-02 16:40:48 615

原创 BZOJ3190[JLOI2013]赛车半平面交

看了黄学长的每辆车可以表示成一个一次函数y=kx+by=kx+b, 按kk为第一关键字，bb为第二关键字排序，然后维护一个单调栈就好了，具体的judgejudge函数看代码#include<bits/stdc++.h>#define bug(x) cout<<(#x)<<" "<<(x)<<endl#define ll long long#define eps 1e-7using name

2017-11-30 09:31:12 564

原创 BZOJ5100[POI2018]Plan metra 构造

首先可以发现在11到nn的链上的点的d1+d2d1+d2是最小的这样我们可以求出11到nn的链对于其他的点他一定与这条链的上点链接可以发现对于点ii 和11到nn上的点j 有d1[i]−d2[i]=d1[j]−d2[j]d1[i]-d2[i]=d1[j]-d2[j] 因此可以求出每个点连向谁如果没有11到nn上符合差值相等的点就不存在解我一开始用map+sort 无线TLE+RE#

2017-11-29 11:00:32 612

原创 BZOJ1880[Sdoi2009]Elaxia的路线 spfa+拓扑序

首先我们求出来每一个点到x1,x2,y1,y1x1,x2,y1,y1的最短路令s1,s2s1,s2分别为两个人的最短路枚举每条边如果dis[x1][u]+dis[y1][v]+e[i].c=s1,dis[x2][u]+dis[y2][v]+e[i].c=s2dis[x1][u]+dis[y1][v]+e[i].c=s1,dis[x2][u]+dis[y2][v]+e[i].c=s2 则在

2017-11-28 10:26:10 521

原创 BZOJ1924 tarjan+拓扑序

先按题目要求连边缩点之后建反向图按拓扑序转移 sum[u]=max{sum[v]+sz[u]};sum[u]=max\{sum[v]+sz[u]\}; ans=max{sum[i]}(i∈[1,n]);ans=max\{sum[i]\} (i∈[1,n]);#include<bits/stdc++.h>#define bug(x) cout<<(#x)<<" "<<(x)<<endl#de

2017-11-28 09:24:15 556

原创 BZOJ3594 树状数组优化DP

可以发现每一次区间加都要从[i,n]这样才能让最优可以发现每一次区间加都要从[i,n] 这样才能让最优直接上转移方程 f[i][j]表示用了i次区间加操作最高为j所能取得的最大值f[i][j]表示用了i次区间加操作最高为j所能取得的最大值 f[i][j]=maxf[k][l]|k<i,l<=j,a[k]+l<=a[i]+j+1f[i][j]=max{f[k][l]|k<i,l<=j,a[k

2017-11-24 17:46:23 547

原创 BZOJ2588 主席树

几乎没怎么写过主席树今天看着hzwer的写了写各种RE 对于询问(u,v,k)对于询问(u,v,k) a=u,b=v,c=LCA(u,v),d=father(lca)a=u,b=v,c=LCA(u,v),d=father(lca) 在主席树上二分s=sum[ls[a]]+sum[ls[b]]−sum[ls[c]]−sum[ls[d]]; s=sum[ls[a]]+sum[ls[b]]-s

2017-11-24 17:41:30 583

原创 NOIP2017D2T2 宝藏

考试的时候yy了一发可以枚举层数然后枚举当前层选那些但是我不会枚举一个状态补集的子集于是就GG了昨天看了CQzhangyu的博客发现原来lowbit可以实现我才想到lowbit就是找了的从右至左的第一个1的位置茅塞顿开对于当前状态f[i][s]第i层已经选了s枚举他的补集的子集p,则f[i+1][s|p]=min(f[i+1][s|p],f[i][s]+cost[p])对于当前状态

2017-11-23 09:31:09 618

原创 BZOJ2748 DP

noip完了有些差啊想了想之前好多题都是直接粘的代码跟没做一样所以以后的题都自己做吧这个DP f[i][j]f[i][j]表示第i次乐曲能不能调到j的音量转移 f[0][beginLevel]=1,f[i][j]=max(f[i−1][j−a[i]],f[i−1][j+a[i]]);f[0][beginLevel]=1 ,f[i][j]=max(f[i-1][j-a[i]],f[i

2017-11-23 09:17:55 475

原创 NOIP2017 游记

看各位大佬都写了跟着凑个热闹考得好差啊这会都不能接受（怎么对得起我逃过的几百节课??）虽然陕西是弱省但是还是虚虚的 day1 上场旁边坐着为不是很强的学校的oier 好像压力不是很大发题之后没有浏览全部题目直接应怼t1（好吧是因为t1题意太好懂了）看了将近半小时啊我内心可是快崩溃了什么exgcd（感觉会的数学知识已经用尽了）毫无希望 8:34 暴力的几个手造数据

2017-11-12 21:23:43 737 1

原创洛谷1037 NOIP2009 最优贸易

好吧我太zz了居然花了3个小时还是找了一组大数据测的 wa无数次有一个很简单的思路就是正反跑2遍spfa存最大值和最小值每个点做差取max 这个想法好像比较（特别）好想也很好实现可是我这个蒟蒻先写了个tarjan 然后就一直顺着这个思路陷入深坑不过跑完灰常快（O(∩_∩)O哈哈~）我的思路是先缩点然后建反向边跑一边看那些点是可以到的然后正向建边dfs 当然得剪枝啦我这里t了

2017-11-08 16:53:51 487

原创 Tarjan求无向图桥和割点

突然发现这个知识点不太清楚了搜了一个学一学最近各种被题虐可能得多反思反思感觉一直没有进步#include<iostream>using namespace std;#include<cstdio>#include<cstring>#include<vector>#define N 201vector<int>G[N];int n,m,low[N],dfn[N];bool

2017-11-03 10:08:25 597

给定一个长度为n的01序列以及L个整数a[i]a[i]。每次可以选择连续的长度为a[i]a[i]的一段取反，给出末状态。求最少操作的次数。首先，这类选择一段区间操作的题可以把序列差分。于是我们把给出的末状态差分，然后考虑把每次操作也差分，于是每次操作就是选择两个位置差为a[i]a[i]的数对取反。然后我们对所有的a[i]a[i]跑一遍背包（即取正也取负），这样就得到了把任意位置差的两个点取反的最小代

2017-11-03 08:53:46 715

原创 BZOJ4173 数学

好有趣 Orz PoPoQQQn%k+m%k≥k≡⌊n+mk⌋−⌊nk⌋−⌊mk⌋=1∑(n%k+m%k≥k)φ(k)=∑n+mk=1φ(k)∗⌊n+mk⌋−∑nk=1φ(k)∗⌊nk⌋−∑mk=1φ(k)∗⌊mk⌋∑ni=1i=∑ni=1∑k|iφ(k)=∑nk=1φ(k)∗⌊nk⌋φ(n)∗φ(m)∗(∑n+mi=1i−∑ni=1i−∑mi=1i)=φ(n)∗φ(m)∗n∗mn\%k+m\%k

2017-10-31 15:26:02 560

原创 BZOJ4999 树剖+动态开点

表示只会树剖对于每个新点动态开线段树就好了 #include<bits/stdc++.h>#define N 100010#define lson l , mid , ls[x]#define rson mid + 1 , r , rs[x]using namespace std;map<int , int> mp;int a[N] , head[N] , to[N << 1] ,

2017-10-31 13:56:10 576

原创 LOJ6226 网络流24题骑士

这题就是跑个二分图或者最小割 ans=n*n-m-最小割可以黑白染色很好想到上代码#include<bits/stdc++.h>#define inf (~0u>>2)#define cal(i,j) (i-1)*(n)+jusing namespace std;const int N=2e5+5;const int M=2e2+5; int n,m,ans,s,t,cnt,t

2017-10-30 20:12:58 558

原创 LOJ6005 网络流24题

再来一道短短的 #include<bits/stdc++.h>#define inf ~0u>>2using namespace std;const int N=1e3+5;int n,ans,ans2,ans3,s,t,tot=1;int head[N],dis[N],cur[N],a[N],f[N];struct Egde{ int v,nxt,w;}e[N*2];q

2017-10-30 20:11:21 580

原创 LOJ6004 网络流24题

听zjq大爷说noip要考网络流吓得切了几道都是很裸的虽然跑的慢但是挺短的 using namespace std;const int N=205;int n,m,sum,le;int mp[N][N],fr[N],vis[N],in[N],fa[N];vector <int > path[N];int get(int x) { return x==fa[x]?x:fa

2017-10-30 20:10:19 590

原创 BZOJ4580 DP

好神奇的DP 题意给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个，问最大能合出多少设f[i][x]表示由i结尾合成2^x 的开头在哪里转移很好想#include<bits/stdc++.h>#define N 300010 using namespace std; int n,ans,f[N][61]; inline int read(){ int x=

2017-10-26 15:46:26 558

原创 BZOJ3503

很裸的高斯消元解异或方程学了高斯消元之后一直没用过这次算复习了一下对于 (i,j) 有(i,j)^(i-1,j)^(i+1,j)^(i,j-1)^(i,j+1)=0 总共 nm个式子高斯消元解出来就好因为不能全是零所以自由元直接赋值1#include<bits/stdc++.h>using namespace std;const int N=100000+5;int n,m,c

2017-10-26 15:19:22 2553

原创 BZOJ2789 逆序对

每个字母在的最终位置都是确定的求得它以后就是很简（e）单（xin）的求逆序对的个数了感觉理解深了很多#include<bits/stdc++.h>#define N 1000010using namespace std;char s[N];int tot[27],tot2[27];int a[N],b[N],c[N];int n;void change(int x,int v){

2017-10-24 17:03:48 576

转载 BZOJ1700 DP

好几天没写一直頽看到这道题的DP很经典状态函数f[i][j]=解答前i个problem且最后一次连续进行j个problem的解答所需要的最小月数状态转移方程：　　1.在前i~j件事情付清尾款当月付j个项目的首款：d[i][j]=min{d[i-j][x]+1 | sumb[j-1-x+1][j-1]+suma[j][i]<=pay} 　　2.在前i~j件事情付清尾款后的一个月付j

2017-10-24 08:51:10 460

原创 BZOJ4592 线段树

这个题有毒我调了3个小时各种奇葩错（还是我太菜了）这题就线段树维护一个区间1的个数 0的个数左端最长连续0 右端最长连续0 区间内最长连续0 转移的思路还是很好想的对于那个补脑洞的操作（明明脑洞越来越多）二分一下再区间修改还是得多码（我学了假的线段树常数大到离谱）#include<bits/stdc++.h>using namespace std;const int

2017-10-21 09:52:38 523

原创 BZOJ1076 状压+期望

又来一道期望我又一次没看数据范围怎么想都觉得不可做啊结果n<=15（沃尼玛）言归正传这题有很多无效状态所以我们考虑倒着做这样就可以保证从有效状态转移到有效状态 f[i][p]表示第i轮取到p这个状态期望得分转移见代码 #include<bits/stdc++.h>using namespace std;double f[101][65536];int N,K;int v

2017-10-20 15:27:02 541

原创 BZOJ3036 期望DP

我期望一直渣的不行这道题怕是太水了一开始想着拓扑序一下然后倒着转移然后发现直接dfs就是了直接看代码很好懂 #include<bits/stdc++.h>using namespace std;const int N=1e5+5;int n,m,tot=1,out[N],head[N];double dis[N];bool vis[N];struct Edge{ i

2017-10-20 14:50:46 453

空空如也

空空如也