Monthly Archives: 3 月 2013

UVA 11292(Dragon of Loowater-勇者斗恶龙)

Posted on by

Problem C: The Dragon of Loowater

Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major problem.

The shores of Rellau Creek in central Loowater had always been a prime breeding ground for geese. Due to the lack of predators, the geese population was out of control. The people of Loowater mostly kept clear of
the geese. Occasionally, a goose would attack one of the people, and perhaps bite off a finger or two, but in general, the people tolerated the geese as a minor nuisance.

One day, a freak mutation occurred, and one of the geese spawned a multi-headed fire-breathing dragon. When the dragon grew up, he threatened to burn the Kingdom of Loowater to a crisp. Loowater had a major problem.
The king was alarmed, and called on his knights to slay the dragon and save the kingdom.

The knights explained: "To slay the dragon, we must chop off all its heads. Each knight can chop off one of the dragon's heads. The heads of the dragon are of different sizes. In order to chop off a head, a knight
must be at least as tall as the diameter of the head. The knights' union demands that for chopping off a head, a knight must be paid a wage equal to one gold coin for each centimetre of the knight's height."

Would there be enough knights to defeat the dragon? The king called on his advisors to help him decide how many and which knights to hire. After having lost a lot of money building Mir Park, the king wanted to minimize
the expense of slaying the dragon. As one of the advisors, your job was to help the king. You took it very seriously: if you failed, you and the whole kingdom would be burnt to a crisp!

Input Specification:

The input contains several test cases. The first line of each test case contains two integers between 1 and 20000 inclusive, indicating the number n of heads that the dragon has, and the number m of
knights in the kingdom. The next n lines each contain an integer, and give the diameters of the dragon's heads, in centimetres. The following m lines each contain an integer, and specify the heights of the knights of Loowater, also in centimetres.

The last test case is followed by a line containing:

0 0

Output Specification:

For each test case, output a line containing the minimum number of gold coins that the king needs to pay to slay the dragon. If it is not possible for the knights of Loowater to slay the dragon, output the line:

Loowater is doomed!

Sample Input:

2 3
5
4
7
8
4
2 1
5
5
10
0 0

Output for Sample Input:

11
Loowater is doomed!

让最差的骑士优先杀最差的，

否则这个骑士不取。

可以证明这样取最优。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
int n,m,a[MAXN],b[MAXN];
int main()
{
	while (scanf("%d%d",&n,&m)&&n&&m)
	{
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		for (int i=1;i<=m;i++) scanf("%d",&b[i]);
		sort(a+1,a+n+1);sort(b+1,b+m+1);
		int i=1,j=1,cost=0;
		for (;i<=n&&j<=m;i++,j++)
		{
			if (b[j]>=a[i]) cost+=b[j];
			else i--;
		}
		if (i>n) cout<<cost<<endl;
		else cout<<"Loowater is doomed!n";
	}
	return 0;
}

人偶师(Gauss消元xor版-多解)

Posted on by

Problem 2 人偶师(alice.cpp/c/pas)

【题目描述】

n点m双向边的图，每个点有2个状态：开和关。每次操作改变一个点的状态，以及与其有边直接相连的点的状态。问开启所有点至少需要多少次操作。

【输入格式】

第一行2个整数n,m。

第二行n个整数，第i个数表示第i点的状态，0为关，1为开。

第3..m+2行，每行2个整数a,b，表示a和b直接相连，同一条边不会出现多次。

【输出格式】

第一行一个整数k表示最少的操作次数，所有数据保证至少有一组可行解。

第二行k个整数，表示操作的点的编号。

【样例输入】

4 3

1 1 0 0

2 3

1 3

2 4

【样例输出】

3

1 2 3

【数据范围】

对于30%的数据，1<=n<=10，0<=m<=40

对于60%的数据，1<=n<=30，0<=m<=100

对于100%的数据，1<=n<=40，0<=m<=500

这题还是高斯消元xor.

不同的是要考虑多解. 

高斯消元多解考虑方法：

Gauss();

dfs(n,1)//把值往回代

如果遇到a[i][i]==0,则分情况dfs.

这样做的好处是O(2^n)  

如果求出所有情况再往回代就是O(n^2*2^n) 


#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAXN (40+2)
#define MAXM (500+10)
int a[MAXN][MAXN];
int ans[MAXN],tot=MAXN,tot2=0,ans2[MAXN];
int n,m;
/*
void print(int a[MAXN][MAXN],int _n)
{
	for (int i=1;i<=_n;i++)
	{
		for (int j=1;j<=n+1;j++)
			printf("%d ",a[i][j]);
		printf("n");
	}
	printf("===n");
}

void res(int a[MAXN][MAXN])
{
	int tot2=0;
	for (int i=1;i<=n;i++) if (a[i][n+1]) ans2[++tot2]=i;
	if (tot2<tot)
	{
		tot=tot2;
		memcpy(ans,ans2,(tot+1)*sizeof(int));
	}
}
*/
void gauss()
{
	for (int i=1;i<=n;i++)
	{
		if (a[i][i]==0)
			for (int j=i+1;j<=n;j++) if (a[j][i]) {for (int k=1;k<=n+1;k++) swap(a[j][k],a[i][k]);break;}
		if (a[i][i]==0)	continue;
		for (int j=1;j<=n;j++)
			if (a[j][i]&&j!=i)
			{
				for (int k=1;k<=n+1;k++) a[j][k]^=a[i][k];
			}
//		print(a,n);
	}
//	res(a);
}
int uknow[MAXN],uq[MAXN],un=0;
bool b[MAXN]={0};
void dfs(int i,int tot2)
{
	if (tot2>=tot) return;
	if (i==0)
	{
		if (tot2<tot)
		{
			tot=tot2;
			memcpy(ans,ans2,sizeof(tot)*(tot+1));
		}
		return;
	}
	ans2[tot2+1]=i;
	if (a[i][i])
	{
		bool flag=a[i][n+1];
		for (int j=i+1;j<=n;j++) if (a[i][j]&b[j]) flag^=1;
		b[i]=flag;
		dfs(i-1,tot2+flag);
	}
	else
	{
		b[i]=1;
		dfs(i-1,tot2+1);
		b[i]=0;
		dfs(i-1,tot2);
	}

}
int main()
{
	freopen("alice.in","r",stdin);
	freopen("alice.out","w",stdout);
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i][n+1]);
		a[i][n+1]^=1;
		a[i][i]=1;

	}
	for (int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		a[u][v]=a[v][u]=1;
	}
//	print();
//	memcpy(a2,a,sizeof(a));
	gauss();
//	print(a,n);
	for (int i=1;i<=n;i++)
		if (!a[i][i]) uknow[++un]=i;
	dfs(n,0);
//	sort(ans+1,ans+1+tot);
	printf("%dn",tot);
	for (int i=1;i<tot;i++) printf("%d ",ans[i]);
	printf("%dn",ans[tot]);
	return 0;
}

POJ 1091(跳蚤-扩展欧几里德有解推论+容斥原理)

Posted on by
Language:
跳蚤
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 6911   Accepted: 1951

Description

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 

Input

两个整数N和M(N <= 15 , M <= 100000000)。

Output

可以完成任务的卡片数。

Sample Input

2 4

Sample Output

12

Hint

这12张卡片分别是： 
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4), 
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4) 

Source

HNOI 2001

假设

a1x1+a2x2+--anxn+a(n+1)M=1

则(a1,a2,..an,M)=1

所以用容斥原理计算出gcd≠1的情况的总数

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<functional>
using namespace std;
#define MAXN (15)
#define MAXM (100000000)
int n,m;
long long ans=0,temp=0;
int a[MAXM],tot=0;
long long pow2(long long a,int b)
{
	if (b==1) return a;
	else if (b%2)
	{
		long long p=pow2(a,b/2);
		return p*p*a;
	}
	else
	{
		long long p=pow2(a,b/2);
		return p*p;
	}
}
void dfs(int j,int c,int cost,int l)
{
	if (c==l)
	{
		int p=m/cost;
		if (l&1) ans+=pow2(p,n);
		else ans-=pow2(p,n);
		return;
	}
	for (int i=j+1;i<=tot+1-l+c;i++)
		dfs(i,c+1,cost*a[i],l);



}
int main()
{
	scanf("%d%d",&n,&m);
	int m2=m;
	for (int i=2;i<=(int)sqrt((double)m2);i++)
		if (0==m2%i)
		{
			a[++tot]=i;
			while (0==m2%i) m2/=i;
		}
	if (m2^1) a[++tot]=m2;
//	for (int i=1;i<=tot;i++) cout<<a[i]<<' ';
	for (int i=1;i<=tot;i++) dfs(0,0,1,i);
//	ans=pow(m,n)-ans;
	printf("%lldn",(long long)pow2(m,n)-ans);


	return 0;
}

POJ 1330(Nearest Common Ancestors-Lca模板题)

Posted on by
Nearest Common Ancestors
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 13559   Accepted: 7236

Description

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below: 

 
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor
of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node
x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common
ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is. 

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest
common ancestor of y and z is y. 

Write a program that finds the nearest common ancestor of two distinct nodes in a tree. 

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,...,
N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers
whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

Sample Input

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

Sample Output

4
3

Source

Taejon 2002


Rt,纯粹无聊写的……(其实至今为止就写过2个………("▔□▔)/)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (10000+10)
#define Li (17)
int t,n,father[MAXN][Li];
int edge[MAXN],pre[MAXN],next[MAXN],size=0;
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=pre[u];
	pre[u]=size;
}

int queue[MAXN],deep[MAXN],bin[Li];
void bfs()
{
	int head=1,tail=1;
	for (int i=1;i<=n;i++)
		if (!father[i][0]) {queue[1]=i;deep[i]=1;break;}
	while (head<=tail)
	{
		int &u=queue[head];
		for (int i=1;i<Li;i++)
		{
			father[u][i]=father[father[u][i-1]][i-1];
			if (father[u][i]==0) break;
		}
		for (int p=pre[u];p;p=next[p])
		{
			int &v=edge[p];
			deep[v]=deep[u]+1;
			queue[++tail]=v;
		}
		head++;
	}
}
int lca(int x,int y)
{
	if (x==y) return x;
	if (deep[x]<deep[y]) swap(x,y);
	int t=deep[x]-deep[y];
	for (int i=0;i<Li;i++)
		if (bin[i]&t)
		{
			x=father[x][i];
		}
	int i=Li-1;
	while (x^y)
	{
		while (father[x][i]==father[y][i]&&i) i--;
		x=father[x][i];y=father[y][i];
	}
	return x;
}
int main()
{
//	freopen("poj1330.in","r",stdin);
	scanf("%d",&t);
	for (int i=0;i<Li;i++) bin[i]=1<<i;

	while (scanf("%d",&n)!=EOF)
	{
		memset(pre,0,sizeof(pre));size=0;
		memset(father,0,sizeof(father));
		for (int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			father[v][0]=u;
			addedge(u,v);
		}
		bfs();
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%dn",lca(x,y));

	}
	return 0;
}

BZOJ 1977([BeiJing2010组队]次小生成树 Tree-LCA的位运算)

Posted on by

1977: [BeiJing2010组队]次小生成树 Tree

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1176  Solved: 234
[Submit][Status][Discuss]

Description

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法 等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一 个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么 需要满足：(value(e) 表示边 e的权值) 这下小
C 蒙了，他找到了你，希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值 为z。

Output

包含一行，仅一个数，表示严格次小生成树的边权和。(数 据保证必定存在严格次小生成树)

Sample Input

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

Sample Output

11

HINT

数据中无向图无自环； 
50% 的数据N≤2 000 M≤3 000； 
80% 的数据N≤50 000 M≤100 000； 
100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9
。

Source

这题的关键就在于求Lca,记录路径上的最小与严格次小值.

用f[i][j]表示i的第2^j个儿子(0 表示 不存在)

那么f[i][j]=f[ f[i][ j-1] ][j-1]

dp[i][j]和dp0[i][j]表示点i到f[i][j]的最小和严格次小值（不存在=-1），那么只需特判即可.

int lca(int x,int y,int &nowdp,int &nowdp0)
{
	if (deep[x]<deep[y]) swap(x,y);
	int t=deep[x]-deep[y]; //差的数量
	for (int i=0;t;i++)
		if (t&bin[i])   //转化为位运算 bin[i]表示2<<i 把t看成2进制
		{
			x=f[x][i];
			t-=bin[i];
		}
	int i=Li-1; //Li 表示 最高存到2^(Li-1)个父亲
	while (x^y) //x和y不相等时
	{
		while (f[x][i]==f[y][i]&&i) i--; //当i==0时只能向上跳
		x=f[x][i];y=f[y][i];
	}
}

程序：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (100000+10)
#define MAXM (600000+10)
#define Li (17)
#define INF (2000000000)
int edge[MAXM],pre[MAXM],weight[MAXM],next[MAXM],size=0;
int addedge(int u,int v,int w)
{
	edge[++size]=v;
	weight[size]=w;
	next[size]=pre[u];
	pre[u]=size;
}
int addedge2(int u,int v,int w)
{
	addedge(u,v,w);
	addedge(v,u,w);
}
int f[MAXN][Li]={0},dp[MAXN][Li]={0},dp0[MAXN][Li]={0},deep[MAXN],n,m;
struct E
{
	int u,v,w;
	friend bool operator<(E a,E b){return a.w<b.w;	}
}e[MAXM];
bool b[MAXM],vis[MAXN];
int queue[MAXN],head,tail;
void bfs()
{
	memset(vis,0,sizeof(vis));
	head=tail=1;queue[1]=1;vis[1]=1;deep[1]=0;
	while (head<=tail)
	{
		int &u=queue[head];
		if (u!=1)
		{
			for (int i=1;i<17;i++)
			{
				if (f[u][i-1])
				{
					f[u][i]=f[f[u][i-1]][i-1];
				}
				if (f[u][i]==0) break;
				if (f[u][i])
				{
					dp[u][i]=max(dp[u][i-1],dp[f[u][i-1]][i-1]);
				}
				if (i==1)
				{
					if (dp[u][0]!=dp[f[u][0]][0]) dp0[u][1]=min(dp[u][0],dp[f[u][0]][0]);
					else dp0[u][1]=-1;
				}
				else
				{
					dp0[u][i]=max(dp0[u][i-1],dp0[f[u][i-1]][i-1]);
					if (dp[u][i-1]!=dp[f[u][i-1]][i-1]) dp0[u][i]=max(dp0[u][i],min(dp[u][i-1],dp[f[u][i-1]][i-1]));
				}
			}
		}
		for (int p=pre[u];p;p=next[p])
		{
			int &v=edge[p];
			if (!vis[v])
			{
				queue[++tail]=v;
				vis[v]=1;deep[v]=deep[u]+1;
				f[v][0]=u;dp[v][0]=weight[p];dp0[v][0]=-1;
			}
		}
		head++;
	}
}
int bin[Li];
void check(int &nowdp,int &nowdp0,int c)
{
	if (c<=nowdp0) return;
	else if (nowdp0<c&&c<nowdp) nowdp0=c;
	else  if (c==nowdp) return;
	else if (nowdp<c) {nowdp0=nowdp;nowdp=c;}
}
int lca(int x,int y,int &nowdp,int &nowdp0)
{
	nowdp=nowdp0=-1;
	if (deep[x]<deep[y]) swap(x,y);
	int t=deep[x]-deep[y];
	for (int i=0;t;i++)
		if (t&bin[i])
		{
			check(nowdp,nowdp0,dp[x][i]);
			check(nowdp,nowdp0,dp0[x][i]);
			x=f[x][i];
			t-=bin[i];
		}
	int i=Li-1;
	while (x^y)
	{
		while (f[x][i]==f[y][i]&&i) i--;
		check(nowdp,nowdp0,dp[x][i]);
		check(nowdp,nowdp0,dp0[x][i]);
		check(nowdp,nowdp0,dp[y][i]);
		check(nowdp,nowdp0,dp0[y][i]);
		x=f[x][i];y=f[y][i];
	}
}
int father[MAXN];
long long sum_edge=0;
int getfather(int x)
{
	if (father[x]==x) return x;
	father[x]=getfather(father[x]);
	return father[x];
}
void union2(int x,int y)
{
	father[father[x]]=father[father[y]];
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) father[i]=i;
	memset(b,0,sizeof(b));
	memset(next,0,sizeof(next));
	for (int i=0;i<Li;i++) bin[i]=1<<i;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+1+m);
	for (int i=1;i<=m;i++)
	{
		if (getfather(e[i].u)!=getfather(e[i].v)) {union2(e[i].u,e[i].v);addedge2(e[i].u,e[i].v,e[i].w);sum_edge+=e[i].w;	}
		else b[i]=1;
	}
	bfs();

	long long mindec=-1;
	for (int i=1;i<=m;i++)
		if (b[i])
		{
			int nowdp,nowdp0;
			lca(e[i].u,e[i].v,nowdp,nowdp0);
			if (nowdp==e[i].w) nowdp=nowdp0;
			if (nowdp==-1) continue;
			if (mindec==-1||mindec>e[i].w-nowdp) mindec=e[i].w-nowdp;
		}
	printf("%lldn",sum_edge+mindec);
	return 0;
}





POJ 3070(Fibonacci-矩阵幂)

Posted on by
Language:
Fibonacci
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6733   Accepted: 4765

Description

 Fibonacci integer sequence指 F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. eg:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Fibonacci 的矩阵乘法求法如下

.

Given an integer n, 求 Fn mod 10000.

Input

多组数据,每行一个 n (where 0 ≤ n ≤ 1,000,000,000). 数据以 −1 结尾.

Output

对每组数据打印一行 Fn mod 10000).

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

Hint

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

.

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

.

Source

Stanford Local 2006

正宗矩阵幂练手题。

做了这题就差不多理解矩阵乘法了。

补充：递归一般能用矩阵乘法，如f[i]=g(f[i-1],f[i-2])...

    但是规划不行，如f[i]=max(....)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<functional>
using namespace std;
#define MAXN (1000000000)
#define F (10000)
struct M
{
	int a[3][3];
	M(int i){a[1][1]=a[1][2]=a[2][1]=1;a[2][2]=0;	}
	M(){memset(a,0,sizeof(a));	}
	friend M operator*(M a,M b)
	{
		M c;
		for (int i=1;i<=2;i++)
			for (int j=1;j<=2;j++)
				for (int k=1;k<=2;k++)
				{
					c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%F;
				}
		return c;
	}
	friend M pow(M a,int b)
	{
		if (b==1)
		{
			M c(1);
			return c;
		}
		else
		{
			M c=pow(a,b/2);
			c=c*c;
			if (b%2) return c*a;
			return c;
		}
	}
};
int n;
int main()
{
	while (cin>>n&&n!=-1)
	{
		if (n==0) printf("0n");
		else
		{
			M a=pow(M(1),n);
			printf("%dn",a.a[1][2]);
		}
	}
}

FZU 1922(非主流-0/1预处理统计个数)

Posted on by
Problem 1922 非主流

Accept: 172    Submit: 538
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

非主流指不属于主流的事物，如文化上的次文化，宗教上的异端，人群中的异类等。非主流是相对于主流而存在概念。一个事物既可以从非主流变成主流，也可以从主流变为非主流。因此，没有绝对的主流，也不会有绝对的非主流。

福大新校区的周围有若干个养鸭场，当然鸭群里面也有另类的。养鸭场的老板认为，这些另类的鸭子，要么可以卖个好价钱，要么一文不值。

我们定义每只鸭子的特征为一个一维的0-1向量如：

鸭子a1在这三只鸭子里的另类度为：dist (a1,a1)+dist (a1,a2)+dist (a1,a3)。

定义dist运算为：

dist (a1,a1)= (|1-1|+|0-0|+|0-0|+|1-1|+|0-0|) = 0

dist (a1,a2) = (|1-0|+|0-1|+|0-0|+|1-0|+|0-1|) = 4;

dist (a1,a3) = (|1-0|+|0-0|+|0-1|+|1-0|+|0-1|) = 4;

就得到鸭子a1在这三只鸭子里的另类度为8。

另类的鸭子越多，风险就越大，因此，养鸭场的老板希望可以确定他的鸭群里面到底有多少另类的鸭子。

Input

首先第一行为T，表示有T组数据。接下来为每组数据的结构：

每组数据第一行为空格隔开的三个整数n、m和p。n表示有n只鸭子(2 <= n <= 10,000)，m表示这群鸭子有m个特征值(5 <= m <= 200)，p表示另类度的界限，认为大于等于p的另类度的鸭子就为另类的鸭子(0 <= p <= 2,000,000)。

接下来n行，每行有m个用空格隔开的0或1数字，表示鸭子的特征值。

Output

对于每组数据输出一行先输出组数(从1开始)，接着输出该群鸭子中另类的鸭子数。

Sample Input

13 5 81 0 0 1 00 1 0 0 10 0 1 0 1

Sample Output

Case 1: 1

Source

FOJ有奖月赛-2010年06月

这题要注意将0/1合并处理，统计0/1在每个组别的出现次数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<functional>
using namespace std;
#define MAXN (10000+10)
#define MAXM (200+10)
#define MAXP (2000000)
int t,n,m,p;
int a[MAXN][MAXM],d[MAXM];
int main()
{
	scanf("%d",&t);
	for (int tt=1;tt<=t;tt++)
	{
		memset(d,0,sizeof(d));
		scanf("%d%d%d",&n,&m,&p);
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				scanf("%d",&a[i][j]);
				d[j]+=a[i][j];
			}
		int ans=0;
		for (int i=1;i<=n;i++)
		{
			int tot=0;
			for (int j=1;j<=m;j++) tot+=(a[i][j])?n-d[j]:d[j];
			if (tot>=p) ans++;
		}

		printf("Case %d: %dn",tt,ans);
	}
	return 0;
}

FZU 1040(基因序列相似性问题-CLCS)

Posted on by
Problem 1040 基因序列相似性问题

Accept: 59    Submit: 548
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Genotype 是一个有限的基因序列集。它的每个成员都是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。一个基因种类可以分化成为若干新的基因种类。这种分化一般呈树状结构。树根处的基因序列称为母序列。基因序列中含有母序列的基因子序列称为本质基因子序列。生物信息学家们在研究Genotype 基因序列时，需要研究同一种类基因序列的相似性。对于同一种类的2个基因序列X和Y，已知它们的母序列P，基因序列X和Y的最长公共本质基因子序列给出其相似性的准确刻画。为了有效地分析基因序列的相似性，科学家们希望设计出一个高效的计算程序，能对给定的基因序列X，Y和它们的母序列P，快速计算出基因序列X和Y的最长公共本质基因子序列的长度。

编程任务:
给定基因序列X，Y和母序列P，计算出基因序列X和Y的最长公共本质基因子序列的长度。

Input

输入数据的前3行中每行有一个正整数，分别表示序列X，Y和P的长度m，n和r（1≤m,n,r≤1000）。接下来的3行给出序列X，Y和P。

Output

在屏幕上输出基因序列X和Y的最长公共本质基因子序列的长度。如果基因序列X和Y没有以P为母序列的公共本质基因子序列，则输出0。

Sample Input

331ABCBCAA

Sample Output

1

这题是为了找省选题无意发现的，原问题的加强版。

解法：

首先我有一个用i滚动的做法，反正是T了，正误不明。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
	freopen("fzu1040.out","r",stdin);
	while (scanf("%d%d%d",&n,&m,&p)==3)
	{
		scanf("%s%s%s",a+1,b+1,c+1);
		memset(f,0,sizeof(f));
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)
				for (int k=0;k<=min(i,j);k++)
				{
					f[i%2][j][k]=max(f[i%2][j-1][k],f[(i-1)%2][j][k]);
					if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(i-1)%2][j-1][k-1]||k==1)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k-1]+1,f[i%2][j][k]);
					if ((a[i]==b[j])&&(f[(i-1)%2][j-1][k]||k==0)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k]+1,f[i%2][j][k]);
				}
			for(int j=1;j<=m;j++)
				for (int k=1;k<=p;k++)
					f[(i+1)%2][j][k]=0;
		}
	if (f[n%2][m][p]<p) cout<<"0"<<endl;
	else cout<<f[n%2][m][p]<<endl;
	}
	return 0;
}

找到反例请回复我.


再来说说正解(输出时记得输的是f[p%2][n][m]不是f[k%2][n][m]，变量名乱设害死人）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
//	freopen("fzu1040.out","r",stdin);
	while (scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		scanf("%s%s%s",a+1,b+1,c+1);
		memset(f,0,sizeof(f));
		int k=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
				else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
			}
		bool flag=1;
		int ta=MAXN,tb=MAXN,mina=1,minb=1;
		for (int k=1;k<=p&&flag;k++)
		{
			flag=0;
			for (int i=mina-1;i<=n;i++)
				for (int j=minb-1;j<=m;j++)
					f[k%2][i][j]=0;
			for (int i=mina;i<=n;i++)
				for (int j=minb;j<=m;j++)
				{
					f[k%2][i][j]=0;
					if ((a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
					{
						f[k%2][i][j]=f[(k%2)^1][i-1][j-1]+1;
						flag=1;ta=min(ta,i);tb=min(tb,j);
					}
					else if (a[i]==b[j]&&b[j]==c[k]) continue;
					else if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
					else if (a[i]==b[j]) continue;
					else f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
				}
			mina=ta;minb=tb;
			ta=tb=MAXN;
		}
		/*
		if (!flag)
		{
			if (f[k%2][n][m]>=k) while (1);
		}
		*/
		if (!flag) printf("0n");
		else printf("%dn",f[p%2][n][m]);
	}
	return 0;
}

很直观的Dp。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
//	freopen("fzu1040.out","r",stdin);
	while (scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		scanf("%s%s%s",a+1,b+1,c+1);
		memset(f,0,sizeof(f));
		int k=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
				else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
			}
		bool flag=1;
		int ta=MAXN,tb=MAXN,mina=1,minb=1;
		for (int k=1;k<=p&&flag;k++)
		{
			flag=0;
			for (int i=mina-1;i<=n;i++)
				for (int j=minb-1;j<=m;j++)
					f[k%2][i][j]=0;
			for (int i=mina;i<=n;i++)
				for (int j=minb;j<=m;j++)
				{

					f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
					if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
					{
						f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);
						flag=1;ta=min(ta,i);tb=min(tb,j);
					}
					if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
				}
			mina=ta;minb=tb;
			ta=tb=MAXN;
		}
		/*
		if (!flag)
		{
			if (f[k%2][n][m]>=k) while (1);
		}
		*/
		if (!flag) printf("0n");
		else printf("%dn",f[p%2][n][m]);
	}
	return 0;
}

要考虑从f[k-1][i-1][j-1],f[k][i-1][j-1],f[k][i-1][j],f[k][i][j-1]转移的情况,输出记得清0.

事实上，关于数组清0部分，我们还可以做得更好

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
//	freopen("fzu1040.out","r",stdin);
	while (scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		scanf("%s%s%s",a+1,b+1,c+1);
		memset(f,0,sizeof(f));
		int k=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
				else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
			}
		bool flag=1;
		int ta=MAXN,tb=MAXN,mina=1,minb=1;
		for (int k=1;k<=p&&flag;k++)
		{
			flag=0;
			for (int i=mina-1;i<=n;i++)
				f[k%2][i][minb-1]=0;
			for (int j=minb-1;j<=m;j++)
				f[k%2][mina-1][j]=0; //只要把边界情况赋0
			for (int i=mina;i<=n;i++)
				for (int j=minb;j<=m;j++)
				{

					f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
					if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
					{
						f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);
						flag=1;ta=min(ta,i);tb=min(tb,j);
					}
					if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
				}
			mina=ta;minb=tb;
			ta=tb=MAXN;
		}
		if (!flag) printf("0n");
		else printf("%dn",f[p%2][n][m]);
	}
	return 0;
}

不妨把对k=0的特判写在一起

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
//	freopen("fzu1040.out","r",stdin);
	c[0]=' ';
	while (scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		scanf("%s%s%s",a+1,b+1,c+1);
		bool flag=1;
		int ta=MAXN,tb=MAXN,mina=1,minb=1;
		for (int k=0;k<=p&&flag;k++)
		{
			flag=0;
			for (int i=mina-1;i<=n;i++)
				f[k%2][i][minb-1]=0;
			for (int j=minb-1;j<=m;j++)
				f[k%2][mina-1][j]=0;
			for (int i=mina;i<=n;i++)
				for (int j=minb;j<=m;j++)
				{
					f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
					if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
					{
						f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);
						flag=1;ta=min(ta,i);tb=min(tb,j);
					}
					if ((a[i]==b[j])&&(f[k%2][i-1][j-1]||k==0)) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
				}
			mina=ta;minb=tb;
			ta=tb=MAXN;
			if (!k)
			{
				flag=1;mina=minb=1;
			}
		}
		if (!flag) printf("0n");
		else printf("%dn",f[p%2][n][m]);
	}
	return 0;
}


跳跃(处理操作迭代-等价替代)

Posted on by

Problem2 跳跃(jump.cpp/c/pas)

【题目描述】

一开始你位于数轴上的x位置，一次跳跃你可以从x跳跃到（9x+4）mod 1000000007或者（27x+13）mod 1000000007。求跳回到原点的最少跳跃次数。

保证通过有限次跳跃可以回到原点。

【输入格式】

一行一个整数x表示你的初始坐标，保证0<=x<1000000007

【输出格式】

一行一个整数表示最小的跳跃次数。

【样例输入】

555555559

【样例输出】

1

【数据范围】

对于40%的数据，答案<=20

对于100%的数据，答案<=100000

神结论：

9x+4等价于2次3x+1

27x+13等价于3次3x+1

#include<cstdio>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXN (100000)
#define F (1000000007)
long long x;
int main()
{
	freopen("jump.in","r",stdin);
	freopen("jump.out","w",stdout);
	while (scanf("%d",&x)==1)
	{
		int ans=0;
		for (;!((!x)&&ans!=1);x=(3*x+1)%F) ans++;
		printf("%dn",ans/3+bool(ans%3));
	}
	return 0;
}