Educational Codeforces Round 104 Div. 2 A~E

传送门：https://codeforces.com/contest/1487

A-Arena

输出n-最小数的个数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
##include "bits/stdc++.h"

using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        map<int, int> mp;
        int mx = 1e9;
        for(int i = 1;i <= n; i++) {
            int x; cin >> x;
            mp[x]++;
            mx = min(mx, x);
        }
        cout << n - mp[mx] << endl;
    }
}

signed main() {
    solve();
}

B - Cat Cycle

因为猫B首先呆在1的位置，所以k要减1，最后位置加1即可。

当n为奇数时，直接输出$(k-1)\%n+1$ 当n为偶数时，因为会有相遇问题。 而相遇时间为$(n-1)/2$，总相遇次数为$\frac{(k-1)}{(n-1)/2}$. 最后位置为$(k-1+\frac{(k-1)}{(n-1)/2})\%n+1$.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
##include "bits/stdc++.h"

using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n, k; cin >> n >> k;
        k -= 1;
        if(n & 1) {
            cout << (k + k / ((n - 1) / 2)) % n + 1 << endl;
        }
        else cout << k % n + 1 << endl;
    }
}

signed main() {
    solve();
}

C - Minimum Ties

当n为奇数时，那么每个队都是$\frac{n}{2}$的赢和输。所以输出1、-1、1…即可。

当n为偶数时，那么每个队都是$\frac{n}{2}-1$的赢和输还有一场平局。

平局场就是1和2，3和4，5和6等等。剩下场都是一半赢一半输。

Code

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;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        if(n & 1) {
            for(int i = 1;i <= (n - 1) * n / 2; i++) {
                if(i & 1) cout << 1 << " ";
                else cout << -1 << " ";
            }
        }
        else {
            int t = 0;
            while(n--) {
                t++;
                for(int i = 1;i <= n; i++){
                    if(i == 1 && (t & 1)) cout << 0 << " ";
                    else {
                        if(!(i & 1)) cout << 1 << " ";
                        else cout << -1 << " ";
                    }
                }
            }
        }
        cout << endl;
    }
}

signed main() {
    solve();
}

D - Pythagorean Triples

三个条件：

  • $c=a^2-b$
  • $c^2=a^2+b^2$
  • $1\leq a,b,c\leq n$

问这样(a,b,c)的组数有多少？

来化简一下，二式-一式得$c^2-c=b^2+b\;\;\;\;\;(c+b)(c-b)=b+c$ 继续化简$c-b=1\;\;b=c-1$，带入一式得$2c=a^2+1$。

所以整个条件就变为，a一定要是奇数，并且$a\leq n$，得：

$$ans=\left \lceil \frac{\sqrt{2*n-1}}{2} \right \rceil-1$$

这个减1是因为c=1时，b=0，错误组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;

void solve() {
    int _; cin >> _;
    while(_--) {
        ll n; cin >> n;
        ll a = sqrt(2 * n - 1);
        cout << a / 2 + (a % 2 == 1) - 1 << endl;
    }
}

signed main() {
    solve();
}

E - Cheap Dinner

因为限制只在相邻的两种食物之间，所以我们可以把这个问题分割成三个子问题：对于每种第二种食物来说，与他能在一起且价格最低的食物是谁，对于第三种和第四种同理求即可，最后把答案合并起来。那么如何找最小值，并且在限制关系中又可以有删除的操作呢，就可以用map实现。

Code

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
##include "bits/stdc++.h"

using namespace std;

##define endl "\n"
##define pb push_back

vector<int> a[5], n(5);
vector<pair<int, int>> que, tt;
map<int, set<int>> mp[5];

void solve() {
    for (int i = 1; i <= 4; i++) cin >> n[i], a[i].pb(0);
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= n[i]; j++) {
            int x;
            cin >> x;
            a[i].pb(x);
        }
    }
    for (int i = 1; i <= 3; i++) {
        int m;
        cin >> m;
        for (int j = 1; j <= m; j++) {
            int x, y;
            cin >> x >> y;
            mp[i][x].insert(y);
        }
    }
    for (int i = 1; i <= n[1]; i++) que.pb({a[1][i], i});
    for (int k = 2; k <= 4; k++) {
        sort(que.begin(), que.end());
        for (int i = 1; i <= n[k]; i++) {
            for (auto j : que) {
                int x = j.first, y = j.second;
                if (mp[k - 1][y].find(i) == mp[k - 1][y].end()) {
                    tt.pb({a[k][i] + x, i});
                    break;
                }
            }
        }
        que = tt;
        tt.clear();
    }
    sort(que.begin(), que.end());
    if (que.empty())
        cout << -1 << endl;
    else
        cout << que[0].first << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/16/educational-codeforces-round-104-div-2-ae/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！