Paranoid String - 洛谷

?首先由題目很容易看出，每次操作也就是相當于把不同的兩個字符刪去左邊那個留下右邊那一個。

枚舉以s[j]字符為結尾的子串，

如果s[j]==s[j-1]

也就是說這兩個字符無法相消，那么以s[j]為結尾的前部分子串更無法消去此時答案數+1，因為本身s[j]這個字符就可以看作長度為1的字符串。

如果s[j]!=s[j-1]

可以證明，此時以s[j]為結尾的所有子串都會被消去只剩s[j]

設一個串xxxxx?01，首先我們知道題目的意思就是兩個字符不同時保留右邊那個。?

????????如果當 " ?" 不同于0 .那么 "?" 在0的左邊，且不相同，則可以被0消去。剩下字符串 xxxxx01??

? ? ? ???如果 "?" 和0相同，也就是說 "?" 和1不同。那么1可以先消去0，原串變成xxxxx?1，因為此時？和1不同，也可以看做xxxxx01。

所以不管哪種情況都能變成結尾為s[j-1]+s[j]的情況，接下來繼續這樣討論直到消去j前面的所有字符。

所以子串s[j-j],s[j-1 - j],s[j-2 - j]...s[1-j]都可以被消去，此時答案+j，因為以s[j]結尾的子串 有j個。

代碼很簡單，但是我認為思維難度還是不小的....

cin >> s; int ans = 0; rep(j, 0, n - 1) {if (s[j] == s[j - 1])ans++;else if (s[j] != s[j - 1])ans += (j + 1); } pln(ans);

總結

以上是生活随笔為你收集整理的CF1694B Paranoid String 构造/子串计数的全部內容，希望文章能夠幫你解決所遇到的問題。

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