2014-10-22 NOIP模拟赛

时间:2022-12-17 11:26:22

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,且数据规模呈梯度上升。

2014-10-22 NOIP模拟赛2014-10-22 NOIP模拟赛
#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);
}
70分 暴力
2014-10-22 NOIP模拟赛2014-10-22 NOIP模拟赛
/*
    表打出来就很容易看出结论
    
    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;
}
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

2014-10-22 NOIP模拟赛2014-10-22 NOIP模拟赛
#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;
}
40分 暴力
2014-10-22 NOIP模拟赛2014-10-22 NOIP模拟赛
#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;
}
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

2014-10-22 NOIP模拟赛2014-10-22 NOIP模拟赛
#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;
    }
}
15分 暴力
2014-10-22 NOIP模拟赛2014-10-22 NOIP模拟赛
/*
    对于一个状态,中间的一个棋子可以往两边跳,而两边的棋子最多只有一个可以往中间跳
    故每个状态看做一个点,有关连的状态连起来,就形成了一棵二叉树
    对于一个某个有解的状态而言,中间往两边跳的两个状态是它的儿子,两边往中间跳的状态是它的父亲
    于是就变成了树上两点求距离问题。
    暴力只有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;
}
100分 lca+二分