AtCoder Beginner Contest 043

A

题目大意：

求 1−n之和

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
55
56
57
58
59
60
61
#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]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
int n;
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++)
{
    sum+=i;
}
cout<<sum<<'\n';
return 0;
}

B

题目大意：

给一个字符串，01表示输入，B表示退格，问最后结果

直接用栈模拟。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    string s;
    cin >> s;
    stack<char> a;
    for (auto c : s)
    {
        if (c == 'B')
        {
            if (!a.empty())
            {
                a.pop();
            }
        }
        else
        {
            a.push(c);
        }
    }
    string h = "";
    while (!a.empty())
    {
        char c = a.top();
        h += c;
        a.pop();
    }
    reverse(h.begin(), h.end());
    cout << h << '\n';

    return 0;
}

C

题目大意： 把 n个整数都变成一个相同的数，将 x 转成 y 的代价为 \((x−y)^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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    int n;
    cin >> n;
    int sum = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    int s = sum / n;
    int res = 1e9;
    for (int x = s - 1; x <= s + 1; x++)
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ans += (x - a[i]) * (x - a[i]);
        }
        res = min(res, ans);
    }
    cout << res << '\n';
    return 0;
}

D

题目大意： 给你一个字符串 s，请你求出它的一个子串，这个子串中同一个字符出现次数大于一半，输出任意一个满足条件的子串的起止位置。

手玩一下会发现满足这个条件的子串最小一定是长度为2或者长度为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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    string s;
    cin >> s;
    int n = s.length() - 1;
    for (int i = 0; i <= n - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            cout << i + 1 << " " << i + 2 << '\n';
            return 0;
        }
        if (s[i] == s[i + 2])
        {
            cout << i + 1 << " " << i + 3 << '\n';
            return 0;
        }
    }
    cout << -1 << ' ' << -1 << '\n';
    return 0;
}