Competition3_t3

题目描述

咕咕东很聪明，但他最近不幸被来自宇宙的宇宙射线击中，遭到了降智打击，他的英语水平被归零了！这一切的始作俑者宇宙狗却毫不知情！
此时咕咕东碰到了一个好心人——TT，TT在吸猫之余教咕咕东学英语。今天TT打算教咕咕东字母A和字母B，TT给了咕咕东一个只有大写A、B组成的序列，让咕咕东分辨这些字母。
但是咕咕东的其他学科水平都还在，敏锐的咕咕东想出一个问题考考TT：咕咕东问TT这个字符串有多少个子串是Delicious的。
TT虽然会做这个问题，但是他吸完猫发现辉夜大小姐更新了，不想回答这个问题，并抛给了你，你能帮他解决这个问题吗？
Delicious定义：对于一个字符串，我们认为它是Delicious的当且仅当它的每一个字符都属于一个大于1的回文子串中。

输入格式

输入第一行一个正整数n，表示字符串长度。
接下来一行，一个长度为n只由大写字母A、B构成的字符串。

输出格式

输出仅一行，表示符合题目要求的子串的个数。

输入样例

5
AABBB

输出样例

6

数据约定

解题思路

这道题的思路其实就是：判断某个字符串有多少个子串满足，这个子串的每个字符都属于一个长度大于1的回文串，并且这个回文串是这个子串的子串。
在测试的时候一直想着如何解出符合条件的算法，结果不出意外的TLE了。
当时的思路很明确：判断回文串就是了。

#include <iostream>
#include <string>
#include <cstring>using namespace std;string s;
int a[300005];bool judge(int l, int r)
{memset(a, 0, sizeof a);for (int i = l; i <= r; i++){int j = i + 1;while (j <= r){if (s[i] == s[j]){a[i] = a[j] = 1;j++;}else break;}int k = i - 1;while (k >= l && j <= r){if (s[k] == s[j]){a[i] = a[k] = a[j] = 1;j++;k--;}else break;}int m = i - 1, n = i + 1;while (m >= l && n <= r){if (s[m] == s[n]){a[i] = a[m] = a[n] = 1;m--;n++;}else break;}}bool OK = true;for (int i = l; i <= r; i++){if (a[i] == 0){OK = false;break;}}return OK;
}int main() 
{int length;cin >> length;cin >> s;int ans = 0;for (int l = 0; l < length; l++)for (int r = l + 1; r < length; r++){if (judge(l, r)){ans++;}}cout << ans << endl;}

但是这样子没能满分，超时。
在接下来的课程里，得到了这个问题的正确解法：
正难则反。
即找出不合法的子串的个数，然后用总数减去不合法的子串，结果就是对的了。
那什么样的子串是不合法的呢？符合下面四个格式之一的子串就是不合法的：

  • ABB…BB
  • BAA…AA
  • AA…AAB
  • BB…BBA

识别出连续的一段，判断左右是否有字符。

typedef long long ll;void solve(ll n,char* s)
{ll ans = n * (n - 1) / 2;ll l=0;for(int i = 0; s[i]; i++){if(s[l] != s[i+1]){if(s[i+1]) ans -= i - l;if(l) ans -= i - l + 1;l = i + 1;}}cout << ans << endl;
}

Competition3_t3

题目描述

咕咕东很聪明，但他最近不幸被来自宇宙的宇宙射线击中，遭到了降智打击，他的英语水平被归零了！这一切的始作俑者宇宙狗却毫不知情！
此时咕咕东碰到了一个好心人——TT，TT在吸猫之余教咕咕东学英语。今天TT打算教咕咕东字母A和字母B，TT给了咕咕东一个只有大写A、B组成的序列，让咕咕东分辨这些字母。
但是咕咕东的其他学科水平都还在，敏锐的咕咕东想出一个问题考考TT：咕咕东问TT这个字符串有多少个子串是Delicious的。
TT虽然会做这个问题，但是他吸完猫发现辉夜大小姐更新了，不想回答这个问题，并抛给了你，你能帮他解决这个问题吗？
Delicious定义：对于一个字符串，我们认为它是Delicious的当且仅当它的每一个字符都属于一个大于1的回文子串中。

输入格式

输入第一行一个正整数n，表示字符串长度。
接下来一行，一个长度为n只由大写字母A、B构成的字符串。

输出格式

输出仅一行，表示符合题目要求的子串的个数。

输入样例

5
AABBB

输出样例

6

数据约定

解题思路

这道题的思路其实就是：判断某个字符串有多少个子串满足，这个子串的每个字符都属于一个长度大于1的回文串，并且这个回文串是这个子串的子串。
在测试的时候一直想着如何解出符合条件的算法，结果不出意外的TLE了。
当时的思路很明确：判断回文串就是了。

#include <iostream>
#include <string>
#include <cstring>using namespace std;string s;
int a[300005];bool judge(int l, int r)
{memset(a, 0, sizeof a);for (int i = l; i <= r; i++){int j = i + 1;while (j <= r){if (s[i] == s[j]){a[i] = a[j] = 1;j++;}else break;}int k = i - 1;while (k >= l && j <= r){if (s[k] == s[j]){a[i] = a[k] = a[j] = 1;j++;k--;}else break;}int m = i - 1, n = i + 1;while (m >= l && n <= r){if (s[m] == s[n]){a[i] = a[m] = a[n] = 1;m--;n++;}else break;}}bool OK = true;for (int i = l; i <= r; i++){if (a[i] == 0){OK = false;break;}}return OK;
}int main() 
{int length;cin >> length;cin >> s;int ans = 0;for (int l = 0; l < length; l++)for (int r = l + 1; r < length; r++){if (judge(l, r)){ans++;}}cout << ans << endl;}

但是这样子没能满分，超时。
在接下来的课程里，得到了这个问题的正确解法：
正难则反。
即找出不合法的子串的个数，然后用总数减去不合法的子串，结果就是对的了。
那什么样的子串是不合法的呢？符合下面四个格式之一的子串就是不合法的：

  • ABB…BB
  • BAA…AA
  • AA…AAB
  • BB…BBA

识别出连续的一段，判断左右是否有字符。

typedef long long ll;void solve(ll n,char* s)
{ll ans = n * (n - 1) / 2;ll l=0;for(int i = 0; s[i]; i++){if(s[l] != s[i+1]){if(s[i+1]) ans -= i - l;if(l) ans -= i - l + 1;l = i + 1;}}cout << ans << endl;
}