A. Yura's New Name
题意：
给出一个仅由_或^组成的字符串，你可以在任意位置添加_或^字符，使得字符串满足：
任意字符要么属于^_^的一部分，要么属于^^的一部分。求最少添加的字符数量。
分析：
- 对于_我们只需处理没有组成^_^的_:
①如果_在首位置且左边没有^则添加^
②如果_在尾位置且右边没有^则添加^
③如果_在中间部分且右边没有^则添加^ - 当字符串只有一个^时末尾添加一个^
code:
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < s.size(); i ++)
{
if (!i && s[i] == '_')
cnt ++;
if (s[i] == '_' && i + 1 < s.size() && s[i + 1] != '^')
cnt ++;
}
if (s[s.size() - 1] == '_' || (s.size() == 1 && s[0] == '^'))
cnt ++;
cout << cnt << endl;
}
return 0;
}
B. JoJo's Incredible Adventures
题意：
给定一个长度为n的01串，每次向右循环移动一位,例如00111->10011,循环移动n-1次，得到一个n×n的矩阵。取一个最大的子矩阵，这个矩阵的元素均为1，求其面积。文章来源：https://www.toymoban.com/news/detail-424666.html
分析:
- 若全为1：S_max = n × n。
- 若不全为1：
考虑全为1的最长子串,其长度为k。设矩阵的长宽分别为a, b。则a + b = k + 1。
S = ab，S当且仅当a = b = (k + 1) / 2时取最大值(基本不等式)。由于每移动一次a减1，b 加1，当a = b = (k + 1) / 2时一共移动（k + 1) / 2 - 1次，(k + 1) / 2 - 1 < n - 1，所以S_max能取到。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
string s;
cin >> s;
if (s.size() == 1)
cout << (s[0] == '0' ? 0 : 1) << endl;
else
{
LL len_m = 0, n = s.size();
int idx = s.find('0');
if (idx == -1)
cout << n * n << endl;
else
{
s += s;
for (int i = 0; i < s.size(); i ++)
{
LL len = 0;
while (s[i] == '1' && i < s.size())
len ++, i ++;
len_m = max(len_m, len);
}
cout << (len_m + 1) * (len_m + 1) / 4 << endl;
}
}
}
return 0;
}
C. Constructive Problem
题意：
能否只进行一次操作："将序列a中的某个子序列修改为k"，使得mex(a)恰好比原来多1。
mex(a)即不在集合a中的最小非负整数。文章来源地址https://www.toymoban.com/news/detail-424666.html
分析：
- 当只有一个元素时：若该元素不为0则输出"Yes"，否则输出"No"
- 当有多个元素时：
①序列中不存在Mex + 1：只有当原序列是0,1,2,...,n - 1即n = Mex时输出"No"，否则输出"Yes"。因为当n != Mex时我们可以将任意比Mex大的元素换成Mex使得最后mex(a) = Mex + 1
②序列中存在Mex:目的是增加Mex，消去Mex + 1。考虑贪心，将包含Mex + 1的最短子序列全部赋值为Mex,最后check一下mex(a)是否等于Mex + 1，如果等于输出"Yes"否则输出"No"。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5;
int a[N];
int Mex(int b[], int n)
{
set<int> s;
for (int i = 0; i < n; i ++)
s.insert(b[i]);
for (int i = 0;; i ++)
if (s.count(i) == 0)
return i;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
unordered_map<int, int> mp;
int mex = 0, mex2 = 0;
for (int i = 0; i < n; i ++)
{
cin >> a[i];
mp[a[i]] += 1;
}
mex = Mex(a, n);
if (n == 1)
{
if (a[0] == 0)
cout << "No" << endl;
else
cout << "Yes" << endl;
}
else
{
if (mp[mex + 1] == 0)
{
if (n == mex)
cout << "No" << endl;
else
cout << "Yes" << endl;
}
else
{
int l = 0x3f3f3f3f, r = -1;
for (int i = 0; i < n; i ++)
{
if (a[i] == mex + 1)
{
l = min(l, i);
r = max(r, i);
}
}
for (int i = l; i <= r; i ++)
a[i] = mex;
mex2 = Mex(a, n);
if (mex2 == mex + 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}
return 0;
}
到了这里，关于Codeforces Round 866 (Div. 2)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
