AtCoder Beginner Contest 051

A

Time limit : 2sec / Memory limit : 256MB

Score : 100 points

Problem Statement

As a New Year's gift, Dolphin received a string s of length 19. The string s has the following format: [five lowercase English letters],[seven lowercase English letters],[five lowercase English letters]. Dolphin wants to convert the comma-separated string s into a space-separated string. Write a program to perform the conversion for him.

Constraints

  • The length of s is 19.
  • The sixth and fourteenth characters in s are ,.
  • The other characters in s are lowercase English letters.

Input

The input is given from Standard Input in the following format:

1
s

Output

Print the string after the conversion.

Sample Input 1

1
happy,newyear,enjoy

Sample Output 1

1
happy newyear enjoy

Replace all the commas in happy,newyear,enjoy with spaces to obtain happy newyear enjoy.

Sample Input 2

1
haiku,atcoder,tasks

Sample Output 2

1
haiku atcoder tasks

Sample Input 3

1
abcde,fghihgf,edcba

Sample Output 3

模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
map<ll, ll> f;
ll cal(ll n)
{
    if (f[n])
    {
        return f[n];
    }
    return f[n] = (cal(n / 2) + cal((n - 1) / 2) + cal((n - 2) / 2)) % mod;
}
int main()
{
    string s;
    cin >> s;
    for (auto c : s)
    {
        if (c == ',')
        {
            cout << ' ';
        }
        else
        {
            cout << c;
        }
    }
    cout << '\n';
    return 0;
}

B

Time limit : 2sec / Memory limit : 256MB

Score : 200 points

Problem Statement

You are given two integers K and S. Three variable X,Y and Z takes integer values satisfying 0≤X,Y,Z≤K. How many different assignments of values to X,Y and Z are there such that X+Y+Z=S?

Constraints

  • 2≤K≤2500
  • 0≤S≤3K
  • K and S are integers.

Input

The input is given from Standard Input in the following format:

1
K S

Output

Print the number of the triples of X,Y and Z that satisfy the condition.

Sample Input 1

1
2 2

Sample Output 1

1
6

There are six triples of X,Y and Z that satisfy the condition:

  • X=0,Y=0,Z=2
  • X=0,Y=2,Z=0
  • X=2,Y=0,Z=0
  • X=0,Y=1,Z=1
  • X=1,Y=0,Z=1
  • X=1,Y=1,Z=0

Sample Input 2

1
5 15

Sample Output 2

1
1

The maximum value of X+Y+Z is 15, achieved by one triple of X,Y and Z.

暴力枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
map<ll, ll> f;
ll cal(ll n)
{
    if (f[n])
    {
        return f[n];
    }
    return f[n] = (cal(n / 2) + cal((n - 1) / 2) + cal((n - 2) / 2)) % mod;
}
int main()
{
    int k, s;
int ans=0;
    cin >> k >> s;
    for (int x = 0; x <= k; x++)
    {
        for (int y = 0; y <= k; y++)
        {
            int z = s - x - y;
            if (z >= 0 && z <= k)
                ans++; // 越界否？
        }
    }
    cout << ans;
    return 0;
}

C

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

Dolphin resides in two-dimensional Cartesian plane, with the positive x-axis pointing right and the positive y-axis pointing up. Currently, he is located at the point (sx,sy). In each second, he can move up, down, left or right by a distance of 1. Here, both the x- and y-coordinates before and after each movement must be integers. He will first visit the point (tx,ty) where sx<tx and sy<ty, then go back to the point (sx,sy), then visit the point (tx,ty) again, and lastly go back to the point(sx,sy). Here, during the whole travel, he is not allowed to pass through the same point more than once, except the points (sx,sy) and (tx,ty). Under this condition, find a shortest path for him.

Constraints

  • −1000≤sx<tx≤1000
  • −1000≤sy<ty≤1000
  • sx,sy,tx and ty are integers.

Input

The input is given from Standard Input in the following format:

Output

Print a string S that represents a shortest path for Dolphin. The i-th character in S should correspond to his i-th movement. The directions of the movements should be indicated by the following characters:

  • U: Up
  • D: Down
  • L: Left
  • R: Right

If there exist multiple shortest paths under the condition, print any of them.

构造题：沿着外围构造即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// LUOGU_RID: 173261940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
map<ll, ll> f;
ll cal(ll n)
{
    if (f[n])
    {
        return f[n];
    }
    return f[n] = (cal(n / 2) + cal((n - 1) / 2) + cal((n - 2) / 2)) % mod;
}
int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    for (int i = 1; i <= ty - sy; i++)
        cout << "U";
    for (int i = 1; i <= tx - sx; i++)
        cout << "R";
    for (int i = 1; i <= ty - sy; i++)
        cout << "D";
    for (int i = 1; i <= tx - sx + 1; i++)
        cout << "L";
    for (int i = 1; i <= ty - sy + 1; i++)
        cout << "U";
    for (int i = 1; i <= tx - sx + 1; i++)
        cout << "R";
    cout << "DR";
    for (int i = 1; i <= ty - sy + 1; i++)
        cout << "D";
    for (int i = 1; i <= tx - sx + 1; i++)
        cout << "L";
    cout << "U" << endl;
    return 0;
}

D

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges. The i-th (1≤i≤M) edge connects vertex *a**i* and vertex *b**i* with a distance of *c**i. Here, a self-loop* is an edge where ai=bi(1≤i≤M), and double edges are two edges where (ai,bi)=(aj,bj) or (ai,bi)=(bj,aj)(1≤i<j≤M). A connected graph is a graph where there is a path between every pair of different vertices. Find the number of the edges that are not contained in any shortest path between any pair of different vertices.

Constraints

  • 2≤N≤100
  • N−1≤M≤min(N(N−1)⁄2,1000)
  • 1≤ai,bi≤N
  • 1≤*c**i*≤1000
  • *c**i* is an integer.
  • The given graph contains neither self-loops nor double edges.
  • The given graph is connected.

思路：看范围知做法：考虑Floyd的更新方式进行求解，因为被更新了，这条边就没用了，ans++，由于是无向图，最后需要÷2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// LUOGU_RID: 173271809
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
map<ll, ll> f;
ll cal(ll n)
{
    if (f[n])
    {
        return f[n];
    }
    return f[n] = (cal(n / 2) + cal((n - 1) / 2) + cal((n - 2) / 2)) % mod;
}
const int N = 101;
int g[N][N];
bool vis[N][N];
int main()
{
    int n, m;
    cin >> n >> m;
     memset(g, 0x3f3f3f, sizeof g);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = g[y][x] = z;
        vis[x][y] = vis[y][x] = 1;
    }
    ll ans = 0;
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (g[i][j] > g[i][k] + g[k][j])
                {
                    if (vis[i][j])
                    {
                        ans++;
                        vis[i][j] = 0;
                    }
                    g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
    }
    cout << (ans >> 1) << '\n';
    return 0;
}

今日收获：Floyd经验++？这种题其实也很套路。