Codeforces Round 866 (Div. 2)
2023.4.15
A - Yura's New Name
如果第一个或最后一个字符是 _ ，那么无论如何至少都要加一个 ^ 。
然后看中间的。显然如果一个 _ 前面不是 ^ 那么就要在它前面加一个 ^ 以满足要求。因为加了这次之后就用不着上一个字符了，所以这样做是没有后效性的。
这说明直接扫一遍就行了。时间复杂度 $ \Theta(T|s|) $ 。
点击查看代码
#include <cstdio>
#include <cstring>
using namespace std;
int T;
inline int solve()
{
int n,ans=0;
char s[105]; scanf("%s",s+1),n=strlen(s+1);
if(n==1&&s[1]=='^') return 1;
if(s[1]=='_') ans++;
for(int i=2;i<=n;++i)
if(s[i]=='_'&&s[i-1]!='^') ans++;
if(s[n]=='_') ans++;
return ans;
}
int main()
{
scanf("%d",&T);
while(T--) printf("%d\n",solve());
return 0;
}
B - JoJo's Incredible Adventures
对于一段连续的1串，它不断右移的运动轨迹是这样子的：
\[ \begin{matrix}
1 & 1 & 1 & \\
& 1 & 1 & 1 & \\
& & 1 & 1 & 1 & \\
& & & 1 & 1 & 1 & \\
\end{matrix} \]
显然是一个平行四边形，我们要在里面截取一些矩形的话，假设连续1段的长为 \(n\) ，那么显然可以截取到的面积有
\[1 \times n,2 \times (n-1),3 \times (n-2)...
\]
根据基本不等式，我们可以在 $ \left \lfloor \frac{n}{2} \right \rfloor \times \left (n- \left \lfloor \frac{n}{2} \right \rfloor \right )$ 的时候取到最大值。
显然 \(n\) 越大越好。所以我们要找出原来的最长连续1串，然后答案就是上述式子的值。
坑：
-
因为是循环右移，所以最长连续1串可能是左端最长连续1串+右端最长连续1串
-
要开
long long
时间复杂度为 $ \Theta(Tn) $ 。
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lint long long
using namespace std;
int T;
char s[200005];
inline lint solve()
{
int n;
lint ans=0,left=0,right=0,maxlen=0;
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n&&s[i]=='1';++i) left++;
for(int i=n;i>=1&&s[i]=='1';--i) right++;
for(int i=1,cnt=0;i<=n;++i)
{
cnt+=s[i]-'0';
if(s[i]=='0') cnt=0;
maxlen=max(maxlen,1ll*cnt);
}
if(maxlen==n) return 1ll*n*n;
maxlen=max(maxlen,left+right);
for(lint i=1;i<=(maxlen+1)>>1;++i) ans=max(ans,i*(maxlen-i+1));
return ans;
}
int main()
{
scanf("%d",&T);
while(T--) printf("%lld\n",solve());
return 0;
}