A. Yura's New Name
题意
在字符串\(s\)中添加 "_" 或者 "^"，使得\(s\)中的任意字符都必须为 "_" 或者 "^^" 的一部分，求最少要添加的字符数量
思路
- 当字符串头部为 "_" 时,一定要在前面添加1个字符 "^"
- 当字符串尾部为 "_" 时,一定要在后面添加1个字符 "^"
- 当字符串中出现连续两个"_"时，要在它们之间添加一个"^"
- 注意当\(s\)为 "^" 时，再添加1个字符"^"即可
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int main()
{
int T;
cin>>T;
while(T--)
{
string s;
cin>>s;
int cnt=0;
if(s=="^")//特殊情况
{
cout<<1<<endl;
continue;
}
if(s[0]=='_')cnt++;
if(s[s.size()-1]=='_')cnt++;
for(int i=0;i<s.size()-1;i++)
{
if(s[i]=='_'&&s[i+1]=='_')cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
B. JoJo's Incredible Adventures
题意
给定一个长度为\(n\)的\(01\)串，将字符串循环右移\(n\)次，得到一个矩阵。取一个最大的子矩阵，使得矩阵中的元素均为\(1\)，求矩阵的最大面积。
-
比如长度为\(3\)的字符串\(101\)，循环右移\(3\)次，可得到如下的矩阵：
1 0 1 1 1 0 0 1 1
思路
- 显然，当字符串中只含有\(0\)时，答案为\(0\)；只含有\(1\)时，答案为\(n*n\)。
- 将字符串拼接到原字符串后面，统计最长的连续\(1\)的个数。假设最长的连续\(1\)的个数为\(k\)，则矩阵的最大面积为\(\frac{(k+1)^2}{4}\)
- 给出证明：如果存在\(a\times b\)的矩阵，通过观察可得，当字符串右移时，矩形长方向上出现 1 的次数减1，但是宽方向上加1，即满足关系式 \(a+b=k+1\)。
1111 11111 111111
1111 11111 111111
1111 11111 111111
1111 11111 111111
11111 111111
111111
若要使 \(a\times b\) 最大，则有
\[\begin{align}
a+b &\geq 2\sqrt{ab} \\\
ab &\leq \frac{(a+b)^2}{4}=\frac{(k+1)^2}{4}
\end{align}
\]
由此得证
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef long long ll;
int main()
{
int T;
cin>>T;
while(T--)
{
string s;
cin>>s;
int n=s.size();
if(s.find('0')==-1)//只有1
{
cout<<(ll)n*n<<endl;
continue;
}
s+=s;//成环
ll maxv=0;
//求连续1的最长个数
for(int i=0;i<s.size();i++)
{
if(s[i]=='0')continue;
int j=i;
while(j<s.size()&&s[j]=='1')j++;
maxv=max(maxv,(ll)j-i);
i=j-1;
}
cout<<(maxv+1)*(maxv+1)/4<<endl;
}
return 0;
}
C. Constructive Problem
题意
给定\(n\)个非负整数，执行一次操作，将其中一段连续的子数组修改为非负整数\(k\)，问是否能使新序列的\(MEX\)值比之前恰好增加\(1\)。
\(MEX\)：集合中未出现过的最小非负整数
思路
分类讨论
- 若数组中有\(MEX+1\)存在，则一定要将\(MEX+1\)最早出现和最晚出现之间的数修改为\(MEX\),之后判断\(MEX\)是否比原来增加\(1\)即可
- 若数组中不存在\(MEX+1\)
- 若其他元素有重复，选择\(1\)个改为\(MEX\)即可
- 若其他元素无重复，
- 若有元素大于\(MEX+1\)，则将该元素改为\(MEX\)即可
- 若所有元素小于\(MEX+1\)，则答案为\(No\)
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef long long ll;
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
vector<int>a(n);
map<int,int>mp;
for(int i=0;i<n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
int mex;
for(int i=0;;i++)
if(!mp.count(i))
{
mex=i;
break;
}
bool flag=false;
if(!mp.count(mex+1))
{
for(int i=0;i<n;i++)
if(mp[a[i]]>1||a[i]>mex)
{
flag=true;
break;
}
}
else{
int start,ed;
bool first=false;
for(int i=0;i<n;i++)
{
if(a[i]==mex+1)
{
if(!first)first=true,start=i;
ed=i;
}
}
for(int i=start;i<=ed;i++)
{
mp[a[i]]--;
mp[mex]++;
}
flag=true;
for(int i=0;i<mex;i++)
if(!mp[i])
{
flag=false;
break;
}
}
puts(flag?"Yes":"No");
}
return 0;
}