A-Entertainment in MAC

题意

可以对一个字符串进行两种操作：

将字符串反转
将该字符串反转后接在原串的后面。

可以进行任意次上述操作，获得字典序最小的字符串。

数据范围

$t(1≤t≤500)$

$n(2≤n≤10^9)$

$s(1\le |s|\le 100)$

思路

对比反转前后的字符串字典序大小，再决定是操作1还是操作2

参考代码

1
void solve() {
2
    ll n;cin >> n;
3
    string s;cin >> s;
4
    string t = s;
5
    reverse(t.begin(), t.end());
6
    if (s > t) {
7
        cout << t << s << endl;
8
    }
9
    else {
10
        cout << s << endl;
11
    }
12
}

B-Informatics in MAC

题意

$MEX$ ：不属于该数组的最小非负整数。

对一个数组分成 $k$ 个子段，要求每段的 $MEX$ 都等于相同的数。

找到这样的子段分法，或者报告不存在合法的分法。

数据范围

$t(1≤t≤10^4)$

$n(2≤n≤10^5)$

$a_i(0\le a_i\lt n)$

思路

假设 $MEX=2$ ，则分成 $k$ 段的方式为前 $k-1$ 段只要都出现过 $0,1$ 就进行分段，最后一段保证含 $0,1$ 和达到第 $n$ 个数。

确定 $MEX$ ：遍历数组 $a$ ，找到最小的没有出现过的数（该数不大于 $n$ ），该数即为 $MEX$ 。

参考代码

1
// MEX:不属于该数组的最小非负整数
2

3
void solve() {
4
    ll n;cin >> n;
5
    vector<ll>a(n + 1);
6
    vector<bool>ck(n + 1, false);
7
    for (int i = 1;i <= n;i++) {
8
        ll x;cin >> x;
9
        a[i] = x;
10
        ck[x] = true;
11
    }
12

13
    bool f = false;
14
    int y = -1;
15
    for (int i = 0;i < n;i++) {
16
        if (ck[i] == false) {
17
            y = i;
18
            f = true;
19
            break;
20
        }
21
    }
22

23
    if (!f) {
24
        cout << -1 << endl;
25
        return;
26
    }
27

28
    // MEX=y
29
    // cout << y << endl;
30
    if (y == 0) {
31
        cout << n << endl;
32
        for (int i = 1;i <= n;i++) {
33
            cout << i << ' ' << i << endl;
34
        }
35
        return;
36
    }
37

38
    int p = 1;
39
    int cnt = 0;
40
    vector<pair<int, int>>ans;
41
    vector<bool>hs(y, false);
42
    vector<bool>hsf(y, false);
43
    for (int i = 1;i <= n;i++) {
44
        if (a[i] < y && !hs[a[i]]) {
45
            hs[a[i]] = true;
46
            cnt++;
47
        }
48
        if (cnt == y) {
49
            ans.push_back({ p, i });
50
            p = i + 1;
51
            cnt = 0;
52
            // 会不会Tle
53
            hs = hsf;
54
        }
55
    }
56

57
    if (ans.size() == 1) {
58
        cout << -1 << endl;
59
        return;
60
    }
61

62
    cout << ans.size() << endl;
63
    for (int i = 0;i < ans.size();i++) {
64
        if (i != ans.size() - 1)
65
            cout << ans[i].first << " " << ans[i].second << endl;
66
        else {
67
            cout << ans[i].first << " " << n << endl;
68
        }
69
    }
70

71
}

D-Exam in MAC

题意

有一个集合 $s$ 。

找到满足 $0\le x\le y\le c$ 且 $x+y$ 和 $y-x$ 均不包含在集合 $s$ 中的整数对 $(x,y)$ 的个数。

数据范围

$t(1≤t≤2\times 10^4)$

$n(1≤n≤3\times 10^5)$

$c(1\le c\le 10^9)$

思路

容斥。

合格的整数对=满足 $x+y\in s$ +满足 $y-x\in s$ -既满足 $x+y\in s$ 又满足 $y-x\in s$ 。

参考代码

1
void solve() {
2
    ll n, c;cin >> n >> c;
3
    ll tot = (c + 1) * (c + 2) / 2;
4
    ll cnt0 = 0, cnt1 = 0;
5
    for (ll i = 0;i < n;i++) {
6
        ll x;cin >> x;
7
        tot -= x / 2 + 1;
8
        tot -= c + 1 - x;
9
        if (x & 1)cnt1++;
10
        else cnt0++;
11
    }
12
    tot += (cnt0 + 1) * cnt0 / 2 + cnt1 * (cnt1 + 1) / 2;
13
    cout << tot << endl;
14
}