BZOJ 1001([BeiJing2006]狼抓兔子-最大流转对偶图最短路)

1001: [BeiJing2006]狼抓兔子

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 5779  Solved: 1297
[Submit][Status][Discuss]

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形: 左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为N,M.表示网格的大小,N,M均小于等于1000.接下来分三部分 第一部分共N行,每行M-1个数,表示横向道路的权值. 第二部分共N-1行,每行M个数,表示纵向道路的权值. 第三部分共N-1行,每行M-1个数,表示斜向道路的权值. 输入文件保证不超过10M

Output

输出一个整数,表示参与伏击的狼的最小数量.

Sample Input

3 4

5 6 4

4 3 1

7 5 3

5 6 7 8

8 7 6 5

5 5 5

6 6 6

Sample Output

14

本题是最大流转最小割转对偶图最短路
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN (999*999*2+2+10)
#define MAXM (MAXN*3)
#define For(i,n) for(int i=1;i<=n;i++)
int n,m,N,M,s,t,pre[MAXN]={0},edge[MAXM],next[MAXM],weight[MAXM],size=0;
int no(int i,int j,int k){return (i-1)*2*M+j*2-(k^1);}
void addedge(int u,int v,int w)
{
	edge[++size]=v;
	weight[size]=w;
	next[size]=pre[u];
	pre[u]=size;
}
void addedge2(int u,int v){int w;scanf("%d",&w);addedge(u,v,w),addedge(v,u,w);}
int q[MAXN*9],d[MAXN];
void SPFA()
{
	memset(d,127,sizeof(d));d[s]=0;
	int head=1,tail=1;
	q[1]=s;
	while (head<=tail)
	{
		int now=q[head];
		for (int p=pre[now];p;p=next[p])
		{
			int &v=edge[p];
			if (d[now]+weight[p]<d[v])
			{
				d[v]=d[now]+weight[p];
				q[++tail]=v;
			}
		}
		head++;
	}
}
int main()
{
//	freopen("bzoj1001.in","r",stdin);
	scanf("%d%d",&n,&m);
	N=n-1,M=m-1;
	s=N*M*2+1;t=s+1;
	For(i,n) For(j,m-1)
	{
		if (i==1) addedge2(s,2*j);
		else if (i==n) addedge2(no(i-1,j,0),t);
		else addedge2(no(i,j,1),no(i-1,j,0));
	}

	For(i,n-1) For(j,m)
	{
		if (j==1) addedge2(t,2*M*(i-1)+1);
		else if (j==m) addedge2(2*M*i,s);
		else addedge2(no(i,j-1,1),no(i,j,0));
	}
	For(i,n-1) For(j,m-1) addedge2(no(i,j,0),no(i,j,1));
	SPFA();
	cout<<d[t]<<endl;
	return 0;
}

BZOJ 3132(上帝造题的七分钟-树状数组求和+2D逆求和数组)

3132: 上帝造题的七分钟

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 46  Solved: 18
[Submit][Status][Discuss]

Description

“第一分钟,X说,要有矩阵,于是便有了一个里面写满了0的n×m矩阵。

第二分钟,L说,要能修改,于是便有了将左上角为(a,b),右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。

第三分钟,k说,要能查询,于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟,彩虹喵说,要基于二叉树的数据结构,于是便有了数据范围。

第五分钟,和雪说,要有耐心,于是便有了时间限制。

第六分钟,吃钢琴男说,要省点事,于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。

第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。”

       ——《上帝造裸题的七分钟》

所以这个神圣的任务就交给你了。

Input

 输入数据的第一行为X n m,代表矩阵大小为n×m。

从输入数据的第二行开始到文件尾的每一行会出现以下两种操作:

  L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。

  k a b c d   —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。

 

请注意,k为小写。


        

Output

针对每个k操作,在单独的一行输出答案。

Sample Input

X 4 4

L 1 1 3 3 2

L 2 2 4 4 1

k 2 2 3 3



Sample Output

12

HINT

对于100%的数据,1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, 1 ≤ delta ≤ 500,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。

Source

2D树状数组支持单点修改+求和(1,1)-(x,y)矩形

因此按照zkw的思路用逆求和数组做(就是把区间修改结构-用2个单点修改的逆求和数组d',{i*d'}代替,神思路)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (2050)
int lowbit(int x){return x&(-x);}
int n,m,x1,x2,y1,y2,delta;
struct arr_tree
{
	int b[MAXN][MAXN];
	arr_tree(){memset(b,0,sizeof(b));	}
	void add(int x,int y,int c,bool b1,bool b2)
	{
		if (!x||!y||x>n||y>m) return;
		if (b1) c*=(x-1);if (b2) c*=(y-1);if (!c) return;
		for (int i=x;i<=n;i+=lowbit(i))
			for (int j=y;j<=m;j+=lowbit(j)) b[i][j]+=c;
	}
	int qur(int x,int y)
	{
		if (!x||!y) return 0;
		int ans=0;
		for (int i=x;i;i-=lowbit(i))
			for (int j=y;j;j-=lowbit(j)) ans+=b[i][j];
		return ans;
	}
	void add(int x1,int y1,int x2,int y2,int c,bool b1,bool b2)
	{
		add(x2+1,y2+1,delta,b1,b2),add(x1,y1,delta,b1,b2);
		add(x1,y2+1,-delta,b1,b2),add(x2+1,y1,-delta,b1,b2);
	}
}d,di,dj,dij;
int Dsum(int x,int y)
{
	return d.qur(x,y)*x*y+dij.qur(x,y)-di.qur(x,y)*y-dj.qur(x,y)*x;
}
int main()
{
	scanf("X %d %d",&n,&m);
	char c;
	while (scanf("%c",&c)==1)
	{
		while (c^'L'&&c^'k') if (scanf("%c",&c)!=1) return 0;
		switch(c)
		{
			case 'L':
				scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta);
				if (x1>x2) swap(x1,x2),swap(y1,y2);
				d.add(x1,y1,x2,y2,delta,0,0),di.add(x1,y1,x2,y2,-delta,1,0);
				dj.add(x1,y1,x2,y2,-delta,0,1),dij.add(x1,y1,x2,y2,delta,1,1);
				break;
			default:
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				if (x1>x2) swap(x1,x2),swap(y1,y2);
				printf("%dn",Dsum(x2,y2)+Dsum(x1-1,y1-1)-Dsum(x1-1,y2)-Dsum(x2,y1-1));
		}
	}
}

BZOJ 2111([ZJOI2010]Perm 排列计数-乘法逆元+完全二叉树模型+数列分数表示法)

2111: [ZJOI2010]Perm 排列计数

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 478  Solved: 283
[Submit][Status][Discuss]

Description

称一个1,2,...,N的排列P1,P2...,Pn是Magic的,当且仅当2<=i<=N时,Pi>Pi/2. 计算1,2,...N的排列中有多少是Magic的,答案可能很大,只能输出模P以后的值

Input

输入文件的第一行包含两个整数 n和p,含义如上所述。

Output

输出文件中仅包含一个整数,表示计算1,2,⋯, �的排列中, Magic排列的个数模 p的值。

Sample Input

20 23

Sample Output

16

HINT

100%的数据中,1 ≤ � N ≤ 106, P� ≤ 10^9,p是一个质数。

显然可以把这题看成-有n个节点的完全二叉树(小根堆性质)的排列数。
那就把最小的那个拎出来,其它的点随便塞入2边(不影响结果)。
接下来就是把答案分解成分数,乘法逆元啥的。。。
lyd的题解
#include<cstdio>
#include<cmath>
#include<functional>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN (1000000+1)
#define eps (1e-9)
int n,F;
int exgcd(int a,int b,long long &x,long long &y){if (!b) {x=1,y=0;return a;}int ans=exgcd(b,a%b,x,y);long long z=x;x=y;y=z-(a/b)*y;return ans;}
long long f[MAXN],g[MAXN],jc[MAXN];
long long mulinv(int b)
{
	long long x,y;
	exgcd(b,F,x,y);
//	return ((-x)/F*F+F+x)%F;
	return (x+abs(x)/F*F+F)%F;
}
int main()
{
	scanf("%d%d",&n,&F);
	f[0]=g[0]=f[1]=g[1]=1%F;
	jc[0]=jc[1]=1;
	for (int i=2;i<=n;i++) jc[i]=jc[i-1]*i%F;
	for(int i=2;i<=n;i++)
	{
		int dep=(int)(log(i)/log(2)+eps)+1;
		int l=(int)pow(2.0,dep-2)-1;
//		cout<<l<<' '<<(int)(eps+pow(2.0,dep-2))<<' '<<(i-1-2*l)<<' ';
		l+=min((i-1-2*l),(int)(eps+pow(2.0,dep-2)));
		int r=i-l-1;
//		cout<<i<<' '<<dep<<' '<<l<<' '<<r<<' '<<f[l]<<' '<<f[r]<<endl;
		f[i]=f[l]*f[r]%F*jc[i-1]%F;
		g[i]=g[l]*g[r]%F*jc[l]%F*jc[r]%F;
	}
//	cout<<f[n]<<' '<<g[n]<<endl;
	cout<<f[n]*mulinv(g[n])%F<<endl;
	return 0;
}

上学路线(递归sap-不完全)

Problem 2 上学路线(route.cpp/c/pas)

【题目描述】

可可和卡卡家住马赛克市的东郊,每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。

马赛克市一共设有N个公交车站,不妨将它们编号为1…N的自然数,并认为可可和卡卡家住在1号汽车站附近,而他们学校在N号汽车站。市内有M条直达汽车路线,执行第i条路线的公交车往返于站点pi和qi之间,从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N)

两个人坐在电脑前,根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子,他想趁卡卡不备,在卡卡的输入数据中删去一些路线,从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci:删去路线的ci越大卡卡就越容易发现这个玩笑,可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。

马赛克市的公交网络十分发达,你可以认为任意两个车站间都可以通过直达或转车互相到达,当然如果在你提供的删除方案中,家和学校无法互相到达,那么则认为上学需要的最短为正无穷大:这显然是一个合法的方案。

 

【输入格式】

输入文件中第一行有两个正整数N和M,分别表示马赛克市公交车站和公交汽车路线的个数。以下M行,每行(第i行,总第(i+1)行)用四个正整数(之间由一个空格隔开)描述第i条路线:pi, qi, ti, ci;具体含义见上文描述。

【输出格式】

输出文件最多有两行。 第一行中仅有一个整数,表示从可可和卡卡家到学校需要的最短时间。第二行输出一个整数C,表示Ci之和

【样例输入】

6 7

1 21 3

2 61 5

1 31 1

3 41 1

4 61 1

5 61 2

1 51 4

【样例输出】

2

5

【数据范围】

   

2<=N<=500,1<=M<=124 750, 1<=ti, ci<=10 000

 

这题我用的是递归sap(),谁知道狂Wa。

大家用递归sap的时候想必经常会莫名NTR。

结论://dfs_sap()的Z正确性目前有待考证。。。

根据我的研究,经验总结如下:

1.退出条件:

-PS:有可能某次增广flow=0,但是改距离标号可以继续flow

-PS:有时候无限增广,输答案能看出上面的错误

2.修改距离标号:

-PS:距离标号最好直接+1,minj等手段极有可能造成≈没有距离标号优化的状况

3.dfs时的flow

-PS:一定要提前return,要不然改距离标号a~

4.重构图:

-PS:这样是质的差别,递归不卡时间?

5.唯一重点:

PS:实在不行时,去掉距离标号优化!另可T到死,不能WA到爆

6.用递归sap唯一的好处是省事……(什么你1分钟BFS_sap()?当我没说)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define MAXN (500+10)
#define MAXM (124750+10)
#define MAXCi (10000+10)
#define INF (2139062143)
#define For(i,n) for(int i=1;i<=n;i++)
#define Forp(p,u) for (int p=pre[u];p;p=next[p])
using namespace std;
int n,m,edge[2*MAXM],weight[2*MAXM],c[2*MAXM],next[2*MAXM],pre[MAXN],size=1;
void addedge(int u,int v,int w,int w2)
{
	edge[++size]=v;
	weight[size]=w;
	c[size]=w2;
	next[size]=pre[u];
	pre[u]=size;
}
int d[MAXN],q[MAXN*8];
void spfa()
{
	memset(d,127,sizeof(d));
	d[1]=0;
	int head=1,tail=1;q[1]=1;
	while (head<=tail)
	{
		int &u=q[head];
		Forp(p,u)
		{
			int &v=edge[p];
			if (d[v]==INF||d[u]+weight[p]<d[v])
			{
				q[++tail]=v;d[v]=d[u]+weight[p];
			}
		}
		head++;
	}
}
int d2[MAXN],cnt[MAXN];
void spfa2()
{
	memset(d2,127,sizeof(d2));
	memset(cnt,0,sizeof(cnt));
	d2[n]=0;cnt[0]=1;
	int head=1,tail=1;q[1]=n;
	while (head<=tail)
	{
		int &u=q[head];
		Forp(p,u)
		{
			int &v=edge[p];
			if (d[u]-weight[p]!=d[v]) continue;
			if (d2[v]==INF)
			{
				q[++tail]=v;d2[v]=d2[u]+1;
				cnt[d2[v]]++;
			}
		}
		head++;
	}
}
bool sap_T=1,b[2*MAXM]={0};
int sap(int u,int flow)
{
	if (u==n) return flow;
	int tot=0,minj=INF;
	Forp(p,u)
	{
		int &v=edge[p];
	/*
		if (d2[v]==INF) continue;
		if (!(d[u]+weight[p]==d[v]||d[u]-weight[p]==d[v])) continue;
	*/
		if (!b[p]) continue;
		if (c[p]>0&&d2[u]==d2[v]+1)
		{
			int w=sap(v,min(flow-tot,c[p]));
			c[p]-=w;c[p^1]+=w;tot+=w;
			if (flow==tot) return tot;
		}else if (c[p]) minj=min(minj,d2[v]);
	}
	if (--cnt[d2[u]]==0)
		{
			d2[1]=n,sap_T=0;/*return tot;*/
		}//d2[1]=n+1;
//	if (minj^INF) cnt[d2[u]=minj+1]++;
/*	else*/ cnt[++d2[u]]++;
	return tot;
}
int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	memset(pre,0,sizeof(pre));
	scanf("%d%d",&n,&m);
	For(i,m)
	{
		int u,v,w1,w2;
		scanf("%d%d%d%d",&u,&v,&w1,&w2);
		addedge(u,v,w1,w2);
		addedge(v,u,w1,w2);
	}
	spfa();
//	for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<endl;
	cout<<d[n]<<endl;
	int ans=0;
	spfa2();
	int de_bug_1=0;
	For(i,n)
		Forp(p,i)
		{
			if (d[i]>d[edge[p]]) c[p]=0;
		//*0
		//	if (d2[i]!=INF&&d2[edge[p]]!=INF&&c[p]) cout<<i<<' '<<edge[p]<<endl,de_bug_1++;
			if (d[i]+weight[p]==d[edge[p]]) b[p]=b[p^1]=1,/*cout<<i<<' '<<edge[p]<<endl,*/de_bug_1++;
		}
//	cout<<de_bug_1<<endl;
	b[0]=1;
	For(i,n)
		Forp(p,i)
		{
			while (next[p]&&!b[next[p]]) next[p]=next[next[p]];
		}

	while(/*sap_T*/1)
	{
		if (d2[1]>=n) break;
		int w=sap(1,INF);
	//	if (!w) break;
//		cout<<ans<<' '<<d2[1]<<endl;
		ans+=w;
	}
	cout<<ans<<endl;
	return 0;
}

BZOJ 3097(Hash Killer I-哈希%u64的不可行)

3097: Hash Killer I

Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 76  Solved: 34
[Submit][Status][Discuss]

Description

这天天气不错,hzhwcmhf神犇给VFleaKing出了一道题:
给你一个长度为N的字符串S,求有多少个不同的长度为L的子串。
子串的定义是S[l]、S[l + 1]、... S[r]这样连续的一段。
两个字符串被认为是不同的当且仅当某个位置上的字符不同。

VFleaKing一看觉得这不是Hash的裸题么!于是果断写了哈希 + 排序。
而hzhwcmhf神犇心里自然知道,这题就是后缀数组的height中 < L的个数 + 1,就是后缀自动机上代表的长度区间包含L的结点个数,就是后缀树深度为L的结点的数量。
但是hzhwcmhf神犇看了看VFleaKing的做法表示非常汗。于是想卡掉他。

VFleaKing使用的是字典序哈希,其代码大致如下:
u64 val = 0;
for (int i = 0; i < l; i++)
 val = val * base + s[i] - 'a';
u64是无符号int64,范围是[0, 2^64)。VFleaKing让val自然溢出。
base是一个常量,VFleaKing会根据心情决定其值。
VFleaKing还求出来了base ^ l,即base的l次方,这样就能方便地求出所有长度为L的子串的哈希值。
然后VFleaKing给哈希值排序,去重,求出有多少个不同的哈希值,把这个数作为结果。
其算法的C++代码如下:

typedef unsigned long long u64;

const int MaxN = 100000;

inline int hash_handle(const char *s, const int &n, const int &l, const int &base)
{
 u64 hash_pow_l = 1;
 for (int i = 1; i <= l; i++)
  hash_pow_l *= base;

 int li_n = 0;
 static u64 li[MaxN];

 u64 val = 0;
 for (int i = 0; i < l; i++)
  val = val * base + s[i] - 'a';
 li[li_n++] = val;
 for (int i = l; i < n; i++)
 {
  val = val * base + s[i] - 'a';
  val -= (s[i - l] - 'a') * hash_pow_l;
  li[li_n++] = val;
 }

 sort(li, li + li_n);
 li_n = unique(li, li + li_n) - li;
 return li_n;
}

hzhwcmhf当然知道怎么卡啦!但是他想考考你。

Input

没有输入。

Output

你需要输出一组数据使得VFleaKing的代码WA掉。我们会使用Special Judge检查你的结果的正确性。
输出文件共两行。
第一行两个用空格隔开的数n、l。
第二行是一个长度为n的字符串。只能包含'a'~'z'。
需要保证1 <= n <= 10^5, 1 <= l <= n,
不符合以上格式会WA。
不要有多余字符,很可能导致你WA。

Sample Input

没有

Sample Output

8 4

buaabuaa

(当然这个输出是会WA的)



HINT

orz 波兰人 & fotile96 & sillycross

这题要一定的数论知识(其实不要……)

如果s[1]=1 s[i]=s[i-1]+s[i-1].flip(1...size)

则有

strlen(s[i])=2^(i-1)

若设f[i]=hash(s[i])-(hash(!s[i]))=2^k * t (t是奇数)

则易证(把hash值有base带,慢慢算……)

f[i]=f[i-1]*(base^[2^(i-2)]-1)

∵2^i-1=(2^(i-1)-1)*(2^(i-1)+1),

所以k很大。  

如果base是偶数,那么只要最高位不同,其它都相同让其溢出就行。


#include<cstdio>
#include<iostream>
#include<functional>
#include<bitset>
#include<string>
using namespace std;
#define MAXN (100000+10)
int n,l;
bitset<MAXN> s;
int main()
{
	n=MAXN-10;
	int bin=1;
	s[1]=1;
	for (int i=2;i<=13;i++,bin<<=1)
	{
		for(int j=bin+1;j<=bin*2;j++)
			s[j]=s[j-bin]^1;
	}
	cout<<n<<' '<<bin/2<<endl;
	for (int i=1;i<=bin;i++)
	{
		if (s[i]) cout<<'a';
		else cout<<'b';
	}
	cout<<'b';
	for (int i=bin+2;i<=n;i++) cout<<'a';

	cout<<endl;
	return 0;
}

PE 47(Distinct primes factors-Python数组)

Distinct primes factors

Problem 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

Answer:
134043
Completed on Sat, 6 Apr 2013, 05:40

Go to the thread for problem 47 in the forum.

本题考察Python中数组的运用:
n=1000000
a=[0 for i in range(n+1)]
i=2
while i<=n:
    if (a[i]==0):
        j=2*i
        while j<n:
            a[j]=a[j]+1
            j+=i
    i+=1
for i in range(1,n+1-3):
    if (a[i]==4 and a[i+1]==4 and a[i+2]==4 and a[i+3]==4):
        print i

UVA 11538(Chess Queen-矩阵对角线长度)

Problem A
Chess Queen
Input:
Standard Input

Output: Standard Output

 

王后互相攻击的前提是在一行,一列,或一对角线。:

 

在 (NxM) 的棋盘上 2 王后互相攻击,求方案数.

 

Input

 

输入数据不超过 5000 行 ,每行为M and N (0< M, N£106) ,数据以0 0结尾.

 

Output

 

每行一个整数表示方案数,保证它在u64范围内.

 

Sample Input                              Output for Sample Input

2 2

100 223

2300 1000

0 0

12

10907100

11514134000                                                                        

 

Problemsetter: Shahriar Manzoor

Special Thanks to: Mohammad Mahmudur Rahman

首先,一个矩形的长宽若为m,n(m>=n)

那么它一个方向的对角线应为1..(n-1)各2条,n有(m-n+1)条

知道这个的化,本题就转化为,在一列一行或一对角线任取2点,有几种取法。

#include<cstdio>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAXN (1000000+10)
unsigned long long n,m;
int main()
{
	while (cin>>n>>m&&n&&m)
	{
		if (n>m) swap(n,m);
		cout<<n*m*(n+m-2)+2*n*(n-1)*(3*m-n-1)/3<<endl;
	}
	return 0;
}



BZOJ 3098(Hash Killer II-生日攻击)

3098: Hash Killer II

Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 66  Solved: 22
[Submit][Status][Discuss]

Description

这天天气不错,hzhwcmhf神犇给VFleaKing出了一道题:
给你一个长度为N的字符串S,求有多少个不同的长度为L的子串。
子串的定义是S[l]、S[l + 1]、... S[r]这样连续的一段。
两个字符串被认为是不同的当且仅当某个位置上的字符不同。

VFleaKing一看觉得这不是Hash的裸题么!于是果断写了哈希 + 排序。
而hzhwcmhf神犇心里自然知道,这题就是后缀数组的height中 < L的个数 + 1,就是后缀自动机上代表的长度区间包含L的结点个数,就是后缀树深度为L的结点的数量。
但是hzhwcmhf神犇看了看VFleaKing的做法表示非常汗。于是想卡掉他。

VFleaKing使用的是字典序哈希,其代码大致如下:
u64 val = 0;
for (int i = 0; i < l; i++)
 val = (val * base + s[i] - 'a') % Mod;
u64是无符号int64,范围是[0, 2^64)。
base是一个常量,VFleaKing会根据心情决定其值。
Mod等于1000000007。
VFleaKing还求出来了base ^ l % Mod,即base的l次方除以Mod的余数,这样就能方便地求出所有长度为L的子串的哈希值。
然后VFleaKing给哈希值排序,去重,求出有多少个不同的哈希值,把这个数作为结果。
其算法的C++代码如下:

typedef unsigned long long u64;

const int MaxN = 100000;

inline int hash_handle(const char *s, const int &n, const int &l, const int &base)
{
 const int Mod = 1000000007;

 u64 hash_pow_l = 1;
 for (int i = 1; i <= l; i++)
  hash_pow_l = (hash_pow_l * base) % Mod;

 int li_n = 0;
 static int li[MaxN];

 u64 val = 0;
 for (int i = 0; i < l; i++)
  val = (val * base + s[i] - 'a') % Mod;
 li[li_n++] = val;
 for (int i = l; i < n; i++)
 {
  val = (val * base + s[i] - 'a') % Mod;
  val = (val + Mod - ((s[i - l] - 'a') * hash_pow_l) % Mod) % Mod;
  li[li_n++] = val;
 }

 sort(li, li + li_n);
 li_n = unique(li, li + li_n) - li;
 return li_n;
}

hzhwcmhf当然知道怎么卡啦!但是他想考考你。

Input

没有输入。

Output

你需要输出一组数据使得VFleaKing的代码WA掉。我们会使用Special Judge检查你的结果的正确性。
第一行两个用空格隔开的数n、l。
第二行是一个长度为n的字符串。只能包含'a'~'z'。
需要保证1 <= n <= 10^5, 1 <= l <= n,
不符合以上格式会WA。
不要有多余字符,很可能导致你WA。

Sample Input

没有

Sample Output

8 4

buaabuaa

(当然这个输出是会WA的)

HINT

如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。

Source

生日攻击:如果你在n个数中随机选数,那么最多选√n次就能选到相同的数(不考虑Rp broken)

同样的,这题的Hash值在0到1000000007.

那就要选差不多10^5次

唯一注意的是l要取大,使得方案数超过Mod

否则就不可能有2个数有相同的Hash值

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (100000)
int n=MAXN,l=13;
int main()
{
	cout<<n<<' '<<l<<endl;
	for(int i=1;i<=n;i++) cout<<char(rand()%26+'a');
	cout<<endl;
	return 0;
}




POJ 2484(博弈-对称博弈)

A Funny Game
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 3345   Accepted: 1960

Description

Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 <= n <= 106) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, leaving all other coins untouched. At least one coin must
be removed. Players alternate moves with Alice starting. The player that removes the last coin wins. (The last player to move wins. If you can't move, you lose.) 
 

Note: For n > 3, we use c1, c2, ..., cn to denote the coins clockwise and if Alice remove c2, then c1 and c3 are NOT adjacent! (Because there is an empty place between c1 and c3.) 

Suppose that both Alice and Bob do their best in the game. 
You are to write a program to determine who will finally win the game.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (1 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input. 

Output

For each test case, if Alice win the game,output "Alice", otherwise output "Bob". 

Sample Input

1
2
3
0

Sample Output

Alice
Alice
Bob

Source

POJ Contest,Author:Mathematica@ZSU

博弈第一招——对称博弈。

思路:无论对方怎么取,我都取与它对称(或者相反/一样的)

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
	int n;
	while(scanf("%d",&n)&&n)
	{
		if (n>=3) cout<<"Bob"<<endl;
		else cout<<"Alice"<<endl;
	}
	return 0;
}

POJ 2362(Square-搜索剪枝1-相对顺序)

Language:
Square
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 17066   Accepted: 5878

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

Sample Output

yes
no
yes

Source

《搜索是怎样剪枝的-1》

1.只要找到3条边。

2.从大到小顺序找。

3.每次搜边时要确定边的相对顺序唯一(直接从TLE→秒)


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXM (20+10)
int tt,n,a[MAXM],cnt,len;
bool b[MAXM],flag;
bool dfs(int l,int x,int pre)
{
//	cout<<l<<' '<<x<<' '<<kth<<endl;
	if (x==len) {l++;x=0;pre=n-1;}
	if (l==4)
	{
		return 1;
	}
	for(int i=pre-1;i;i--)
		if (!b[i]&&x+a[i]<=len)
		{
			b[i]=1;
			if (dfs(l,x+a[i],i)) return 1;
			b[i]=0;
		//	if (!x) return 0;
		}
	return 0;
}
int main()
{
	scanf("%d",&tt);
	while (tt--)
	{
		cnt=0;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			cnt+=a[i];b[i]=0;
		}
		sort(a+1,a+1+n);
		if (n<4||cnt%4||a[n]>cnt/4)
		{
			printf("non");continue;
		}
		b[n]=1;len=cnt/4;
		if (dfs(1,a[n],n))
		{
			printf("yesn");
		}
		else printf("non");
	}
	return 0;
}