Beyond the Void
BYVoid
NOI 2001 解题报告

NOI2001的题目是[反正切函数的应用][聪明的打字员][陨石的秘密][食物链][炮兵阵地][方程的解数]。

其中[反正切函数的应用][聪明的打字员]较为简单,[陨石的秘密][食物链][炮兵阵地][方程的解数]稍有难度。

[反正切函数的应用]是一个求函数最值的问题,要配合数学知识解决。[聪明的打字员]是广度优先搜索问题。[陨石的秘密]是一个树形动态规划的问题,需要仔细思考。[食物链]用到了并差集。[  炮兵阵地]是个不易看出的动态规划问题。[方程的解数]是搜索问题,需要用哈希表来优化。

[反正切函数的应用]

根据题中公式,可以推出 a=(b*c-1)/(b+c)。由此得出c=(a*b+1)/(b-a)。因为b,c均为正整数,所以b>a。

我们要求b+c最小,设函数y=f(x),自变量x为b的取值,但不限于正整数。则有

  • f(x) = (a*x+1)/(x-a) + x = a + ((1+a^2)/(x-a)) + x

对f(x)求导,得导数

  • f’(x)=1-(1+a^2)/(x-a)^2

f’(x)=0 得出 x = a+(a^2+1)^0.5 或 x = a-(a^2+1)^0.5,由于x>0,取 x = a+(a^2+1)^0.5

且x > a+(a^2+1)^0.5时,f’(x)>0,x < a+(a^2+1)^0.5时,f’(x)<0,所以当x = a+(a^2+1)^0.5时,f(x)取得最小值。

由于b和c都是正整数,只需在x一边寻找距离x最近的整数b,c,b+c即要求的最小值。

/*
 * Problem: NOI2001 arctan
 * Author: Guo Jiabao
 * Time: 2009.3.21 14:18
 * State: Solved
 * Memo: 函数最值问题
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int a,b,c,Ans=0x7FFFFFFF;
int main()
{
	freopen("arctan.in","r",stdin);
	freopen("arctan.out","w",stdout);
	scanf("%d",&a);
	double t=ceil(a+sqrt((double)a*a+1));
	for (;;t--)
	{
		b=(int)(t+0.1);
		long long q=a;
		q=q*b+1;
		if (q%(b-a)==0)
		{
			c=q/(b-a);
			Ans=b+c;
			break;
		}
	}
	printf("%d\n",Ans);
	return 0;
}

[聪明的打字员]

简单的广搜题,对于每个状态,直接按照规则扩展6状态,开一个哈希表判重,直到搜索到结果为止。

/*
 * Problem: NOI2001 clever
 * Author: Guo Jiabao
 * Time: 2009.3.17 13:37
 * State: Solved
 * Memo: BFS
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int LIM=1000000;
using namespace std;
struct state
{
	int s,step,pos;
};
bool used[LIM][7];
int S,T;
int Q_size,Q_head,Q_tail;
state Q[LIM];
state start;
void init()
{
	freopen("clever.in","r",stdin);
	freopen("clever.out","w",stdout);
	scanf("%d%d",&S,&T);
	start.s=S;
	start.pos=1;
	start.step=0;
	Q_head=-1;Q_tail=0;Q_size=0;
}
void Answer(int ans)
{
	printf("%d\n",ans);
	exit(0);
}
void Q_ins(state p)
{
	if (used[p.s][p.pos]) return;
	used[p.s][p.pos]=true;
	if (p.s==T) Answer(p.step);
	Q_size++;
	if (++Q_head==LIM) Q_head=0;
	Q[Q_head]=p;
}
state Q_pop()
{
	state r=Q[Q_tail];
	Q_size--;
	if (++Q_tail==LIM) Q_tail=0;
	return r;
}
void BFS()
{
	state u,v;
	int pos[7],su,sv,tim,p,i;
	Q_ins(start);
	while (Q_size)
	{
		u=Q_pop();
		su=sv=u.s;
		p=u.pos;
		tim=LIM;
		for (i=1;i<=p;i++)
			tim/=10;
		for (i=6;i>=1;i--)
		{
			pos[i]=sv%10;
			sv/=10;
		}
		if (p>1) //swap0
		{
			sv=su;
			sv-=100000*pos[1] + tim*pos[p];
			sv+=tim*pos[1] + 100000*pos[p];
			v.pos=u.pos;
			v.step=u.step+1;
			v.s=sv;
			Q_ins(v);
		}
		if (p<6) //swap1
		{
			sv=su;
			sv-=pos[6] + tim*pos[p];
			sv+=tim*pos[6] + pos[p];
			v.pos=u.pos;
			v.step=u.step+1;
			v.s=sv;
			Q_ins(v);
		}
		if (pos[p]!=9) //up
		{
			sv=su;
			sv+=tim;
			v.pos=u.pos;
			v.step=u.step+1;
			v.s=sv;
			Q_ins(v);
		}
		if (pos[p]!=0) //down
		{
			sv=su;
			sv-=tim;
			v.pos=u.pos;
			v.step=u.step+1;
			v.s=sv;
			Q_ins(v);
		}
		if (p>1) //left
		{
			v.s=u.s;
			v.pos=u.pos-1;
			v.step=u.step+1;
			Q_ins(v);
		}
		if (p<6) //right
		{
			v.s=u.s;
			v.pos=u.pos+1;
			v.step=u.step+1;
			Q_ins(v);
		}
	}
}
int main()
{
	init();
	BFS();
	return 0;
}

[陨石的秘密]

容易看出是动态规划,但是状态转移方程容易考虑不周全。

题目中样例的8种方案为{[]()} {()[]} {}[()] [()]{} []{()} {()}[] (){[]} {[]}() 可以看出每个SS表达式都可以看成由几个小的SS组成,组成方式可能是嵌套或者连接。如果是嵌套(包括仅1层),我们把这个嵌套体看作一个整体部分,称为一个组。则每个SS表达式都是由几个组连接而成了。

设定 F[p1,p2,p3,d]为深度不超过d,包含p1个{},p2个[],p3个()的SS表达式的可能组成的方案数。S[p1,p2,p3,d]为深度不超过d,包含p1个{},p2个[],p3个()的一个组的可能组成的方案数。

则状态转移方程为

S[p1,p2,p3,d]=
{
	0 (p1==p2==p3==0)
	F[p1-1,p2,p3,d-1] (p1&gt;=1)
	F[p1,p2-1,p3,d-1] (p1==0 &amp;&amp; p2&gt;=1)
	F[p1,p2,p3-1,d-1] (p1==0 &amp;&amp; p2==0 &amp;&amp; p3&gt;=1)
}

F[p1,p2,p3,d]=Σ(S[x1,x2,x3,d]*F[p1-x1,p2-x2,p3-x3,d]) (0<=x1<=p1,0<=x2<=p2,0<=x3<=p3且x1,x2,x3不同时为0)

初始条件

  • F[0,0,0,i]=1 (0<=i<=D)

最终的结果就是

  • F[L1,L2,L3,D]-F[L1,L2,L3,D-1]
/* 
 * Problem: NOI2001 secret
 * Author: Guo Jiabao
 * Time: 2009.3.18 13:54
 * State: Solved
 * Memo: 动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=11,MAXD=31,MOD=11380;
using namespace std;
int L1,L2,L3,D,Ans;
int F[MAXL][MAXL][MAXL][MAXD];
int single(int p1,int p2,int p3,int d);
int dp(int p1,int p2,int p3,int d);
void init()
{
	freopen("secret.in","r",stdin);
	freopen("secret.out","w",stdout);
	scanf("%d%d%d%d",&L1,&L2,&L3,&D);
	int p1,p2,p3,d;
	for (d=0;d<=D;d++)
	{
		for (p1=0;p1<=L1;p1++)
			for (p2=0;p2<=L2;p2++)
				for (p3=0;p3<=L3;p3++)
					F[p1][p2][p3][d]=-1;
		F[0][0][0][d]=1;
	}
}
int single(int p1,int p2,int p3,int d)
{
	if (p1>=1)
		return dp(p1-1,p2,p3,d-1);
	else if (p1==0 && p2>=1)
		return dp(p1,p2-1,p3,d-1);
	else
		return dp(p1,p2,p3-1,d-1);
}
int dp(int p1,int p2,int p3,int d)
{
	if (d<0) return 0;
	if (F[p1][p2][p3][d]==-1)
	{
		int x1,x2,x3,y1,y2,y3;
		F[p1][p2][p3][d]=0;
		for (x1=0;x1<=p1;x1++)
			for (x2=0;x2<=p2;x2++)
				for (x3=0;x3<=p3;x3++)
				{
					y1=p1-x1;y2=p2-x2;y3=p3-x3;
					if (x1+x2+x3==0) continue;
					F[p1][p2][p3][d]+=single(x1,x2,x3,d)*dp(y1,y2,y3,d)%MOD;
					F[p1][p2][p3][d]%=MOD;
				}
	}
	return F[p1][p2][p3][d];
}
int main()
{
	init();
	Ans=(dp(L1,L2,L3,D)-dp(L1,L2,L3,D-1)+MOD)%MOD;
	printf("%d\n",Ans);
	return 0;
}

[食物链]

这道题真是个并差集的典型应用问题。由于判断真假总是根据前面得到的关系,在某时关系不是完全的,所以不能直接判断a,b究竟是哪个物种,但是可以知道部分的关系。

很显然,合法的关系都是三角形环,如果a,b同属于一个环内,那么它们的关系是可以直接判断的。如果不属于同一环,因为不与前面矛盾,就认 为是正确的,然后把a,b所在的两个环合并。建立一个并差集,表示每个生物所属的物种类型。对于物种i,定义prev[i]为可以吃掉i的物种类 型,next[i]为i可以吃掉的物种类型。初始时,每个物种i对应一个单独的类型,并且引入两个虚节点prev[i]和next[i],可分别为一个单 独的类型。

合并两个环时,对于D=1,a与b为同一物种,分别把(a,b),(prev[a],prev[b]),(next[a],next[b])依次合并。

对于D=2,a可以吃掉b,则分别把(next[a],b),(a,prev[b]),(prev[a],next[b])依次合并。

/* 
 * Problem: NOI2001
 * Author: Guo Jiabao
 * Time: 2009.3.13 13:28
 * State: Solved
 * Memo: 并差集 等价类判断
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=50001;
struct UFS
{
	int f[MAXN*3];
	int getroot(int a)
	{
		int t,r=a;
		while (f[r]!=r) r=f[r];
		while (f[a]!=a) {t=f[a];f[a]=r;a=t;}
		return r;
	}
	bool judge(int a,int b){return getroot(a)==getroot(b);}
	void merge(int a,int b){f[getroot(b)]=getroot(a);}
}U;
using namespace std;
int N,M,Fake;
int prev[MAXN*3],next[MAXN*3];
void init()
{
	int i,p,n;
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++)
	{
		p=N+i;n=p+N;
		U.f[i]=i;U.f[p]=p;U.f[n]=n;
		prev[i]=p;next[i]=n;prev[n]=i;
		next[n]=p;prev[p]=n;next[p]=i;
	}
}
bool relation(int d,int a,int b)
{
	if (d==1)
	{
		if (U.judge(a,b))
			return true;
		if (U.judge(prev[a],b) || U.judge(next[a],b))
			return false;
		U.merge(a,b);
		U.merge(prev[a],prev[b]);
		U.merge(next[a],next[b]);
	}
	else
	{
		if (U.judge(next[a],b))
			return true;
		if (U.judge(a,b) || U.judge(prev[a],b))
			return false;
		U.merge(next[a],b);
		U.merge(a,prev[b]);
		U.merge(prev[a],next[b]);
	}
	return true;
}
void solve()
{
	int i,d,a,b;
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&d,&a,&b);
		if (a>N || b>N || (d==2 && a==b) ||!relation(d,a,b))
			Fake++;
	}
}
int main()
{
	init();
	solve();
	printf("%d\n",Fake);
	return 0;
}

[炮兵阵地]

较难看出的动态规划问题。注意到数据范围N≤100;M≤10,发现每行的宽度都不大,所以可以考虑把一行看成一个状态,表示该行的布置方案。每行的布置方案可以预先处理出,由数学知识可以算出,每行最多的布置方案数也不过60个而已。

状态设定

F[i,a,b]为前i行,第i行的方案为A[a],第i-1行的方案为A[b]的最大炮兵数。

状态转移方程

  • F[i,a,b]=Max{ F[i-1,b,c] + P[a] }

其中c为i-2行的布置方案,a,b,c应保证互不冲突,即放置方案中炮兵都在平地上,且不会互相攻击到。

目标结果

  • Ans=Max{F[N,a,b]}
/* 
 * Problem: NOI2001 cannon
 * Author: Guo Jiabao
 * Time: 2009.3.20 17:54
 * State: Solved
 * Memo: 动态规划 位表示状态
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXM=11,MAXA=61;
using namespace std;
int N,M,Ans,AC;
bool used[MAXN];
int F[MAXN][MAXA][MAXA];
int A[MAXA],C[MAXA],Pla[MAXN];
void init()
{
	int i,j;
	char c;
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++)
	{
		do c=getchar(); while(c==10 || c==13);
		ungetc(c,stdin);
		Pla[i]=0;
		for (j=1;j<=M;j++)
			if ((c=getchar())=='H')
				Pla[i]+=1<<(j-1);
	}
}
inline int Max(int a,int b)
{
	return a>b?a:b;
}
void dynamic()
{
	int i,j,k,l,x,y,z,p,q;
	for (i=2,j=1;j<=AC;j++)
	{
		x=A[j];
		p=C[j];
		if ((x&Pla[1])==0)
		for (k=1;k<=AC;k++)
		{
			y=A[k];
			q=C[k];
			if ((y&Pla[i])==0 && (x&y)==0)
				F[i][k][j]=p+q;
			if (F[i][j][k] > Ans)
				Ans = F[i][j][k];
		}
	}
	for (i=3;i<=N;i++)
	{
		for (j=1;j<=AC;j++)
		{
			x=A[j];	p=C[j];
			if ((x&Pla[i])==0)
				for (k=1;k<=AC;k++)
				{
					y=A[k];
					if ((y&Pla[i-1])==0 && (x&y)==0)
						for (l=1;l<=AC;l++)
						{
							z=A[l];
							if ((z&Pla[i-2])==0 && ((y|z)&x)==0)
								F[i][j][k]=Max(F[i][j][k],F[i-1][k][l] + p);
						}
					if (F[i][j][k] > Ans)
						Ans = F[i][j][k];
				}
		}
	}
}
void arrange(int p)
{
	if (p>M)
	{
		int r=0,c=0;
		for (int i=1;i<=M;i++)
			if (used[i])
			{
				c++;
				r+=1<<(i-1);
			}
		AC++;
		A[AC]=r;
		C[AC]=c;
		return ;
	}
	used[p]=true;
	arrange(p+3);
	used[p]=false;
	arrange(p+1);
}
void solve()
{
	arrange(1);
	dynamic();
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}

[方程的解数]

经典的搜索问题,方法是搜索每个x的所有可能值[1,M],判断符合条件的解的个数。但是对于N=6,搜索量高达11390625000000,显然会超时。

我们不妨把等式变形,对于N项,把后N/2项移到等式右边,则移过去的项的k值全部取相反数。对于左边剩下的N/2项,搜索x的所有可能 值,计算左边式子的值,并插入到哈希表中。然后再对于右边的N-2项,搜索x的所有可能值,计算左边式子的值,然后再哈希表中查找与之相等的值的个数,加 到结果上。

插入到哈希表时先把绝对值Mod一个大质数,我选的是4000037,然后挂链解决冲突。为了提高效率,在哈希表的每个位置上我都建立了一个Treap,这样解决冲突时就能更快得找到了。

做这道题起初我试图直接用一个Treap存储所有的算式可能值,但是这样做会超时。通过使用哈希表,使数据平均分布了许多。哈希表和平衡树,或者Trie树混合使用不失为一种解决冲突优秀的方法。

/* 
 * Problem: NOI2001 equation1
 * Author: Guo Jiabao
 * Time: 2009.3.21 16:15
 * State: Solved
 * Memo: 搜索 + Hash +Treap判重
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=7,MAXM=151,MAXP=7,MOD=4000037;
const bool LEFT=true,RIGHT=false;
using namespace std;
struct TTreap
{
	struct Treap_node
	{
		Treap_node *left,*right;
		int value,weight,fix;
		Treap_node(int v):value(v),weight(1)
		{
			left=right=0;
			fix=rand();
		}
	};
	Treap_node *root;
	TTreap():root(0){}
	inline void rotate_left(Treap_node *&p)
	{
		Treap_node *q=p->right;
		p->right=q->left;
		q->left=p;
		p=q;
	}
	inline void rotate_right(Treap_node *&p)
	{
		Treap_node *q=p->left;
		p->left=q->right;
		q->right=p;
		p=q;
	}
	void insert(Treap_node *&p,int value)
	{
		if (!p)
			p=new Treap_node(value);
		else if (value == p->value)
			p->weight++;
		else if (value < p->value)
		{
			insert(p->left,value);
			if (p->left->fix < p->fix)
				rotate_right(p);
		}
		else
		{
			insert(p->right,value);
			if (p->right->fix < p->fix)
				rotate_left(p);
		}
	}
	int find(Treap_node *p,int value)
	{
		if (!p)
			return 0;
		else if (value == p->value)
			return p->weight;
		else if (value < p->value)
			return find(p->left,value);
		else
			return find(p->right,value);
	}
};
struct item
{
	int k,p,x;
}I[MAXN];
int N,LIM,Mid,Ans;
int POW[MAXM][MAXP];
TTreap Hash[MOD];
bool L;
void init()
{
	freopen("equation1.in","r",stdin);
	freopen("equation1.out","w",stdout);
	scanf("%d%d",&N,&LIM);
	Mid=N/2;
	for (int i=1;i<=N;i++)
	{
		scanf("%d%d",&I[i].k,&I[i].p);
		if (i>Mid)
			I[i].k=-I[i].k;
	}
	srand(9112);
}
inline int power(int x,int p)
{
	if (!POW[x][p])
	{
		POW[x][p]=1;
		for (int i=1;i<=p;i++)
			POW[x][p]*=x;
	}
	return POW[x][p];
}
int compute(int a,int b)
{
	int rs=0,i;
	for (i=a;i<=b;i++)
		rs+=power(I[i].x,I[i].p)*I[i].k;
	return rs;
}
inline int Abs(int a) {return a<0?-a:a;}
void search(int e)
{
	int i,H;
	if (L && e>Mid )
	{
		i=compute(1,Mid);
		H=Abs(i)%MOD;
		Hash[H].insert(Hash[H].root,i);
	}
	else if (!L && e>N)
	{
		i=compute(Mid+1,N);
		H=Abs(i)%MOD;
		int a=Hash[H].find(Hash[H].root,i);
		Ans+=a;
	}
	else
		for (i=1;i<=LIM;i++)
		{
			I[e].x=i;
			search(e+1);
		}
}
void solve()
{
	L=LEFT;
	search(1);
	L=RIGHT;
	search(Mid+1);
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}
<h2><span class="mw-headline">反正切函数的应用 </span></h2>

<a class="image" title="Image:Arctan.gif" href="http://192.168.1.253/wiki/Image:Arctan.gif"><img src="http://192.168.1.253/mw/images/8/85/Arctan.gif" alt="Image:Arctan.gif" width="568" height="670" /></a>

输入文件

输入文件中只有一个正整数a ,其中1&lt;=a&lt;=60000 。

输出文件

输出文件中只有一个整数,为b + c的值。
输入样例
<pre>1</pre>
输出样例
<pre>5</pre>

<h2><span class="mw-headline">聪明的打字员 </span></h2>

阿兰是某机密部门的打字员,她现在接到一个任务:需要在一天之内输入几百个长度固定为6的密码。当然,她希望输入的过程中敲击键盘的总次数越少越好。

不幸的是,出于保密的需要,该部门用于输入密码的键盘是特殊设计的,键盘上没有数字键,而只有以下六个键:Swap0, Swap1, Up, Down, Left, Right,为了说明这6个键的作用,我们先定义录入区的6个位置的编号,从左至右依次为1,2,3,4,5,6。下面列出每个键的作用:
  • Swap0:按Swap0,光标位置不变,将光标所在位置的数字与录入区的1号位置的数字(左起第一个数字)交换。如果光标已经处在录入区的1号位置,则按Swap0键之后,录入区的数字不变;

  • Swap1:按Swap1,光标位置不变,将光标所在位置的数字与录入区的6号位置的数字(左起第六个数字)交换。如果光标已经处在录入区的6号位置,则按Swap1键之后,录入区的数字不变;

  • Up:按Up,光标位置不变,将光标所在位置的数字加1(除非该数字是9)。例如,如果光标所在位置的数字为2,按Up之后,该处的数字变为3;如果该处数字为9,则按Up之后,数字不变,光标位置也不变;

  • Down:按Down,光标位置不变,将光标所在位置的数字减1(除非该数字是0),如果该处数字为0,则按Down之后,数字不变,光标位置也不变;

  • Left:按Left,光标左移一个位置,如果光标已经在录入区的1号位置(左起第一个位置)上,则光标不动;

  • Right:按Right,光标右移一个位置,如果光标已经在录入区的6号位置(左起第六个位置)上,则光标不动。

    当然,为了使这样的键盘发挥作用,每次录入密码之前,录入区总会随机出现一个长度为6的初始密码,而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后,可以得到目标密码,这时光标允许停在任何一个位置。 现在,阿兰需要你的帮助,编写一个程序,求出录入一个密码需要的最少的击键次数。

    输入文件

    文件仅一行,含有两个长度为6的数,前者为初始密码,后者为目标密码,两个密码之间用一个空格隔开。

    输出文件

    文件仅一行,含有一个正整数,为最少需要的击键次数。

    输入样例

    123456 654321

    输出样例

    11

    样例说明:

    初始密码是123456,光标停在数字1上。对应上述最少击键次数的击键序列为:

    Image:Clever.gif

    最少的击键次数为11。

    陨石的秘密

    公元11380年,一颗巨大的陨石坠落在南极。于是,灾难降临了,地球上出现了一系列反常的现象。当人们焦急万分的时候,一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察,科学家们发现陨石上刻有若干行密文,每一行都包含5个整数:

    1 1 1 1 6
      0 0 6 3 57
      8 0 11 3 2845

    著名的科学家SS发现,这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算,他定义了一种SS表达式:

    1. SS表达式是仅由‘{’,‘}’,‘[’,‘]’,‘(’,‘)’组成的字符串。
    2. 一个空串是SS表达式。
    3. 如果A是SS表达式,且A中不含字符‘{’,‘}’,‘[’,‘]’,则(A)是SS表达式。
    4. 如果A是SS表达式,且A中不含字符‘{’,‘}’,则[A]是SS表达式。
    5. 如果A是SS表达式,则{A}是SS表达式。
    6. 如果A和B都是SS表达式,则AB也是SS表达式。
    例如
  • ()(())[]

  • {()[()]}

  • {{[[(())]]}}

    都是SS表达式。

  • ()([])()

  • [()

    不是SS表达式。

    一个SS表达式E的深度D(E)定义如下:

    例如(){()}[]的深度为2。

    密文中的复杂运算是这样进行的:

    设密文中每行前4个数依次为L1,L2,L3,D,求出所有深度为D,含有L1对{},L2对[],L3对()的SS串的个数,并用这个数对当前的年份11380求余数,这个余数就是密文中每行的第5个数,我们称之为“神秘数”。

    密文中某些行的第五个数已经模糊不清,而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

    输入文件

    共一行,4个整数L1,L2,L3,D。相邻两个数之间用一个空格分隔。(0≤L1≤10,0≤L2≤10,0≤L3≤10,0≤D≤30)

    输出文件

    共一行,包含一个整数,即神秘数。

    输入样例

    1 1 1 2

    输出样例

    8

    食物链

    动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。

    现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。

    有人用两种说法对这N个动物所构成的食物链关系进行描述:

  • 第一种说法是“1 X Y”,表示X和Y是同类。

  • 第二种说法是“2 X Y”,表示X吃Y。

    此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

    1. 当前的话与前面的某些真的话冲突,就是假话;
    2. 当前的话中X或Y比N大,就是假话;
    3. 当前的话表示X吃X,就是假话。
    你的任务是根据给定的N(1<=N<=50,000)和K句话(0<=K<=100,000),输出假话的总数。

    输入文件

    第一行是两个整数N和K,以一个空格分隔。

    以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。

  • 若D=1,则表示X和Y是同类。

  • 若D=2,则表示X吃Y。

    输出文件

    只有一个整数,表示假话的数目。

    输入样例

    输入文件

    100 7
      1 101 1
      2 1 2
      2 2 3
      2 3 3
      1 1 3
      2 3 1
      1 5 5

    输出样例

    3

    样例说明

    对7句话的分析

  • 1 101 1 假话

  • 2 1 2 真话

  • 2 2 3 真话

  • 2 3 3 假话

  • 1 1 3 假话

  • 2 3 1 真话

  • 1 5 5 真话

    炮兵阵地

    司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击 范围如图中黑色区域所示:

    如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

    现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。

    Image:Cannon.gif

    输入文件

    文件的第一行包含两个由空格分割开的正整数,分别表示N和M;

    接下来的N行,每一行含有连续的M个字符(‘P’或者‘H’),中间没有空格。按顺序表示地图中每一行的数据。N≤100;M≤10。

    输出文件

    文件仅在第一行包含一个整数K,表示最多能摆放的炮兵部队的数量。

    输入样例

    5 4
      PHPP
      PPHH
      PPPP
      PHPP
      PHHP

    输出样例

    6

    方程的解数

    问题描述

    已知一个n元高次方程:

    Image:Equation1.gif

    其中:x1, x2, …,xn是未知数,k1,k2,…,kn是系数,p1,p2,…pn是指数。且方程中的所有数均为整数。

    假设未知数1≤ xi ≤M, i=1,,,n,求这个方程的整数解的个数。

    输入文件

    文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行,每行包含两个整数,分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1,第n+2行的数据对应i=n。 输出文件

    文件仅一行,包含一个整数,表示方程的整数解的个数。

    输入样例

    3
      150
      1 2
      -1 2
      1 2

    输出样例

    178

    约束条件

    1<=n<=6;1<=M<=150;

    Image:Equation2.gif

    方程的整数解的个数小于2^31。

    ★本题中,指数Pi(i=1,2,……,n)均为正整数。


上次修改时间 2017-05-26

相关日志