Practice.

A. The Ultimate Square

题意

给定 \(n\) 个方块，第 \(i\) 个方块的宽度为 \(1\)，长度为 \(\lceil \frac{i}{2} \rceil\)。选取一些方块横向拼接成一个正方形，输出正方形的最大边长。

思路

显然，当 \(n\) 为奇数的时候，我们一定能将所有方块都用上，拼成一个长为 \(\frac{n + 1}{2}\) 的正方形；当 \(n\) 为偶数的时候，一个大方块将会多出来，而剩余的方块按照奇数的情况处理即可。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

signed main(){
    ios::sync_with_stdio(false);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        cout << n / 2 + n % 2 << '\n';
    }
}

猜测即可

B. Diverse Substrings

题意

给定一串数字 \(a\)，\(a_i \in [0, 9]\)，对于所有连续子串，输出满足下面条件的个数：

对于子串中出现次数最多的数字的次数 \(maxx\) 以及不同数字的种数 \(dif\)，满足 \(maxx \leq dif\)。

思路

考虑到满足条件的子串长度最多只有 \(10 \times 10\)，我们直接暴力枚举即可。

时间复杂度：\(O(nm)\)

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 20, inf = 0x3f3f3f3f, mod = 998244353;

int cnt[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = 0;
        for(int i=0;i<n;i++){
            memset(cnt, 0, sizeof cnt);
            int dif = 0, maxx = 0;
            for(int j=i;j<n&&j-i<100;j++){
                if(cnt[s[j] - '0'] == 0) dif ++;
                cnt[s[j] - '0'] ++;
                maxx = max(maxx, cnt[s[j] - '0']);
                if(maxx <= dif) ans ++;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

太暴力了，虽然双指针确实不可行

C. Zero-Sum Prefixes

题意

给定数组 \(a\)，定义操作为将任意一个值为 \(0\) 的点替换成任意值，输出操作后所有前缀和中值为 \(0\) 的个数。

思路

考虑到修改一个元素，会影响到后面的元素的前缀和值，所以我们不妨直接从后面开始遍历。我们不妨从后往前找 \(0\)，当然，在找的过程中，记录 \(0\) 后面的元素的前缀和的值的出现次数，然后，我们只需把 \(0\) 改成出现次数最多的前缀和的值的相反数即可，该情况下答案加上最多的出现次数，这样不会影响到前面的答案，并且可以让后面前缀和为 \(0\) 的数尽可能多。

时间复杂度：\(O(n)?\)

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N], sum[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        sum[0] = 0;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            sum[i] = sum[i - 1] + a[i];
        }
        int ans = 0;
        map<int, int> mp;
        for(int i=n;i>=1;i--){
            mp[sum[i]] ++;
            if(a[i] == 0){
                int maxx = 0;
                for(auto &e : mp)
                    maxx = max(maxx, e.second);
                ans += maxx;
                mp.clear();
            }
        }
        cout << ans + mp[0]<< '\n';
    }
    return 0;
}

有点小贪心