ABC070

[ABC070B] Two Switches

题面翻译

题目描述

Alice和Bob都有一个开关用来控制机器人。 Alice在A秒按下开关，移动机器人，并在B秒后释放开关。

Bob在C秒按下开关，移动机器人，并在D秒后释放开关。

求Alice和Bob都按下开关的秒数。

输入格式

一行，有四个正整数A，B，C，D。分别代表Alice在第A秒按下开关，在第B秒释放开关。Bob在第C秒按下开关，在第D秒释放开关。

输出格式

输出Alice和Bob都按下开关的秒数

题目描述

Alice と Bob は、ロボットを制御するためのスイッチを1つずつ持っており、ロボットを動かしています。
Alice はロボットを動かし始めて $ A $ 秒後にスイッチを押し始め、ロボットを動かし始めて $ B $ 秒後にスイッチを離しました。
Bob はロボットを動かし始めて $ C $ 秒後にスイッチを押し始め、ロボットを動かし始めて $ D $ 秒後にスイッチを離しました。
Alice と Bob が、二人ともスイッチを押していた秒数を求めてください。

输入格式

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

$ A $ $ B $ $ C $ $ D $

输出格式

Alice と Bob が二人ともスイッチを押していた秒数を出力せよ。

样例 #1

样例输入 #1
0 75 25 100
样例输出 #1
50
样例 #2

样例输入 #2
0 33 66 99
样例输出 #2
0
样例 #3

样例输入 #3
10 90 20 80
样例输出 #3
60
提示

制約

$ 0≦A < B≦100 $

$ 0≦C < D≦100 $

入力は全て整数である。

Sample Explanation 1

ロボットを動し始めて $ 0 $ 秒後から $ 75 $ 秒後までの間、Alice はスイッチを押していました。一方、ロボットを動し始めて $ 25 $ 秒後から $ 100 $ 秒後までの間、Bob はスイッチを押していました。したがって、二人が同時にスイッチを押していた時間は、ロボットを動し始めて $ 25 $ 秒後から $ 75 $ 秒後までの $ 50 $ 秒です。

Sample Explanation 2

Alice と Bob が同時にスイッチを押していないので、答えは $ 0 $ 秒です。

思路

计算重合部分即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int x=max(a,c);
    int y=min(b,d);
    cout<<max(y-x,0);
    return 0;
}

[ABC070C] Multiple Clocks

题面翻译

题目描述

有N台钟表，第i个钟表的秒针经过T[i]秒绕表盘一周。最初，所有的钟表的秒针都指向上方。某人开始同时顺时针拨动所有时钟的秒针。下一次所有的时钟的秒针都向上是在几秒后？

输入

第一行：N；

以下N行：每行一个T[i]。

输出

一行，最少的拨动次数。

题目描述

$ N $ 台の時計があり、$ i(1≦i≦N) $ 番目の時計の針はちょうど $ T_i $ 秒で時計盤を $ 1 $ 周します。
最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。
イルカは、全ての時計の針を同時に動かし始めました。
再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?

输入格式

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

$ N $ $ T_1 $ $ : $ $ T_N $

输出格式

時計の針を動かし始めてから、再び全ての時計の針が真っ直ぐ上に向くまでの秒数を出力せよ。

样例 #1

样例输入 #1
2
2
3
样例输出 #1
6
样例 #2

样例输入 #2
5
2
5
10
1000000000000000000
1000000000000000000
样例输出 #2
1000000000000000000
提示

制約

$ 1≦N≦100 $

$ 1≦T_i≦10^{18} $

入力は全て整数である。

答えは $ 10^{18} $ 秒以内である。

Sample Explanation 1

$ 2 $ つの時計があり、各時計の針が真っ直ぐ上に向くのは以下の時刻です。 - $ 1 $ 番目の時計の針: 時計の針を動かし始めてから、$ 2 $ 秒後、$ 4 $ 秒後、$ 6 $ 秒後、$ ... $ - $ 2 $ 番目の時計の針: 時計の針を動かし始めてから、$ 3 $ 秒後、$ 6 $ 秒後、$ 9 $ 秒後、$ ... $ したがって、$ 2 $ つの時計の針が真っ直ぐ上に向くのにかかる秒数は $ 6 $ 秒となります。

思路

比较容易发现，其实要求的是所有$t$的最小公倍数。

直接利用$lcm(n,m)=\frac{n*m}{gcd(n,m)}$即可。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ull t[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
    }
    ull ans=t[1];
    for(int i=2;i<=n;i++){
        ans=(ans/__gcd(ans,t[i]))*t[i];
    }
    cout<<ans;
    return 0;
}

[ABC070D] Transit Tree Path

题面翻译

给出一棵有N个结点的树，给出Q个询问，求结点xj过结点K到节点yj的最短距离

题目描述

$ N $ 頂点の木が与えられます。
木とはグラフの一種であり、頂点の数を $ N $ とすると、辺の数が $ N-1 $ 本である閉路のない連結グラフです。
$ i(1≦i≦N-1) $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を距離 $ c_i $ で結びます。

また、$ Q $ 個の質問クエリと整数 $ K $ が与えられます。

$ j(1≦j≦Q) $ 番目の質問クエリでは、頂点 $ x_j $ から頂点 $ K $ を経由しつつ、頂点 $ y_j $ まで移動する場合の最短経路の距離を求めてください。

输入格式

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

$ N $ $ a_1 $ $ b_1 $ $ c_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ c_{N-1} $ $ Q $ $ K $ $ x_1 $ $ y_1 $ $ : $ $ x_{Q} $ $ y_{Q} $

输出格式

質問クエリの解答を $ Q $ 行出力せよ。
$ j(1≦j≦Q) $ 行目には、$ j $ 番目のクエリの答えを出力せよ。

样例 #1

样例输入 #1
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5
样例输出 #1
3
2
4
样例 #2

样例输入 #2
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7
样例输出 #2
5
14
22
样例 #3

样例输入 #3
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10
样例输出 #3
17000000000
提示

制約

$ 3≦N≦10^5 $

$ 1≦a_i,b_i≦N (1≦i≦N-1) $

$ 1≦c_i≦10^9 (1≦i≦N-1) $

与えられるグラフは木である。

$ 1≦Q≦10^5 $

$ 1≦K≦N $

$ 1≦x_j,y_j≦N (1≦j≦Q) $

$ x_j≠y_j (1≦j≦Q) $

$ x_j≠K,y_j≠K (1≦j≦Q) $

Sample Explanation 1

与えられた $ 3 $ つの質問クエリに対する最短経路は以下の通りです。 - $ 1 $ つ目の質問クエリ: 頂点 $ 2 $ → 頂点 $ 1 $ → 頂点 $ 2 $ → 頂点 $ 4 $ : 距離 $ 1+1+1=3 $ - $ 2 $ つ目の質問クエリ: 頂点 $ 2 $ → 頂点 $ 1 $ → 頂点 $ 3 $ : 距離 $ 1+1=2 $ - $ 3 $ つ目の質問クエリ: 頂点 $ 4 $ → 頂点 $ 2 $ → 頂点 $ 1 $ → 頂点 $ 3 $ → 頂点 $ 5 $ : 距離 $ 1+1+1+1=4 $

Sample Explanation 2

質問クエリに対する最短経路は、必ず頂点 $ K=2 $ を通過する必要があります。

思路

从$x$节点经过$k$节点到$y$节点的方法分为两步：

1、从$x$节点走到$k$节点。

2、从$k$节点走到$y$节点。

只需要从$k$出发，跑一遍最短路即可，答案就是$dis[x]+dis[y]$。

涉及$m$次询问，直接离线处理。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll n,m,k;
ll dis[MAXN],inq[MAXN];
struct Edge{
    ll from,to,val;
};
vector<Edge> edge[MAXN];
void add(ll from,ll to,ll val){
    Edge e={from,to,val};
    edge[from].push_back(e);
}
//利用spfa求最短路
void spfa(){
    for(int i=1;i<=n;i++){
        dis[i]=1e18;
    }
    dis[k]=0;
    queue<ll> q;
    q.push(k);
    while(q.size()){
        int from=q.front();
        q.pop();
        inq[from]=0;
        for(auto t:edge[from]){
            if(dis[t.to]>dis[from]+t.val){
                dis[t.to]=dis[from]+t.val;
                if(inq[t.to]==0){
                    inq[t.to]=1;
                    q.push(t.to);
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<n;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    cin>>m>>k;
    spfa();
    for(int i=1;i<=m;i++){
        ll x,y;
        cin>>x>>y;
        cout<<dis[x]+dis[y]<<"\n";
    }
    return 0;
}