zyz_3_14159-CSDN博客

原创 BZOJ1030 AC自动机 + DP

题目大意：给定若干个字符串，问长度为m并且至少包含一个之前给定的字符串的字符串有几种？题目解析：考虑补集，dp[i][j]为当前第i位，停留在第j个tire节点上的数目，转移的话看下一个字符存不存在，不存在就一直找fai节点，注意danger； #include<iostream> #include<cstdio> #include<cstring> #...

2018-11-19 20:19:09 170

原创 BZOJ-4827-FFT

先不考虑+c，那么只需要把原式展开，将a数组扩大一倍，求fft即可。 #include<bits/stdc++.h> #define N 262144 #define pi acos(-1) #define ll long long using namespace std; typedef complex<double> E; int n,m,L; int rev[N]...

2018-09-11 16:05:33 320

原创莫比乌斯&线性筛

最难受的莫过于正式赛因为平常不训练，训练懒就不写博客导致莫比乌斯忘记怎么做了？？？菜是原罪，nothing to say。抢救一波线性筛（有生之年还能用上吗）： const int MAX = 1e6+10; const ll mod = 1e9+7; ll mob[MAX],d[MAX],facnum[MAX],sum[MAX],p[MAX],f[MAX]; bool noprime[

2017-12-04 23:56:01 309

原创 codeforces-375D-树上莫队

题目大意：给定一棵有根树，每次询问一个节点的子树中颜色数大于等于k的颜色总数；题目解析：搞出dfs序，其实就变成序列了，莫队也很好写，开个cnt数组记录颜色种数，再开个least数组记录至少i个的颜色个数； AC代码： #include #include #include #include #include #include using namespace std; const int

2017-11-17 00:45:02 273

原创 SPOJ-ZQUERY-分块求区间内和为0的最大长度

题目大意：给定一段只包含-1，1的序列，每次询问区间内满足区间和为0的最长子区间长度；题目解析：分块真的是个很神奇的东西。朴素做法是每次询问搞出前缀和，然后二分，复杂度为M*N*logn，考虑分块的做法，其实就是预处理出每个块的答案，然后询问的时候只需要考虑不在最大块里面的元素即可，总时间复杂度降为M*N^0.5*logn； AC代码： #include using namespace s

2017-11-16 13:38:01 969

原创 LightOJ-1399-线段树求区间相同颜色连续的最大长度

题目大意:区间相同颜色连续的最大长度题目解析：线段树节点保存左右端点颜色，从左右开始的最大长度和答案，pushup和query的时候考虑左儿子右端点和右儿左端点的颜色是否一样需要特判； AC代码： #include #include #include #include #include #define lson rt<<1 #define rson rt<<1|1 using namesp

2017-11-15 23:54:55 361

原创 HDU-2896-AC自动机

题目大意：很裸的AC自动机，就是要按照模式串的先后顺序输出；题目解析：只需要在tire树上每个节点加上一个end，表示当前结束的是哪一个模式串，之后query的时候记录下来，最后扫一遍O(n)； AC代码: #include #include #include #include #include using namespace std; const int N = 510; co

2017-09-19 22:10:32 294

原创 HDU-2222-AC自动机

题目大意：就是给定若干个模式串，求它们在匹配串中出现的个数；题目解析：AC自动机的模板题，用来保存模板； AC代码： #include #include #include struct Node { int cnt;//是否为该单词的最后一个结点 Node *fail;//失败指针 Node *next[26];//Trie中每个结点的各个节点 }*queue[50000

2017-09-19 16:31:12 328

原创 POJ-3261-后缀数组

题目大意：求可重叠的出现k次最长重复子串的长度；题目解析：首先二分答案，问题转化成了有没有出现k次以上并且长度大于mid的子串，这样贪心O（N）在height数组里面扫一遍就好了； AC代码： #include #include #include using namespace std; const int MAXN = 200005; char ch[MAXN], All[M

2017-09-12 16:00:34 173

原创 POJ-2774-后缀数组

题目大意：给定两个字符串，求他们的最长连续子串；题目解析：先用分隔符把两个字符串拼接在一起，然后求一下后缀数组，枚举height，如果发现i，i-1分别在分隔符的左边和右边，就更新最大值； AC代码： #include #include #include using namespace std; const int MAXN = 200005; char ch[MAXN], A

2017-09-11 16:01:02 183

原创 BZOJ-3944-杜教筛

题目大意：题目解析：杜教筛科普：前面那项需要快速求解，最好O（1），后面那项可以dfs求解； AC代码： #include #include #include #include #include #include using namespace std; #define N 5000000 #define LL long long int T,n;

2017-09-03 16:06:59 338

原创 HDU-1695-莫比乌斯

题目大意：求在a 题目解析：跟上题一样，只不过要开ll，而且需要减去重复的，只要减去cal(b,b)/2即可； AC代码： #include #include using namespace std; typedef long long ll; #define MAXN 100010 int a,b,c,d,k,p[MAXN+10],pcnt,n; ll ans,sum[MAXN+10],m

2017-09-01 23:08:28 235

原创 BZOJ-2301-莫比乌斯

2017-09-01 22:37:27 284

原创 HDU-3966-树链剖分

题目大意：给定一棵树，两两种操作，一种是询问v，u所有节点的sum，还有一种是修改u到v上所有路径的val；题目解析：裸的树链剖分； AC代码： #include #include #include #include #include #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; con

2017-08-13 20:24:39 196

原创 HDU-5724-组合博弈

题目大意：n行20列的棋盘，对于每行，如果当前棋子右边没棋子，那可以直接放到右边，如果有就跳过放到其后面的第一个空位子，A先操作，最后谁无法操作则输；题目解析：只有20列，我们通过状态压缩得出序列传入sg函数，写的时候会发现需要把从左往右的序列倒过来，详细看代码； AC代码： #include #include #include #include #include using name

2017-07-31 23:26:23 288

原创 HDU-1848-组合博弈

题目大意：有三堆石子，两个人轮流取一堆石子中只能为斐波那契数的石子，问最后谁赢；题目解析：预处理f函数和sg函数，直接把三堆石子的sg函数异或起来判断是否为0； AC代码： #include #include #include #include #include using namespace std; const int N=1010; int f[N]; int sg[N]; int

2017-07-31 22:40:03 217

原创 uva-10498-线性规划

题目大意：标准的线性规划，m个约束条件都是小于等于；题目解析：单纯形法模板； AC代码： #include #include #include using namespace std; const double dinf=1e10; const int MAX=55; int n,m,B[MAX],N[MAX]; double A[MAX][MAX],b[MAX],c[MAX],

2017-07-29 14:31:23 322

原创 HDU-4609-FFT

题目大意：给定n条线段，任取三根，问能够组成三角形的概率；题目解析：首先三角形肯定是两边之后大于第三边，为此我们需要处理出任意两边的和以及方案数，朴素算法肯定是O（N^2）会超时，所以我们需要用到fft降到O（NlogN）；然后预处理出前缀和，枚举每条边作为最大值的时候，需要剪去一个大，一个小的情况，两个都比它大的情况，和用到自身的情况； AC代码： #include #include #

2017-07-27 23:35:25 178

原创 hihocoder-1388-高精度fft

感谢师兄的blog终于让我初略得明白卷积,dft及fft可以用来干什么。。附上链接：http://blog.csdn.net/viphong/article/details/52665620 其实就是求一个循环卷积，然后把他转化成求对应相关系数的最大值，因为卡精度，所以我们只能求得最大时的k值； AC代码： #include #include #include #include #inc

2017-07-27 21:22:25 390

原创 codeforces-827C-树状数组，同余定理

题目大意：给定一段DNA序列，和q个query，每次可以改变一个碱基，或者查询一个区间里面有多少个碱基与给定碱基序列（可以无限重复）相同；题目解析：首先因为匹配序列可以无限循环，所以可以根据位置%长度来确定一般性，因为如果一个碱基的位置mod (len)与匹配序列一个碱基的位置mod(len)一样，那么这个无限延长的碱基序列一定能匹配到第一个碱基，所以我们可以BIT来维护前缀和，根据碱基种类，

2017-07-27 21:15:38 475

原创 UvaLive-3700-lucas

题目大意：问第n+1层的杨辉三角所有数中有几个数是不能被p整除的；题目解析：根据lucas定理，要是（n，m）不能被p整除，则n和m转化成p进制后牵着每一位都必须大于等于后者；如果其中有一个不满足，那么就被p整除，所有我们只需要枚举n的每一位，设为a，ans*=ans+1; AC代码： #include #include #include #include #include

2017-07-25 23:01:04 262

原创 codeforces-832D-LCA,RMQ

题目大意：问一棵树上取三个点，可以任选一点为w，求u，v到w两条路径所重合的顶点数；题目解析：在线LCA； AC代码： #include #include #include #include using namespace std; const int N = 100010; const int M = 25; int dp[2*N][M]; //这个数组记得开到2*N，因为遍历

2017-07-25 15:32:21 375

原创 HDU-4547-离线LCA

题目大意：dos命令，每一步可以跳到任意子目录，但只能返回上一个根目录，问a,b之间最少需要几次dos操作；题目解析：采用离线lca，先建树，对于一个query中u和v，如果u=v，答案是0，如果v是u的祖先，答案是两者深度之差，如果u是v的祖先，答案是1，否则就是u到lca的距离再加一； AC代码： #include #include #include #include #inc

2017-07-25 15:24:35 337

原创 POJ-3207-TwoSAT

题目大意：一个圆上有m对点需要相连，连的方法可以在圆里外连，问是否可以使得两两连线不相交；题目解析：判断如果两个线段如果会有冲突，那么只能一个在里面一个在外面； AC代码： #include #include #include #include #include #include #include using namespace std; const int maxn=51010*2; c

2017-07-12 14:26:43 226

原创 HDU-1814-TwoSAT

题目大意：有(1,2),(3,4), ...(2n-1,2n),n对数，要在每对中选出一个共n个，并且满足m个约束条件，条件(a,b)表示ab不能同时被选,按字典序输出答案；题目解析：如果有a b有约束，那么建边A->B^1,B->A^1，字典序最后直接遍历输出； AC代码： #include #include #include #include #include #include #in

2017-07-12 12:47:51 203

原创 LA-3713-TwoSAT

题目大意：有ABC三个任务需要分配给n个宇航员，任务C没有限制，年龄大于等于平均年龄的可以分配A任务，否则是B任务，有m对宇航员互相讨厌，他们不能顾分配相同的方案，问是否可以找出一种方案。题目解析：如果相互讨厌的话，那么肯定不能够同时分配C，并且不能分配A和B，如果一个A一个B则不需要考虑； AC代码： #include #include #include #include #includ

2017-07-12 12:20:59 225

原创 LA-3211-TwoSAT,二分

题目大意：有你个飞机需要降落，每个飞机有两个可选时间降落，求所有飞机降落时间的最小值的最大值；题目解析：二分那个值，然后枚举每个时间，如果冲突的话，假设x,y冲突，那么连接x^1->y,y^1->x，然后判断是否可行就可以了； AC代码： #include #include #include #include #include #include using namespace std; c

2017-05-27 15:18:32 213

原创 UVA-11168-凸包

题目大意：平面上有n个点，找一条直线，使得所有点在直线的同侧，且到直线的距离之和尽量小；题目解析：首先这条直线肯定在凸包的某一条边上，所以先求出凸包来，再枚举每一条直线，注意两点确定一条直线，这条直线要转化成一般式，方便求距离，因为都在同一侧，所以可以预处理出x和y的前缀和； AC代码： #include using namespace std; const double PI = aco

2017-05-17 16:12:38 196

原创 UVA-10652-凸包

题目大意：平面上给定n个矩形，问用一个面积最小的凸多边形把他们包起来，计算出木板占整个包装面积的百分比；题目解析：求一个凸包就可以了，注意角度转化； AC代码： #include using namespace std; const double PI = acos(-1.0); struct Point { double x,y; Point(double x=0,dou

2017-05-17 15:14:56 160

原创 UVA-11796-计算几何

题目大意：有两条狗分别沿着自己的折线段跑，他们都是匀速运动并且同时开始同时到达，问中间过程的他们两者距离的最大值减去最小值的值是多少；题目解析：首先他们运动的过程可以分解成在某一段时间内都在线段上运动，那么在线段上运动，我们就可以考虑运动的相对性，一个看成静止不动，另一个还是匀速运动，那么这就是个点到线段的距离问题了； AC代码： #include using namespace std;

2017-05-15 20:52:12 189

原创 LA-3263-计算几何，欧拉定理

题目大意：有n个点组成的一笔画，问这个图形把平面分成了几个部分；题目解析：先把那些直线相交得出的点算出来得出点数，再把边数算出来，有一个点在原来的线段上并且不与端点重合边数就加一，因为一条线段变成了两条线段，最后根据欧拉定理f=e+2-v算出面数； AC代码： #include using namespace std; struct Point { double x,y;

2017-05-15 20:08:29 261

原创 UVA-11178-计算几何

题目大意：求一个三角形中每个内角的角三等分线组成的三角形的三个点的坐标；题目解析：没有算法可言，直接上模板； AC代码： #include using namespace std; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y){} }; typedef Point Vector; Vect

2017-05-15 19:42:12 189

原创 HDU-4507-数位dp

题目大意：给定区间，问满足条件所有数的平方和；题目解析：因为要求平方和，所以要用结构体保存个数，和，平方和；（附上大佬的解析）需要维护三个值（推荐使用结构体）, 假定dfs推出返回的结构体是next，当前结果的结构体是ans ①符合条件数的个数 cnt ②符合条件数的和 sum ③符合添加数的平方和 sqsum 其中①是基础数位DP。②next.sum

2017-05-11 00:13:39 316

原创 HDU-4352-数位dp,LIS

题目大意：求给定区间呢的数满足最长子序列长度为k；题目解析：LIS，dp第二维表示当前的序列，第三维表示目标长度为k，dfs的时候更新序列的时候要像LIS一样找到>=i的第一位并且去掉然后加上第i位； AC代码： #include #include #include #include #include using namespace std; typedef long long ll; l

2017-05-10 19:41:15 221

原创 HDU-3886-数位dp

题目大意：为一个区间内有多少数满足给定函数曲线的数的个数；题目解析：首先因为数据很大，需要用字符串保存，并且要处理掉前导零，否则会对答案有影响，dp第二维表示前一个数是多少，dp的第三维表示当前表示的opt； AC代码： #include #include #include #include #include using namespace std; typedef long long l

2017-05-09 23:45:36 214

原创 LightOJ-1205-数位dp

题目大意：给定区间问区间内有多少数是回文数；题目解析：因为给定长度，其实就已经知道看了他的对称中心，所以从前往后dfs，判断前i位的时候，要判断后面是否可以取到，如果不可以去到，那么后面那位的前一位就必须小于limit，所以dfs要多一个变量ok； AC代码： #include #include #include #include #include

2017-05-09 17:14:32 311

原创 LightOJ-1140-数位dp

题目大意：给定区间问区间内所有数的10进制0的个数的总和是多少；题目解析：dp的第二维表示当前已经有多少个0，注意前导零和只有1个0要输出1； AC代码： #include #include #include #include #include using namespace std; typedef long long ll; ll dp[35][300];

2017-05-08 23:00:09 307

原创 UESTC-250-数位dp

题目大意：求一个区间内有多少个数中相邻数位之差大于等于2；题目解析:：dp的第二维保存上一个数是多少，注意要处理前导零； AC代码： #include #include #include #include #include using namespace std; typedef long long ll; ll dp[20][12]; int num[20]; int ab(int x,

2017-05-08 19:50:26 280

原创 HDU-3652-数位dp

题目大意：求区间[0,n]有几个数中间的位数有13并且这个数能够被13整除；题目解析：跟上题一样。只不过因为要整除13所以dp多了一维表示当前位数模13的余数； AC代码： #include #include #include #include #include using namespace std; int dp[12][3][14]; int n,num[12]; int dfs(i

2017-05-08 16:49:33 244

原创 HDU-3555-数位dp

题目大意：问区间[0,n]中有多少个数中数位包括49；题目解析：定义dp[i][j]表示有多少个符合条件，i表示第几位，j=0的时候前面的位没有49并且上一位不是4，j=1的时候前面的位数没有49但是上一位是4，j=2的时候表示前面的位数已经包括49了； AC代码： #include #include #include #include #include using namespace s

2017-05-08 16:44:54 202

空空如也

空空如也