Skip to content

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 โ€‹

cpp
#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

Just observe ๐Ÿ‘€