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[30],v2[30]; void dfs(int x,int y,int sum){ ans=max(ans,sum); if(y>m||x>n)return; if(!v1[x-y+10]&&!v2[x+y]){ v1[x-y+10]=1; v2[x+y]=1; if(y==m)dfs(x+1,1,sum+1); else dfs(x,y+1,sum+1); v1[x-y+10]=0; v2[x+y]=0; } if(y==m)dfs(x+1,1,sum); else dfs(x,y+1,sum); } int main(){ freopen("bishop.in","r",stdin); freopen("bishop.out","w",stdout); scanf("%d%d",&n,&m); dfs(1,1,0); printf("%d",ans); }
/* 表打出来就很容易看出结论 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==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; }
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<0)return; ans=min(ans,sum); return; } for(int i=1;i<=n;i++){//下一个要把的妹 if(!vis[i]){ vis[i]=1; dfs(i,cnt+1,sum+q[i].w*(tim+dis[i][now]),tim+dis[i][now]); vis[i]=0; } } } int main(){ //freopen("Cola.txt","r",stdin); freopen("czybm.in","r",stdin); freopen("czybm.out","w",stdout); scanf("%d%d",&n,&s); vis[s]=1; for(int i=1;i<=n;i++) scanf("%d%d",&q[i].pos,&q[i].w); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=abs(q[i].pos-q[j].pos); dfs(s,1,0,0); cout<<ans; return 0; }
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n,v,rp[1010],x[1010],sum[1010],l[1010][1010],r[1010][1010]; int main(){ freopen("czybm.in","r",stdin); freopen("czybm.out","w",stdout); int i,j,L; scanf("%d%d",&n,&v); for(i=1;i<=n;i++) scanf("%d%d",&x[i],&rp[i]); for(i=1;i<=n;i++) sum[i]=sum[i-1]+rp[i]; for(i=1;i<=n;i++) r[i][i]=l[i][i]=abs(x[i]-x[v])*sum[n]; for(L=2;L<=n;L++){ for(i=1;i<=n;i++){ j=i+L-1; if(j>n) break; l[i][j]=l[i+1][j]+(x[i+1]-x[i])*(sum[i]+sum[n]-sum[j]); l[i][j]=min(l[i][j],r[i][j-1]+(x[j]-x[j-1])*(sum[i-1]+sum[n]-sum[j-1])+(x[j]-x[i])*(sum[n]-sum[j]+sum[i-1])); r[i][j]=r[i][j-1]+(x[j]-x[j-1])*(sum[i-1]+sum[n]-sum[j-1]); r[i][j]=min(r[i][j],l[i+1][j]+(x[i+1]-x[i])*(sum[i]+sum[n]-sum[j])+(x[j]-x[i])*(sum[i-1]+sum[n]-sum[j])); } } printf("%d\n",min(l[1][n],r[1][n])); return 0; }
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[23333334]; struct node{ int a,b,c,step; }cur,nxt; int hash(int a,int b,int c){ int a1=1LL*(a+1000000000)*456%mod2; int a2=1LL*(b+1000000000)*32%mod2; int a3=1LL*(c+1000000000)*147%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)]=1; vis[hash(a,c,b)]=1; vis[hash(b,a,c)]=1; vis[hash(b,c,a)]=1; vis[hash(c,a,b)]=1; vis[hash(c,b,a)]=1; } bool pan(int a,int b,int c){ if(a==t1&&b==t2&&c==t3)return 1; if(a==t1&&b==t3&&c==t2)return 1; if(a==t2&&b==t1&&c==t3)return 1; if(a==t2&&b==t3&&c==t1)return 1; if(a==t3&&b==t1&&c==t2)return 1; if(a==t3&&b==t2&&c==t1)return 1; return 0; } int z[5]; int bfs(){ while(!q.empty()){ node now=q.front();q.pop(); int s=now.step; z[1]=now.a,z[2]=now.b,z[3]=now.c; sort(z+1,z+4); int a,b,c; int dis; a=z[1],b=z[1]-(z[2]-z[1]),c=z[3]; if(pan(a,b,c))return s+1; if(!vis[hash(a,b,c)])push(a,b,c,s+1); a=z[1],b=z[3]+(z[3]-z[2]),c=z[3]; if(pan(a,b,c))return s+1; if(!vis[hash(a,b,c)])push(a,b,c,s+1); if(z[2]-z[1]>z[3]-z[2]){ a=z[1],b=z[2]-(z[3]-z[2]),c=z[2]; if(pan(a,b,c))return s+1; if(!vis[hash(a,b,c)])push(a,b,c,s+1); } if(z[2]-z[1]<z[3]-z[2]){ a=z[2],b=z[2]+(z[2]-z[1]),c=z[3]; if(pan(a,b,c))return s+1; if(!vis[hash(a,b,c)])push(a,b,c,s+1); } } return -1; } 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,0); int ans=bfs(); if(ans==-1){ printf("NO");return 0; } else { printf("YES\n%d",ans); return 0; } }
/* 对于一个状态，中间的一个棋子可以往两边跳，而两边的棋子最多只有一个可以往中间跳 故每个状态看做一个点，有关连的状态连起来，就形成了一棵二叉树 对于一个某个有解的状态而言，中间往两边跳的两个状态是它的儿子，两边往中间跳的状态是它的父亲 于是就变成了树上两点求距离问题。 暴力只有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[4]; bool operator != (const data b){ return (a[1]!=b.a[1]||a[2]!=b.a[2]||a[3]!=b.a[3]); } }; int t1,t2,tmp,ans; int a[4],b[4]; data calc(int *a,int k){ data res; int t1=a[2]-a[1],t2=a[3]-a[2],t; for(int i=1;i<4;i++)res.a[i]=a[i]; if(t1==t2)return res; if(t1<t2){ t=min(k,(t2-1)/t1); k-=t,tmp+=t; res.a[2]+=t*t1,res.a[1]+=t*t1; } else { t=min(k,(t1-1)/t2); k-=t,tmp+=t; res.a[2]-=t*t2,res.a[3]-=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=1;i<4;i++)scanf("%d",&a[i]); for(int i=1;i<4;i++)scanf("%d",&b[i]); sort(a+1,a+4); sort(b+1,b+4); t1=calc(a,INF),d1=tmp,tmp=0; t2=calc(b,INF),d2=tmp,tmp=0; if(t1!=t2){ printf("NO"); return 0; } if(d1>d2){ swap(d1,d2); for(int i=1;i<4;i++)swap(a[i],b[i]); } ans=d2-d1; t1=calc(b,ans); for(int i=1;i<4;i++)b[i]=t1.a[i]; int l=0,r=d1,mid; while(l<=r){ mid=l+r>>1; if(calc(a,mid)!=calc(b,mid))l=mid+1; else r=mid-1; } printf("YES\n%d",ans+2*l); return 0; }