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;
}

BZOJ 1076([SCOI2008]奖励关-期望dp-从后向前)

Posted on by

1076: [SCOI2008]奖励关

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 328  Solved: 199
[Submit][Status][Discuss]

Description

你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。 宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1次系统都抛出宝物1（这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。 获取第i种宝物将得到Pi分，但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过一次，才能吃第i种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，Pi可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。
假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？

Input

第一行为两个正整数k和n，即宝物的数量和种类。以下n行分别描述一种宝物，其中第一个整数代表分值，随后的整数依次代表该宝物的各个前提宝物（各宝物编号为1到n），以0结尾。

Output

输出一个实数，保留六位小数，即在最优策略下平均情况的得分。

Sample Input

1 2

1 0

2 0

Sample Output



1.500000

HINT

【样例2】 
Input 
6 6 
12 2 3 4 5 0 
15 5 0 
-2 2 4 5 0 
-11 2 5 0 
5 0 
1 2 4 5 0 
Output 
10.023470 
【数据规模】 
1<=k<=100,1<=n<=15，分值为[-10^6,10^6]内的整数。 

Source

期望DP.

根据期望DP 这一步的期望=(上一步的期望+上一步de得分)/k
(k为种类数)

从后往前算是规避不可能状态的常用手段


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (100+10)
#define MAXK (16)
double f[MAXN][(1<<MAXK)-1];
int n,k,p[MAXK+1],d[MAXK+1]={0};
int main()
{
	scanf("%d%d",&n,&k);
	int m=(1<<k)-1;
	for (int i=0;i<MAXN;i++)
		for (int j=0;j<=m;j++) f[i][j]=0.0;
	for (int i=1;i<=k;i++)
	{
		scanf("%d",&p[i]);
		int t;
		while (scanf("%d",&t)!=EOF&&t)
		{
			d[i]|=(1<<(t-1));
		}
	}
	for (int i=n;i;i--)
		for (int j=0;j<=m;j++)
		{
			for (int l=1;l<=k;l++)
				if ((d[l]&j)==d[l])
					f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<(l-1))]+p[l]);//eat or not
					else f[i][j]+=f[i+1][j]; //can't eat
			f[i][j]/=(double)k;
		}
	printf("%.6lfn",f[1][0]);
	return 0;
}


UVA 10905(Children's Game-C的qsort函数和sprintf)

Posted on by

4th IIUC Inter-University Programming
Contest, 2005

A

Children’s Game

Input: standard input
Output: standard output

Problemsetter: Md. Kamruzzaman

给你 N 个正数. 如 123, 124, 56, 90 ,它们可以拼成 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 etc. 有 24 种拼法， 9056124123 最大.

请你找出这个最大的数。

Input

每组数据第一行为 N (≤ 50). 接下来1行有 N 个正数，数据以  0 结尾.

Output

对每组数据，输出最大的拼法.

Sample Input

Output for Sample Input

4
123 124 56 90
5
123 124 56 90 9
5
9 9 9 9 9
0

9056124123
99056124123
99999


按照字符串连起来后（len相等）的字符串比较

值得一提的是qsort中cmp的写法(char[]无法用sort排序)

以及sprintf(占位符随便改，可以将任意类型转换成字符串)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (100+10)
int cmp(const void *a1,const void *b1)
{
	char *a=(char*)a1,*b=(char*)b1;
	char _a[MAXN*2]={0},_b[MAXN*2]={0};
	sprintf(_a,"%s%s",a,b);
	sprintf(_b,"%s%s",b,a);
	return strcmp(_b,_a);
}
int n;
char a[MAXN][MAXN];
int main()
{
	while(scanf("%d",&n)&&n)
	{
		for (int i=1;i<=n;i++) scanf("%s",a[i]);
		qsort(a+1,n,sizeof(a[1]),cmp);
		for (int i=1;i<=n;i++) printf("%s",a[i]);
		printf("n");
	}
	return 0;
}

数位和乘积(高精组合数学)

Posted on by

Problem 3 数位和乘积(digit.cpp/c/pas)

【题目描述】

一个数字的数位和乘积为其各位数字的乘积。求所有的N位数中有多少个数的数位和乘积恰好为K。请注意，这里的N位数是可以有前导零的。比如01，02视为二位数，但是他们的数位和乘积都是0。

【输入格式】

一行两个整数N，K

【输出格式】

一个行一个整数表示结果。

【样例输入】

2 3

【样例输出】

2

【样例输入2】

2 0

【样例输出2】

19

【数据范围】

对于20%：N <= 6。

对于50%：N<=16

存在另外30%：K=0。

对于100%：N <= 50，0 <= K <= 10^9。

法1：

k=0时，ans=10^n-9^n

否则就用记忆化搜索填1..9的个数

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (50+10)
#define F (10000)
int n,k;
struct highn
{
int len,a[900];
highn():len(1){memset(a,0,sizeof(a));}
highn(int x)
{
memset(a,0,sizeof(a));
int i=0;
while (x)
{
a[++i]=x%F;
x/=F;
}
len=i;
}
void print()
{
printf("%d",a[len]);
for (int i=len-1;i;i--)
{
// if (a[i]<10000) printf("0");
if (a[i]<1000) printf("0");
if (a[i]<100) printf("0");
if (a[i]<10) printf("0");
printf("%d",a[i]);
}

}
friend highn operator+(highn& a,highn& b)
{
highn c;
int maxlen=max(a.len,b.len);
for (int i=1;i< =maxlen;i++) { c.a[i]=c.a[i]+a.a[i]+b.a[i]; if (c.a[i]>F)
{
c.a[i+1]+=c.a[i]/F;
c.a[i]%=F;
}
}
c.len=maxlen+1;
while (!c.a[c.len]&&c.len>1) c.len--;
return c;

}
friend highn operator-(highn& a,highn& b)
{
highn c;
int maxlen=a.len;
for (int i=1;i< =maxlen;i++) { c.a[i]+=a.a[i]-b.a[i]; if (c.a[i]<0) { c.a[i+1]--; c.a[i]+=F; } } c.len=maxlen; while (!c.a[c.len]&&c.len>1) c.len--;
return c;
}
friend highn operator*(highn& a,highn& b)
{
highn c;
for (int i=1;i< =a.len;i++) { for (int j=1;j<=b.len;j++) { c.a[i+j-1]+=a.a[i]*b.a[j]; if (c.a[i+j-1]>F)
{
c.a[i+j]+=c.a[i+j-1]/F;
c.a[i+j-1]%=F;
}
}
}
c.len=a.len+b.len+1;
while (!c.a[c.len]&&c.len>1) c.len--;
return c;
}

};
highn pow2(highn a,int b)
{
highn c;
if (!b) return 1;
if (b%2)
{
c=pow2(a,b/2);
c=c*c;
c=c*a;
}
else
{
c=pow2(a,b/2);
c=c*c;
}
return c;
}
int a[11],tot,b[11];
highn ans,C[51][51];
void dfs(int deep,highn rel,int hasget)
{
if (n

法2：

f[i][j][k][l][m]表示填到第i个数,2,3,5,7分别用j,k,l,m个的方案数

考虑后面填1..9的情况(显然不可能填0)

Bug：n=50,C(n,m)最大为C(50,25),可用long long.

----

----

法3：

容易发现

k=2^a*3^b*5^c*7^d时才有解

而且5,7取了当且只当数位为5,7的情况.

2-2,4,6,8

3-3,6,9

5-5

7-7

故可只考虑2,3,不考虑5,7

f[i][j]k]表示i位，取了j个2和k个3后的方案数，

因为可以用1填充，

所以答案=∑f[p][j][k]*C(p,j+k)*C(n,a[5])*C(n-a[5],a[7]) (p<=n-a[5]-a[7])