ABC074

[ABC074C] Sugar Water

题面翻译

废柴君正在烧杯中配置糖水。最初，烧杯是空的。废柴君可以多次执行以下四种类型的操作,每种操作不是必须的。

• 操作1：将 \(100 \times A\) 克水倒入烧杯中。
• 操作2：将 \(100 \times B\) 克水倒入烧杯中。
• 操作3：将 \(C\) 克糖放入烧杯中。
• 操作4：将 \(D\) 克糖放入烧杯中。

在我们的实验环境中，至多 \(E\) 克糖可溶解于 \(100\) 克水。 \(a\) 克水，\(b\) 克糖的糖水记作百分之 $ $。 废柴君想用现有材料配置具有百分率最高的糖水。 烧杯最多可容纳 \(F\) 克糖水，并且烧杯中不能有任何不溶解的糖。

输入 一行按顺序给出 \(A \sim F\)

输出 输出废柴君将配置的糖水的质量，以及溶解在其中的糖的质量。如果有多种答案，任意输出一个即可。

\(1 \leqslant A < B \leqslant 30\)

\(1 \leqslant C < D \leqslant 30\)

\(1 \leqslant E \leqslant 100\)

\(100A \leqslant F \leqslant 3000\)

输入数据均为整数。

样例 1 解释

此时，\(15\) 克糖可溶解于 \(100\) 克水，烧杯最多可容纳 \(200\) 克糖水。

我们可以配置 \(110\) 克糖水，即执行操作 \(1\) 和操作 \(3\)。但我们无法制造更优的糖水。例如，以下操作顺序就是不可行的：

如果我们进行一次操作 \(1\) 和一次操作 \(4\)，则烧杯中将会有未溶解的糖。 如果我们执行操作 \(2\) 一次和操作 \(3\) 三次，烧杯中的糖水质量将超过 \(200\) 克。

样例2解释

\(200 ~ 100\)

\(400 ~ 200\) 也是正确的。

\(300 ~ 150\) 是错误的。 这是因为，为了配置 \(300\) 克 \(50\%\) 的糖水我们得准确倒入 \(150\) 克糖，这当然是不可能的。

Translated by @yyhhenry

题目描述

すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の $ 4 $ 種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。

• 操作 1: ビーカーに水を $ 100A $ [g] 入れる。
• 操作 2: ビーカーに水を $ 100B $ [g] 入れる。
• 操作 3: ビーカーに砂糖を $ C $ [g] 入れる。
• 操作 4: ビーカーに砂糖を $ D $ [g] 入れる。

すぬけ君の実験環境下では、水 $ 100 $ [g] あたり砂糖は $ E $ [g] 溶けます。

すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。

ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が $ F $ [g] 以下であり、 ビーカーの中に砂糖を溶け残らせてはいけないとき、 すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。 答えが複数ある場合はどれを答えても構いません。

水 $ a $ [g] と砂糖 $ b $ [g] を混ぜた砂糖水の濃度は $ $ [%]です。 また、この問題では、砂糖が全く溶けていない水も濃度 $ 0 $ [%] の砂糖水と考えることにします。

输入格式

入力は以下の形式で標準入力から与えられる。

$ A $ $ B $ $ C $ $ D $ $ E $ $ F $

输出格式

整数を空白区切りで $ 2 $ つ出力せよ。 $ 1 $ つ目は求める砂糖水の質量、$ 2 $ つ目はそれに溶けている砂糖の質量とせよ。

样例 #1

样例输入 #1

1 2 10 20 15 200

样例输出 #1

110 10

样例 #2

样例输入 #2

1 2 1 2 100 1000

样例输出 #2

200 100

样例 #3

样例输入 #3

17 19 22 26 55 2802

样例输出 #3

2634 934

提示

制約

• $ 1 ≦ A < B ≦ 30 $
• $ 1 ≦ C < D ≦ 30 $
• $ 1≦ E ≦ 100 $
• $ 100A ≦ F ≦ 3,000 $
• $ A, B, C, D, E, F $ はすべて整数である。

Sample Explanation 1

この入力例の状況では、水 $ 100 $ \[g\] あたり砂糖は $ 15 $ \[g\] 溶けます。 また、ビーカーに物質を $ 200 $ \[g\] まで入れることができます。 操作 1 と操作 3 を $ 1 $ 回ずつ行うことで $ 110 $ \[g\] の砂糖水を作ることができます。 また、これ以上濃度の高い砂糖水を作ることはできません。 たとえば、以下のような操作は条件を満たしません。 - 操作 1 と操作 4 を $ 1 $ 回ずつ行うと、ビーカーに砂糖が溶け残ってしまいます。 - 操作 2 を $ 1 $ 回と操作 3 を $ 3 $ 回行うと、ビーカーの中の物質の量が $ 200 $ \[g\] を超えてしまいます。

Sample Explanation 2

ほかに、たとえば以下の出力も正解となります。 400 200 一方、以下の出力は不正解となります。 300 150 なぜなら、砂糖が $ 150 $ \[g\] 溶けた $ 300 $ \[g\] の砂糖水を作るにはビーカーに水をちょうど $ 150 $ \[g\] 入れる必要がありますが、そのようなことは不可能だからです。

思路

这道题有两种方法：循环枚举或者使用DP。

先介绍枚举法：我们可以枚举每一种可能的操作，判断是否符合题意，再取最大值。

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int ans1,ans2;
int a,b,c,d,e,f;
ld sum;
void check(ld x,ld y){
    if(x+y>f)return;			//总质量不能超过f
    if(x*e<y*100)return;		//最多100克水可以溶解e克糖
    if(sum<=100*y/(x+y)){		//取max
        sum=100*y/(x+y),ans1=x+y,ans2=y;
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>a>>b>>c>>d>>e>>f;
    for(int i=0;i<=100;i++){			//为什么枚举的范围是100？因为f最大为3000，a最大为30
        for(int j=0;j<=100;j++){
            for(int k=0;k<=100;k++){
                for(int l=0;l<=100;l++){
                    check(100*a*i+100*b*j,c*k+d*l);
                }
            }
        }
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}

更加有效的解法是使用DP。

#include<bits/stdc++.h>
using ll=long long;
using ld=long double;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int a,b,c,d,e,f;
//思路：使用dp
//其实有点类似于背包问题：体积限制和比例限制，属于方案问题
//dp[i][j]表示i克水，j克糖的溶剂能否配出。
//可以通过枚举i和j进行dp
//比例限制直接在dp的过程中判断即可。
bool dp[3010][3010];
int li,lj;
int ans1,ans2;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>a>>b>>c>>d>>e>>f;
    dp[0][0]=true;
    li=100,lj=0;
    for(int i=0;i<=f;i++)
    {
        for(int j=0;j+i<=f;j++)
        {
            if(i-100*a>=0)  dp[i][j]=dp[i-100*a][j]|dp[i][j];
            if(i-100*b>=0)  dp[i][j]=dp[i-100*b][j]|dp[i][j];
            if(j-c>=0)      dp[i][j]=dp[i][j]|dp[i][j-c];
            if(j-d>=0)      dp[i][j]=dp[i][j]|dp[i][j-d];
            if(e*i>=j*100 && dp[i][j])
            {
                if(j*li>=i*lj)			//这里=不能漏了，不然会WA一个点，因为是合法的情况，后续可能一些其他的情况是从这里开始更新的，所以即使是=，也必须更新。
                {
                    ans1=i+j,   ans2=j;
                    li=i;
                    lj=j;
                }
            }
        }
    }
    std::cout<<ans1<<" "<<ans2;
}

[ABC074D] Restoring Road Network

题面翻译

题面翻译

曾经存在的高桥王国有N个城市，城市与城市之间用长度为正整数的无向道路连接。

现有一考古学家找到了一张N×N的表A，这张表代表了这N座城市两两之间的最短路。即表中的第u行第v列的值代表了从城市u到v的最短路长度。

问能否根据这张表，求出高桥王国的最小道路长度总和。

输入格式

第一行：N 下面是大小为N×N的表A

输出格式

一个整数，表示最小道路长度总和。如果无解，输出−1

数据范围与约定

• 1 <= N <= 300
• 当 i != j 时，1 <= 表A中第i行第j列的值 == 表A中第j行第i列的值 <= 10^9
• 表A中第i行第i列的值为0

样例1解释

• 从城市1到城市2有长度为1的直接道路
• 从城市2到城市3有长度为2的直接道路
• 从城市1到城市3无直接道路

样例2解释

从城市1走到城市2要走长度为1的道路，从城市2走到城市3要走长度为1的道路，所以从城市1到城市3要走的距离为2，但表中是3，所以无解。

题目描述

かつて存在した高橋王国には $ N $ 個の都市があり、いくつかの都市の組は道路で双方向に結ばれていました。 道路の構造は以下のようであったことがわかっています。

• 都市間の移動は道路を通ってのみ行われ、どの都市からどの都市へも必要なら他の都市を経由することで移動できるようになっていた。
• 道路の長さは道路によって異なっていたかもしれないが、全て正整数であった。

考古学者のすぬけ君は、高橋王国の遺跡で整数からなる $ N  N $ の表 $ A $ を発見しました。 すぬけ君は、この表は高橋王国における都市間の道路に沿った最短距離を表した表ではないかと考えました。

すべての $ u, v $ について、$ A $ の $ u $ 行目 $ v $ 列目の整数 $ A_{u, v} $ が都市 $ u $ から都市 $ v $ への最短経路の長さとなるような 道路の構造が存在するかどうか判定してください。 さらに、存在する場合、そのような道路の構造のうち、存在する道路の長さの和が最小となるようなものについて、その和を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_{1, 1} $ $ A_{1, 2} $ $ ... $ $ A_{1, N} $ $ A_{2, 1} $ $ A_{2, 2} $ $ ... $ $ A_{2, N} $ $ ... $ $ A_{N, 1} $ $ A_{N, 2} $ $ ... $ $ A_{N, N} $

输出格式

条件を満たす道路の構造が存在しない場合、-1 と出力せよ。 存在する場合、道路の長さの和の最小値を出力せよ。

样例 #1

样例输入 #1

3
0 1 3
1 0 2
3 2 0

样例输出 #1

3

样例 #2

样例输入 #2

3
0 1 3
1 0 1
3 1 0

样例输出 #2

-1

样例 #3

样例输入 #3

5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

样例输出 #3

82

样例 #4

样例输入 #4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

样例输出 #4

3000000000

提示

制約

• $ 1≦N≦300 $
• $ i ≠ j $ のとき、$ 1 ≦ A_{i, j} = A_{j, i} ≦ 10^9 $
• $ A_{i, i} = 0 $

Sample Explanation 1

条件を満たす道路の構造は以下のとおりです。 - 都市 $ 1 $ と都市 $ 2 $ の間は長さ $ 1 $ の道路によって結ばれている。 - 都市 $ 2 $ と都市 $ 3 $ の間は長さ $ 2 $ の道路によって結ばれている。 - 都市 $ 3 $ と都市 $ 1 $ の間は道路で結ばれていない。

Sample Explanation 2

都市 $ 1 $ から都市 $ 2 $ へ、および都市 $ 2 $ から都市 $ 3 $ へそれぞれ距離 $ 1 $ で移動できることから、 都市 $ 1 $ から都市 $ 3 $ へは都市 $ 2 $ を経由することで距離 $ 2 $ で移動できることがわかります。 一方、都市 $ 1 $ と都市 $ 3 $ の間の最短距離は $ 3 $ でなければなりません。 よって条件を満たす道路の構造は存在しないことがわかります。

思路

题意看上去有些复杂，实际上就是根据题目给的最短路地图，判断是否合法。

如果不合法输出-1，否则输出全部的最短路。

因为是全图的，所以不难想到Floyd算法。

#include<bits/stdc++.h>
using ll=long long;
using ld=long double;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll d[310][310];
ll a[310][310];
bool vis[310][310];
ll ans;
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            std::cin>>a[i][j];
            d[i][j]=a[i][j];
            ans+=a[i][j];
        }
    }
    ans/=2;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=std::min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(d[i][j]!=a[i][j]) //|| a[i][j]!=a[j][i])
            {
                std::cout<<-1;
                return;
            }
        }
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(k==i)    continue;
            for(int j=i+1;j<=n;j++)
            {
                if(k==j)    continue;
                if(d[i][j]==d[i][k]+d[k][j] && !vis[i][j])          //这里还需要特别留意处理可能重复计算的情况，所以需要vis处理，避免多算
                {
                    ans-=d[i][j];
                    vis[i][j]=true;
                }
            }
        }
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
}