NetworkFlow.Dinic Let's do it.
网络流算法有许多种,最基本的一种方法是Fold-Fulkerson.不过裸奔的Fold-Fulkerson的效率总是不尽如人意.于是各种优化层出不穷.
比较牛X的一个就是基于分层图思想的MPLA(最短路径增值).在层次图里,从源点开始,不管怎么走,总能走到汇点,而且保证是最短路.这是一个非常优美的性质.复杂度证明...找WC2007王欣上论文吧..
于是便有了以下的裸的MPLA程序(附件1).每次计算出一个层次图.然后进行若干次DFS寻找增广路.
Dinic是基于MPLA上的另外一个改进.引入一个新的名词叫做块流,表示在一张剩余图上所有可增广的流量.Dinic在每次计算出层次图后,仅用一次DFS来找出这张图的块流,避免了许多废的搜索状态和回溯状态.详见程序(附件2).
在Ural上被阴了一题 -> Ural 1028
题目就不多说了..原本是找些线段树的题目来练练手.
结果这题..看起来好水..可以用树状数组切掉..
看到这么水的题目不忍心放弃..就开始随便写..
结果交上去TLE..觉得非常新奇..找了段线段树的程序扔上去AC了.(没天理啊..)
仔细观察题目.才发现..当坐标为0的时候..我可怜的树状数组啊..就开始无限的循环下去了.
还好..赶紧解决..可以把所有坐标加个1..也可以对于0的情况特判.
以下为我AC的程序:
#include <stdio.h> #include <memory.h> int n,a[15001],b[15001],ans[15001],tree[60000],t; int Query(int a) { if (!a) return tree[0]; int ans = 0; while (a) { ans += tree[a]; a -= (a & (-a)); } return ans + tree[0]; } void update(int a) { if (!a) { ++ tree[0]; return; } while (a <= 32768) { ++ tree[a]; a += (a & (-a)); } } int main() { freopen("input.txt","r",stdin); scanf("%d",&n); for (int i=1; i<=n; ++i) scanf("%d %d",&a[i],&b[i]); for (int i=1; i<=n; ++i) { update(a[i]); t = Query(a[i]); ++ ans[t]; } for (int i=1; i<=n; ++i) printf("%d\n",ans[i]); }
POJ 3719 Art of Balance
PKU某月的月赛中的一道题.写一写来练手.
题目大意是: 给出m个砝码(m<=16),有一个有n个节点的二叉树(n<=100),这棵树上有m个叶子节点,每个叶子节点可以挂上一颗砝码,一颗子树的重量是地下挂的所有砝码的重量之和,定义不平衡量为abs((lch.weight / root.weight)-1/2)*1000 , 要求给出一种方案,是的不平衡量的总和最小.
稍微想了下..m只有16..好吧...状态压缩的treedp.
记下f[root,state]为处理根为root的子树,底下用的砝码的状态为state..然后直接转移吧..
#include <stdio.h> #include <memory.h> typedef struct treenode{ int lch,rch,count; }; int cases,n,m,a[17],st[17][65538]; double f[102][65538],w[65538]; struct treenode tree[102]; int dfs(int root) //统计每棵子树所包含的叶子节点的数目. { if (tree[root].lch < 0 && tree[root].rch < 0) tree[root].count = 1; else tree[root].count += dfs(tree[root].lch) + dfs(tree[root].rch); return tree[root].count; } void calc_w() //计算各种状态的重量 { memset(w,0,sizeof(w)); for (int i=1; i<(1 << m); ++i) for (int j=0; j<m; ++j) if (i & (1 << j)) w[i] += a[j+1]; } void build_state(int state,int posi,int len) //生成有用状态 { if (posi > 16) return; build_state(state,posi+1,len); state = state | (1 << (posi-1)); st[++len][++st[len][0]] = state; build_state(state,posi+1,len); } double abs(double a) { if (a < 0) a = -a; return a; } double search(int root,int state) //DP主过程.(记忆化搜索) { if (f[root][state] < 0) { f[root][state] = 2000000000; if (tree[root].count == 1) { f[root][state] = 0; return 0; } for (int i=1; i<=st[tree[tree[root].lch].count][0]; ++i) { int tstate = st[tree[tree[root].lch].count][i]; if ((state & tstate) == tstate) { double temp = search(tree[root].lch,tstate)+search(tree[root].rch,state ^ tstate)+abs((w[tstate]/w[state])-0.5)*1000; if (f[root][state] > temp) f[root][state] = temp; } } } return f[root][state]; } int main() { scanf("%d",&cases); build_state(0,1,0); for (; cases; --cases) { scanf("%d",&n); memset(tree,0,sizeof(tree)); for (int i=1; i<=n; ++i) scanf("%d %d",&tree[i].lch,&tree[i].rch); dfs(1); scanf("%d",&m); memset(a,0,sizeof(a)); for (int i=1; i<=m; ++i) scanf("%d",&a[i]); calc_w(); for (int i=1; i<=n; ++i) for (int j=1; j<(1 << m); ++j) f[i][j] = -1.0; printf("%.3lf\n",search(1,(1 << m)-1)); } }
NOIP2008 提高组复赛试题数据及个人题解
第一题 word
题意简述:给出一个单词,统计其中出现最多的字母出现的次数maxn,以及出现最少的字母的次数minn,如果maxn-minn是质数的话则作为一个Lucky Word..否则即为No Answer.
类型: 模拟水题....
代码:
#include <stdio.h> #include <string.h> int count[27],max,min; char s[200]; bool notprime[102]; int main() { freopen("word.in","r",stdin); freopen("word.out","w",stdout); gets(s); memset(count,0,sizeof(count)); for (int i=0;s[i];i++) count[s[i]-96]++; min = 2147483647; max = 0; for (int i=1;i<=26;i++) { if (!count[i]) continue; if (max<count[i]) max = count[i]; if (min>count[i]) min = count[i]; } int j; notprime[0] = true; notprime[1] = true; for (int i=2;i<=50;i++) { j = i*2; while (j<=100) { notprime[j] = true; j += i; } } max -= min; if (notprime[max]) { printf("No Answer\n"); max = 0; } else printf("Lucky Word\n"); printf("%d\n",max); return 0; }
第二题 matches
题意简述: 给你n(n<=24)根火柴棒,叫你拼出 "A + B = C"这样的等式,求方案数.
解题思路: 直接枚举A和B(事实证明只到3位数),事先预处理2000以内各个数所用的火柴数.直接枚举出解
代码:
#include <stdio.h> #include <string.h> int n,ans; int c[2002]={6,2,5,5,4,5,6,3,7,6}; int main() { freopen("matches.in","r",stdin); freopen("matches.out","w",stdout); scanf("%d",&n); for (int i=10;i<=1800;i++) c[i] = c[i/10]+c[i%10]; n -= 4;ans = 0; for (int i=0;i<=800;i++) for (int j=0;j<=800;j++) if (c[i]+c[j]+c[i+j]==n) ans++; printf("%d\n",ans); return 0; }
第三题 message
题意简述: 给一个矩阵(左上角和右下角固定为0),从左上角走两次到右下角,两次走的路径不能有交集(即一个点不能被走两次),求两次走过的格子上的数的和最大是多少.(类似二取方格数.)
解题思路: 二取方格数很经典的题目了,于是便直接以 f[i][j][k][p] 表示第一条路径走到(i,j),第二条路径走到(k,p)所取到的数的最大值..转移方程就很好办了..同时注意判断两条路不要从同一个点转移过来就好了.
#include <stdio.h> #include <string.h> int a[52][52],f[52][52][52][52],n,m,ni,nj,nk,np; int next[4][4]={0,-1,-1,0,-1,0,-1,0,0,-1,0,-1,-1,0,0,-1}; int main() { freopen("message.in","r",stdin); freopen("message.out","w",stdout); scanf("%d %d",&n,&m); memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) for (int p=j;p<=m;p++) for (int m=0;m<=3;m++) { ni = i + next[m][0]; nj = j + next[m][1]; nk = k + next[m][2]; np = p + next[m][3]; if ((ni!=nk)||(nj!=np)) if (f[i][j][k][p] < f[ni][nj][nk][np] + a[i][j] + a[k][p]) f[i][j][k][p] = f[ni][nj][nk][np] + a[i][j] + a[k][p]; } printf("%d",f[n][m][n][m]); return 0; }
第四题 twostack
以下引用saybi的题解 http://sqybi.com/blog/archives/78
这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1q2的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1q2的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.
第一步需要解决的问题是,判断是否有解.
考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].
首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.
接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈."
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]
这样,原命题的逆否命题得证,所以原命题得证.
此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.
这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满足p1[k]< p1[i]
此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解.
此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~
还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]
MRain:程序是我自己写的(懒得按照格式输出了),已经过了所有标准数据.
var a,b,head,next,point,color:array[0..2001]of longint; s:array[1..2,0..1000]of longint; n,p,i,j,last:longint; procedure badend; begin writeln(0); close(output); halt; end; procedure addedge(a,b:longint); var t:longint; begin inc(p); point[p]:=b; if head[a]=0 then head[a]:=p else begin t:=head[a]; while next[t]<>0 do t:=next[t]; next[t]:=p; end; end; procedure dfs(now:longint); var t:longint; begin t:=head[now]; while t<>0 do begin if color[point[t]]=0 then begin color[point[t]]:=3-color[now]; dfs(point[t]); end; if color[point[t]]=color[now] then badend; t:=next[t]; end; end; begin assign(input,'twostack.in'); reset(input); assign(output,'twostack.out'); rewrite(output); fillchar(s,sizeof(s),0); fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do read(a[i]); b[n+1]:=maxlongint;p:=0; for i:=n downto 1 do begin b[i]:=b[i+1]; if a[i]<b[i] then b[i]:=a[i]; end; for i:=1 to n do for j:=i+1 to n do if (b[j+1]<a[i])and(a[i]<a[j]) then begin addedge(i,j); addedge(j,i); end; for i:=1 to n do if color[i]=0 then begin color[i]:=1; dfs(i); end; last:=1; for i:=1 to n do begin if color[i]=1 then write('a ') else write('c '); inc(s[color[i],0]); s[color[i],s[color[i],0]]:=a[i]; while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do begin if s[1,s[1,0]]=last then begin write('b '); dec(s[1,0]); end; if s[2,s[2,0]]=last then begin write('d '); dec(s[2,0]); end; inc(last); end; end; close(input); close(output); end.
最后附上据说是四川省的测试数据
几种常用的字符串Hash
明天就NOIP了..
今天找到一堆常用的字符串Hash算法.贴出来分享+以后自己找也方便..
RS Hash:
function RSHash(S: string): Cardinal; var a, b: Cardinal; I: Integer; begin Result := 0; a := 63689; b := 378551; for I := 1 to Length(S) do begin Result := Result * a + Ord(S[I]); a := a * b; end; Result := Result and $7FFFFFFF; end;
JS Hash
function JSHash(S: string): Cardinal; var I: Integer; begin Result := 1315423911; for I := 1 to Length(S) do begin Result := ((Result shl 5) + Ord(S[I]) + (Result shr 2)) xor Result; end; Result := Result and $7FFFFFFF; end;
P.J.Weinberger Hash
function PJWHash(S: string): Cardinal; var OneEighth, ThreeQuarters, BitsInUnignedInt, HighBits, test: Cardinal; I: Integer; begin Result := 0; test := 0; BitsInUnignedInt := SizeOf(Cardinal) * 8; ThreeQuarters := BitsInUnignedInt * 3 div 4; OneEighth := BitsInUnignedInt div 8; HighBits := $FFFFFFFF shl (BitsInUnignedInt - OneEighth); for I := 1 to Length(S) do begin Result := (Result shl OneEighth) + Ord(S[I]); test := Result and HighBits; if test <> 0 then Result := ((Result xor (test shr ThreeQuarters)) and not HighBits); end; Result := Result and $7FFFFFFF; end;
最普遍的 ELF Hash:
function ELFHash(S: string): Cardinal; var X: Cardinal; I: Integer; begin Result := 0; X := 0; for I := 1 to Length(S) do begin Result := (Result shl 4) + Ord(S[I]); X := Result and $F0000000; if X <> 0 then begin Result := Result xor (X shr 24); Result := Result and not X; end; end; Result := Result and $7FFFFFFF; end;
简单的BKDR Hash
function BKDRHash(S: string): Cardinal; var seed: Cardinal; I: Integer; begin Result := 0; seed := 131; // 31 131 1313 13131 131313 etc.. for I := 1 to Length(S) do begin Result := Result * seed + Ord(S[I]); end; Result := Result and $7FFFFFFF; end;
SDBM Hash
function SDBMHash(S: string): Cardinal; var I: Integer; begin Result := 0; for I := 1 to Length(S) do begin Result := Ord(S[I]) + (Result shl 6) + (Result shl 16) - Result; end; Result := Result and $7FFFFFFF; end;
DJB Hash
function DJBHash(S: string): Cardinal; var I: Integer; begin Result := 5381; for I := 1 to Length(S) do begin Result := Result + (Result shl 5) + Ord(S[I]); end; Result := Result and $7FFFFFFF; end;
AP Hash:
function APHash(S: string): Cardinal; var I: Integer; begin Result := 0; for I := 1 to Length(S) do begin if (i and 1) <> 0 then Result := Result xor ((Result shl 7) xor Ord(S[I]) xor (Result shr 3)) else Result := Result xor (not (Result shl 11) xor Ord(S[I]) xor (Result shr 5)); end; Result := Result and $7FFFFFFF; end;
