专栏首页数据结构与算法2057. [ZLXOI2015]殉国

2057. [ZLXOI2015]殉国

输入文件:BlackHawk.in   输出文件:BlackHawk.out 评测插件 时间限制:0.05 s   内存限制:256 MB

【题目描述】

正义的萌军瞄准了位于南极洲的心灵控制器,为此我们打算用空袭摧毁心灵控制器,然而心灵控制器是如此强大,甚至能缓慢控制飞行员。一群勇敢的士(feng)兵(zi)决定投弹后自杀来避免心灵控制。然而自杀非常痛苦,所以萌军指挥官决定到达目的地后让飞机没油而坠落(也避免逃兵)。军官提供两种油:石油和中国输送来的地沟油,刚开始飞机没有油,飞机可以加几桶石油和几桶地沟油(假设石油和地沟油都有无限桶),飞机落地时必须把油耗尽,已知一桶石油和一桶地沟油所能支撑的飞行距离分别为a,b,驾驶员们必须飞往一个目的地,总距离为c.

1.最少,最多需要加几桶油,若只有一种方案,最少和最多的是相同的.

2.总共有多少种不同的加油配方(死法)能到达目的地。

【输入格式】

只有一行,三个正整数a,b,c

【输出格式】

两行,第一行为最少加几次油和最多加几次油,

第二行为加油方法总数。

若不存在任何方法,第一行输出-1 -1

第二行输出0

【样例输入】

样例1:
2 3 10
样例2:
6 8 10

【样例输出】

样例1:
4 5
2
样例2:
-1 -1
0

【提示】

样例解释:

样例一:飞机加两次石油,两次地沟油,总次数为4,2*2+3*3=10

飞机加五次石油,不加地沟油,总次数为5,2*5+3*0=10

总共两种

样例二:飞机无法到达目的地

数据范围:

对于10%的数据,a<=103,b<=103,c<=103

对于20%的数据,a<=104,b<=104,c<=106

对于50%的数据,a<=109,b<=109,c<=109

对于100%数据,a<=3⋅1018,b<=3⋅1018,c<=3⋅1018

三个答案分值权重分别为20%,30%,50%

【来源】

这个题就是个扩展欧几里得的裸题,也不算太裸,因为涉及到求最小值和最大值的问题

但是自己写了一个交上去爆零,后来看了看比人写的代码,发现还是懵逼在45—49行里。。

4546貌似是求最大区间,,但是为什么要/b/a呢?x为什么要加负号呢??

还有ans1,ans2的b-a是什么鬼。。

啊啊啊啊啊啊为什么为什么为什么。。。。。。

=.=

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<vector>
 6 #include<map>
 7 #define LL long long 
 8 using namespace std;
 9 LL a,b,c,x,y;
10 LL read(LL & n)
11 {
12     int flag=0,x=0;char c='/';
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
15     if(flag)n=-x;
16     else n=x;
17 }
18 LL gcd(LL a,LL b)
19 {
20     if(b==0)return a;
21     else return gcd(b,a%b);
22 }
23 LL exgcd(LL a,LL b,LL &x ,LL & y)
24 {
25     if(b==0)
26     {x=1;y=0;return a;}
27     LL r=exgcd(b,a%b,x,y);
28     LL tmp=x;x=y;y=tmp-(a/b)*y;
29     return r;
30 }
31 int main()
32 {
33     //freopen("BlackHawk.in","r",stdin);
34     //freopen("BlackHawk.out","w",stdout);
35     //read(a);read(b);read(c);
36     cin>>a>>b>>c;
37     LL p=gcd(a,b);
38     if(c%p!=0)
39     {
40         printf("-1 -1\n0");
41         return 0;
42     }
43     exgcd(a,b,x,y);
44 //    printf("%d %d",x,y);
45     LL xx=ceil((long double)-x/b*c);
46     LL yy=floor((long double)y/a*c);
47     LL ans=yy-xx+1;
48     LL ans1=x*c/p+y*c/p+(b-a)/p*yy;
49     LL ans2=x*c/p+y*c/p+(b-a)/p*xx;
50     if(ans<=0) printf("-1 -1\n0");
51     else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl<<ans;
52     return 0;
53 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷 P1313 计算系数

    题目描述 给定一个多项式 ,请求出多项式展开后 项的系数。 输入输出格式 输入格式: 输入文件名为factor.in。 共一行,包含5 个整数,分别为 a...

    attack
  • 洛谷P3383 【模板】线性筛素数(Miller_Rabin)

    题目描述 如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内) 输入输出格式 输入格式: 第一行包含两个正整数N、M,分别表示...

    attack
  • 11.6NOIP模拟赛解题报告

    很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

    attack
  • 打表法——暴力破解方法之一

    特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~

    lollipop72
  • POJ 2773 Happy 2006(容斥原理+二分)

    Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

    ShenduCC
  • 洛谷 P1313 计算系数

    题目描述 给定一个多项式 ,请求出多项式展开后 项的系数。 输入输出格式 输入格式: 输入文件名为factor.in。 共一行,包含5 个整数,分别为 a...

    attack
  • 11.6NOIP模拟赛解题报告

    很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

    attack
  • 洛谷P3383 【模板】线性筛素数(Miller_Rabin)

    题目描述 如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内) 输入输出格式 输入格式: 第一行包含两个正整数N、M,分别表示...

    attack
  • 洛谷P3178 [HAOI2015]树上操作

    题目描述 有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节...

    attack
  • 洛谷P1306 斐波那契公约数

    题目描述 对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多...

    attack

扫码关注云+社区

领取腾讯云代金券