Jams倒酒(pour)
1s,256MB
题目描述
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最小的。
样例输入
1 | 5 3 |
样例输出
1 | 1 |
提示&约定
倾倒方案为:
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
solution
对于一个a>b
每次都是把B倒满,把B倒入A,这时候B不一定倒完,但A满了,把A倒掉,把B中剩下的倒入A……这样循环下去。能取到酒的量为$-ax+by$,所以能取到的最小值就是$gcd(a,b)$
我们要求$-ax+by=gcd(a,b)$,所以用exgcd先求出一组x,y的解,然后判断x,y是否可以变小,或者y小于0,那么x变小,y变大。
code
1 |
|
土豪聪要请客(stol)
1s,256MB
题目描述
众所周知,聪哥(ndsf)是个土豪,不过你们不知道的是他的MZ和他的RMB一样滴多……
某天土豪聪又赚了10^10000e的RMB,他比较开心,于是准备请客。他在自己在XX星上的别墅里面大摆酒席,想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅,并且桌子的边必须与别墅的边界平行。给定别墅的平面图,请你求出聪哥最多可以请多少个MZ。
输入
第一行n,m。表示别墅的长宽
下面n行,每行M个字符,表示一个方块是空的(‘.’)或是被占用了(‘X’)。
聪哥只要他的桌子放在别墅里,并且桌子不能占用任何一个已经占用了的方块。
输出
一个数,表示聪哥最多可以请几个Maze。
样例输入1
1 | 2 2 |
样例输出1
1 | 7 |
样例输入2
1 | 4 4 |
样例输出2
1 | 9 |
提示&约定
对于60%的数据,n,m<=100
对于100%的数据,n,m<=400
solution
枚举m上的边长范围,然后对n跑最大连续子段和
code
1 |
|
最强大脑(zhber)
5s,256MB
问题描述
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的自然数矩阵,为Bij和Aij
最后一行六个数,分别代表X,Y,Z所在地的行号和列号。
输出
第一行输出一个字符X、Y或者Z。表示最优集合地点。
第二行输出一个整数,表示最小费用。
如果无法集合,只输出一行NO
样例输入
1 | 4 4 |
样例输出
1 | Z |
提示&约定
20% N, M ≤ 10; Bij ≤ 20
40% N, M ≤ 100; Bij ≤ 20
100% 1 ≤ N, M ≤ 150; 0 ≤ Bij ≤ 109; 0 ≤ Aij ≤ 1000
solution
跑3遍堆优化dijk
code
1 |
|