Codeforces Round #833 (Div. 2）A — C

Codeforces Round #833 (Div. 2)

A. The Ultimate Square

题目分析

除以二向上取整即为答案

code

#include

using namespace std;

int n, m, k, t;

void solve()
{
    cin >> n;
    cout << (n + 1) / 2 << "\n";
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

B. Diverse Substrings

题目大意

非空数字字符串中每个字符的出现次数不超过其中不同字符的数量，则该字符串是多样化的。求一个字符串多样化子串的个数。

题目分析

一共有十种字符，所以满足条件的字串最长长度为100，，所以只需要遍历长度为100以内的子串即可，结合数据范围我们可以直接采取暴力解法，判断每一个子串是否满足条件。

code

#include

using namespace std;

int n, m, k, t;
string s;
map<char, int>q;

void solve()
{
    long long ans = 0;
    cin >> n >> s;

    for(int i = 0; i < n; i ++)
    {
        q.clear();
        int cnt = 0;
        int maxn = 0;
        for(int j = i; j < min(i + 100, n); j ++)
        {
            if(!q[s[j]]) cnt ++;
            q[s[j]] ++;
            maxn = max(maxn, q[s[j]]);
            if(maxn <= cnt) ans ++;
        }
    }

    cout << ans << "\n";
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 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

C. Zero-Sum Prefixes

题目大意

数组的评分定义为从前缀和为零的，索引 i (1≤i≤n)的个数。每个可以多次执行以下操作:选择一个a[i]=0的索引 i ;然后a[i]替换为任意整数。

通过执行一系列这样的操作，数组的最大可能得分是多少?

题目分析

以下提到的前缀和均为从第一个数开始累计的和

改变某一个位置的数，只会影响此位置以及之后位置的前缀和，假定两个符合a[i]=0的下标为i和j(i < j, 且之间没有其他符合a[]=0的点)，使得区间[i, j)内更多前缀和为零即可此段能够得到的最大得分，若有多个0则每段都满足即可

需要注意的是，区间[i, j)右边为开区间，因此我们需要额外设定第n+1个点为0才能做到全部考虑到每个位置

使得区间[i, j)内更多前缀和为零，可以找到此区间内出现次数最多的前缀数值x，此时x的数量即为此段可提供的最大得分（令a[i] = -x）

code

#include

using namespace std;

const int N = 2e5 + 10;
typedef long long ll;

int n, m, k, t;
ll a[N];
ll b[N];

void solve()
{
    vector<int>v;

    cin >> n;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> a[i];
        if(a[i] == 0) v.push_back(i);
        a[i] = a[i] + a[i - 1];
    }
    v.push_back(n + 1);

    ll ans = 0;
    for(int i = 1; i < v[0]; i ++)
        if(a[i] == 0) ans ++;
    
    for(int i = 0; i < v.size() - 1; i ++)
    {
        map<ll, int>q;
        int maxn = 0;
        for(int j = v[i]; j < v[i + 1]; j ++)
        {
            q[a[j]] ++;
            maxn = max(maxn, q[a[j]]);
        }
        ans += maxn;
    }

    cout << ans << "\n";
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 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