Daily Archives: 3 11 月, 2012

CF 217B(逆向思维-Fibonacci)

Posted on by

这题是逆向思维贪心……当时咋没想到……

本题启示：memset的效率与for一遍差不多，故千万memset导致超时……

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (1000000+10)
int n,r,minchange=MAXN;
bool ans[MAXN]={0},res[MAXN];
bool flag=0;
int calc()
{
	int tot=0;
	for (int i=2;i<=n;i++) if (!res[i]^res[i-1]) tot++;
	return tot;
}
void relax()
{
/*	for (int i=1;i<=n;i++) cout<<res[i]<<' ';
	cout<<endl;
*/	int now=calc();
	if (!flag||now<minchange)
	{
		flag=1;minchange=now;
		memcpy(ans,res,sizeof(ans));
		return;
	}
	if (now>minchange) return;


	for (int i=2;i<=n;i++)
	{
		if (ans[i]<res[i]) return ;
		if (ans[i]>res[i])
		{
			memcpy(ans,res,sizeof(ans));
			return;
		}
	}
}
bool is_ok(int l,int r)
{
//	memset(res,0,sizeof(res));
	res[1]=1;
	for (int i=n;i>1;i--)
	{
		if (!l||!r) return 0;
		if (r<l) {l=l-r; res[i]=1;}
		else {r-=l; res[i]=0;}
	}
	if (l!=1||r!=1) return 0;
	relax();
	for (int i=2;i<=n;i++) res[i]=!res[i];
	relax();
}
int main()
{
	cin>>n>>r;
	for (int i=1;i<=r;i++)
	{
		flag=is_ok(i,r)|flag;
//1		cout<<i<<endl;
	}
	if (!flag) cout<<"IMPOSSIBLEn";
	else
	{
		cout<<minchange<<'n';
		for (int i=1;i<=n;i++)
		{
			if (ans[i]) printf("T");
			else printf("B");
		}
		printf("n");
	}
//	while (1);
	return 0;
}

环上的游戏(贪心-博弈）

Posted on by

环上的游戏（cycle）

有一个取数的游戏。初始时，给出一个环，环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后，将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下：

（1）选择硬币左边或者右边的一条边，并且边上的数非0；

（2）将这条边上的数减至任意一个非负整数(至少要有所减小)；

（3）将硬币移至边的另一端。

如果轮到一个玩家走，这时硬币左右两边的边上的数值都是0，那么这个玩家就输了。

如下图，描述的是Alice和Bob两人的对弈过程，其中黑色节点表示硬币所在节点。结果图(d)中，轮到Bob走时，硬币两边的边上都是0，所以Alcie获胜。

现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。

 

【输入格式】

第一行一个整数N（N≤20），表示环上的节点数。

第二行N个数，数值不超过30，依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。

 

【输出格式】

仅一行。若存在必胜策略，则输出“YES”，否则输出“NO”。

 

【样例】

cycle.incycle.out

4 YES

2 5 3 0

cycle.incycle.out

3 NO

0 0 0

最后取到数的人获胜

稍加模拟

不难发现

若

0-x-x-x-x-x-x-1-x-x-x-x-x-0

显然任意取一个数，若全取，则

0-10-10-0

  ↑

对方再取 0- 9-10-0

↑

我记续取 0- 9-0-0

    ↑

想办法让对方只能向一个方向取

0-x-x-x-x-0

  ↑

此时奇数次必胜，偶数次必败

若两个方向都是偶数个x

0-x-x-x-x- 0

        ↑

此时无论我怎么取

0-x-(x-?)-x-x-0

     ↑   

于是又成了必胜态，故上次为必败态

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20+10)
int n;
int a[MAXN];
bool flag=0;
int main()
{
	freopen("cycle.in","r",stdin);
	freopen("cycle.out","w",stdout);

	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int i=1; while (a[i]) i++;
	if ((i-1)%2) flag=1;
	i=n; while (a[i]) i--;
	if ((n-i)%2) flag=1;

	if (flag) printf("YESn");
	else printf("NOn");

//	while (1);
	return 0;
}

高级打字机 (Tries）

Posted on by

Problem 1 高级打字机(type.cpp/c/pas)

【题目描述】

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。

请为这种高级打字机设计一个程序，支持如下3种操作：

1.T x：在文章末尾打下一个小写字母x。(type操作)

2.U x：撤销最后的x次修改操作。（Undo操作）

（注意Query操作并不算修改操作）

3.Q x：询问当前文章中第x个字母并输出。（Query操作）

文章一开始可以视为空串。

 

【输入格式】

第1行：一个整数n，表示操作数量。

以下n行，每行一个命令。保证输入的命令合法。

 

【输出格式】

每行输出一个字母，表示Query操作的答案。

 

【样例输入】

7

T a

T b

T c

Q 2

U 2

T c

Q 2

【样例输出】

b

c

【数据范围】

对于40%的数据 n<=200;

对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。

<IOI挑战>

必须使用在线算法完成该题。

这题要用字典树（Tries)

还有msm（倍增算法）

另外 补充一点

char  s[0]   或者 char 

scanf("%s",s)

 这句会存不下""

因此会把正在循环的自变量i 变成 0

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define LOGMAXN (16+10)
int n,tot=0;
struct Tnode
{
	int deep,f[LOGMAXN];
	char edge;
	Tnode()
	{
		memset(f,0,sizeof(f));
		deep=-1;
		edge='';
	}
	Tnode(char _edge,int _fa,int _deep)
	{
		memset(f,0,sizeof(f));
		f[0]=_fa;
		edge=_edge;
		deep=_deep;
	}
	int logdeep()
	{
		return int(trunc(log(deep)/log(2)));
	}
}node[MAXN];
int log2(int a)
{
	return int(trunc(log(a)/log(2)));
}
void msm(Tnode &a)
{
	int n=a.logdeep();
//	if (n==1) return;
	for (int i=1;i<=n;i++)
	{
		a.f[i]=node[a.f[i-1]].f[i-1];
	}
}
void type()
{
	char c;
	scanf("%s",&c);
	tot++;
	node[tot]=Tnode(c,tot-1,node[tot-1].deep+1);
	msm(node[tot]);
}

void quere()
{
	int p;
	scanf("%d",&p);
	Tnode now=node[tot];
	p=now.deep+1-p; //第i's 祖先
	while (p)
	{
		int i=log2(p);
		p-=(1<<i);
		now=node[now.f[i]];

	}
	printf("%cn",now.edge);

}
void undo()
{
	int p;
	scanf("%d",&p);
	tot++;
	node[tot]=node[tot-1-p];
}
int main()
{
	freopen("type.in","r",stdin);
	freopen("type.out","w",stdout);
	scanf("%d",&n);
	node[0]=Tnode();
	for (int ii=1;ii<=n;ii++)
	{
//		printf("%dn",ii);
		char s[10];
//		printf("%dn",ii);
		scanf("%s",s);
//		printf("%dn",ii);
//		while(1);
		switch(s[0])
		{
			case 'T':type();break;
			case 'U':undo();break;
			case 'Q':quere();break;
		}


	}
//	while (1);
	return 0;
}