?牛客IOI周賽26-普及組：B 子序列

?

鏈接：https://ac.nowcoder.com/acm/contest/11233/B

?

給出一個僅包含 a,b 的字符串 A。在 A 中間任意位置（包括開頭結尾）插入一個字符，最大化 aab 作為子序列（可以不連續）在 A 中出現的次數。

輸入描述:

?

第一行一個僅包含 a,b 的字符串 A。

?

輸出描述:

?輸出一個整數，為插入一個字符后，aab 作為子序列在 A 中出現的次數的最大值。?

輸入

abababa

輸出

10

說明

在第一個字符后插入一個 a，變為 aabababa。

示例2

輸入

ababbaababa

輸出

33

輸入

aa

輸出

1

備注:

設 n 為 A 的長度。
對于20% 的數據，n≤10。?

對于 40% 的數據，n≤1000。

對于另外 10% 的數據，A 中只有 a。

對于另外 10%?的數據，A 中只有 b。

對于 90%?的數據，?n≤2×。
對于 100% 的數據， 1≤n≤5.5×

?

知道最優方案后，主要的問題就是計數了，計數的關鍵在于找到 b 字符前有多少個 a 字符，然后算Cn2；

用樣例2演示一下吧；

按照以上方法試了一遍，發現有一個大數據樣例不過，試了好久還是沒搞出來，結束之后才發現要用到?unsigned long long ;?

#include<bits/stdc++.h> using namespace std; #define ll unsigned long longll c(ll a) {return a*(a-1)/2; }int main() {string a;cin>>a;string b = a + 'b';ll sum = 1;ll cnt1 = 0;for(int i=0; i<a.length(); i++){if(a[i]=='a')sum++;if(a[i]=='b')cnt1+=c(sum);}sum=0;ll cnt2=0;for(int i=0; i<b.length(); i++){if(b[i]=='a')sum++;if(b[i]=='b')cnt2+=c(sum);}cnt1>cnt2?cout<<cnt1:cout<<cnt2; }

?

總結

以上是生活随笔為你收集整理的B 子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。