Codeforces Round #833 (Div. 2)

A. The Ultimate Square

题目分析

除以二向上取整即为答案

code

#includeusing 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;
}

B. Diverse Substrings

题目大意

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

题目分析

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

code

#includeusing namespace std;int n, m, k, t;
string s;
mapq;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;
}

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

#includeusing namespace std;const int N = 2e5 + 10;
typedef long long ll;int n, m, k, t;
ll a[N];
ll b[N];void solve()
{vectorv;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 ++){mapq;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;
}