高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=3106

题意

一个n*n（n>=2）棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。

        A：移动白棋子。可以往上下左右四个方向之一移动一格。

        B：移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

当某游戏者把自己的棋子移动到对方棋子所在的格子时就赢了。两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。判断谁会赢，需要多少回合。

题解

不看题解不会- =

然后找到一种很奇怪的做法。。

首先没有平局- =，

如果黑色不在白色的旁边，黑色一定赢（因为白色永远吃不到它0.0）。

接下来的问题是求需要多少步

暴力，然后，其实是卡时。。

我们猜测答案不超过3n步。。。。

记忆化搜索，f[a][b][c][d][x][y]表示白(a,b)，黑(c,d)，x步，y表示当前游戏者是谁。

于是就过了，不明真相。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=21;
int f[N][N][N][N][N*3][2],n,a,b,c,d;
int DFS(int a,int b,int c,int d,int x,int y)
{
    if(x>3*n)  return 1<<30;
    if(a==c&&b==d)  return y==1?1<<30:0;
    if(f[a][b][c][d][x][y])  return f[a][b][c][d][x][y];
    int &ans=f[a][b][c][d][x][y];
    if(y==0)
    {
        if(a>1)  ans=max(ans,DFS(a-1,b,c,d,x+1,1)+1);
        if(b>1)  ans=max(ans,DFS(a,b-1,c,d,x+1,1)+1);
        if(a<n)  ans=max(ans,DFS(a+1,b,c,d,x+1,1)+1);
        if(b<n)  ans=max(ans,DFS(a,b+1,c,d,x+1,1)+1);
    }
    else
    {
        ans=1<<30;
        if(c>1)  ans=min(ans,DFS(a,b,c-1,d,x+1,0)+1);
        if(d>1)  ans=min(ans,DFS(a,b,c,d-1,x+1,0)+1);
        if(c<n)  ans=min(ans,DFS(a,b,c+1,d,x+1,0)+1);
        if(d<n)  ans=min(ans,DFS(a,b,c,d+1,x+1,0)+1);
        if(c>2)  ans=min(ans,DFS(a,b,c-2,d,x+1,0)+1);
        if(d>2)  ans=min(ans,DFS(a,b,c,d-2,x+1,0)+1);
        if(c+2<=n)  ans=min(ans,DFS(a,b,c+2,d,x+1,0)+1);
        if(d+2<=n)  ans=min(ans,DFS(a,b,c,d+2,x+1,0)+1);
    }
    return ans;
}
int main()
{
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    if(abs(a-c)+abs(b-d)==1) printf("WHITE 1\n"); 
    else DFS(a,b,c,d,0,0),printf("BLACK %d\n",f[a][b][c][d][0][0]);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3107

题意

给三个数a,b,c。

构造三个新二进制数A,B,C，要求每个数与原数中1的个数相同，且满足A+B=C。

求满足条件的最小的C

题解

DP，f[t][i][j][k][p]，表示枚举到第t位，A已放i个1，B已放j个1，C已放k个1，若p=0，表示该状态无进位；否则表示有进位。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
const int N=31;
int n,a,b,c,f[2][N][N][N][2];
inline int get(int x)
{
	int s;
	for(s=0;x;x>>=1)
		if(x&1) s++;
	return s;
}
void init()
{

	int x,y,z;scanf("%d%d%d",&x,&y,&z);
	a=get(x);b=get(y);c=get(z);
	x=max(x,max(y,z));
	for(n=0;x;x>>=1) n++;
}

void work(int &a,int b)
{
	if(a==-1) a=b;
	else a=min(a,b);
}

int main()
{
	init();
	memset(f,-1,sizeof(f));
	f[0][0][0][0][0]=0;
	int cur=0;
	for(int t=0;t<n;t++,cur^=1)
		for(int i=0;i<=min(t,a);i++)
			for(int j=0;j<=min(t,b);j++)
				for(int k=0;k<=min(t,c);k++)
				{
					if(f[cur][i][j][k][0]!=-1)
					{
						int now=f[cur][i][j][k][0];
						work(f[cur^1][i][j][k][0],now);
						if(i+1<=a&&k+1<=c) work(f[cur^1][i+1][j][k+1][0],now+(1<<t));
						if(i+1<=a&&j+1<=b) work(f[cur^1][i+1][j+1][k][1],now);
						if(j+1<=b&&k+1<=c) work(f[cur^1][i][j+1][k+1][0],now+(1<<t));
					}
					if(f[cur][i][j][k][1]!=-1)
					{
						int now=f[cur][i][j][k][1];
						work(f[cur^1][i][j][k+1][0],now+(1<<t));
						if(i+1<=a) work(f[cur^1][i+1][j][k][1],now);
						if(j+1<=b) work(f[cur^1][i][j+1][k][1],now);
						if(i+1<=a&&j+1<=b&&k+1<=c)  work(f[cur^1][i+1][j+1][k+1][1],now+(1<<t));
					}
				}				
	printf("%d\n",f[cur][a][b][c][0]);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3108

题意

原图中的一条边为新图中的一个点，原图中两条相接的边为新图中的一条边，即a→b为点ab，a→b→c为ab→bc。

题目要求根据新图判断是否存在一个原图。

题解

如果在新图中存在 i->k 和 j->k

那么在原图里一定是这样的

所以我们可以发现，如果存在i->k和j->k

但只存在i->t或j->t其中之一，则新图不合法。

O(N^3)验证

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=301;
int n,m;bool a[N][N];

inline void init()
{
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=0;i<m;i++)
		scanf("%d%d",&x,&y),a[x][y]=1;
}

inline bool check()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			bool f1=0,f2=0;
			for(int k=0;k<n;k++)
			{
				if(a[i][k]&&a[j][k]) f1=true;
				if(a[i][k]!=a[j][k]) f2=true;
				if(f1&&f2) return 0;
			}
		}
	return 1;
}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		init();
		if(check()) puts("Yes");
		else puts("No");
	}
}