「NOIP模拟赛」传教士

2014年10月22日3,5362

问题描述：

panzhili王国的疆土恰好是一个矩形，为了管理方便，国王jjs将整个疆土划分成N＊M块大小相同的区域。由于jjs希望他的子民也能信教爱教（”打拳”神教），所以他想安排一些传教士到全国各地去传教。但这些传教士的传教形式非常怪异，他们只在自己据点周围特定的区域内传教且领地意识极其强烈（即任意一个传教士的据点都不能在其他传教士的传教区域内，否则就会发生冲突）。现在我们知道传教士的传教区域为以其据点为中心的两条斜对角线上（如图）。现在jjs请你帮忙找出一个合理的安置方案，使得可以在全国范围内安置尽可能多的传教士而又不至于任意两个传教士会发生冲突。

			X
X		X
	A
X		X

（若A为某传教士的据点，则其传教范围为所有标有X的格子。为不产生冲突，则第二个传教士的据点只能放在上图的空格中。）

输入数据

输入文件共一行，包含两个整数N和M，代表国土的大小，n为水平区域数，m为垂直区域数。

输出数据

输出文件仅一行，包含一个整数，即最多可以安置的传教士的数目。

样例输入bishop.in

3 4

样例输出bishop.out

说明：样例安置方案如下图所示，X表示为某传教士的据点。

XXX

OOO

XXX

对于100%的数据，1<=n,m<=9，且数据规模呈梯度上升。

题解

这个数据范围是给深搜的

暴力当然是像N皇后那样。。。

过不了加卡时位运算什么的，或者打出表

大不了上网络流啊

打表：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define dfsnxt(x,y,t) y==m?dfs(x+1,1,t):dfs(x,y+1,t)
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans[10][10];
bool a[30],b[30];
void dfs(int x,int y,int t)
{
	if(x==n+1)
	{
		ans[n][m]=max(ans[n][m],t);
		return;
	}
	if(!a[x+y]&&!b[x-y+15])
	{
		a[x+y]=b[x-y+15]=1;
		dfsnxt(x,y,t+1);
		a[x+y]=b[x-y+15]=0;
	}	
	dfsnxt(x,y,t);
}
int main()
{
	for(n=1;n<=7;n++)
		for(m=1;m<=7;m++)
			dfs(1,1,0);
	for(int i=1;i<=7;i++)
	{
		for(int j=1;j<=7;j++)
			printf("%d ",ans[i][j]);	
		puts("");
	}
	return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define dfsnxt(x,y,t) y==m?dfs(x+1,1,t):dfs(x,y+1,t)

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,ans[10][10];

bool a[30],b[30];

void dfs(int x,int y,int t)

{

if(x==n+1)

{

ans[n][m]=max(ans[n][m],t);

return;

}

if(!a[x+y]&&!b[x-y+15])

{

a[x+y]=b[x-y+15]=1;

dfsnxt(x,y,t+1);

a[x+y]=b[x-y+15]=0;

}

dfsnxt(x,y,t);

}

int main()

{

for(n=1;n<=7;n++)

for(m=1;m<=7;m++)

dfs(1,1,0);

for(int i=1;i<=7;i++)

{

for(int j=1;j<=7;j++)

printf("%d ",ans[i][j]);

puts("");

}

return 0;

}

表打出来就很容易看出结论

1 2 3 4 5 6 7
2 2 4 4 6 6 8
3 4 4 6 7 8 9
4 4 6 6 8 8 10
5 6 7 8 8 10 11
6 6 8 8 10 10 12
7 8 9 10 11 12 12

奇偶列分类，然后n=m特判

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans;
int main()
{
	n=read();m=read();
	if(n==1&&m==1){puts("1");return 0;}
	if(n>m)swap(n,m);
	if(n&1)
	{
		ans=n+m-1;
		if(n==m)ans--;
	}
	else ans=n+(m-1)/2*2;
	printf("%d",ans);
	return 0;
}