Binary String Reconstruction

题面翻译

给出一种01串的变换方法及对一个串变换后的结果串，求出原串（可以有多种），多组询问。

变换方法如下：

原串为 $w$，变换后的串为 $s$，两串长度相等；给出一个整数 $x$；01串从下标 $1$ 开始。

• 如果原串 $w_{i-x}$ 这一位存在且为 $1$，那么 $s_i$ 为 $1$（形式化地说，如果 $i>x$ 且 $w_{i-x}=1$，那么 $s_i=1$）。

• 如果原串 $w_{i+x}$ 这一位存在且为 $1$，那么 $s_i$ 为 $1$（形式化地说，如果 $i+x\le n$ 且 $w_{i+x}=1$，那么 $s_i=1$）。

• 如果上述两种情况均不成立，那么 $s_i=0$。

给出 $s$，求出一种可能的 $w$，若不存在任意一种 $w$，输出-1。

保证 $s$ 的总长度不超过 $10^5$，$t$（数据组数）不超过 $1000$。

题目描述

Consider the following process.

You have a binary string (a string where each character is either 0 or 1) $w$ of length $n$ and an integer $x$ .

You build a new binary string $s$ consisting of $n$ characters.

The $ i $ -th character of $s$ is chosen as follows:

• if the character $w_{i-x}$ exists and is equal to 1, then $s_i$ is 1 (formally, if $i>x$ and $w_{i-x}=$ 1, then $s_i=$ 1);
• if the character $w_{i+x}$ exists and is equal to 1, then $s_i$ is 1 (formally, if $i+x\le n$ and $w_{i+x}=$ 1, then $s_i=$ 1);
• if both of the aforementioned conditions are false, then $s_i$ is 0.

You are given the integer $x$ and the resulting string $s$ .

Reconstruct the original string $w$ .

输入格式

The first line contains one integer $t$ ( $1\le t\le 1000$ ) — the number of test cases.

Each test case consists of two lines.

The first line contains the resulting string $s$ ( $2\le |s|\le 10^5$ , each character of $s$ is either 0 or 1).

The second line contains one integer $x$ ( $1\le x\le |s|-1$ ).

The total length of all strings $s$ in the input does not exceed $10^5$ .

输出格式

For each test case, print the answer on a separate line as follows:

• if no string $w$ can produce the string $s$ at the end of the process, print $-1$ ;
• otherwise, print the binary string $w$ consisting of $|s|$ characters.

If there are multiple answers, print any of them.

样例 #1

样例输入 #1

3
101110
2
01
1
110
1
1
2
3
4
5
6
7

样例输出 #1

111011
10
-1
1
2
3

#include
using namespace std;
const int N=3e5+10;
typedef long long ll;
int t,x,n;
char s[N],w[N];
int main(){
	cin>>t;
	while(t--){
		bool ok=1;
		scanf("%s%d",s,&x);
		n=strlen(s);
		for(int i=0;i<n;i++) w[i]='1';
        w[n]=0;
		for(int i=0;i<n;i++){
			if(s[i]=='0'){
				if(i-x>=0) w[i-x]='0';
				if(i+x<n) w[i+x]='0';
			}
		}
		for(int i=0;i<n;i++){
			if(s[i]=='1'&&(i-x<0||w[i-x]=='0')&&(i+x>=n||w[i+x]=='0')){
				ok=0;
				break;
			}
		}
		if(!ok)puts("-1");
		else printf("%s\n",w);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Killjoy

题面翻译

题目给出 $t$ 组数据，对于每一组数据：

一种新型病毒感染了Codeforces，他的感染机制是：如果未感染者B在某场比赛开始前或开始后与感染者A积分相同，那么他将会被感染。一旦被感染，则无法被治愈。

有 $n$ 个用户和Killjoy在Codeforces，最初只有Killjoy被感染。Killjoy的初始积分为 $x$ ，所有用户都有一个初始的积分，第 $i$ 个用户积分为 $a_i$ 。

比赛定期在Codeforces举行，每场比赛可有任意数量用户参加，Killjoy不能参加。每场比赛后参与的用户积分会升降一个整数，且所有参与用户变化的总分和为0。

问至少需要几场比赛可将所有用户感染？

题目描述

A new agent called Killjoy invented a virus COVID-2069 that infects accounts on Codeforces.

Each account has a rating, described by an integer (it can possibly be negative or very large).

Killjoy’s account is already infected and has a rating equal to $x$ .

Its rating is constant.

There are $n$ accounts except hers, numbered from $1$ to $n$ .

The $i$ -th account’s initial rating is $a_i$ .

Any infected account (initially the only infected account is Killjoy’s) instantly infects any uninfected account if their ratings are equal.

This can happen at the beginning (before any rating changes) and after each contest.

If an account is infected, it can not be healed.

Contests are regularly held on Codeforces.

In each contest, any of these $n$ accounts (including infected ones) can participate. Killjoy can’t participate.

After each contest ratings are changed this way: each participant’s rating is changed by an integer, but the sum of all changes must be equal to zero.

New ratings can be any integer.

Find out the minimal number of contests needed to infect all accounts.

You can choose which accounts will participate in each contest and how the ratings will change.

It can be proven that all accounts can be infected in some finite number of contests.

输入格式

The first line contains a single integer $t$ $(1\le t\le 100)$ — the number of test cases.

The next $2t$ lines contain the descriptions of all test cases.

The first line of each test case contains two integers $n$ and $x$ ( $2\le n\le 10^3$ , $-4000\le x\le 4000$ ) — the number of accounts on Codeforces and the rating of Killjoy’s account.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ $(-4000\le a_i\le 4000)$ — the ratings of other accounts.

输出格式

For each test case output the minimal number of contests needed to infect all accounts.

样例 #1

样例输入 #1

3
2 69
68 70
6 4
4 4 4 4 4 4
9 38
-21 83 50 -59 -77 15 -71 -78 20
1
2
3
4
5
6
7

样例输出 #1

1
0
2
1
2
3

提示

In the first test case it’s possible to make all ratings equal to $69$ .

First account’s rating will increase by $1$ , and second account’s rating will decrease by $1$ , so the sum of all changes will be equal to zero.

In the second test case all accounts will be instantly infected, because all ratings (including Killjoy’s account’s rating) are equal to $4$ .

#include
using namespace std;
const int N=3e5+10;
typedef long long ll;
int t,n,x;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>x;
		int h,f,sum; h=f=sum=0;
		for(int i=1,a;i<=n;++i){
			cin>>a;
			h|=(x==a),f|=(x!=a),sum+=a;
		}
		printf("%d\n",n*x==sum?f:2-h);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

k-Amazing Numbers

题面翻译

• 定义 一个序列的 $k$ 数 为 出现在序列所有长度为 $k$ 的子区间内的最小数，如没有数出现在所有长度为 $k$ 的子区间内，则 $k$ 数为 $-1$。
• 给出一个序列，求出对于 $k\in [1,n]$ 的每一个 $k$ 数。
• 数据组数 $t\le 1000$，序列长度 $n\le 3\times 10^5$，元素大小 $1\le a_i\le n$。

题目描述

You are given an array $a$ consisting of $n$ integers numbered from $1$ to $n$ .

Let’s define the $k$ -amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $k$ (recall that a subsegment of $a$ of length $k$ is a contiguous part of $a$ containing exactly $k$ elements).

If there is no integer occuring in all subsegments of length $k$ for some value of $k$ , then the $k$ -amazing number is $-1$ .

For each $k$ from $1$ to $n$ calculate the $k$ -amazing number of the array $a$ .

输入格式

The first line contains one integer $t$ ( $1\le t\le 1000$ ) — the number of test cases.

Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ( $1\le n\le 3\cdot 10^5$ ) — the number of elements in the array.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le n$ ) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$ .

输出格式

For each test case print $n$ integers, where the $i$ -th integer is equal to the $i$ -amazing number of the array.

样例 #1

样例输入 #1

3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1
1
2
3
4
5
6
7

样例输出 #1

-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1
1
2
3

#include
using namespace std;
const int N=3e5+10;
typedef long long ll;
int f[N],n;
vector <int> v[N];
int main()
{
	int i,j;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		int tmp;
		f[0]=0x3f3f3f3f;
		for(i=1;i<=n;i++) v[i].push_back(0);
		for(i=1;i<=n;i++)
		{	
			f[i]=0x3f3f3f3f;
			cin>>tmp;
			v[tmp].push_back(i);
		}
		int deltammx=0;
		for(i=1;i<=n;i++)
		{
			v[i].push_back(n+1);
			deltammx=0;
			for(j=1;j<v[i].size();j++)
			deltammx=max(v[i][j]-v[i][j-1],deltammx);
			if(v[i].size()!=2) 
			{
				f[deltammx]=min(f[deltammx],i);
			}
			v[i].clear();
		}
		for(i=1;i<=n;i++) 
		{
			f[i]=min(f[i],f[i-1]);
			if(f[i]==0x3f3f3f3f) cout<<-1<<" ";
			else cout<<f[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Binary String To Subsequences

题面翻译

对于长度为 $n$，只包含 $0$ 和 $1$ 的一个字符串 $s$，把它拆成 $k$ 个新字符串，使得：

• 每个新字符串是 $s$ 的一个子序列；
• $s$ 的每一个字符在这 $k$ 个新字符串中出现且仅出现一次；
• 对于每一个新字符串，相邻两个字符不同（例如 010101…，101010…）。

求出 $k$ 的最小值。

输入：$t$ 组数据（$1\le t\le 2\times 10^4$），对于每组数据，第一行一个整数 $n$（$1\le n\le 2\times 10^5$），第二行一个 01 字符串 $s$。保证所有数据 $n$ 的总和小于 $2\times 10^5$。

输出：对于每组数据，第一行是 $k$ 的最小值，第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示 $s_i$ 所在新字符串的编号（$1\le a_i\le k$）。如有多解，输出任意一个即可。

题目描述

You are given a binary string $s$ consisting of $n$ zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like “010101 …” or “101010 …” (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that 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, subsequences of “1011101” are “0”, “1”, “11111”, “0111”, “101”, “1001”, but not “000”, “101010” and “11100”.

You have to answer $t$ independent test cases.

输入格式

The first line of the input contains one integer $t$ ( $1\le t\le 2\cdot 10^4$ ) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ( $1\le n\le 2\cdot 10^5$ ) — the length of $s$ .

The second line of the test case contains $n$ characters ‘0’ and ‘1’ — the string $s$ .

It is guaranteed that the sum of $n$ does not exceed $2\cdot 10^5$ ( $\sum n\le 2\cdot 10^5$ ).

输出格式

For each test case, print the answer: in the first line print one integer $k$ ( $1\le k\le n$ ) — the minimum number of subsequences you can divide the string $s$ to.

In the second line print $n$ integers $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le k$ ), where $a_i$ is the number of subsequence the $i$ -th character of $s$ belongs to.

If there are several answers, you can print any.

样例 #1

样例输入 #1

4
4
0011
6
111111
5
10101
8
01010000
1
2
3
4
5
6
7
8
9

样例输出 #1

2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4
1
2
3
4
5
6
7
8

#include
using namespace std;
const int N=3e5+10;
typedef long long ll;
int t,n,k,ans[N];
char s[N];
int main(){
	cin>>t;
	while(t--){
		scanf("%d",&n);
		scanf("%s",s);
		k=1;
		vector<int>jk[2];
		jk[s[0]-'0'].push_back(1);
		ans[0]=1;
		for(int i=1;i<n;i++){
			int p=(s[i]-'0')^1;
			if(jk[p].empty()){
				ans[i]=++k;
				jk[p^1].push_back(k);
			}
			else{
				int ed=jk[p][jk[p].size()-1];
				ans[i]=ed;
				jk[p].pop_back();
				jk[p^1].push_back(ed);
			}
		}
		cout<<k<<endl;
		for(int i=0;i<n;i++) cout<<ans[i]<<" ";
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34