Educational Codeforces Round 94 (Div. 2) 题解 (CDE)

C. Binary String Reconstruction

大意：字符串w是由字符串s转换过来的，其中w[i]为‘1‘当且仅当s[i-x]或者s[i+x]为‘1‘。已知w，求s

容易得知s[i]为‘0‘的时候，w[i-x]和w[i+x]一定都是‘0‘。我们让这些位赋值为‘0‘，其他位都是‘1‘，然后检验一下

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;}
#define int ll
char s[N],ans[N];
void Solve(){
	scanf("%s",s); int n=strlen(s),x=read();
	repeat(i,0,n)ans[i]=‘1‘;
	repeat(i,0,n)
	if(s[i]==‘0‘){
		if(i-x>=0)ans[i-x]=‘0‘;
		if(i+x<n)ans[i+x]=‘0‘;
	}
	repeat(i,0,n)
	if(s[i]==‘1‘){
		if(i-x>=0 && ans[i-x]==‘1‘);
		else if(i+x<n && ans[i+x]==‘1‘);
		else{puts("-1"); return;}
	}
	repeat(i,0,n)putchar(ans[i]);
	puts("");
}
signed main(){
	//freopen("data.txt","r",stdin);
	int T=1; T=read();
	while(T--)Solve();
	return 0;
}

D. Zigzags

大意：给定 \(n\) 个数 \(a_i\)，求有多少个 \((i,j,k,l)\) 满足 \(i<j<k<l\) 且 \(a_i=a_k,a_j=a_l\)

将 \(a_i\) 看成颜色。首先固定两个颜色，然后让 \(i,k\) 枚举第一个颜色，用 lower_bound 求出在第二个颜色集合中，\(i,k\) 之间、\(k,n\) 之间有多少数（即计算 \(j,l\) 的方案数），相乘

特判一下 \(a_i=a_j=a_k=a_l\) 的情况

（我对所有颜色集合排了个序，然后查找就小的集合往大的集合找，可以加速，不知道不加速能不能过）

复杂度我也不知道

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=3010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;}
#define int ll
vector<int> a[N];
ll ans;
void work(const vector<int> &a,const vector<int> &b){
	repeat(i,0,a.size()){
		int p1=lower_bound(b.begin(),b.end(),a[i])-b.begin();
		repeat(j,i+1,a.size()){
			int p2=lower_bound(b.begin(),b.end(),a[j])-b.begin();
			ans+=(p2-p1)*p1+(p2-p1)*(b.size()-p2);
		}
	}
}
void Solve(){
	int n=read(); ans=0;
	repeat(i,1,n+1)a[i].clear();
	repeat(i,1,n+1){
		int t=read();
		a[t].push_back(i);
	}
	sort(a+1,a+n+1,[](const vector<int> &a,const vector<int> &b){
		return a.size()<b.size();
	});
	repeat(i,1,n+1)sort(a[i].begin(),a[i].end());
	repeat(i,1,n+1){
		repeat(j,i+1,n+1)
			work(a[i],a[j]);
		if(a[i].size()>=4){
			int n=a[i].size();
			ans+=n*(n-1)*(n-2)*(n-3)/(2*3*4);
		}
	}
	printf("%lld\n",ans);
}
signed main(){
	//freopen("data.txt","r",stdin);
	int T=1; T=read();
	while(T--)Solve();
	return 0;
}

E. Clear the Multiset

dp，我一直在死磕贪心，最终还是没做出来，还是zkx告诉我的dp呜呜呜

dp[i][j]表示处理到第i个数，进行了j次操作1后的操作数最小值

待补

Educational Codeforces Round 94 (Div. 2) 题解 (CDE)

原文：https://www.cnblogs.com/axiomofchoice/p/13562839.html