牛客周赛 Round 34（A,B,C,D,E,F,G）

把这场忘了。。官方也迟迟不发题解

比赛链接

出题人题解

A 小红的字符串生成

思路：

枚举四种字符串打印出来即可，为了防止重复可以用set先去一下重。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;

set<string> S;
string a,b;

int main(){
	cin>>a>>b;
	S.insert(a);
	S.insert(b);
	S.insert(a+b);
	S.insert(b+a);
	cout<<S.size()<<endl;
	for(auto x:S)
		cout<<x<<endl;
	return 0;
}

B 小红的非排列构造

思路：

如果它本身就不是一个排列，那么就不需要修改，如果是排列，我们就换一个不是排列中的数进去，那么它就一定不是排列了。

判定是否为排列的方法很多，我是先排序再去重，然后看一下两头的数是不是1和n就行了

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;

int n,a[maxn],cnt;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	cnt=unique(a+1,a+n+1)-a-1;
	if(cnt==n && a[1]==1 && a[n]==n)printf("1\n1 1000000");
	else printf("0");
	return 0;
}

C 小红的数字拆解

思路：

看半天没看懂，原来是切割数位啊😅

观察一下不难发现，如果想要切割出来的数是个偶数，那么就需要个数为偶数，高位无所谓。而我们要尽可能切出来最多偶数，所以奇数一定和和它右边遇到的第一个偶数进行结合。

切割方法找到了，现在问题变成了怎么存，怎么排序。一般想法是用string存，并用string内置的排序办法。但是string排序默认是字典序排序而不是数字的先比数位。于是用结构体存一个string，并重载一下排序办法就可以了。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

string str,t;
struct Str{
	string s;
	Str(string x):s(x){};
	bool operator<(const Str x)const{
		if(s.size()==x.s.size())return s<x.s;
		return s.size()<x.s.size();
	}
};
multiset<Str> S;

int main(){
	cin>>str;
	for(auto x:str){
		t+=x;
		if(~(x-'0')&1){
			S.insert(Str(t));
			t.clear();
		}
	}
	for(auto x:S)
		cout<<x.s<<endl;
	return 0;
}

D 小红的陡峭值

思路：

手玩一会不难发现：中间的 $0$ 都是没用的。

如果中间的 $0$ 都取两边其一的数，那么中间的 $0$ 就可以看作没有。而如果都不取，差值势必大于1，直接就不满足条件了。因此为了满足条件，中间的 $0$ 就只能取一边的数，就相当于没用。

现在有用的只有两端的 $0$ 。我们用两个 $b oo l$ 变量 $f 1, f 2$ 记录一下开头和结尾有无 $0$ ，然后直接把原序列中所有的 $0$ 全部去掉（或者直接先替换成一端的数）。问题变成了现在要如何填数？

发现需要求一下中间的数的陡峭值是多少，如果是 $0$ ，就需要两端的 $0$ 来补，如果是 $1$ ，就不需要两端有 $0$ ，如果大于 $1$ ，直接无解。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;

int n,a[maxn],cnt;

int main(){
	cin>>n;
	if(n==1){
		printf("-1");
		return 0;
	}
	int flag=0;
	for(int i=1,t;i<=n;i++){
		cin>>a[i];
		if(a[i]==0){
			if(i==1)flag=1;
			else if(i==n)flag=2;//两端有一端有就行了，所以用了一个变量
			a[i]=a[i-1];
		}
	}
	if(a[n]==0)a[n]=5;
	for(int i=n;i>=1;i--)
		if(a[i]==0)
			a[i]=a[i+1];
	
	int tot=0;
	for(int i=2;i<=n;i++)
		tot+=abs(a[i]-a[i-1]);
	
	if(tot==0 && flag){
		if(flag==1)a[1]=(a[2]==1)?2:a[2]-1;
		else if(flag==2)a[n]=(a[n-1]==1)?2:a[n-1]-1;
		for(int i=1;i<=n;i++)
			printf("%d ",a[i]);
	}
	else if(tot==1){
		for(int i=1;i<=n;i++)
			printf("%d ",a[i]);
	}
	else printf("-1");
	return 0;
}

E 小红的树形 dp

思路：

一开始的思路是：把一个点钦定为根节点，那么每个点的深度就确定了，如果某个点的值确定，那么对应奇数和偶数深度的点就确定了，然后巴拉巴拉。

不过不用那么麻烦，因为一个点确定了，其他点就随之确定了，因此我们直接遍历一下有没有d或p，如果有，就以它为根节点开始往下填数，如果出现了冲突的点就无解。如果没有d或p，就随便填了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;

int n;
string color;

int head[maxn],cnt;
struct edge{
	int v,nxt;
}e[maxn<<1];
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

void dfs(int u,int rt){
	for(int i=head[u],v;i;i=e[i].nxt){
		v=e[i].v;
		if(v==rt)continue;
		if(color[v]==color[u]){
			printf("-1");
			exit(0);
		}
		color[v]=(color[u]=='d')?'p':'d';
		dfs(v,u);
	}
}

int main(){
	cin>>n>>color;
	color=" "+color;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	
	if(color.find_first_of("dp",1)!=string::npos)dfs(color.find_first_of("dp",1),-1);
	else {
		color[1]='d';
		dfs(1,-1);
	}
	
	cout<<color.substr(1);
	return 0;
}

F 小红的矩阵构造

思路：

就是很固定的构造方式，官方讲解讲的已经很明白了，在视频一小时九分那里。大概就是这个样子：

在这里插入图片描述

注意 $n,m\ge 4$ 还 $x$ 是偶数。

code：

#include <iostream>
#include <cstdio>
using namespace std;

int n,m,x;
int a[5][5];

int main(){
	cin>>n>>m>>x;
	if(x==2)cout<<-1<<endl;
	else if(x%4==0){
		a[1][1]=a[1][2]=a[2][1]=a[2][2]=x/4;
		for(int i=1;i<=n;i++,puts(""))
			for(int j=1;j<=m;j++){
				if(i>4 || j>4)printf("0 ");
				else printf("%d ",a[i][j]);
			}
	}
	else {
		x-=6;
		a[1][1]=a[1][2]=a[2][1]=a[2][2]=x/4;
		a[3][2]=a[2][3]=a[3][3]=a[2][4]=a[4][2]=a[4][4]=1;
		for(int i=1;i<=n;i++,puts(""))
			for(int j=1;j<=m;j++){
				if(i>4 || j>4)printf("0 ");
				else printf("%d ",a[i][j]);
			}
	}
	return 0;
}

G 小红的元素交换

思路：

用到了置换环这个小知识点。将排列打乱，然后给 $a_i\rightarrow i$ 连一条边，连完之后就会出现多个环，只出现环的原因是：如果将每个位置看作一个点，每个点都只有一个入度和一个出度。而且环上每个位置上的数的正确位置都是它指向的下一个位置（废话），也就是环上每个位置的数都只偏移了一位。

根据这个思路，可以把问题转化为，多个置换环怎么把数归位。假设环长为 $a$ ，发现如果环中两种颜色都存在，那么它可以通过交换 $a - 1$ 次把所有数归位。

归位方法是：环上每一段连续的白色或黑色的最后一个标记一下，都先不动，然后从中随便取一个开始向后给路上的每个点进行归位，然后遇到下一个被标记的点，让它接着向下交换，换一遍后剩下的就是黑白黑白颜色交替的颜色没有归位了，再随便找一个，把它和在它的正确位置上的点交换位置（因为是黑白交替，它下一个位置的点一定和它颜色不同，所以一定是可以交换的），然后换出来的点以此类推和正确位置上的点交换，最后就能换好，因为每次交换都会有一个点被放入正确位置，而最后一次交换两个点会同时归位，所以一共需要 $a - 1$ 次交换。

如果是纯色的环，就需要在别处借一个异色过来，然后再还回去，这就需要 $a + 1$ 次交换。

但是如果有两个不同纯色的环，它们可以先交换其中一个点，两边都排好序后再换回来，这样两边都只需要 $a$ 次交换就可以了。

所以这个题我们需要统计每个环是同色还是异色，如果是异色就加 $环长 - 1$ ，否则加 $环长 + 1$ 。再统计纯黑和纯白分别有几个，最后再减去两值小的*2就行了。~~啊嘞，好像不是黑色是红色~~

code：

#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1e5+5;

int n,a[maxn];
string color;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cin>>color;
	color=" "+color;
	
	int ans=0,w=0,r=0;
	vector<bool> vis(n+5,false);
	for(int i=1;i<=n;i++){
		int cnt=0;
		bool f1=false,f2=false;//有红 有白 
		if(!vis[i]){
			vis[i]=true;
			cnt++;
			if(color[i]=='W')f1=true;
			else f2=true;
			for(int p=a[i];p!=i;p=a[p]){
				vis[p]=true;
				cnt++;
				if(color[p]=='W')f1=true;
				else f2=true;
			}
			if(cnt==1)continue;
			else if(f1 && f2)ans+=cnt-1;
			else {
				ans+=cnt+1;
				if(f1)w++;
				else r++;
			}
		}
	}
	if(ans==0)cout<<0<<endl;
	else if(color.find("W")==string::npos || color.find("R")==string::npos)cout<<-1<<endl;
	else cout<<ans-min(w,r)*2<<endl;
	
	return 0;
}