NOI 2001 解題報告

本文正體字版由OpenCC轉換

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

隕石的祕密

食物鏈

炮兵陣地

方程的解數

相關日誌