AtCoder Beginner Contest 313

发表于 分类于

AtCoder Beginner Contest 313

Complete problemset

A - To Be Saikyo

题意

给出n个数，求第一个数至少需要增加多少才能成为最大的数。

思路

先找最大的数，如果第一个数不是最大，那么我们只需让最大-去第一个数+1，就是需要增长的量。

如果第一个数是最大，考虑是不是只有一个最大，如果是一个最大，那么不用增长，否则增长1。

代码

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
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& i : a)
        cin >> i;
    int mx = *max_element(a.begin(), a.end());
    if (mx == a[0] && count(a.begin(), a.end(), mx) == 1) {
        cout << "0\n";
    } else {
        cout << mx - a[0] + 1 << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B - Who is Saikyo?

题意

现在有n个人，给出m对数(x,y)，代表第x个人比第y个人强。

问是否存在一个人比所有人都强。

思路

我们将人与人的关系视为一个有向图。如果这个图中只有一个入度为0的点则是最强的点。

代码

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
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 55
#define MOD 998244353
using namespace std;

vector<int> g[N];

int in[N];

void sol() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        in[y]++;
    }
    int ans = -1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            cnt++;
            ans = i;
        }
    }
    if (cnt == 1)
        cout << ans << "\n";
    else
        cout << "-1\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C - Approximate Equalization 2

题意

给出一个长度为n的数组，每次操作可以选择任意两个数让其中一个增大1，另一个减少1。

找到使得最大值和最小值的差不超过1的所需的最小操作数。

思路

设s是所有数的总和。我们发现每次操作不会让s改变。

最后最大值和最小值之差不超过1，只有一种局面，那就是$s \bmod n$个$\lfloor \frac{s}{n} \rfloor + 1$，剩余的都是$\lfloor \frac{s}{n} \rfloor$。

我们可以对数组排序贪心处理。

代码

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
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    vector<ll> b(n);
    for (int i = 0; i < n; i++) {
        if (i < sum % n)
            b[i] = 1;
        b[i] += sum / n;
    }
    reverse(b.begin(), b.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += max(0LL, a[i] - b[i]);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D - Odd or Even

题意

交互题，现在有一个隐藏的长度为n的01数组。和一个数k。k是奇数。

最多查询n次，最后确定这个隐藏数组。

每次查询必须选择k个不同下标，然后会返回数组中k个数的和模2。

思路

如果我们选择k个数查询了一次。然后再查询一次，这次查询只修改了一个下标，如果得到的结果与上次相同则说明这两个下标对于的值是相等的。

通过n次查询可以得到n对下标对应的数是否相等。而这个相等又具有传递性，最后可以演变为第一个数与其他任何数是否相等。

最后我们只需要隐藏数组的第一个数的值，就可以知道所有值了。

如何确定第一个值，关键就在k是奇数。假设我们查询了前k个数，返回值如果是个奇数，那么说明前k个数中有奇数个1偶数个0；反之则是偶数个1奇数个0。这时候我们看前k个数与第一个数相等的个数，如果它和返回值的奇偶性相同，那么第一个数就是1，否则就是0。

所以n次操作就可以确定所有数值。

代码

1
2


E - Duplicate

题意

给出一个只有数字1到9的字符串S，我们不断的执行函数f(S)得到新的S。直到S的长度为1则输出需要执行函数的次数；或者如果可以无限执行则输出-1。

函数f(S)就是构造一个新串T，刚开始T为空，如果S的长度为n，那么对于i=2,3,…,n。加入S[i]个S[i-1]。

思路

如果存在两个相邻位置的字符没有一个是1。那么就会无限执行。

所以如果不想无限执行，初始串中非1的字符之间存在至少一个1。

字符串S最后长度变成1，是逐渐消去尾部字符的过程，但是中间非1的字符会增加大量的1，那么这些非1字符到底会增加多少1.

假设有个非字符串首位置的字符k，k也不是字符1，等到k被消去的时候如果已经执行了t次，在第一次操作中k会将前面的1修改为k个1，所以增长了k-1个1。同样的第二次操作也是如此，共增长了2k-2个1。那么规律其实也就发现了第t次共计增长了tk-t个1。

所以我们只需将字符串从后向前模拟这个过程即可。

运算过程中需要取模，可以用modint模板，由于c++中可以重载运算符的特性，只需修改原先定义的数据类型，即可完美移植原先不取模的代码。

代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

// #define MOD 1000000007
#define mint Modint<MOD>
template <const int _MOD>
struct Modint {
    int v;
    Modint() { v = 0; }
    Modint(long long o) { v = o % _MOD; }
    int val() { return v; }
    int pow(long long o) {
        int ret = 1, tmp = v;
        while (o) {
            if (o & 1)
                ret = ((long long)ret * tmp) % _MOD;
            o >>= 1;
            tmp = ((long long)tmp * tmp) % _MOD;
        }
        return ret;
    }
    void operator=(long long o) { v = o % _MOD; }
    bool operator==(long long o) const { return v == o; }
    bool operator==(Modint o) const { return v == o.v; }
    bool operator!=(long long o) const { return v != o; }
    bool operator!=(Modint o) const { return v != o.v; }
    bool operator<(long long o) const { return v < o; }
    bool operator<(Modint o) const { return v < o.v; }
    bool operator>(long long o) const { return v > o; }
    bool operator>(Modint o) const { return v > o.v; }
    bool operator<=(long long o) const { return v <= o; }
    bool operator<=(Modint o) const { return v <= o.v; }
    bool operator>=(long long o) const { return v >= o; }
    bool operator>=(Modint o) const { return v >= o.v; }

    Modint operator+(long long o) const { return *this + Modint(o); }
    Modint operator+(Modint o) const { return ((long long)v + o.v) % _MOD; }
    Modint operator*(long long o) const { return *this * Modint(o); }
    Modint operator*(Modint o) const { return (long long)v * o.v % _MOD; }

    Modint operator-(long long o) const { return *this - Modint(o); }
    Modint operator-(Modint o) const {
        return ((long long)v - o.v + _MOD) % _MOD;
    }

    Modint operator/(long long o) const { return *this / Modint(o); }
    Modint operator/(Modint o) const {
        return ((long long)v * o.pow(_MOD - 2)) % _MOD;
    }
    void operator+=(long long o) { *this = *this + o; }
    void operator+=(Modint o) { *this = *this + o; }
    void operator*=(long long o) { *this = *this * o; }
    void operator*=(Modint o) { *this = *this * o; }
    void operator-=(long long o) { *this = *this - o; }
    void operator-=(Modint o) { *this = *this - o; }
    void operator/=(long long o) { *this = *this / o; }
    void operator/=(Modint o) { *this = *this / o; }

    Modint operator^(long long o) { return Modint(pow(o)); }
    Modint operator^(Modint o) { return Modint(pow(o.v)); }

    template <class T>
    friend bool operator==(T o, Modint u) {
        return u == o;
    }
    template <class T>
    friend Modint operator+(T o, Modint u) {
        return u + o;
    }
    template <class T>
    friend Modint operator*(T o, Modint u) {
        return u * o;
    }
    template <class T>
    friend Modint operator-(T o, Modint u) {
        return Modint(o) - u;
    }
    template <class T>
    friend Modint operator/(T o, Modint u) {
        return Modint(o) / u;
    }

    void operator++() { *this = *this + 1; }
    void operator--() { *this = *this - 1; }
    void operator++(int k) { *this = *this + 1; }
    void operator--(int k) { *this = *this - 1; }

    template <const int T>
    friend std::istream& operator>>(std::istream& in, Modint<T>& modint) {
        ll x;
        in >> x;
        modint = Modint<T>(x);
        return in;
    }

    template <const int T>
    friend std::ostream& operator<<(std::ostream& os, const Modint<T>& modint) {
        os << modint.v;
        return os;
    }
};

void sol() {
    int n;
    string s;
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        if (s[i - 1] != '1' && s[i] != '1') {
            cout << "-1\n";
            return;
        }
    }
    mint stp = 0;
    while (s.size() != 1) {
        stp++;
        if (s.back() != '1') {
            stp += stp * (s.back() - '0' - 1);
        }
        s.pop_back();
    }
    cout << stp << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

F - Flip Machines

题意

思路

代码

1
2


G - Redistribution of Piles

题意

思路

代码

1
2


Ex - Group Photo

题意

思路

代码

1
2