AtCoder Beginner Contest 257

D - Jumping Takahashi 2

Title Description ：

On a two-dimensional plane there is n A trampoline , Each trampoline has an elastic value p, You have an initial jumping ability S, The condition for jumping from one point to another is $P_i\ast S>=|x_i-x_j|+|y_i-y_j|$

ask S When the minimum is , Satisfaction can make starting from any point , Can reach any other point

Ideas ：

According to the above formula , It's not hard to find out $S>=\lceil \frac{|x_i-x_j|+|y_i-y_j|}{p_i}\rceil$

We can use this , As the distance between two points , run floyed Maintain the maximum weight on the shortest path , Enumerate each point as the starting point , Find the maximum value of the path from each point to other points , Take a minimum

Or you can split the answer , then dfs Explosive search , But I think this method is too complicated to write

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, k, op, x;
struct ran{
    
    ll x, y;
    ll p;
}tr[MAX];
ll dis[205][205];
void work(){
    
    cin >> n;
    for(int i = 1; i <= n; ++i){
    
        cin >> tr[i].x >> tr[i].y >> tr[i].p;
    }
    for(int i = 1; i <= n; ++i){
    
        for(int j = 1; j <= n; ++j){
    
            dis[i][j] = (abs(tr[i].x - tr[j].x) + abs(tr[i].y - tr[j].y) + tr[i].p - 1) / tr[i].p;
        }
    }
    for(int k = 1; k <= n; ++k){
    
        for(int i = 1; i <= n; ++i){
    
            for(int j = 1; j <= n; ++j){
    
                dis[i][j] = min(dis[i][j], max(dis[i][k] , dis[k][j]));
            }
        }
    }
    ll ans = 1e18;
    for(int i = 1; i <= n; ++i){
    
        ll cnt = 0;
        for(int j = 1; j <= n; ++j){
    
            cnt = max(cnt, dis[i][j]);
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}


int main(){
    
    io;
    work();
    return 0;
}

E - Addition and Multiplication 2

Title Description ：

You have now n element , You can spend c[i] Yuan , Multiply the current value by 10 + i, The initial value in hand is 0, Ask how much value you can get at most

Ideas ：

Obviously, it is best to keep the length as long as possible

When the length is the longest , Let's consider choosing some that won't make the length smaller , And value i Bigger , Just be greedy

Let's first determine how many numbers are output , Then enumerate which number is output each time , Enumeration starts from 9 Enumerate to 1, Judge the remaining money minus the current c[i] Whether the total length will be changed

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op, x;
int c[10];
void work(){
    
    cin >> n;
    for(int i = 1; i <= 9; ++i){
    
        cin >> c[i];
    }
    int minx = *min_element(c + 1, c + 10);
    k = n / minx;
    for(int i = 1; i <= k; ++i){
    
        for(int j = 9; j >= 1; --j){
    
            if(n - c[j] >= minx * (k - i)){
    
                n -= c[j];
                cout << j;
                break;
            }
        }
    }
}


int main(){
    
    io;
    work();
    return 0;
}

F - Teleporter Setting

Title Description ：

n A little bit ,m side , The weight of each edge is 1, When there are some edge endpoints 0, It means that this edge is not fixed

Now you need to output n A digital , Indicates that all unfixed edges are connected to i After going up ,1 To n One of the most short circuit

Ideas ：

Because all unfixed edges are connected to the same point every time , So we can consider when we build the map , hold 0 As a special point , Normal mapping , Then we run twice bfs, Find out respectively with 1 As a starting point and with n The shortest circuit when it is the starting point , For each connection to i The situation of , We have two situations , One is not to take that special side , The answer is 1 To n One of the most short circuit , The other is to take a special side , At this time we can put 0 as i, There are two situations , One is 1 To i, Again from i To n, The other case is 1 To 0, Again from i To n, For these three cases, we can find a minimum value

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op, x, y;
vector<int>G[MAX];
int dis1[MAX];
int dis2[MAX];
void work(){
    
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
    
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    mem(dis1, inf);
    mem(dis2, inf);
    queue<int>q;
    q.push(1);
    dis1[1] = 0;
    while(!q.empty()){
    
        int u = q.front();q.pop();
        for(auto v : G[u]){
    
            if(dis1[v] != inf)continue;
            dis1[v] = dis1[u] + 1;
            q.push(v);
        }
    }
    q.push(n);
    dis2[n] = 0;
    while(!q.empty()){
    
        int u = q.front();q.pop();
        for(auto v : G[u]){
    
            if(dis2[v] != inf)continue;
            dis2[v] = dis2[u] + 1;
            q.push(v);
        }
    }
    for(int i = 1; i <= n; ++i){
    
        int ans = min(dis1[n], min(dis1[i] + dis2[0], dis1[0] + dis2[i]));
        if(ans == inf)cout << -1 << ' ';
        else cout << ans << ' ';
    }
    cout << endl;
}


int main(){
    
    io;
    work();
    return 0;
}