集训模拟赛-1-T2

好了不要在铺垫了直接整吧就

题目拿来！！！！！！！

倒水
（water）
(256MB,1s)
【问题描述】
你有一个水桶（记为 0），两个杯子（记为 1，2）。水桶中的水量
无限，容量也无限。1 号杯子容量为 a ml，2 号杯子容量为 b ml。一
开始，两个杯子里都没有水。
你可以执行以下几种操作：
1、将 1 号杯子中的水倒入水桶
2、将水桶中的水倒入 2 号杯子
3、将 2 号杯子中的水倒入 1 号杯子
每次倒水直到倒出水的杯子满或倒入水的杯子空才停止。
现在希望 1 号杯子中的水尽量少，但大于 0。
问通过以上操作能够获得 1 号杯子的最少水量 t 为多少？（t>0）
记获得最少水量执行了 pa 次操作 1，pb 次操作 2，希望在最少水量
的条件下 pa 尽量小（在 pa 相同的情况下还希望 pb 尽量小）。

【输入格式】
输入文件名为water.in
一行，两个数正整数 a b
【输出格式】
输出文件名为water.out
一行，三个数 t pa pb
（各变量含义如题所述）
【输入样例】
water.in water.out
5 3 1 1 2

倾倒方案为：
 0->2；
 2->1；
 0->2;
 2->1;
 1->0；
 2->1;
【数据规模与约定】
对于 20%的数据，pa,pb 总和不超过 5
对于 60%的数据，pa<=10^8
对于 100%的数据，0<b<=a<=10^9

说实话当时看完这个题我直接套各种东西= =因为一点思路都没有

但它实际上是个推理题

首先我们要知道每个操作执行时满足的条件

1号杯它不会在没有满时倒出，因为1杯未满说明2杯已空（一定有2->1的情况）若倒了就又重新开始了。

2号杯也只有在空的时候会执行二号操作

而2->1可以看作一步操作，因为水量是一定的，他们不对1号杯最小水量做出影响

把1杯2杯步骤三看作一个整体

杯子容量a+b=x 一开始a,b为空

到了末期一定是a>=0,b=0

体现在代码上：

一号操作：x=x-a

二号：x=x+b

三号：x=x

则求a（min）等于求x（min）

一号操作Pa次，二号操作Pb次，余下的水s=Pb*b-Pa*a

余下a与b的线性组合

x（min）=gcd(a,b)

s=gcd(a,b)

且他们的解还要除一个gcd才是min值的累加

解为-Pa+kb,Pb-ka

最小为 -Pa+kb/gcd(a,b),Pb-ka/gcd(a,b)

（好了我知道你们看不懂= =算了，代码一上估计就好理解多了）

那就代码走起！！！！！！！

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 using namespace std;

 int g[][];//邻接矩阵

 int f[][][][];//floyd

 int _Min(int x,int y){return x<y?x:y;}

 int main()

 {

     freopen("travel.in","r",stdin);

     freopen("travel.out","w",stdout);

     memset(g,,sizeof(g));

     memset(f,,sizeof(f));

     int n,m,T,x,y,k,i,j,l,r,s,t,L;

     scanf("%d%d",&n,&m);

     for(i=;i<=m;i++)

     {

       scanf("%d%d%d",&x,&y,&k);

       g[x][y]=_Min(g[x][y],k);//保存邻接矩阵中

     }

     for(l=;l<=n;l++)//f[] 预处理

       for(r=l;r<=n;r++)//先枚举 l r

       {

         for(i=;i<=n;i++)

           for(j=;j<=n;j++)

           {

             if(l==r)//只能途经一个点

               f[l][r][i][j]=_Min(g[i][j],g[i][l]+g[l][j]);//比较

             else

               f[l][r][i][j]=_Min(f[l][r-][i][j],f[l][r-][i][r]+f[l][r-][r][j]);//经不经过r

           }

       }

     scanf("%d",&T);//询问

     while(T--)

     {

       scanf("%d%d%d",&s,&t,&L);

       if(g[s][t]<=L){

       printf("-1\n");//-1为最小的能取到直接出最小答案

       continue;

       }

       r=;//分界点右边的节点 恰好小于等于限制条件的那个

       int ans=<<;

       for(l=;l<=n;l++)

       {

         while(r<=n&&f[l][r][s][t]>L)r++;//对于每一行看看是否需要右移 限制在n之内分界点不出去

         if(r>n)break;

         ans=_Min(ans,r-l);//更新答案

       }

       if(ans==<<)ans=-;//没有满足条件，直接出-2

       printf("%d\n",ans);

     }

     return ;

 }

o的k？

奥利给！整他就完了！

好了今天就到这里吧如有不懂我也不会讲= =

散会！

巴特西

集训模拟赛-1-T2

最新文章

热门文章