Category Archives: DefaultCategory

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

稳定性(单向图tarjen)

Posted on by

Problem2 稳定性(cp.cpp/c/pas)

【题目描述】

有2*n个装置，其中奇数编号的为供电装置，偶数编号的为用电装置。

第i*2-1个装置通过单向导线第i*2个装置输送能量（它们称为第i对装置）。除此之外还有m条单向导线。

第i对装置是稳定的，当且仅当：直接连接2者的单向导线损坏时，仍然有一个供电方案使得每个供电装置给一个用电装置供电，且每个用电装置只由一个供电装置供电。

求每对装置稳定与否。

【输入格式】

第一行2个整数n,m。

接下来m行，每行2个整数a、b，表示a往b有一条单向导线。保证a为奇数，b为偶数。

【输出格式】

输出n行，若第i对装置是稳定的，输出“~”，否则输出“@”

 

【样例输入】

2 1

3 2

【样例输出】

@

@

【样例输入2】

2 2

3 2

1 4

【样例输出2】

~

~

【数据范围】

对于20%：N<=10

对于40%：N<=100

对于60%：N<=1000

对于100%：N<=100000，M<=2*N

注意Tarjen模板。

Ps:边最多有300000(原来的n条边+另外m条单向边)

#include<cstdio>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN (200000+10)
#define MAXM (300000+10)
int edge[MAXM],pre[MAXM],next[MAXM],size=0;
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=pre[u];
	pre[u]=size;
}
int t[MAXN],tim=0,dfs[MAXN];
int s[MAXN],tot=0,n,m;
int kind=0,h[MAXN];
bool b[MAXN],numk[MAXN];
void tar(int u)
{
	t[u]=dfs[u]=++tim;b[u]=1;
	s[++tot]=u;
	for (int p=pre[u];p;p=next[p])
	{
		int &v=edge[p];
		if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]);
		else if (!h[v]) dfs[u]=min(dfs[u],t[v]);
	}
	if (dfs[u]==t[u])
	{
		kind++;
		bool flag=0;
		while (s[tot]!=u) h[s[tot--]]=kind,flag=1;
		h[s[tot--]]=kind;
		numk[kind]=flag;
	}
}
int main()
{
	freopen("cp.in","r",stdin);
	freopen("cp.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(pre,0,sizeof(pre));
	memset(b,0,sizeof(b));
	memset(h,0,sizeof(h));
	for (int i=1;i<=n;i++) addedge(2*i-1,2*i);
	for (int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(v,u);
	}
	for (int i=2;i<=2*n;i+=2)
	{
		if (!b[i]) tar(i);
		if (numk[h[i]]) printf("~n");
		else printf("@n");
	}

	return 0;
}

子序列(省略已知值法与挪位得解法)

Posted on by

Problem 1 子序列(subsequence.pas/c/cpp)

【题目描述】

给定一个长度为N（N为偶数）的序列，问能否将其划分为两个长度为N/2的严格递增子序列，

 

【输入格式】

若干行，每行表示一组数据。对于每组数据，首先输入一个整数N，表示序列的长度。之后N个整数表示这个序列。

 

【输出格式】

同输入行数。对于每组数据，如果存在一种划分，则输出“Yes!”，否则输出“No!“。

 

【样例输入】

6 3 1 4 5 8 7

6 3 2 1 6 5 4

【样例输出】

Yes!

No!

【数据范围】

共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9

第一组(30%)：N <= 20

第二组(30%)：N <= 100

第三组(40%)：N <= 2000

一般青年Dp方案：F[i][j][k][l] 表示前i+j位分为一个长度为i以j结尾，一个长度为k以l结尾的序列
是否可行(0,1)

省略已知值：观察发现j和l中至少有一个为a[i+j]

故可省略其中一位

n=2000必跪

文艺青年Dp方案：

挪位得解：把f[i][j][k]中的k挪出来 

原因：显然i和j不变时，我们希望k越小越好

所以记录min(k)，并记录无解情况

O(n^2)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN (2000+10)
#define INF (2139062143)
int n,a[MAXN],f[MAXN][MAXN];
int main()
{
	freopen("subsequence.in","r",stdin);
	freopen("subsequence.out","w",stdout);
	while (scanf("%d",&n)!=EOF)
	{
		memset(f,127,sizeof(f));
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		f[1][1]=-1;
		for (int i=1;i<n;i++)
		{
			for (int j=1;j<=i;j++)
			{
				if (f[i][j]!=INF)
				{
					if (a[i]<a[i+1]) f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);
					if (f[i][j]<a[i+1])
						f[i+1][i-j+1]=min(f[i+1][i-j+1],a[i]);
				}
			}
		}
		/*
		for (int i=0;i<=n;i++)
		{
			for (int j=0;j<=n;j++)
				printf("%d ",f[i][j]);
			printf("n");
		}
		*/
		if (f[n][n>>1]!=INF) printf("Yes!n");
		else printf("No!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<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cctype>
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<hasget) {return;}
	if (deep==0||n==hasget)
	{
		for (int i=1;i<=9;i++) if (b[i]) return;
		ans=ans+rel;
		return;
	}
	else if (deep==9)
	{
		int m=min(n-hasget,b[3]/2);
		for (int i=0;i<=m;i++)
		{
			b[3]-=i*2;
			dfs(8,rel*C[n-hasget][i],hasget+i);
			b[3]+=i*2;
		}
	}
	else if (deep==8)
	{
		int m=min(n-hasget,b[2]/3);
		for (int i=0;i<=m;i++)
		{
			b[2]-=i*3;
			dfs(6,rel*C[n-hasget][i],hasget+i);
			b[2]+=i*3;
		}
	}
	else if (deep==6)
	{
		int m=min(n-hasget,min(b[2],b[3]));
		for (int i=0;i<=m;i++)
		{
			b[2]-=i;b[3]-=i;
			dfs(4,rel*C[n-hasget][i],hasget+i);
			b[2]+=i,b[3]+=i;
		}
	}
	else if (deep==4)
	{
		int m=min(n-hasget,b[2]/2);
		for (int i=0;i<=m;i++)
		{
			b[2]-=i*2;
			dfs(2,rel*C[n-hasget][i],hasget+i);
			b[2]+=i*2;
		}
	}
	else
	{
		if (b[2]+b[3]+b[5]+b[7]+hasget<=n)
		{
			int f[4]={2,3,5,7};
			for (int i=0;i<4;i++)
			{
				rel=rel*C[n-hasget][b[f[i]]];
				hasget+=b[f[i]];
			}
			ans=ans+rel;
			return ;
		}
	}
}
int main()
{
//	highn a=1254321,b=7612345;
//	highn c=pow(a,3);
//	c.print();
	freopen("digit.in","r",stdin);
	freopen("digit.out","w",stdout);
	scanf("%d%d",&n,&k);
	if (!k)
	{
		highn c=pow2(10,n),d=pow2(9,n);
		highn e=c-d;
		e.print();
	}
	else
	{

		memset(a,0,sizeof(a));
		tot=0;
		C[0][0]=1;
		for (int i=1;i<=n;i++)
		{
			C[i][0]=C[i][1]=1;
			for (int j=1;j<=i;j++)
			{
				C[i][j]=C[i-1][j]+C[i-1][j-1];
			}
		}
//		C[16][10].print();

		for(int i=2;i<=9;i++)
		{
			while (k%i==0)
			{
				a[i]++;
				k/=i;
				tot++;
			}
		}
		memcpy(b,a,sizeof(a));
		if (k==1) dfs(9,1,0);
		ans.print();
	}
	cout<<endl;
	return 0;
}

法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])



BZOJ 1507([NOI2003]Editor-块状链表)

Posted on by

1507: [NOI2003]Editor

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 922  Solved: 323
[Submit][Status][Discuss]

Description

很久很久以前，DOS3.x 的程序员们开始对 EDLIN 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器……
多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试）！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？
为了明确任务目标，小明对“文本编辑器”做了一个抽象的定义：
文本：由 0 个或多个字符构成的序列。这些字符的 ASCII 码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。
光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。
文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下六条操作的程序。
如果这段文本为空，我们就说这个文本编辑器是空的。

你的任务是：
 建立一个空的文本编辑器。
 从输入文件中读入一些操作指令并执行。
 对所有执行过的 GET 操作，将指定的内容写入输出文件。

Input

第一行是指令条数 t，以下是需要执行的 t 个操作。其中：
为了使输入文件便于阅读，Insert 操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。
除了回车符之外，输入文件的所有字符的 ASCII 码都在闭区间[32, 126]内。且行尾没
有空格。
这里我们有如下假定：
1. MOVE 操作不超过 50000 个，INSERT 和 DELETE 操作的总个数不超过 4000，PREV 和 NEXT 操作的总个数不超过 200000。
2. 所有 INSERT 插入的字符数之和不超过 2M（1M=1024*1024），正确的输出文件长度不超过 3M 字节。
3. DELETE 操作和 GET 操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。
4. 输入文件没有错误。
对 C++选手的提示：经测试，对最大的测试数据使用 fstream 进行输入有可能会比使用 stdio 慢约 1 秒，因此建议在可以的情况下使用后者。

Output

输出每行依次对应输入文件中每条GET指令的输出。

Sample Input

15

Insert 26

abcdefghijklmnop

qrstuv wxy

Move 16

Delete 11

Move 5

Insert 1

^

Next

Insert 1

_

Next

Next

Insert 4

./.

Get 4

Prev

Insert 1

^

Move 0

Get 22

Sample Output

./.

abcde^_^f./.ghijklmno

这题我是用块状链表做的

块状链表的复杂度大约是O（√n）

一定要尽可能将块分成长度为√tot的，balance()时要把所有的长度分为介于1/2√tot-2√tot之间

另外merge时要注意先把cur移动再重载合并格的长度（不容易查出错,不知为何,加错也能过8个点）

要参考老董的讲解与nocow的模板

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXP (1024*1024)
#define MAXN (2900)
struct block
{
    int n;
    char a[MAXN];
    block *next,*pre;
    block():n(0){next=pre=NULL;}
}*first;
block* q[MAXN];
int size=0,tot=0;
void del(block *x)
{
    q[++size]=x;
    if (x->pre) x->pre->next=x->next;
    if (x->next) x->next->pre=x->pre;
    if (x==first) first=x->next;
}
block *newblock()
{
    if (size) return q[size--];
    block *x=new block();
    return x;
}
void link(block *a,block *b)
{
    if (a) a->next=b;
    if (b) b->pre=a;
}
void spilt(block *x,int nowsize)
{
    if (!nowsize||nowsize==x->n) return;
    block *tmp=x->next;
    x->next=newblock();
    block *x2=x->next;
    x2->n=x->n-nowsize;
    for (int i=1;i<=x2->n;i++) x2->a[i]=x->a[nowsize+i];
    x->n=nowsize;
    link(x2,tmp);
    link(x,x2);
}
struct cursor
{
    int n;
    block *ll;
    cursor():n(0){ll=first; }
    void pre()
    {
        n--;
        if (n<0)
        {
            ll=ll->pre;
            n=ll->n-1;
        }
    }
    void next()
    {
        n++;
        if (n>ll->n)
        {
            ll=ll->next;
            n=1;
        }
    }
    void move(int k)
    {
        n=k,ll=first;
        while (n>ll->n)
        {
            n-=ll->n;
            ll=ll->next;
        }
    }
}cur;
void get(cursor cur,int k)
{
    int p=cur.ll->n-cur.n;
    if (p>=k)
    {
        for (int i=cur.n+1;i<=cur.n+k;i++)
            printf("%c",cur.ll->a[i]);
    }
    else
    {
        for (int i=cur.n+1;i<=cur.ll->n;i++) printf("%c",cur.ll->a[i]);
        cur.ll=cur.ll->next;cur.n=0;
        get(cur,k-p);
    }
}
void merge(block *x)
{
    if (!x->next) return;
    for (int i=1;i<=x->next->n;i++) x->a[x->n+i]=x->next->a[i];
    if (cur.ll==x->next)
    {
        cur.ll=x;
        cur.n+=x->n;
    }
    x->n+=x->next->n;
    del(x->next);
}
void balance()
{
    int maxsize=min(MAXN,(int)sqrt(tot)*2);
    int minsize=(int)sqrt(tot)/2;
    block *x=first;
    while (x)
    {
        while (x->n<minsize||x->n>maxsize)
        {
            if (x->n<minsize)
            {
                merge(x);
                if (!x->next) break;
            //  get(cur,1);
            }
            else
            {
                spilt(x,(x->n)>>1);
                if (cur.ll==x&&cur.n>cur.ll->n)
                {
                    cur.n-=cur.ll->n;
                    cur.ll=cur.ll->next;
                }
            //  get(cur,1);
            }
        }
        x=x->next;
    }
}
void delet(int k)
{
    if (!k) return;
    if (cur.n)
    {
        spilt(cur.ll,cur.n);
        cur.ll=cur.ll->next; cur.n=0;
    }
    while (k>cur.ll->n)
    {
        del(cur.ll);
        k-=cur.ll->n;
        cur.ll=cur.ll->next;
    //  cur.n=0;
    }
    if (k==cur.ll->n)
    {
        cur.ll->n=0;
    }
    else
    {
        spilt (cur.ll,k);
        delet(k);
    }
    balance();
}
void insert(int k)
{
    block *l=newblock();*l=block();
    block *r=l;
    int maxsize=min(MAXN,(int)sqrt(tot));
    for (int i=1;i<=k;i++)
    {
        char c;
        for (scanf("%c",&c);(c<32)||(c>126)||(c=='n');scanf("%c",&c));
        if (r->n>maxsize)
        {
            block *tmp=r;
            r=newblock();*r=block();link(tmp,r);
        }
        r->a[++r->n]=c;
    }
    if (cur.n)
    {
        spilt(cur.ll,cur.n);
        block *tmp=cur.ll->next;
        link(cur.ll,l),link(r,tmp);
    }
    else
    {
        link(cur.ll->pre,l),link(r,cur.ll),cur.ll=l;
        if (first->pre) first=l;
    }
    balance();
}
int main()
{
    first=newblock();cur.ll=first;
    int t;scanf("%d",&t);
    while (t--)
    {
        char s[10];
        scanf("%s",s);
        int k;
        switch(s[0])
        {
            case'M':scanf("%d",&k);cur.move(k);break;
            case'I':scanf("%d",&k);tot+=k;insert(k);break;
            case'D':scanf("%d",&k);tot-=k;delet(k);break;
            case'G':scanf("%d",&k);get(cur,k);printf("n");break;
            case'P':cur.pre();break;
            case'N':cur.next();break;
        }
//      get(cursor(),tot);cout<<endl;
    }
    return 0;
}

UVA 10209(Is This Integration ?-容斥原理)

Posted on by

Problem C
Is This Integration ?
Input: Standard Input
Output: Standard Output
Time Limit: 3 seconds

 

In the image below you can see a square ABCD, where AB = BC = CD = DA = a. Four arcs are drawn taking the four vertexes A, B, C, Das centers and a as the radius. The arc that is drawn taking A as
center, starts at neighboring vertex B and ends at neighboring vertex D. All other arcs are drawn in a similar fashion. Regions of three different shapes are created in this fashion. You will have to determine the total area
if these different shaped regions.  

 

Input

The input file contains a floating-point number a (a>=0 a<=10000) in each line which indicates the length of one side of the square. Input is terminated by end of file.  

 

Output

For each line of input, output in a single line the total area of the three types of region (filled with different patterns in the image above). These three numbers will of course be floating point numbers with three digits after the decimal point. First
number will denote the area of the striped region, the second number will denote the total area of the dotted regions and the third number will denote the area of the rest of the regions.

 

Sample Input:

0.1
0.2
0.3

Sample Output:

0.003 0.005 0.002
0.013 0.020 0.007
0.028 0.046 0.016

Shahriar Manzoor

设中间那块面积为x，四个角的面积为y，四个凹形的面积为z


则有

x+4y+4z=a^2

x+3y+2z=pi/4*a^2

x+2y+z=(pi/3-√3/4)a^2 (2个扇形-中间重叠的三角形)

解出：

x=(1+pi/3-√3)*a^2

y=(pi/12+√3/2-1)*a^2

z=(-pi/6+1-√3/4)*a^2

另：注意pi的精度

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXa (10000)
double a;
const double pi=3.141592653589793;
int main()
{
	while (scanf("%lf",&a)!=EOF)
	{
		printf("%.3lf %.3lf %.3lfn",a*a*(1+pi/3-sqrt(3.0)),a*a*(pi/3+2*sqrt(3.0)-4),a*a*(-2*pi/3+4-sqrt(3.0)));
	}
	return 0;
}