2014-10-23 NOIP模拟赛

NOIP2014模拟赛

-----lwher

时限均为1s，内存 256MB

1、Jams倒酒(pour)

Jams是一家酒吧的老板，他的酒吧提供2种体积的啤酒，a ml 和 b ml，分别使用容积为a ml 和 b ml的酒杯来装载。

酒吧的生意并不好。Jams发现酒鬼们都很穷，不像他那么土豪。有时，他们会因为负担不起a ml 或者 b ml酒的消费，而不得不离去。因此，Jams决定出手第三种体积的啤酒(较小体积的啤酒)。

Jams只有两种杯子，容积分别为 a ml 和 b ml，而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。

倒酒步骤为:

(1) 规定a>=b

(2) 酒桶容积无限，酒桶中酒体积无限大。

(3) 只能包含三种可能的倒酒操作：

1、将酒桶中的酒倒入容积为b ml的酒杯中；

2、将容积为a ml的酒杯中的酒倒入酒桶；

3、将容积为b ml的酒杯中的酒倒入容积为 a ml的酒杯中。

(4) 每次倒酒必须把杯子倒满或者把被倾倒的杯子倒空。

Jams希望通过若干次倾倒得到容积为 a ml酒杯中剩下的就体积尽可能小，他请求你帮助他设计倾倒方案。

输入:

两个整数a,b(0<b<=a<=10^9)

输出

第一行一个整数，表示可以得到的最小体积的酒。

第二行两个整数Pa和Pb（中间用一个空格分开），分别表示从体积为a ml的酒杯中到处酒的次数和将酒倒入体积为b ml的酒杯的次数。

若有多种可能的Pa，Pb满足要求，那么请输出Pa最小的。若Pa最小的时候有多个Pb，那么输出Pb最小的。

样例输入

5 3

样例输出

1 2

倾倒方案为：

1、桶->B；

2、 B->A；

3、桶->B;

4、 B->A;

5、 A->桶；

6、 B->A;

对于20%的数据，pa,pb总和不超过5

对于60%的数据，pa<=10^8

对于100%的数据，0<b<=a<=10^9

/*
    一开始竟然没看出是个扩展欧几里得
    混着考还是找不出算法来，无地自容
    有没有感觉代码里有故事
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll a,b,c,x,y,ans;
void exgcd(ll soda,ll cola){
    if(cola==0){
        ans=soda;
        x=1;
        y=0;
        return;
    }
    exgcd(cola,soda%cola);
    ll coco=x;
    x=y;y=coco-(soda/cola)*y;
}
int main(){
    freopen("pour.in","r",stdin);
    freopen("pour.out","w",stdout);
    scanf("%lld%lld",&a,&b);
    exgcd(a,b);
    printf("%lld
",ans);
    a/=ans;b/=ans;
    while(y<0) y+=a;
    x=(1-y*b)/a;
    printf("%I64d %I64d",-x,y);
    return 0;
}

土豪聪要请客(stol)

众所周知，聪哥(ndsf)是个土豪，不过你们不知道的是他的MZ和他的RMB一样滴多……

某天土豪聪又赚了10^10000e的RMB，他比较开心，于是准备请客。他在自己在XX星上的别墅里面大摆酒席，想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给定别墅的平面图，请你求出聪哥最多可以请多少个MZ。

输入格式

第一行n,m。表示别墅的长宽

下面n行，每行M个字符，表示一个方块是空的(‘ ’)或是被占用了(‘X’)。

聪哥只要他的桌子放在别墅里，并且桌子不能占用任何一个已经占用了的方块。

输出格式

一个数，表示聪哥最多可以请几个Maze。

样例输入1

2 2

样例输出1

样例输入2

4 4

X.XX

X..X

..X.

..XX

样例输出2

对于60%的数据，n,m<=100

对于100%的数据，n,m<=400

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[410][410],ans;
char s[410];
int main(){
    //freopen("Cola.txt","r",stdin);
    freopen("stol.in","r",stdin);
    freopen("stol.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            if(s[j]=='.')a[i][j]=1;
            a[i][j]+=a[i][j-1];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j++){
            int mx=0,sum=0;
            for(int k=1;k<=n;k++){
                if(a[k][j]-a[k][i-1]==j-i+1)sum++;
                else sum=0;
                mx=max(mx,sum);
            }
            if(mx)ans=max(ans,2*(mx+j-i+1)-1);
        }
    }
    printf("%d",ans);
}

最强大脑(zhber)(本题每个点5s)

【问题描述】

zhb国是一个传说中的国度，国家的居民叫做最强(chang)大脑(diao)。Zhb国是一个N×M的矩形方阵，每个格子代表一个街区。

然而zhb国是没有交通工具的。居民大脑(diao)们完全靠地面的弹射装置来移动。

每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。

我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何居民大脑(diao)都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图

（从红色街区交费以后可以跳到周围的任意蓝色街区。）

现在的问题很简单。有三个居民，她们分别是zhb的maze，分别叫做X，Y，Z。现在她们决定聚在一起玩找zhb玩(….)，于是想往其中一人的位置集合。但由于zhb太抠门了，不给报销路费，所以告诉你3个maze的坐标，求往哪里集合大家需要花的费用总和最低。

Zhb:如果你完美解决了这个问题，就授予你“最强(chang)大脑(diao)”称号。

【输入格式】

输入的第一行包含两个整数N和M，分别表示行数和列数。

接下来是2个N×M的自然数矩阵，为Aij和Bij

最后一行六个数，分别代表X，Y，Z所在地的行号和列号。

【输出格式】

第一行输出一个字符X、Y或者Z。表示最优集合地点。

第二行输出一个整数，表示最小费用。

如果无法集合，只输出一行NO

【样例输入】

4 4

0 0 0 0

1 2 2 0

0 2 2 1

0 0 0 0

5 5 5 5

2 1 3 4 2 2

【样例输出】

【范围】

20% N, M ≤ 10; Bij ≤ 20

40% N, M ≤ 100; Bij ≤ 20

100% 1 ≤ N, M ≤ 150; 0 ≤ Bij ≤ 10⁹; 0 ≤ Aij ≤ 1000