3 zyz_3_14159

尚未进行身份认证

暂无相关简介

等级
TA的排名 4w+

BZOJ1030 AC自动机 + DP

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

2018-11-19 20:19:09

BZOJ-4827-FFT

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

2018-09-11 16:05:33

莫比乌斯&线性筛

最难受的莫过于正式赛因为平常不训练,训练懒就不写博客导致莫比乌斯忘记怎么做了???菜是原罪,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

codeforces-375D-树上莫队

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

2017-11-17 00:45:02

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

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

2017-11-16 13:38:01

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

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

2017-11-15 23:54:55

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

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

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

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

BZOJ-3944-杜教筛

题目大意:题目解析:杜教筛科普:前面那项需要快速求解,最好O(1),后面那项可以dfs求解;AC代码:#include#include#include#include#include#includeusing namespace std;#define N 5000000#define LL long longint T,n;

2017-09-03 16:06:59

HDU-1695-莫比乌斯

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

2017-09-01 23:08:28

BZOJ-2301-莫比乌斯

莫比乌斯反演;形式一:F(n)=∑d|nf(d)=>f(n)=∑d|nμ(d)F(nd)形式二:F(n)=∑n|df(d)=>f(n)=∑n|dμ(dn)F(d)题目大意:求在a题目解析:满足gcd(x,y)是k的(x,y)的对数也等价于1令f(i)表示满足gcd(x,y)=i时(x,y)的对数,F(i)表示满足i|gcd(x,y)的(x,y)的对数,F(i

2017-09-01 22:37:27

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|1using namespace std;con

2017-08-13 20:24:39

HDU-5724-组合博弈

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

2017-07-31 23:26:23

HDU-1848-组合博弈

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

2017-07-31 22:40:03

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

HDU-4609-FFT

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

2017-07-27 23:35:25

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

codeforces-827C-树状数组,同余定理

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

2017-07-27 21:15:38

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!