1 1 、传教士 (bishop)
问题描述：
panzhili 王国的疆土恰好是一个矩形，为了管理方便，国王 jjs 将整个疆土划分成 N＊
M 块大小相同的区域。由于 jjs 希望他的子民也能信教爱教（”打拳”神教） ，所以他想安排一
些传教士到全国各地去传教。 但这些传教士的传教形式非常怪异， 他们只在自己据点周围特
定的区域内传教且领地意识极其强烈 （即任意一个传教士的据点都不能在其他传教士的传教
区域内，否则就会发生冲突） 。现在我们知道传教士的传教区域为以其据点为中心的两条斜
对角线上（如图） 。现在 jjs 请你帮忙找出一个合理的安置方案，使得可以在全国范围内安
置尽可能多的传教士而又不至于任意两个传教士会发生冲突。
X
X X
A
X X
（若 A 为某传教士的据点，则其传教范围为所有标有 X 的格子。为不产生冲突，则第
二个传教士的据点只能放在上图的空格中。 ）
输入数据
输入文件共一行，包含两个整数 N 和 M，代表国土的大小，n 为水平区域数，m 为垂
直区域数。
输出数据
输出文件仅一行，包含一个整数，即最多可以安置的传教士的数目。
样例输入 样例输入 bishop.in
3 4
样例输出 样例输出 bishop.out
6
说明：样例安置方案如下图所示，X 表示为某传教士的据点。
XXX
OOO
OOO
XXX
对于 100%的数据，1<=n,m<=9，且数据规模呈梯度上升。
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ans;
bool v1[],v2[];
void dfs(int x,int y,int sum){
ans=max(ans,sum);
if(y>m||x>n)return;
if(!v1[x-y+]&&!v2[x+y]){
v1[x-y+]=;
v2[x+y]=;
if(y==m)dfs(x+,,sum+);
else dfs(x,y+,sum+);
v1[x-y+]=;
v2[x+y]=;
}
if(y==m)dfs(x+,,sum);
else dfs(x,y+,sum);
}
int main(){
freopen("bishop.in","r",stdin);
freopen("bishop.out","w",stdout);
scanf("%d%d",&n,&m);
dfs(,,);
printf("%d",ans);
}
70分 暴力
/*
表打出来就很容易看出结论 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<cstdio>
using namespace std;
int n,m,ans;
int main(){
freopen("bishop.in","r",stdin);
freopen("bishop.out","w",stdout);
scanf("%d%d",&n,&m);
if(n==&&m==){puts("");return ;}
if(n>m)swap(n,m);
if(n&){
ans=n+m-;
if(n==m)ans--;
}
else ans=n+(m-)/*;
printf("%d",ans);
return ;
}
100分 打表找规律
2 、czy 把妹(czybm)
Czy 是个大丧失，非常喜欢 bm。他经常挑战 bm 的极限，同时 b 很多的 mz。(虽然也
许质量不容乐观)
这一天，czy 又开始了他的极限挑战。在一个数轴上有 n 个 maze,她们都在等待着
czy 的到来。Czy 一开始站在 k 号妹子的旁边，他需要搞定所有的妹子(由于他向 fewdan
学会了绝技，所以搞定妹子的时间是无限接近于 0 的，也就是一瞬间就搞定而不用花额外
的时间)。 Maze 们都很没有耐心， 每让她们多等 1s,她们就会增加 w[i]的不开心值。 现在，
czy 从 k 号妹子这里出发，以 1m/s 的速度开始行动，他希望在搞定所有 maze 的情况下使
得她们的不开心值总和最小，于是他找到了即将在 NOIP2014 AK 的你来帮他解决这个问
题。
文件输入:
输入文件的第一行包含一个整数 N，2<=N<=1000，表示 maze 的数量。
第二行包含一个整数 V，1<=V<=N，表示开始时 czy 站在几号 maze 的旁边.接下来的 N 行
中，每行包含两个用空格隔开的整数 D 和 W，用来描述每个 maze，其中 0<=D<=1000，
0<=W<=1000。D 表示 MM 在数轴上的位置(单位: m)，W 表示每秒钟会增加的不开心值。
文件输出:
一个整数，最小的不开心值。(答案不超过 10^9)
样例输入
4
3
2 2
5 8
6 1
8 7
样例输出
56
对于 40%的数据，1<=n<=7
对于 100%的数据，1<=n<=1000 0<=D<=1000 0<=w<=1000
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
#define maxn 1010
int n,dis[maxn][maxn],s;
long long ans=0x7fffffff;
bool vis[maxn];
struct node{
int pos,w;
}q[maxn];
void dfs(int now,int cnt,long long sum,int tim){
if(sum>=ans)return;
if(cnt==n){
if(sum<)return;
ans=min(ans,sum);
return;
}
for(int i=;i<=n;i++){//下一个要把的妹
if(!vis[i]){
vis[i]=;
dfs(i,cnt+,sum+q[i].w*(tim+dis[i][now]),tim+dis[i][now]);
vis[i]=;
}
}
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("czybm.in","r",stdin);
freopen("czybm.out","w",stdout);
scanf("%d%d",&n,&s);
vis[s]=;
for(int i=;i<=n;i++)
scanf("%d%d",&q[i].pos,&q[i].w);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dis[i][j]=abs(q[i].pos-q[j].pos);
dfs(s,,,);
cout<<ans;
return ;
}
40分 暴力
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,v,rp[],x[],sum[],l[][],r[][];
int main(){
freopen("czybm.in","r",stdin);
freopen("czybm.out","w",stdout);
int i,j,L;
scanf("%d%d",&n,&v);
for(i=;i<=n;i++) scanf("%d%d",&x[i],&rp[i]);
for(i=;i<=n;i++) sum[i]=sum[i-]+rp[i];
for(i=;i<=n;i++) r[i][i]=l[i][i]=abs(x[i]-x[v])*sum[n];
for(L=;L<=n;L++){
for(i=;i<=n;i++){
j=i+L-; if(j>n) break;
l[i][j]=l[i+][j]+(x[i+]-x[i])*(sum[i]+sum[n]-sum[j]);
l[i][j]=min(l[i][j],r[i][j-]+(x[j]-x[j-])*(sum[i-]+sum[n]-sum[j-])+(x[j]-x[i])*(sum[n]-sum[j]+sum[i-]));
r[i][j]=r[i][j-]+(x[j]-x[j-])*(sum[i-]+sum[n]-sum[j-]);
r[i][j]=min(r[i][j],l[i+][j]+(x[i+]-x[i])*(sum[i]+sum[n]-sum[j])+(x[j]-x[i])*(sum[i-]+sum[n]-sum[j]));
}
}
printf("%d\n",min(l[][n],r[][n]));
return ;
}
100分 dp
3、hzwer的跳跳棋(hop)
【问题描述】
Hzwer的跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。
某一天，黄金大神和cjy用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。他们要通过最少的跳动把它们的位置移动成x，y，z。（棋子是没有区别的）
跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
【输入格式】
第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）
第二行包含三个整数，表示目标位置x y z。（互不相同）
【输出格式】
如果无解，输出一行NO。
如果可以到达，第一行输出YES，第二行输出最少步数。
【样例输入】
1 2 3
0 3 5
【样例输出】
YES
2
【范围】
20% 输入整数的绝对值均不超过10
40% 输入整数的绝对值均不超过10000
100% 绝对值不超过10^9
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
#define mod1 23333333
#define mod2 45975231
int s1,s2,s3,t1,t2,t3;
bool vis[];
struct node{
int a,b,c,step;
}cur,nxt;
int hash(int a,int b,int c){
int a1=1LL*(a+)*%mod2;
int a2=1LL*(b+)*%mod2;
int a3=1LL*(c+)*%mod2;
int res=(1LL*a1*a2%mod1)*a3%mod1;
return res;
}
queue<node>q;
void push(int a,int b,int c,int step){
node now;
now.a=a;now.b=b;now.c=c;now.step=step;
q.push(now);
vis[hash(a,b,c)]=;
vis[hash(a,c,b)]=;
vis[hash(b,a,c)]=;
vis[hash(b,c,a)]=;
vis[hash(c,a,b)]=;
vis[hash(c,b,a)]=;
}
bool pan(int a,int b,int c){
if(a==t1&&b==t2&&c==t3)return ;
if(a==t1&&b==t3&&c==t2)return ;
if(a==t2&&b==t1&&c==t3)return ;
if(a==t2&&b==t3&&c==t1)return ;
if(a==t3&&b==t1&&c==t2)return ;
if(a==t3&&b==t2&&c==t1)return ;
return ;
}
int z[];
int bfs(){
while(!q.empty()){
node now=q.front();q.pop();
int s=now.step;
z[]=now.a,z[]=now.b,z[]=now.c;
sort(z+,z+);
int a,b,c;
int dis; a=z[],b=z[]-(z[]-z[]),c=z[];
if(pan(a,b,c))return s+;
if(!vis[hash(a,b,c)])push(a,b,c,s+); a=z[],b=z[]+(z[]-z[]),c=z[];
if(pan(a,b,c))return s+;
if(!vis[hash(a,b,c)])push(a,b,c,s+); if(z[]-z[]>z[]-z[]){
a=z[],b=z[]-(z[]-z[]),c=z[];
if(pan(a,b,c))return s+;
if(!vis[hash(a,b,c)])push(a,b,c,s+);
}
if(z[]-z[]<z[]-z[]){
a=z[],b=z[]+(z[]-z[]),c=z[];
if(pan(a,b,c))return s+;
if(!vis[hash(a,b,c)])push(a,b,c,s+);
}
}
return -;
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("hop.in","r",stdin);
freopen("hop.out","w",stdout);
scanf("%d%d%d%d%d%d",&s1,&s2,&s3,&t1,&t2,&t3);
push(s1,s2,s3,);
int ans=bfs();
if(ans==-){
printf("NO");return ;
}
else {
printf("YES\n%d",ans);
return ;
}
}
15分 暴力
/*
对于一个状态，中间的一个棋子可以往两边跳，而两边的棋子最多只有一个可以往中间跳
故每个状态看做一个点，有关连的状态连起来，就形成了一棵二叉树
对于一个某个有解的状态而言，中间往两边跳的两个状态是它的儿子，两边往中间跳的状态是它的父亲
于是就变成了树上两点求距离问题。
暴力只有40分
若记前两个数差t1，后两个数差t2，不妨设t1<t2则左边最多往中间跳(t2-1)/t1次然后只能右边往中间跳，是一个辗转相除的过程，即在logK的时间内我们可以用这种方法得到某个结点它向上K次后的结点，或者根节点，同时还可以顺便算下深度
于是就变成了先把两个节点调到树上同一深度再二分LCA的深度即可
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=(int)1e9;
struct data{
int a[];
bool operator != (const data b){
return (a[]!=b.a[]||a[]!=b.a[]||a[]!=b.a[]);
}
};
int t1,t2,tmp,ans;
int a[],b[]; data calc(int *a,int k){
data res;
int t1=a[]-a[],t2=a[]-a[],t;
for(int i=;i<;i++)res.a[i]=a[i];
if(t1==t2)return res;
if(t1<t2){
t=min(k,(t2-)/t1);
k-=t,tmp+=t;
res.a[]+=t*t1,res.a[]+=t*t1;
}
else {
t=min(k,(t1-)/t2);
k-=t,tmp+=t;
res.a[]-=t*t2,res.a[]-=t*t2;
}
return k?calc(res.a,k):res;
} int main(){
freopen("hop.in","r",stdin);
freopen("hop.out","w",stdout);
int d1,d2;
data t1,t2;
for(int i=;i<;i++)scanf("%d",&a[i]);
for(int i=;i<;i++)scanf("%d",&b[i]);
sort(a+,a+);
sort(b+,b+);
t1=calc(a,INF),d1=tmp,tmp=;
t2=calc(b,INF),d2=tmp,tmp=;
if(t1!=t2){
printf("NO");
return ;
}
if(d1>d2){
swap(d1,d2);
for(int i=;i<;i++)swap(a[i],b[i]);
}
ans=d2-d1;
t1=calc(b,ans);
for(int i=;i<;i++)b[i]=t1.a[i];
int l=,r=d1,mid;
while(l<=r){
mid=l+r>>;
if(calc(a,mid)!=calc(b,mid))l=mid+;
else r=mid-;
}
printf("YES\n%d",ans+*l);
return ;
}
100分 lca+二分