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演算法日常。

點贊的時候，請寵溺一點