Saikaai-CSDN博客

原创 manachar 模板

int manachar(){ int len = strlen(t); s[0] = '&'; s[1] = '^'; for(int i = 1; i <= len; ++i)s[i << 1] = t[i - 1], s[i << 1 | 1] = '^';//在字符串中加入特殊字符 len ++; len <<= 1;//长度变为2 int ret = 0, mx = 0, id

2015-04-16 21:39:07 561

原创 BZOJ 3221 花神游历各国（线段树）

题目链接：BZOJ 3221最多进行5次操作，数将变为1，之后就不会改变。可以记录一个值col表示数是否需要开平方的操作。#include#include#include#includeusing namespace std;#define LL long longconst int maxn = 100000 + 10;int N, M;int a[ma

2015-04-13 21:03:34 549

原创 BZOJ 1562 [NOI2009]变换序列（二分图匹配）

题目链接：BZOJ 1562#include#include#include#includeusing namespace std;const int maxn = 10000 + 10;int N;bool vis[2 * maxn];int head[2 * maxn], belong[2 * maxn], choose[2 * maxn], d[10];

2015-04-13 21:01:53 486

原创 codeforces 387D George and Interesting Graph （二分图匹配）

题目自己去找吧~~~这道题我一开始想的二分图，将每个节点拆点，x点集表示每一个节点的流出的点，y点集表示每一个节点流入的节点。对于题目中的好点对，我们将中心节点以及与中心节点相连的边删除之后，剩下的每个节点的入度和出度都为1，直接计算二分图最大匹配即可。容易得出答案为加上的边和删去的边之和。加上的边为2 * N - 1 - 与中心节点相连的边 + 点数 - 二分图最大匹配。然后我莫名其

2015-04-12 11:40:09 626

原创 BZOJ 2324 [ZJOI2011] 营救皮卡丘

题目链接：BZOJ 2324对于限制“对于k节点，只有1到k - 1节点都被摧毁时，才能经过节点k”，我们可以通过用floyd处理，设dis[i][j]为i到j经过小于j节点的最短路径，进行转移即可。对于限制“每个节点都要被摧毁”，可以用有下界费用流解决。每个节点拆点，S节点与0节点的流出点连容量为k费用为0的边以保证有k个人到达N号节点。我开始wa了两次，因为我拆点的时候，直接是将点

2015-04-12 11:24:49 739

原创 BZOJ 2298 [HAOI2011]problem a

题目链接：BZOJ 2298这道题，我一开始想的居然是2 - SAT。。。被否决后想一想发现，对于每个人的可能的排名为一个区间，然后我尝试着将区间作为权值来看，说谎的人数就是总人数减去可选的不相交的区间权值和，然后我就不知道怎么统计答案了QAQ。我们可以用dp[i]表示到i节点，选的区间的权值和，转移dp[i] = max(dp[i], dp[j - 1] + i - j)。我们对于每一个

2015-04-12 10:20:54 473

原创 CH round # 65 solve

题目链接：CH round # 65 T1对于每个数考虑每一位的贡献。预处理num[i][0 / 1]数组表示二进制中第i位为0 / 1的数的和。对于求每一位的答案，直接枚举每一位求和即可。时间复杂度为NlogN。我能说这场比赛我们是在飞机上打的吗？那感觉。。。#include#include#includeusing namespace std;const

2015-04-11 22:34:47 498

原创 BZOJ 1492 [NOI 2007] 货币兑换Cash （dp + 分治）

题目链接：BZOJ 1492其实这种用单调队列来更新答案的dp可以用平衡树这种鬼畜做法来维护，做到时间复杂度为NlogN，前不久我还写了一道用splay维护的dp题。这道题就是学习一下cdq分治，代码确实比用splay写的要短。#include#include#include#include#includeusing namespace std;const int m

2015-04-07 19:59:10 515

原创攻略世界树（网络流）

【问题描述】这是在ALO世界线上。为了帮助桐子救出本子娜，ALfheim Online的多个工会展开了针对世界树的攻略活动。但是在攻略之前，必须策划好进攻方案。策划进攻方案之前也要先完成基础人员分组。在ALO中的小组分配中大致有四种定位，队长，战士，牧师，法爷。一个标准的小队应当拥有这四种人至少每种各一个。但是实际情况往往不如人意，人员职业往往并非正好1:1:1:1（就好像电院

2015-04-03 19:49:34 958 1

原创 BZOJ 3560 DZY Loves Math V

题目链接：BZOJ 3560首先，可以根据phi函数为积性函数，可以分解质因数，计算每个质因数对答案的贡献，最后乘起来即可。那么现在问题就来了，怎样计算质因数对答案的贡献？我们可以对每个数ai分解质因数，对于它的一个质因数p，记录p出现的次数bi，那么这个质数p对答案的贡献，是对于每个数ai，p的j(1华丽丽的传送门。（不会用公式编辑器的哭了QAQ。）#include#include#

2015-04-01 20:45:49 777

原创各种数论知识

博客好久没有更新了。。。感觉自己这段时间集训就像是在学数学一样ORZ。高一的那些触们会那么多高数是要闹哪样QAQ。下面是一些自己这段时间的学到的一些数论知识。我太弱，不要鄙视内容。。。原根1.设M为正整数,a为整数,若a % M 的阶(群论的定义下为元素的个数)为phi(M),则a为模M的一个原根。2.设g为P(P为素数)的原根,则满足,g ^ (P -1) = 1 (mo

2015-04-01 19:21:48 834

原创概率和期望

这几天集训有几道概率和期望的题，才知道到我之前的概率和期望的题简直就像小学生数数一样QAQ。所以我打算看一下概率和期望。下面是一些总结，至于那几道非人哉的题之后弄清楚了再写吧。不定期更新。1.连续型变量的期望：概率密度积分什么的。2.离散型变量的期望：E(x)=sigma(x[i]*p[i])3.平方的期望：E(x^2)=E(x)^2+D(x)证明：E(x^2)

2015-03-25 19:12:47 938

原创重建（树链剖分+线段树）

只是一个仅仅6KB的代码#include#include#includeusing namespace std;const int maxn = (int)1e5+10;int N,Q,k,tot=0;double xsum,xmin,xmax,count;int head[maxn],dep[maxn],fa[maxn],hv[maxn],anc[maxn],size[m

2015-03-23 20:29:17 426

原创 BZOJ 3670 [NOI 2014] 动物园

题目链接：BZOJ 3670好像O(N)的做法很神奇。next[i]表示i失配时下一个该匹配的位置；cnt[i]表示从i位置根据i=next[i]的方式经过cnt[i]次转移到0位置。这道题先用KMP求出next数组和cnt数组，然后再进行一次匹配。这次匹配，要保证对于i，若它的next[i]=k，那么k应该满足k#include#include#includeusing

2015-03-21 16:58:22 590

原创 Poj 3461 Oulipo （KMP）

题目链接：poj 3461所以这是水KMP模板？#include#include#includeusing namespace std;const int maxn=1000000+10;int next[maxn];char a[maxn];char b[maxn];void get_next(char *s){ int l=strlen(s); int k=-

2015-03-21 16:57:41 437

原创 Poj 3017 Cut the Sequence （DP，单调队列优化，数据结构优化）

题目链接：poj 3017论暴力姿势的优雅性。这道题直接用单调队列的大暴力居然过了，而且跑得很快。正解的话应该是用数据结构维护。时间复杂度为NlogN。先粘一个用单调队列优化的DP#include#include#includeusing namespace std;#define LL long long#define inf (1e18)const int m

2015-03-20 21:30:11 678

原创 BZOJ 3594 [SCOI 2014] 方伯伯的玉米田（DP，树状数组优化）

题目链接：BZOJ 3594二维树状数组优化DP。首先写出暴力的动态转移方程：dp[i][j]=max{dp[o][p]}+1.其中满足o然后就是优化问题。对于条件p+a[o]-a[i]其中第一维是j+a[i]，第二维是j。但是状态有可能由j=0的转移而来，所以我们将其整体右移一位即可。#include#include#includeusing namespa

2015-03-20 21:28:51 792

原创 BZOJ 1875 [SDOI 2009] HH去散步（DP，矩阵乘法优化）

题目链接：BZOJ 1875这道题的思路，主要是构建矩阵的思路很巧妙。我们普通的用矩阵乘法转移是用点来转移，但是这样不能去掉在一个地方逗留的情况。一个很神奇的做法就是用边来构图(对于一条边i，除去一条边j满足i==(j^1)的情况，与其他的边都相连)转移t-1次，然后同用与起点相连的边构造的一个矩阵(相当于系数矩阵)相乘。最后统计答案，只需将终点相连的边的答案加上即可。#inc

2015-03-20 21:26:18 1407 1

原创 Poj 3734 Blocks（DP，矩阵乘法优化）

题目链接：poj 3734这道题用矩阵乘法优化DP。考虑到直接转移的话，N太大，会TLE。由于转移的方案数，转移的状态很少，所以可以将转移的方案用矩阵来表示。设dp[i][k]表示涂到第i个格子，状态为k的方案数。其中状态k的定义为：k=1：红色和绿色都为奇数，k=2：红奇绿偶，k=3：红偶绿奇，k=4：红偶绿偶DP方程自己写。表示为矩阵为：2 1 1 01 2 0

2015-03-20 21:24:15 571

原创关于动态规划

不定期更新。概率与期望1.求期望状态设计：始终是当前状态距离最终目标的期望步数，然后倒推即可。2.对于二维的棋盘问题，要增加一位表示已经放了多少个然后进行状态转移。3.对于转移之后又影响初值的问题，用高斯消元解线性方程组即可。数位DP1.思想：逐位思想。本质：字母数上DP。2.关于记忆化搜索：始终注意加上当前这位是否有限制。用一个数组存放当前的答案以记

2015-03-19 22:10:22 448

原创 BZOJ 3209 花神的数论题（数位DP）

题目链接：BZOJ 320910000007不是质数。10000007=941*10627。用费马小定理的请注意。组合数1.组合恒等式：C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)2.全组合数求和：sigma(c(N,i)) (i->0...N) = 2^N#include#include#includeusing namespace s

2015-03-19 22:06:46 642

原创 Poj 2096 Collecting Bugs （概率与期望）

题目链接：poj 2096dp[i][j]:descrip in this step we have found i kinds of bugs and these bugs belong to j kinds of system.dp[i][j]=(i/j)*(n*s)*dp[i][j]+(i/j)*(1-j/s)*dp[i][j+1]+(1-i/n)*(j/s)*dp[i+1][j]+

2015-03-19 22:04:49 550

原创幸运数字（数位DP）

没有题目链接，数据网上也没有。粘一下题面。【题目描述】中国人喜欢数字6和8。特别地，一些人喜欢满足含有特定个数6和8的数。现在请求出，在区间[L,R]之间的第K大的含有X个6和Y个8的数。【输入】输入的第一行包括4个数字，L,R,X,Y。接下来的一行给出该组数据的询问数Q。接下来Q行中，每行有一个整数K。【输出】对于某个询问，输出一行，为对应的第K大的数。如果不

2015-03-18 17:04:02 635

原创 BZOJ 1833 [ZJOI 2010] 数字统计（数位DP）

题目链接：BZOJ 1833听说这道是一道水DP(Orz).我到现在都不知道BZOJ上long long要用I64d输出，还是用lld输出Orz。应该是lld吧(DK)。反正我用I64d输出一直PE，改用cout就A了(这个傲娇的评测机= =)。#include#include#includeusing namespace std;#define LL long longL

2015-03-18 16:58:36 595

原创 BZOJ 1069 [SCOI 2007] 最大土地面积（凸包+旋转卡壳）

题目链接：BZOJ 1069#include#include#include#include#includeusing namespace std;const int maxn=2000+10;int N,top;int L[maxn],R[maxn];struct node{ double x,y;}p[maxn],point,s[maxn];double g

2015-03-18 16:56:25 570

You ask me how I became a madman. It happened thus: One day, long before many gods were born, I woke from a deep sleep and found all my masks were stolen - the seven masks I have fashioned and worn in

2015-03-18 07:16:01 466

原创 Poj 2187 Beauty Contest （凸包+旋转卡壳）

题目链接：poj 2187对于这道题，我只能呵呵呵呵。我靠，我在poj上wa了20多次才发现有一种坑爹的情况：所有的点在同一条直线上QAQ!好吧，我是考虑不够完全，但是这是什么情况：数据中有重点!题中说好的No two farms share the same pair of coordinates呢？贴上我的代码。(我是顺时针转的)#include#include#includ

2015-03-17 21:55:39 367

原创 BZOJ 3597 [SCOI 2014] 方伯伯运椰子（分数规划+消圈算法）

题目链接：BZOJ 3597因为总流量不可改变，只能改变流量的分布，所以就用消圈算法吧。。。因为要求(x-y)/k的最大值，所以用0-1分数规划吧。。。#include#include#include#includeusing namespace std;const int maxn=5000+10;double eps=1e-3;int N,M,col;bool

2015-03-17 07:27:16 752

原创 Poj 2175 Evacuation Plan （消圈算法）

题目链接：poj 2175消圈算法，可以用来判断当前的方案是否是令费用最小的方案。若存在一个负环，那么一定可以找到比当前方案更优的方案。对于这道题，我们只需用残量网络建图，跑spfa判断这个图是否有环。若有环，沿着环更改方案即可。具体怎么建图，挖坑待填。先贴上代码。#include#include#include#include#includeusing namespace

2015-03-16 22:09:34 683

原创关于计算几何

这里是蒟蒻整理的一些计算几何的知识。挖一个坑，不定期填坑。。。一.叉积的性质1.a*b=-b*a;//反交换律2.不满足结合律，但满足 a*(b*c)+b*(a*c)+c*(a*b)=03.a*b=0//向量a，b平行4.拉格朗日公式：a*(b*c)=b*(a*c)-c*(a*b)5.设向量P(x1,y1),Q(x2,y2) => P*Q=x1*y2-x2*

2015-03-15 22:02:48 510

原创 hdu 1348 wall （计算几何，凸包）

题目链接：hdu 1348凸包模板题。但是要注意输出格式，我开始就被输出格式给坑了。。。#include#include#include#include#includeusing namespace std;#define maxn (1000+10)int N,L;double pi=acos(-1);struct node{ int x,y;}p[maxn],

2015-03-15 21:26:26 475

原创 Poj 2318 toys （计算几何，叉积）

题目链接：Poj 2318直接用叉积做。对于每一件玩具，二分所有的隔间，然后用叉积判断每一个点与这个隔间的关系。#include#include#includeusing namespace std;#define maxn (5000+10)int N,M;int cou[maxn];struct node{ int x,y;}S,T,a[maxn];inline

2015-03-15 21:24:41 451

原创 BZOJ 1208 [HNOI 2004] 宠物收养所（splay）

题目链接：BZOJ 1208这道splay写的我还有什么话可说呢？一开始一直TLE，然后各种debug，最后才发现自己if语句写挂了= =。#include#include#include#includeusing namespace std;#define maxn (80000+10)int N,col=-1,root=0,idx=0,mod=1e6,t1,t2;long

2015-03-14 14:14:09 497

原创 BZOJ 1143 [CTSC 2008] 祭祀（二分图匹配，最小相交路径覆盖）

题目链接：BZOJ 1143这道题我查了好久错啊，最后才发现读入边的时候讲M打成N了QAQ。总结了一些二分图匹配的知识：1.最大匹配 == 最小点覆盖 == 总点数-最大点独立集2.最小不相交路径覆盖 == 原图总点数-新图最大匹配3.最小相交路径覆盖 => 先用floyd求传递闭包 => 最小不相交路径覆盖#include#include#includeusin

2015-03-14 14:10:31 496

原创 BZOJ 3571 [HNOI 2014] 画框（KM算法+分治）

题目链接：思路：用类似于最小乘积生成树求解。最小乘积生成树：每个点有两个权值x，y，求一棵生成树使得sigma(x[i])*sigma(y[i])最小。求解方法：建立平面直角坐标系，将每个点看做坐标(x[i],y[i])。设x[i]*y[i]=k(x[i],y[i]满足大于0)，将x[i]除到等式右边y[i]=k/x[i]，那么可以联想到反比例函数。对于反比例函数，k的绝对值越

2015-03-14 14:05:29 1565

原创 hdu 2255 奔小康赚大钱（最大权匹配，KM算法）

题目链接：hdu 2255#include#include#includeusing namespace std;#define inf (1e8)int N;int A[310][310],lx[310],ly[310],link[310],slack[310];bool visx[310],visy[310];inline int read(){ int x=0,f=1

2015-03-12 22:16:19 414

原创 hdu 1533 Going Home （最大权匹配，KM算法）

题目链接：hdu 1533#include#include#includeusing namespace std;#define inf (1e5)int N,M,L;char map[110][110];int A[110][110],s[110][110],w[110][110],ly[110],lx[110],link[110],slack[110];bool visx[

2015-03-12 22:14:40 396

原创 BZOJ 1090 [SCOI 2003] 字符串折叠（区间DP）

题目链接：BZOJ 1090dp[i][j]表示区间[i,j]的最短折叠长度转移方程为：dp[i][j]=min(j-i+1,dp[i][k]+dp[k+1][j])特别地若满足区间[k+1,j]可以由区间[i,k]多次折叠得到，那么dp[i][j]=min(dp[i][j],dp[i][k]+2+get((j-k)/(k-i+1)+1))//get函数是求一个数的位数#i

2015-03-12 12:43:12 470

原创 BZOJ 1076 [SCOI 2008] 奖励关（概率与期望）

题目链接：BZOJ 1076#include#include#includeusing namespace std;int K,N;int a[50],v[50];double dp[110][32800];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch'9'){if(ch=='-')f=-1;ch=g

2015-03-12 12:42:37 579

原创 hdu 4336 Card Collector （概率与期望）

题目链接：hdu 4336dp[i]表示在i这个状态下，收集齐所有卡片所需要的买的袋数，转移方程为：dp[i]=(dp[i]+1)*(1-tot)+(dp[i|a[j]]+1)*p[j] (j为i状态中不包含的袋数，tot为所有符合条件的j的p[j]的和)，即i可以转移到拓展一袋的状态，也可以转移到没有拓展的状态。由于方程左右两边都有要求的量dp[i]那么把等式右边展开，移项可以得到最后的

2015-03-11 19:10:22 409

空空如也

空空如也