比赛链接

A题

先求前缀和，如果当前的和可以拼成一个完整的正方形，可以发现它必须是奇数$2k + 1,k\in 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
std::set<int> ms;
void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i) {
            a[i] += a[i - 1];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (ms.find(a[i]) != ms.end()) {
            ans++;
        }
    }
    cout << ans << '\n';
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    for (int i = 1; i <= 101; i += 2) {
        ms.insert(i * i);
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B题

对于一个长度为$n$的字符串，他可组成的排列数是$\frac{n!}{n_{a}!n_{b}!…n_{z}!}$，我们要改变一个字母，使得这个值最小，也就是使得分母最大，那么只需要将一个数量最少的字母变为一个数量最多的字母，这时相当于把原来的排列方法总数乘$\frac{n_{min}}{n_{max}+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
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    std::vector<int> cnt(26);
    for (char ch : s) {
        cnt[ch - 'a']++;
    }
    char minc, maxc;
    int mn = INF, mx = -1;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] == 0) continue;
        if (mn >= cnt[i]) {
            mn = cnt[i];
            minc = i + 'a';
        }
        if (mx < cnt[i]) {
            mx = cnt[i];
            maxc = i + 'a';
        }
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == minc) {
            s[i] = maxc;
            cout << s << '\n';
            return;
        }
    }
}

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
template<typename T>
void chmax(T& a, T b){
    if (a < b) {
        a = b;
    }
}
void solve() {
    int n;
    cin >> n;
    std::vector<int> sum(n), mx(n);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        sum[i] = num;
        mx[i] = num;
    }
    int mxsum = 0;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        sum[i] += num;
        chmax(mx[i], num);
        mxsum += mx[i];
    }
    int ans = -INF;
    for (int i = 0; i < n; i++) {
        chmax(ans, mxsum - mx[i] + sum[i]);
    }
    cout << ans << '\n';
}

D题

贪心思想，先从尾到头求一个最小栈，以便于判断当前数字是否是之后所有数字中最小的，如果是，那么它一定不需要进行操作，就可以加入到答案序列中；如果不是，则说明它之后还有比它更小的数字，那么它一定需要操作，将其加一之后移到最后，假如这个数是$a$，在它移到最后时就是$a+1$，此时我们又多了个判断条件：因为这个$a+1$是一定会被排到原序列最后面，所以在以后的数字不仅要判断它是否是原序列之后所有数字最小的，还应是所有需要操作移到后面去的数字中最小的，否则我们仍然可以把它移到最后面，而使$a_{min}+1$移动到该位置，使得最后的序列更小。

事实上，我们可以将所有需要移动的数字用一个数组存储起来，使用一个值来随时记录更新数组中最小的数字，这样我们就可以随时知道$a_{min}+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
39
inline void chmin(T& a, T b){
    if (a > b) {
        a = b;
    }
}
void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n), minstack(n), ans;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1) {
            minstack[i] = a[i];
        } else {
            minstack[i] = std::min(minstack[i + 1], a[i]);
        }
    }
    std::vector<int> tmp;
    int mn = INF, mn1 = INF;
    for (int i = 0; i < n; i++) {
        if (a[i] == minstack[i]) {
            if (a[i] <= mn1) {
                cout << a[i] << ' ';
            } else {
                tmp.push_back(a[i]);
            }
        } else {
            tmp.push_back(a[i]);
            chmin(mn1, a[i] + 1);
        }
    }
    std::sort(tmp.begin(), tmp.end());
    for (int i : tmp) {
        cout << i + 1 << ' ';
    }
    cout << '\n';
}