目录

小紫的均势博弈

 小紫的劣势博弈

小紫的01串操作

 小紫的优势博弈

 小紫的线段染色

小紫的树上染色

---

这场的六个题对标洛谷应该就是 红，红，橙，黄，橙，黄

我们来看一下这些题吧

小紫的均势博弈

因为每次只拿一颗石子，连博弈论都算不上，奇数小红赢，偶数小紫赢

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

int n;
signed main()
{
	cin>>n;
	if(n%2==1)
	{
		cout<<"kou";
	}
	else
	{
		cout<<"yukari";
	}
	return 0;
}

 小紫的劣势博弈

思路：如果小红希望x尽可能小，那么肯定是拿小的，如果小紫，希望x大，也是要拿小的，因此哦我们发现他们都是要去抢最小的，我们直接排序一下，奇数位置给x+a[i]，偶数位置给x-a[i]，最后输出x即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(i%2==1)
		{
			ans+=a[i];
		}
		else
		{
			ans-=a[i];
		}
	}
	cout<<ans;
	return 0;
}

小紫的01串操作

 

思路：我们发现每个人最多操作一次，也就是说明最多能够修改三个位置为一个共同的字符，因此我们只需要判断01和10出现的次数不超过4即可，那么就是可以yes，否则就是no

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
string s;
void solve()
{
	cin>>s;
	int n=s.size();
	int cnt=0;
	for(int i=2;i<=n;i++)
	{
		if((s[i]=='0'&&s[i-1]=='1')||(s[i]=='1'&&s[i-1]=='0'))
		cnt++;
	}
	if(cnt>4)
	{
		cout<<"No\n";
	}
	else
	{
		cout<<"Yes\n";
	}
}
signed main()
{
	cin>>t;
	while(t--)
	solve();
	return 0;
}

 小紫的优势博弈

 思路：我们可以考虑状态，既然我们要求的是一个区间里面的数有偶数个1和偶数个0，那么整个区间内的异或应当为0，我们可以对每一个位置去统计状态；

00表示偶数个1和偶数个0；

01表示偶数个1和奇数个0；

10表示奇数个1和偶数个0；

11表示奇数个1和奇数个0；

如果我们一个区间内的异或为0，那么如果当前状态在后面出现过，那么就说明区间内有偶数个1和偶数个0，我们可以用map去存储出现s状态的位置pos，然后用f数组去记录当前i位置的状态s，后面是否出现过

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
map<int,int> mp;
int f[1000005];
signed main()
{
	cin>>n;
	cin>>s;
	s=" "+s;
    int flag0=0;
    int flag1=0;
	for(int i=1;i<=n;i++)
    {
        if(s[i]=='0')
            flag0++,flag0%=2;
        else
            flag1++,flag1%=2;
        int state=(flag1<<1)+flag0;
        if(mp[state]!=0)
        {
            f[mp[state]]=1;
        }
        mp[state]=i;
    }
    int cnt=0;
	for(int i=1;i<=n;i++)
    {
        if(f[i]==1)
        {
            cnt++;
        }
    }
	double sum=((cnt)*1.0)/(n*1.0);
	printf("%.8lf",sum);
	return 0;
}

 小紫的线段染色

思路：我们可以用结构体存储线段的左边界，右边界，当前线段的编号，将线段按照左边界大小排序，如果左边界大小一样，就按照右边界大小排序

然后线性跑一遍，如果当前线段和前面的线段没有交叉，那么就不操作，如果有交叉，那就涂成紫色，如果和前面的紫色也有交叉那么就输出-1，否则直接进入紫色线段的数组，最后输出紫色数组里面的线段编号即可

ps：至少要涂一个，当时没看清，只过了87.5%的数据，我们要特判一下，如果紫色数组的大小为0，那么就输出1,1即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
int n;
struct node{
	int l,r,id;
}a[100005];
int cmp(node a,node b) {
    if(a.l==b.l)return a.r<b.r;
    return a.l < b.l;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].l>>a[i].r;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	int lh=0,rh=0;
	int lz=0,rz=0;
	vector<int> e;
	for(int i=1;i<=n;i++)
	{
		if(a[i].l>rh)
		{
			lh=a[i].l;
			rh=a[i].r;
		}
		else//将线段变成紫色 
		{
			if(a[i].l>rz)
			{
				lz=a[i].l;
				rz=a[i].r;
				e.push_back(a[i].id);
			}
			else
			{
				cout<<"-1\n";
				return 0;
			}
		}
	}
    if(e.size()==0)
    {
        cout<<1<<"\n";
        cout<<1<<"\n";
        return 0;
    }
	cout<<e.size()<<"\n";
	for(int v:e)
	{
		cout<<v<<" ";
	}
	return 0;
 } 

小紫的树上染色

思路 :这题也是一下子就想到二分了，我们可以去枚举连通块的最大大小，然后只要当前节点包括其子节点的大小大于了mid，那么就将这个点涂为紫色，然后这个点的大小变为0，然后继续去统计

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int u,v,w;
vector<int> e[200005];
int cnt[100005];
int dfs(int v,int fa,int mid)
{
	int num=0;
	cnt[v]=1;
	for(int u:e[v])
	{
		if(u!=fa)
		{
			num+=dfs(u,v,mid);
			cnt[v]+=cnt[u];
		}
	}
	if(cnt[v]>mid)
	{
		num++;
		cnt[v]=0;
	}
	return num;
}

signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n-1;i++)
	{
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	int l=0;
	int r=100005;
	while(l<r)
	{
		for(int i=1;i<=n;i++)
		cnt[i]=0;
		int mid=(l+r)/2;
		if(dfs(1,0,mid)>k)
		{
			l=mid+1;
		}
		else
		{
			r=mid;
		}
	}
	cout<<l;
	return 0;
}