Codeforces Round 874 (Div. 3) A-G

比赛地址

A. Musical Puzzle

题意：给出一个字符串，求有多少个不同的长度为2的子串

Solution

直接set存即可

void solve()
{
	int n;cin>>n;
	string s;cin>>s;
	set<string>st;
	for(int i=0;i<n-1;i++)
	{
		st.insert(s.substr(i,2));
	}
	cout<<st.size()<<"\n";
}

B. Restore the Weather

题意：给出a,b两个数组，构造出一种组合，使得|a[i]-b[i]|<=k

Solution

直接把a，b数组从小到大排序即可

struct node
{
	int x,y;
	bool operator < (const node &t)const &{
		if(y!=t.y)return y < t.y;
		else return x < t.x;
	}
}e[N];
int ans[N];
int b[N];
void solve()
{
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		e[i].x=i,e[i].y=x;
	}
	for(int i=1;i<=n;i++)cin>>b[i];
	sort(e+1,e+1+n);
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++)
	{
		ans[e[i].x]=b[i];
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	cout<<"\n";
}

C. Vlad Building Beautiful Array

题意：给出一个数组a，现在要求构造另一个数组b，要求数组b中全为正奇数或者全为正偶数，b[i]可以为a[i]或者a[i]-a[j]

Solution

可以全构造为奇数或者偶数，将数组从小到大排序

对于构造全奇数的情况，对于一个偶数，前面必须要有比它小的奇数

对于构造全偶数的情况，对于一个奇数，前面必须要有比它小的奇数(所以有奇数的话其实是不可能的？)

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	int ans=1;
	int flag=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]&1)
		{
			if(!flag)
			{
				ans=0;
				break;
			}
			flag=1;
		}
	}
	if(ans)
	{
		cout<<"YES\n";
		return;
	}
	flag=0;
	ans=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i]&1)
		{
			flag=1;
		}else
		{
			if(!flag)
			{
				ans=0;
				break;
			}
		}
	}
	if(ans)cout<<"YES\n";
	else cout<<"NO\n";
}

D. Flipper

题意：给出一个数组，可以任选一个区间[l,r]，将其中的数翻转，然后再将左边的数整体放到区间右边，右边的数整体放到区间左边，求字典序最大的情况

Solution

分情况讨论，因为求字典序最大的，所以跟最大值n的位置脱不了关系

当n的位置在最右边时，要把n放在第一位，那么区间就要包含n，然后向左移动看，如果a[l-1]比a[1]大，那么将l-1加进来的字典序是比不加要大的

当n的位置在最左边，此时无论怎么操作字典序都会变小，我们就要看n-1的位置，如果n-1在最右边，同上一种情况我们可以知道，n-1和n之间的数都比n小，答案就是[n,n]，如果n-1在中间位置，答案是[pos-1,pos-1]，因为如果多选的话会使得n的位置在更后面

当n的位置在中间，同第一种情况，把左边所有大于a[1]的数都纳入区间

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int pos;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==n)
		{
			pos=i;
			break;
		}
	}
	int l,r;
	if(pos==n)
	{
		l=n,r=n;
		while(l-1>=1&&a[l-1]>a[1])l--;
	}else if(pos==1)
	{
		int pp;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==n-1)
			{
				pp=i;break;
			}
		}
		if(pp==n)
		{
			l=n,r=n;
		}else
		{
			l=pp-1,r=pp-1;
		}
	}else
	{
		l=pos-1,r=pos-1;
		while(l-1>=1&&a[l-1]>a[1])l--;
	}
	for(int i=r+1;i<=n;i++)cout<<a[i]<<" ";
	for(int i=r;i>=l;i--)cout<<a[i]<<" ";
	for(int i=1;i<l;i++)cout<<a[i]<<" ";
	cout<<"\n";
}

E. Round Dance

题意：有n个人跳舞，在每一组里每个人有两个相邻的人(如果一组人里面只有两个人跳舞，那么他们相邻的人相同)，每个人只记得一个相邻的人，问跳舞的组数最大最小是多少

Solution

并查集求出联通分块数量num，该答案就是最大值，然后再找含有度数不为2的点的连通分块数量cnt，最小值答案是num-max(0,cnt-1)

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		t[i]=i;
		l[i]=0;
	}
	int cnt=n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]<i&&a[a[i]]==i)
		{
			continue;
		}else
		{
			l[a[i]]++;
			l[i]++;
		}
		int aa=find(i),b=find(a[i]);
		if(aa!=b)
		{
			t[aa]=b;
			cnt--;
		}
	}
	unordered_map<int,int>mp;
	for(int i=1;i<=n;i++)
	{
		int z=find(i);
		if(l[i]!=2)mp[z]++;
	}
	cout<<cnt-max(0LL,(long long)mp.size()-1)<<" "<<cnt<<"\n";
}

F. Ira and Flamenco

题意：有n个人跳舞，每个学生都有一个等级，要求找到满足以下要求的组的个数

1.该组有且仅有m个学生跳舞

2.每个学生的等级互不相同

3.每个学生的等级差严格小于m

Solution

从条件里面可以看出，满足条件的必须是一个公差为1的等差数列

那我们把它们的等级排序，然后把满足条件的答案加起来即可

int a[N];
struct node
{
	int x,y;
	bool operator < (const node &t)const &{
		if(y!=t.y)return y<t.y;
		else return x<t.x;
	}
}e[N];
void solve()
{
	int n,m;cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(cnt==0||a[i]!=e[cnt].y)
		{
			e[++cnt].y=a[i];
			e[cnt].x=1;
		}else
		{
			e[cnt].x++;
		}
	}
	int ans=0;
	int res=0;
	int num=0;
	int last=-1;
	for(int i=1;i<=cnt+1;i++)
	{
		if(last==-1)
		{
			last=e[i].y;
			num++;
			res=e[i].x%mod;
		}
		else if(i==cnt+1||e[i].y-last!=1)
		{
			if(num==m)
			{
				ans=(ans+res)%mod;
			}
			num=1;
			res=e[i].x%mod;
			last=e[i].y;
		}else
		{
			if(num==m)
			{
				ans=(ans+res)%mod;
				res=(res*ksm(e[i-m].x,mod-2))%mod;
				num--;
			}
			res=res*e[i].x%mod;
			last=e[i].y;
			num++;
		}
		//cout<<res<<" ";
		
	}
	//cout<<"\n";
	cout<<ans<<"\n";
	
}

G. Ksyusha and Chinchilla

题意：给出一个树，问删除哪些边可以使得每个点仅属于一个长度为3的枝条

Solution

首先树的大小必须为3的倍数，然后删除的边的个数必须为n/3-1，这样才能保证满足条件

然后我们跑一遍dfs，把遇到大小为3的子树就把他删除，记录删除的边即可

vector<pii>e[N];
int sz[N];
int vis[N];
int dfs(int x,int pre,int id)
{
	int res=0;
	sz[x]=1;
	for(auto it:e[x])
	{
		if(it.first==pre)continue;
		res+=dfs(it.first,x,it.second);
		sz[x]+=sz[it.first];
	}
	if(sz[x]-res==3)
	{
		vis[id]=1;
		res+=3;
	}
	return res;
}

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		vis[i]=0;
		e[i].clear();
	}
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		e[u].push_back({v,i});
		e[v].push_back({u,i});
	}
	if(n%3!=0)
	{
		cout<<"-1\n";
		return;
	}
	dfs(1,0,0);
	int num=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])num++;
	}
	if(num!=n/3-1)
	{
		cout<<"-1\n";
		return;
	}
	cout<<num<<"\n";
	for(int i=1;i<=n;i++)
	{
		if(vis[i])cout<<i<<" ";
	}
	cout<<"\n";
}