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

Changelog

Last edited 24 days ago

View full history

1096e02-Add oj solving