傳送門
題意
給出一個字串 S S S( ∣ S ∣ < = 1 e 5 |S|<=1e5 ∣S∣<=1e5),串中只有’0’,‘1’,'2’三種字符,計算不相交的子序列"2020"的最大數量是多少，
題解
觀察"2020"的特點,是左右一樣的結構,于是可以分解為兩個一樣的子問題,即判斷能組成多少第一個"20"串和多少第二個"20"串,把它們組合組合就是答案，問題就在于如何判斷要組成多少個第一個"20"字串呢?暴力列舉顯然不行,這時候就要想到二分,想要用二分首先就要判斷是否符合二分單調的性質;想想發現如果能組成 X X X個"2020"子序列,顯然也能組成 X ? 1 X-1 X?1個"2020"子序列,反之如果不能組成 X X X個"2020"子序列,顯然也就不能組合出 X + 1 X+1 X+1個子序列，
于是就符合二分性質,那么就二分第一個"20"字串的數量,也就是二分答案,具體步驟看看代碼吧，
AC code
/*******************************
* Coder : He Shuo. *
* Type : Original Work *
*******************************/
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 55;
int n;
char s[MAXN];
int check(int x)
{
int a1 = x,a2 = 0,a3 = 0,a4 = 0;
///a1 表示第一個"20"字符中2還需要多少個,a2則是'0'還需要多少個
///a3 表示第二個"20"字符中2還需要多少個,a4則是'0'還需要多少個
for(int i = 1;i <= n;i ++)
{
if(s[i] == '2')
{
if(a1)a1 --,a2 ++;///來了一個'2',優先把第一個"20"中的'2'達成數量要求;
else if(a3)a3 --,a4 ++;///達成之后就填第二個"20"的'2';
}
else if(s[i] == '0')
{
if(a2)a2 --,a3 ++;///來了一個'0',也是優先把第一個"20"中的'0'達成數量要求;
else if(a4)a4 --;///達成之后就填第二個"20"的'0';
}
}
if(a1 == 0 && a2 == 0 && a3 == 0 && a4 == 0)return 1;///所有數量都達成之后說明當前x符合條件
return 0;///否則就不行
}
int main()
{
while(scanf("%d",&n) + 1)
{
scanf("%s",s + 1);
int l = 0,r = n / 4;///答案邊界為[0,n/4],很顯然的吧，
while(l < r)
{
int mid = l + r >> 1;
if(check(mid))l = mid + 1;
else r = mid;
}
if(check(l) == 0)l --;///看看當前l符不符合,不符合就答案減一(本蒟蒻二分就喜歡這么寫,保險一點)
printf("%d\n",l);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198712.html
標籤：AI
上一篇：CCAT考試整理JAVA試題
下一篇：一文教你入門增長黑客