Atcoder ABC 070 B、C、D

时间：2024-10-03 14:04:32

B - Two Switches

Time limit : 2sec / Memory limit : 256MB

Score : 200 points

Problem Statement

Alice and Bob are controlling a robot. They each have one switch that controls the robot.
Alice started holding down her button A second after the start-up of the robot, and released her button B second after the start-up.
Bob started holding down his button C second after the start-up, and released his button D second after the start-up.
For how many seconds both Alice and Bob were holding down their buttons?

Constraints

  • 0≤A<B≤100
  • 0≤C<D≤100
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the length of the duration (in seconds) in which both Alice and Bob were holding down their buttons.

Sample Input 1

Copy
0 75 25 100

Sample Output 1

Copy
50

Alice started holding down her button 0 second after the start-up of the robot, and released her button 75 second after the start-up.
Bob started holding down his button 25 second after the start-up, and released his button 100 second after the start-up.
Therefore, the time when both of them were holding down their buttons, is the 50 seconds from 25 seconds after the start-up to 75 seconds after the start-up.

Sample Input 2

Copy
0 33 66 99

Sample Output 2

Copy
0

Alice and Bob were not holding their buttons at the same time, so the answer is zero seconds.

Sample Input 3

Copy
10 90 20 80

Sample Output 3

Copy
60

求Alice和Bob操作的公共时长
    #include <iostream>

    #include <algorithm>

    #include <cstring>

    #include <cstdio>

    #include <vector>

    #include <queue>

    #include <cstdlib>

    #include <iomanip>

    #include <cmath>

    #include <cassert>

    #include <ctime>

    #include <map>

    #include <set>

    using namespace std;

    #define lowbit(x) (x&(-x))

    #define max(x,y) (x>y?x:y)

    #define min(x,y) (x<y?x:y)

    #define MAX 100000000000000000

    #define MOD 1000000007

    #define pi acos(-1.0)

    #define ei exp(1)

    #define PI 3.141592653589793238462

    #define ios() ios::sync_with_stdio(false)

    #define INF 1044266558

    #define mem(a) (memset(a,0,sizeof(a)))

    typedef long long ll;

    int a,b,c,d;

    int main()

    {

        while(cin>>a>>b>>c>>d)

        {

            int ans=;

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

            {

                if((i>=a && i<=b) && (i>=c && i<=d))ans++;

            }

            printf("%d\n",ans->=?ans-:);

        }

        return ;

    }

C - Multiple Clocks

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

We have N clocks. The hand of the i-th clock (1≤i≤N) rotates through 360° in exactly Ti seconds.
Initially, the hand of every clock stands still, pointing directly upward.
Now, Dolphin starts all the clocks simultaneously.
In how many seconds will the hand of every clock point directly upward again?

Constraints

  • 1≤N≤100
  • 1≤Ti≤1018
  • All input values are integers.
  • The correct answer is at most 1018 seconds.

Input

Input is given from Standard Input in the following format:

N
T1
:
TN

Output

Print the number of seconds after which the hand of every clock point directly upward again.

Sample Input 1

Copy
2

2

3

Sample Output 1

Copy
6

We have two clocks. The time when the hand of each clock points upward is as follows:

  • Clock 1: 2, 4, 6, … seconds after the beginning
  • Clock 2: 3, 6, 9, … seconds after the beginning

Therefore, it takes 6 seconds until the hands of both clocks point directly upward.

Sample Input 2

Copy
5

2

5

10

1000000000000000000

1000000000000000000

Sample Output 2

Copy
1000000000000000000
求n个数的最小公倍数
    #include <iostream>

    #include <algorithm>

    #include <cstring>

    #include <cstdio>

    #include <vector>

    #include <queue>

    #include <cstdlib>

    #include <iomanip>

    #include <cmath>

    #include <cassert>

    #include <ctime>

    #include <map>

    #include <set>

    using namespace std;

    #define lowbit(x) (x&(-x))

    #define max(x,y) (x>y?x:y)

    #define min(x,y) (x<y?x:y)

    #define MAX 100000000000000000

    #define MOD 1000000007

    #define pi acos(-1.0)

    #define ei exp(1)

    #define PI 3.141592653589793238462

    #define ios() ios::sync_with_stdio(false)

    #define INF 1044266558

    #define mem(a) (memset(a,0,sizeof(a)))

    typedef long long ll;

    ll n,front,last;

    ll gcd(ll x,ll y)

    {

        return y==?x:gcd(y,x%y);

    }

    ll lcm(ll x,ll y)

    {

        return x/gcd(x,y)*y;

    }

    int main()

    {

        while(scanf("%lld",&n)!=EOF)

        {

            scanf("%lld",&front);

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

            {

                scanf("%lld",&last);

                front=lcm(front,last);

            }

            printf("%lld\n",front);

        }

        return ;

    }

D - Transit Tree Path

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

You are given a tree with N vertices.
Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N−1 edges, where N is the number of its vertices.
The i-th edge (1≤i≤N−1) connects Vertices ai and bi, and has a length of ci.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

  • find the length of the shortest path from Vertex xj and Vertex yj via Vertex K.

Constraints

  • 3≤N≤105
  • 1≤ai,bi≤N(1≤i≤N−1)
  • 1≤ci≤109(1≤i≤N−1)
  • The given graph is a tree.
  • 1≤Q≤105
  • 1≤K≤N
  • 1≤xj,yj≤N(1≤j≤Q)
  • xj≠yj(1≤j≤Q)
  • xj≠K,yj≠K(1≤j≤Q)

Input

Input is given from Standard Input in the following format:

N
a1 b1 c1
:
aN−1 bN−1 cN−1
Q K
x1 y1
:
xQ yQ

Output

Print the responses to the queries in Q lines.
In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

Copy
5

1 2 1

1 3 1

2 4 1

3 5 1

3 1

2 4

2 3

4 5

Sample Output 1

Copy
3

2

4

The shortest paths for the three queries are as follows:

  • Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3
  • Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2
  • Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4

Sample Input 2

Copy
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

Sample Output 2

Copy
5

14

22

The path for each query must pass Vertex K=2.

Sample Input 3

Copy
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

Sample Output 3

Copy
17000000000

n个顶点，n-1条边，所以不存在最优路径，那么只需要从给定k顶点开始dfs就可以了
    #include <iostream>

    #include <algorithm>

    #include <cstring>

    #include <cstdio>

    #include <vector>

    #include <queue>

    #include <cstdlib>

    #include <iomanip>

    #include <cmath>

    #include <cassert>

    #include <ctime>

    #include <map>

    #include <set>

    using namespace std;

    #define lowbit(x) (x&(-x))

    #define max(x,y) (x>y?x:y)

    #define min(x,y) (x<y?x:y)

    #define MAX 100000000000000000

    #define MOD 1000000007

    #define pi acos(-1.0)

    #define ei exp(1)

    #define PI 3.141592653589793238462

    #define ios() ios::sync_with_stdio(false)

    #define INF 1044266558

    #define mem(a) (memset(a,0,sizeof(a)))

    typedef long long ll;

    vector<pair<int,int> >v[];

    ll dis[];

    int n,k,x,y,w,q;

    bool vis[];

    void dfs(int x)

    {

        vis[x]=;

        for(int i=;i<v[x].size();i++)

        {

            if(!vis[v[x][i].first])

            {

                dis[v[x][i].first]=dis[x]+v[x][i].second;

                dfs(v[x][i].first);

            }

        }

    }

    int main()

    {

        while(scanf("%d",&n)!=EOF)

        {

            memset(vis,,sizeof(vis));

            memset(dis,,sizeof(dis));

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

                v[i].clear();

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

            {

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

                v[x].push_back(make_pair(y,w));

                v[y].push_back(make_pair(x,w));

            }

            scanf("%d%d",&q,&k);

            dfs(k);

            while(q--)

            {

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

                printf("%lld\n",dis[x]+dis[y]);

            }

        }

        return ;

    }

相关文章