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上。对应上述最少击键次数的击键序列为：

最少的击键次数为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”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

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

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

输入文件

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

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

输出文件

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

输入样例
```
5 4
  PHPP
  PPHH
  PPPP
  PHPP
  PHHP
```
输出样例
```
6
```
方程的解数

问题描述

已知一个n元高次方程：

其中：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；

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

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

上次修改时间 2017-05-26

陨石的秘密

食物链

炮兵阵地

方程的解数

相关日志