[数据结构与算法]codeforces#754（div2)A~D题解

这场cf，结论加思维居多。想的道就能秒写,比赛开始1分钟后，A题ac了，第4分钟B题ac了，然后第11分钟交了c，wa了，第33分钟后ac了，没有想会可以直接找字符串，wa了几发，后面暴力直接通过，在这里我挖了一下好的c题代码，然后就是D题，第一眼，看到树，我有点慌，后面看完题目，第53分钟左右ac了。最后比赛还有一个多小时，去刷题去了。写不来E，F。

E，F待补。

A.M. Deviation

题意，就是找三个数，然后按照他给的规则找最小值。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int t;
	cin>>t;
	while (t--)
	{
		int x,y,z,s;
		cin>>x>>y>>z;
		s=x+y+z;
		x=s/3;y=s/3;z=s-x-y;
		if (z-y==2) --z,++y;
		cout<<abs(x+z-2*y)<<'\n';
	}
}

B.

题意就是，给一个串，然后把他变成单调不递减的，要求你用一个子串（单独不递增）的使输入的串变成不递减的，很显然答案只会有0和1；

#include <bits/stdc++.h>
using namespace std;
int st[1002],tp;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int t;
	cin>>t;
	while (t--)
	{
		int n,cnt=0;tp=0;
		string s;
		cin>>n>>s;
		int i;
		for (i=0;i+1<n;i++) if (s[i]>s[i+1]) break;
		if (i+1==n) {cout<<"0\n";continue;}
		cout<<"1\n";
		for (i=0;i<n;i++) cnt+=s[i]=='0';
		for (i=0;i<cnt;i++) if (s[i]=='1') st[++tp]=i+1;
		for (i=cnt;i<n;i++) if (s[i]=='0') st[++tp]=i+1;
		cout<<tp;
		for (i=1;i<=tp;i++) cout<<' '<<st[i];cout<<'\n';
	}
}

C.

题意就是找一个a的数量比b或者c数量多的最长子串，我们可以删前面和后面的字符串来得到这个子串。

最后就是查找固定子串判断就行。

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

int main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		int n;
		cin >> n >> s;
		if (s.find("aa") < n)
			puts("2");
		else if (s.find("aba") < n || s.find("aca") < n)
			puts("3");
		else if (s.find("abca") < n || s.find("acba") < n)
			puts("4");
		else if (s.find("abbacca") < n || s.find("accabba") < n)
			puts("7");
		else
			puts("-1");
	}

}

D

类似二分图，然后结论个数就是n，我们要找一个最多的点要求先手的人能赢，并且要通过

• u⊕v≤min(u,v)这个条件。
• 最后我们建一个树，然后用a[0],a[1]来代表二分图存点。通过深搜来赋值，就行了。

#include <bits/stdc++.h>
using namespace std;
const int N=2.1e5;
vector<int> e[N],a[2];
int dep[N],p[N];
void dfs(int u)
{
	a[dep[u]&1].push_back(u);
	for (auto &v:e[u]) if (!dep[v])
	{
		dep[v]=dep[u]+1;
		dfs(v);
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int t;
	cin>>t;
	while (t--)
	{
		int n,i,j;
		cin>>n;
		memset(dep+1,0,n*sizeof dep[0]);
		for (i=0;i<=1;i++) a[i].clear(),a[i].reserve(n);
		for (i=1;i<=n;i++) e[i].clear();
		for (i=1;i<n;i++)
		{
			int u,v;
			//u=i+1;v=rand()%i+1;
			cin>>u>>v;
			e[u].push_back(v);e[v].push_back(u);
		}
		dfs(dep[1]=1);
		if (a[0].size()<a[1].size()) swap(a[0],a[1]);
		for (i=1;i<=n;i<<=1);
		i>>=1;
		for (j=i;j<=n;j++) p[a[0].back()]=j,a[0].pop_back();
		for (i=0;i<20;i++) if (a[0].size()>>i&1) for (j=1<<i;j<1<<i+1;j++) p[a[0].back()]=j,a[0].pop_back();
		for (i=0;i<20;i++) if (a[1].size()>>i&1) for (j=1<<i;j<1<<i+1;j++) p[a[1].back()]=j,a[1].pop_back();
		for (i=1;i<=n;i++) for (auto &v:e[i]) assert((p[i]^p[v])>min(p[i],p[v]));
		for (i=1;i<=n;i++) cout<<p[i]<<" \n"[i==n];
	}
}