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;
}