Educational_round94题解

A. String Similarity（构造+思维）

解题思路

原字符串长度为$2*n-1$，需要匹配的字符串一共有$n$个，要使所有字符串都得到匹配，即让构造的长度为$n$的字符串每一个位置都能匹配到一个。可得到$w_i=s_{2i}$

题解

#include<iostream>
using namespace std;

char str[200];
char ans[200];

int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		cin >> str;
		for(int i=0;i<n;i++){
			ans[i] = str[i*2];
		}
		ans[n] = '\0';
		cout << ans << "\n";
	}
}

B. RPG Protagonist

解题思路

题解

C. Binary String Reconstruction（模拟）

解题思路

就是一个反推字符串的过程。已知有一种情况是两个条件都为假时才会出现$0$，则先利用这种情况反推出有$0$的部分。但是这并不是唯一的一种情况，当$i-x$跟$i+x$都不在范围内的时候也为$0$，即在$\left (x,n-x\right ]$区间中的字符都为$0$。其余情况为$1$。一共扫两遍，第一遍确定$0$，第二遍判断是否合理

题解

#include<bits/stdc++.h>
using namespace std;

char str[100010];
char ans[100010];

int main(){
	int t;
	int x;
	cin >> t;
	while(t--){
		cin >> str + 1;
		cin >> x;
		int n = strlen(str+1);
		for(int i=1;i<=n;i++){
			ans[i] = '1';
			if(i+x>n&&i<=x){
				ans[i] = '0';
			}
		}
		for(int i=1;i<=n;i++){
			if(str[i]=='0'){
				if(i+x<=n){
					ans[i+x] = '0';
				}
				if(i>x){
					ans[i-x] = '0';
				}
			}
		}
		ans[n+1] = '\0';
		bool flag = true;
		for(int i=1;i<=n;i++){
			if(!(str[i]=='1' && ((i+x<=n&&ans[i+x]=='1') || (i>=x&&ans[i-x]=='1'))
					|| (str[i]=='0' && ( (i+x>n && i<x) || !((i+x<=n&&ans[i+x]=='1') || (i>=x&&ans[i-x]=='1')) ) )
				)){
				flag = false;
			}
		}
		if(flag){
			cout << ans+1 <<"\n";
		}else{
			cout << "-1" << "\n";
		}

	}
}