这个题查询的两个串有可能有公共前缀 trie树做法 include<cstdio> include<cstring> include<queue> include<cstdlib> constintkind=26; usingnamespacestd; chars[1010][1010]; inth[]={-1,-1,0,1,1,1,0,-1}; intg[]={0,1,1,1,0,-1,-1,-1}; intm,n,q,sum; intxx[1010],yy[1010],zz[1010]; structtrie{ structtrief...

catalan数 /include<cstdio> include<algorithm> usingnamespacestd; definemod1000000 intmain(){ intn,i,j,k,sum,s[1010],f; //while(scanf("%d",&n)) for(n=3;n<=20;n){ if(n0)break; for(i=1;i<=n;i) s[i]=i; sum=0; do{ f=1; for(i=1;i<=n&&f;i) for(j=i+1;j<=n&&f;...

很水，但还是WA了好几次 include<cstdio> include<string.h> include<algorithm> usingnamespacestd; intcmp(inta,intb){ returna>b; } intcmp2(inta,intb){ if(a%10b%10) returna<b; returna%10<b%10; } intn,m; intdp[31]; intmain(){ inti,j,t,T,a,b,x[31],y[31]; //freopen("1.in","r",std...

KMP求最小循环节 include<stdio.h> include<stdlib.h> include<math.h> include<string.h> chars1[100005],s2[100005]; intnext[100005],flag; voidgetnext(chars){ intk=1,j=0,len=strlen(&s[1]); next[k]=0; while(k<=len){ if(j0||s[k]s[j]){ j,k; next[k]=j; } else j=next[j]; } } intmin(...

s(m,n)表示把m个有区别的球放到n个相同的盒子中，且无一空盒，其不同的方案数。 s(m,n)=ns(m-1,n)+s(m-1,n-1)    (m>=n) s(m,n)=0  (m<n) s(0,0)=1; longlongdata[N][N]; voidstirling(intm,intn) { intmin,i,j; memset(data,0,sizeof(data)); data[0][0]=1; for(i=1;i<=m;i){ if(i<n)min=i; elsemin=n; for(...

计算整数n的拆分数用的是生成函数的方法。 首先来看一下生成函数所解决的问题(1+x+...+x^n+...)(1+x+...+x^n+...)...(1+x+..+x^n+...)  这个母函数可以这样理解(转化为经典的  不可区分球    放   可区分盒    中的问题)：每一个括号表示一个盒内放的球的情况 在计算拆分数时需要用一个ferrers图像性质：n拆分成m个数的和的拆分数等于将n拆分成最大数不超过m的拆分数。（这里n,m的大小无关...

Description给定一个正整数X，求一个最小的正整数N，使得N能被X整除。并且N有个性质：其各位数字都相同，比如1111,222222…… Input有若干组测试数据，以EOF结束。对于每组测试数据只有一行，包含一个正整数X(0<X<=100000)。 Output每组测试数据输出一行，包含1个正整数N。如果不存在则输出"NoSolution"。 SampleInput74 SampleOutput222http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=519 不...

1.有一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续的n个正面？它的答案是2^(n+1)2。 证明还不会。 http://www.matrix67.com/blog/archives/3638    2.随便取一个0到1之间的数，再加上另一个0到1之间的随机数，然后再加上一个0到1之间的随机数⋯⋯直到和超过1为止。一个有趣的问题：平均需要加多少次，才能让和超过1呢？答案是e次。 http://www.matrix67.com/blog/archives/3507

简单最大流，拆点做。模板敲错WA了好几次 include<cstdio> include<cstring> defineinf1000000 definemin(a,b)((a)>(b))?(b):(a) usingnamespacestd; intnum[60],in[60][11],out[60][11]; intn,k,dist[200],gap[200],edgeHead[200];//双向边 struct{ intu,v,cap,beg,next,re; }edge[3000]; voidaddEdge(intu,intv,intca){ edg...

DescriptionAssumeanintegersequencecontainsNelementswhosevaluecouldonlybeoneof{0,1,-1}.TheremayexistapositiveintegerDwhichcanmakethesumbetweeni-thelementand(i+D)-thelementbezero,whereiisacertainintegerbetween1andN-D.YourtaskistofindoutthemaximalD.InputFirstlinecontainsaintegerTindicatethenumberofcas...

5.继续退化：如果M空集，cut1和cut2重合（变为cut），则网络中割唯一。可以通过if(|S|+|T|总点数)来判断 三、割的三个典型应用（参考《最小割模型在信息学竞赛中的应用》）：最大权闭合图、最大密度子图、二分图的最小点权覆盖（二分图的最大点权独立集）

蔡勒（Zeller）公式：是一个计算星期的公式。随便给一个日期，就能用这个公式推算出是星期几。蔡勒公式如下：w=y+[y/4]+[c/4]-2c+[26(m+1)/10]+d-1公式中的符号含义如下：w：星期；w对7取模得：0-星期日，1-星期一，2-星期二，3-星期三，4-星期四，5-星期五，6-星期六c：世纪（前两位数）y：年（后两位数）m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）d：日[]代表取整，即只要整数部分。

一道很好的DP题 比较容易想到的是时间复杂度为O(N3)，空间复杂度为O(N2)的dp. dp[i][j]表示前i分钟，在已经休息了j分钟的情况下所能拿到的最大分数。于是就有: dp[i][j]=Max{Max{dp[i-k1][j-k1]},Max{dp[i-k2][j]+sum[(i-k2)(i)]}} 其中k1<=i,k1<=j,k2>=L,i-k2>=j转移就是O(n)的了， 但是考虑到数据范围，这样做势必会超时，因此需要将转移的代价降下来。 1.首先考虑Max{dp[i-k1][j-k1]}，我们发现所有的dp[i-k1][j-k1]都满足(i-k...

预处理估价函数。其他的套模板就可以了。 不过有一个地方没住意WA了2小时。 include<stdio.h> include<string.h> include<queue> usingnamespacestd; intsx,sy,tx,ty,n; intlen[5],num[5]; intbound,total; inth[2]={1,-1}; inthx[1010],hy[1010]; boolans; structpoint{ intx; intstep; }; intMin(inta,intb){ returna>b?b:a; } ...

第一次写博文，想了半天就拿一道dp/graph的题作为处作吧 此题有两种常见解法 （题意比较简单，就不赘述） 1.二分图最大匹配        此题等价于问一棵树中最小点覆盖数。树形结构可以把它看做是一个二分图，一个点集为奇数层，另一个点集为偶数层，显然满足二分图定义，可以套用求二分图最小点覆 盖的方法。或者，补全二分图，根据对称性，就是前面构造的二分图的边数的二倍，故最后结果也要除以二。 2.树形dp        写树形dp时首先要考虑好每个点的可能...