E和F题解

E题目：思路：可以直接把小紫的位置当作根节点，这样再去追小红就会比较直观讨论小红的走法

不向根节点的方向走，直接向下去找离自己距离最近的根节点，比较小紫允许小红走的步数与走到最近叶子需要的步数
向上走一步，站在父亲的位置上，确定当下最近的叶子节点，再次比较小紫允许自己走的步数与走到最近叶子需要的步数
以此类推，直到最后无法再向上走的位置的情况
如果上面的情况小红都不能成功，那么就是小紫赢

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+9;
ll T,n,root,dep[N],midep[N],fa[N];
vector<ll>kid[N];
void dfs(ll u,ll f)
{
    fa[u]=f;
    if(u!=root) dep[u]=dep[f]+1;
    for(ll v:kid[u])
    {
        if(v==f) continue;
        dfs(v,u);
        midep[u]=min(midep[u],midep[v]);
    }
    if(kid[u].size()==1) midep[u]=dep[u];
}
void solve()
{
    memset(dep,0,sizeof dep);
    memset(fa,0,sizeof fa);
    memset(midep,0x3f,sizeof midep);
    for(int i=0;i<=n;i++) kid[i].clear();
    cin>>n;
    ll a,b;
    cin>>a>>b;
    root=b;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin>>u>>v;
        kid[u].push_back(v);
        kid[v].push_back(u);
    }
    if(kid[a].size()==1)//特判，小红本身就是叶子节点
    {
        cout<<"red\n";
        return ;
    }
    dfs(root,0);
    ll temp=a,cnt=0;
    while(dep[temp]>cnt*2)//小红与小紫互相靠近但不至于相遇
    {
        ll step=dep[temp]-cnt*3;//现在小紫允许小红走的步数
        //画图理解，小红与小紫中间的距离就是小紫允许小红走的步数，小红向上导致距离-1，在小红向上一步的同时小紫向下2步，所以中间的距离会-2，总和就是-3
        if(step<=0) break;
        if(midep[temp]-dep[temp]<=step)//小红可以成功走到叶子节点
        {
            cout<<"red\n";
            return ;
        }
        cnt++;//在小红的角度向上走的步数增加
        temp=fa[temp];
        if(temp==0) break;
    }
    cout<<"purple\n";//剩下的就是小紫赢的情况
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

F题目思路：情况分为2种：找规律发现

当序列最大值>=n时，小红一定获胜
当序列最大值<n时，小红有可能获胜，找出小红获胜的情况，剩下的就是小紫获胜的情况：方法就是在每***作后我们想要尽量满足当前最大值>=当前剩下的数个数，所以此时小红不会想要现在当前最小数出局，而是去选择第二大的数出局，小的数想要通过小紫的操作来将它去掉，这样可以在相同的轮数内去掉更多的堆，以尽量去满足当前最大值>=当前剩下的数个数这个条件，如果这样都不能满足，那么就只能小紫获胜了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n;
deque<ll>q,te;
void solve()
{
    ll ma=0;
    q=te;
    cin>>n;
    vector<ll>a(n);
    for(int i=0;i<n;i++) {cin>>a[i];ma=max(ma,a[i]);}
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++) q.push_back(a[i]);//从小到大加入双端队列
    if(ma>=n)
    {
        cout<<"red\n";
        return ;
    }
    ll cnt=0;
    while(q.size())
    {
        if(ma>=q.size())//已经满足最大>=当前堆数
        {
            cout<<"red\n";
            return ;
        }
        ll te=q.back();q.pop_back();//还步满足，那就第二大弹出
        q.pop_back();
        q.push_back(te);
        cnt++;ma--;
        while(q.size()&&q.front()<=cnt) q.pop_front();//前面的因为小紫的操作也需要更新，所以需要使用到双端队列，并且在数据进来时就应该是有序的
    }
    cout<<"purple\n";
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}