Educational Codeforces Round 81 (Rated for Div. 2)

• 2020 年 2 月 17 日
• 笔记

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("%dn", ans);      }      return 0;  }  

温馨提示

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

点赞的时候，请宠溺一点