1694B - Paranoid String
題目
Codeforces: 1694B: Paranoid String
Let's call a binary string 𝑇 of length 𝑚 indexed from 1 to 𝑚 paranoid if we can obtain a string of length 1 by performing the following two kinds of operations 𝑚−1 times in any order :
Select any substring of 𝑇 that is equal to 01, and then replace it with 1.
Select any substring of 𝑇 that is equal to 10, and then replace it with 0.
For example, if 𝑇= 001, we can select the substring [𝑇2𝑇3] and perform the first operation. So we obtain 𝑇= 01.
You are given a binary string 𝑆 of length 𝑛 indexed from 1 to 𝑛. Find the number of pairs of integers (𝑙,𝑟) 1≤𝑙≤𝑟≤𝑛 such that 𝑆[𝑙…𝑟] (the substring of 𝑆 from 𝑙 to 𝑟) is a paranoid string.
Input
The first line contains a single integer 𝑡 (1≤𝑡≤1000) — the number of test cases. The description of the test cases follows.
The only line of each test case contains two integers 𝑎 and 𝑏 (1≤𝑎,𝑏≤100) — the numbers of zeroes and ones correspondingly.
說明
- 只要結尾是 01 或 10 ，就可以。
- 以 01 為例: ??????01 →(根據規則2) 0…01 →(根據規則 1) 1
Code
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int lt = 0; lt < T; ++lt) {
int n;
string inp;
cin >> n >> inp;
int64_t ans = n; // len=1 substring
for (size_t i = 1; i < n; ++i) {
if (inp[i] != inp[i - 1]) {
ans += i;
}
}
cout << ans << endl;
}
return 0;
}