Educational Codeforces Round 81 (Rated for Div. 2)

B. Infinite Prefixes

无限前缀

You are given string ? of length ? consisting of 0-s and 1-s. You build an infinite string ? as a concatenation of an infinite number of strings ?, or ?=????… For example, if ?= 10010, then ?= 100101001010010... 给定字符串s，s由0和1组成。创建一个字符串t，t=ssss...，例如，如果s=10010，那么t=100101001010010...

Calculate the number of prefixes of ? with balance equal to ?. The balance of some string ? is equal to ???0,?−???1,?, where ???0,? is the number of occurrences of 0 in ?, and ???1,? is the number of occurrences of 1 in ?. The number of such prefixes can be infinite; if it is so, you must say that. 对于t的前缀字符串q，满足0的数量减去1的数量为x。

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd". 字符串前缀可以为空，比如字符串abcd有5个前缀：空, a, ab, abc, abcd

Input The first line contains the single integer ? (1≤?≤100) — the number of test cases. 第一行是用例数量T

Next 2? lines contain descriptions of test cases — two lines per test case. The first line contains two integers ? and ? (1≤?≤105, −109≤?≤109) — the length of string ? and the desired balance, respectively.

第二行是字符串s The second line contains the binary string ? (|?|=?, ??∈{0,1}).

It's guaranteed that the total sum of ? doesn't exceed 105.

OutputPrint ? integers — one per test case. For each test case print the number of prefixes or −1 if there is an infinite number of such prefixes.

Example

input 4 6 10 010010 5 3 10101 1 0 0 2 0 01

output 3 0 1 -1

Note In the first test case, there are 3 good prefixes of ?: with length 28, 30 and 32.

解题思路

考虑两种情况，s的0和1数量相等和不相等 相等的时候是两个极端，存在即无限，不存在就是0 不相等的时候是求出满足条件的个数

这道题理解起来比较简单，主要是要考虑清楚几种情况，然后小心计算不相等时的个数。

C++源代码

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

void solve() {
	// x是目标值
	int n, x;
	cin >> n >> x;
	// 字符串s
	string s;
	cin >> s;

	int allb = 0;
	vector<int> pb = {0};
	// 计算前缀和
	for (auto t : s) {
		if (t == '0') allb++;
		else allb--;
		pb.push_back(allb);
	}

	pb.pop_back();

	if (allb == 0) {
		// 如果发现一个s的前缀和为0，不管多少个s都是为0，只考虑一个s的情况
		int c = 0;
		// 在一个s中查找是否存在结果
		for (auto t : pb) {
			if (t == x) c = 1;
		}
		if (c) {
			// 存在结果，说明是无穷个，因为可以无限叠加s
			cout << -1 << endl;
		} else {
			// 不存在结果，怎么叠加s都没用
			cout << 0 << endl;
		}
	} else {
		int ans = 0;
		// 普通情况，有限的结果
		for (int i = 0; i < (int)pb.size(); i++) {
			// 处理每一个前缀和的情况
			int k = (x - pb[i]) / allb;
			if (x != pb[i] + k * allb) continue;
			// 如果满足情况，则加1
			if (k >= 0) ans++;
		}
		cout << ans << endl;
	}
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int q;
    // 用例数量
    cin >> q;
    while (q--) {
    	solve();
    }
}

C. Obtain The String

You are given two strings ? and ? consisting of lowercase Latin letters. Also you have a string ? which is initially empty. You want string ? to be equal to string ?. You can perform the following operation to achieve this: append any subsequence of ? at the end of string ?. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if ?=??, ?=?????, you may turn ? into following strings in one operation: 给定字符串s和t，以及空字符串z。每次可以取s的任意一个子序列加到z后面，问至少要取多少次才能让z等价于t。例如z=ac，s=abcde，一次操作可以有如下字符串：

?=????? (if we choose subsequence ???); ?=????? (if we choose subsequence ???); ?=????? (if we choose subsequence ???).

Note that after this operation string ? doesn't change. 注意s不会改变。

Calculate the minimum number of such operations to turn string ? into string ?. 计算最小次数。

Input

The first line contains the integer ? (1≤?≤100) — the number of test cases.

The first line of each testcase contains one string ? (1≤|?|≤105) consisting of lowercase Latin letters.

The second line of each testcase contains one string ? (1≤|?|≤105) consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings ? and ? in the input does not exceed 2⋅105.

Output

For each testcase, print one integer — the minimum number of operations to turn string ? into string ?. If it's impossible print −1.

Example

input 3 aabce ace abacaba aax ty yyt

output 1 -1 3

解题思路：

从字符串s到字符串t，建立一个s的查询表T，依次遍历字符串t，对于每一个字符，查找在表T的位置。这道题精巧之处在于对查询表T的处理，采用二分查找保证了性能。

源代码：C++

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(x) ((x) & (-x))
#define inf 0x3f3f3f3f
using namespace std;

int T;
char s[100005], t[100005];
vector<int> num[200];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        for (int i = 'a'; i <= 'z'; i++)
            num[i].clear();
        scanf("%s", s);
        scanf("%s", t);

        // 从s到t
        // 保存每个字符出现的位置
        for (int i = 0; s[i]; i++)
            num[s[i]].push_back(i);

        int ans = 1;
        int nw = -1;

        for (int i = 0; t[i]; i++)
        {
            int x = t[i];
            // 不存在这个字符，直接返回-1
            if (num[x].size() == 0)
            {
                ans = -1;
                break;
            }

            //二分找大于nw的第一个这个字符的位置
            int p = upper_bound(num[x].begin(), num[x].end(), nw) - num[x].begin();

            if (p == num[x].size())
            {
                //如果已经没法在剩下的位置中取这个字符了，得另起一次从头开始取子序列
                ans++;
                nw = num[x][0];
            }
            else
            {
                nw = num[x][p];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

温馨提示

如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。

点赞的时候，请宠溺一点