題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長度為n的01字符串，求所有滿足條件的區(qū)間對數(shù)[l,r]，使得在區(qū)間[l,r]內(nèi)至少存在一組滿足條件的答案，這里第二層的滿足條件是指存在兩個(gè)正整數(shù)個(gè)x和k，滿足s[x]=s[x+k]=s[x+2*k]，求滿足條件的區(qū)間對數(shù)[l,r]

題目分析：看到這個(gè)題目可以想一下暴力，枚舉左端點(diǎn)l，再枚舉右端點(diǎn)，找到一個(gè)長度最短并且滿足第二個(gè)條件的子串，這時(shí)右端點(diǎn)r右邊的所有點(diǎn)都可以對答案做出貢獻(xiàn)，記錄下來就好了，但時(shí)間復(fù)雜度是n*k級別的，k最大可以到n，我們需要想辦法優(yōu)化

其實(shí)題目給的是01字符串，只有兩種字母，我們可以尋找一下對于這個(gè)題目而言的性質(zhì)，我們以1為例：

首先最短的滿足條件的子字符串肯定是111，這時(shí)的k為1，若要將其斷開也很容易，在其間插入一個(gè)相反的數(shù)即可，比如1011，若變成間隔類型的，比如10101，雖然在k為1時(shí)不滿足條件了，但在k為2的時(shí)候可以滿足條件了， 若想讓k為2的時(shí)候不滿足條件，我們需要將相反的數(shù)加倍一下就好了，變?yōu)?001001，這個(gè)時(shí)候就只能在k為3的時(shí)候滿足條件了，其實(shí)我們將1加倍一下變?yōu)?1001100，這個(gè)是題目給出的樣例，也是最壞的一種情況了，在長度為8的情況下還可以達(dá)到無解，但長度為9時(shí)就一定有解了，因?yàn)槲覀儾还茉趺磁帕薪M合，總是能組合出上面的集中情況之一，所以這就是01字符串在這個(gè)題目中的性質(zhì)了，具體證明我也不太會，只知道時(shí)間復(fù)雜度肯定比較小，也就是k比較小，所以直接暴力試試就行了，實(shí)際上這個(gè)題目中的k為9，總時(shí)間復(fù)雜度也就變成了9*n，剛好可以暴力過

順帶說一下，用goto語句跳出兩層循環(huán)真的好用。。

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);string s;cin>>s;LL ans=0;for(int i=0;i<s.size();i++){for(int j=i+2;j<s.size();j++){for(int k=1;j-(2*k)>=i;k++){if(s[j]==s[j-k]&&s[j]==s[j-2*k]){ans+=s.size()-j;goto end;}}}end:;}cout<<ans<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1168B Good Triple(思维+暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。