N方过百万,关于S组T4的口胡

星空舞涵 · 2020-11-10 11:25:53 · 题解

如果你想要学习正解可以看这个 万恶之源

思路貌似没有见过和我一样的好像,我的思路是先不考虑蛇聪明不聪明,假设蛇都是能吃就吃,这样一共会进行N-1轮游戏,记录每一轮游戏是哪个蛇吃掉哪个蛇,并且记录第i条蛇是在哪一轮游戏死了.

至于如何处理出上面这些东西我们放在后面讲解(想了好长时间,问了很多大佬才想出来

知道上面这些东西以后,我们考虑一个撤回操作,我们倒着便利每一轮决斗,判断发起人是选择结束还是发起,如果选择结束的话,一定要满足这些条件

1.此次操作是发起者的最后一次操作,

2.发起者不是胜利者,并且在目前一定会选择结束的操作之前死了

如果满足上面两个条件,此次操作就是一个一定会选择结束的操作

先放一个70分的代码吧,直接用堆处理出来整个游戏的过程,然后处理.(也可以直接用set模拟)

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<pair<int,int> >q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qq;
int x[1000001];
int y[1000001];
int l[1000001];
int chi[1000001];
int ci=1;
int cha=0;
int nxt[1000001];
int last[1000001];
int minn;
int dead[1000001];
 int a[1000001];

 int read()
{
    int x=0;
    int f=1;
    char ch;
    ch=getchar( );
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar( );
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar( );
    }
    return x*f;
}

int main( )
{   
int t;
    t=read( );
    pair<int,int>ll;
    n=read( );
    for(int i=1;i<=n;i++)
    {   
        a[i]=read();
    } 
    while(t--)
    {
        for(int i=1;i<=n;i++)
        {
            ll.first=a[i];
            ll.second=i;
            q.push(ll);
            qq.push(ll); 
        }
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(l,0,sizeof(l));
        memset(nxt,0,sizeof(nxt));
        memset(last,0,sizeof(last));
        memset(dead,0,sizeof(dead));
        ci=1;
        while(ci<n)
        {
            pair<int,int>xx;
            pair<int,int>yy;
            xx=q.top( );
            while(l[xx.second]==1)
            {
                q.pop( );
                xx=q.top( );
            }
            yy=qq.top( );
            while(l[yy.second]==1)
            {
                qq.pop( );
                yy=qq.top( );
        }
        q.pop( );
        qq.pop( );
        x[ci]=xx.second;
        y[ci]=yy.second;
        dead[yy.second]=ci;
        ll.first=xx.first-yy.first;
        ll.second=xx.second;
        chi[xx.second]++;
        l[yy.second]++; 
        q.push(ll);
        ci++;
        qq.push(ll);
    }
    while(!q.empty( ))q.pop( );
    while(!qq.empty( ))qq.pop( );
/*  for(int i=1;i<=n;i++)
    {
        cout<<dead[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<x[i]<<" "<<y[i]<<endl;

    }*/
    for(int i=n-1;i>=1;i--)
    {
        nxt[i]=last[x[i]];
        last[x[i]]=i;
    }
    minn=n;
    int ans=n-1;
    for(int i=n-1;i>=1;i--)
    {
        if((nxt[i]==0||nxt[i]>=minn)&&(dead[x[i]]<minn&&dead[x[i]]!=0))
        {
            minn=i;
            ans=i-1;
        }
    //  cout<<minn<<" ";
    }
    //cout<<endl;
    cout<<n-ans<<endl;
    if(t==0)continue;
    else 
    {
        int o;
        o=read();
        for(int i=1;i<=o;i++)
        {
            int h,j;
            h=read( );
            j=read();
            a[h]=j;
        }
    }
    }

}

但是因为堆的操作是O(nlongn)的所以只有70分,所以直接用堆模拟这个过程是不可取的.

所以我就选择了一个神奇的做法(一个100分的伪作法

先开两个双端队列,然后把原本的值全部放进第一个队列里面,然后每次操作选择剩下的数里面的最大值和最小值(比较两个队列的头和尾),记录差,如果大于第一个序列的最大值或者小于第一个序列的最小值就放在第一个队列中,否则放在第二个队列中.

这种做法应该算是O(n)的,但是这样并不是完全正确的一个写法,在不考虑序号的情况下,第二个序列是单调的,但是在考虑序列的情况下是不正确的(也就是说差是单调的).

所以对于第二个序列我用暴力维护,如果他放入一个新数后不是单调的,就才用冒泡排序的方法进行处理,使序列仍然有序.(但是应该只需要很少的次数)

#include<bits/stdc++.h>
using namespace std;
deque<pair<int,int> >f;
deque<pair<int,int> >ff;
int x[1000001];
int y[1000001];
int l[1000001];
int chi[1000001];
int ci=1;
int cha=0;
int nxt[1000001];
int last[1000001];
int minn;
int dead[1000001];
 int a[1000001],n;
stack<pair<int,int> >lei;

 int read()
{
    int x=0;
    int f=1;
    char ch;
    ch=getchar( );
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar( );
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar( );
    }
    return x*f;
}
int t;

int main( )
{
    t=read( );
    pair<int,int>ll;
    n=read( );
    for(int i=1;i<=n;i++)a[i]=read();
    while(t--)
    {
        while(!f.empty())f.pop_front( );
        while(!ff.empty())ff.pop_front( );
        for(int i=n;i>=1;i--)
        {
            ll.first=a[i];
            ll.second=i;
            f.push_back(ll);
        }
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(nxt,0,sizeof(nxt));
        memset(last,0,sizeof(last));
        memset(dead,0,sizeof(dead));
        ci=1;
        while(ci<n)
        {
            pair<int,int>xx;
            pair<int,int>yy;
            if(f.empty()==1)
            {
                xx=ff.front( );
                ff.pop_front( );
                yy=ff.back( );
                ff.pop_back();
                ll.first=xx.first-yy.first;
                ll.second=xx.second;
                x[ci]=xx.second;
                y[ci]=yy.second;
                dead[yy.second]=ci;
                f.push_front(ll);
            }
            else if(ff.empty()==1)
            {
                xx=f.front( );
                f.pop_front( );
                yy=f.back( );
                f.pop_back();
                ll.first=xx.first-yy.first;
                ll.second=xx.second;
                if(f.empty()==1)f.push_back(ll);
                else  if(ll<f.back()) f.push_back(ll);
                else if(ll>f.front())  f.push_front(ll);
                else ff.push_front(ll);
                x[ci]=xx.second;
                y[ci]=yy.second;
                dead[yy.second]=ci;
            }
            else
            {
                if(f.front()>ff.front())
                {
                    xx=f.front( );
                    f.pop_front( );
                }
                else
                {
                    xx=ff.front( );
                    ff.pop_front( );
                }
                if(f.empty()==1)
                {
                    yy=ff.back( );
                    ff.pop_back( );
                }
                else if(ff.empty()==1)
                {
                    yy=f.back( );
                    f.pop_back( );
                }
                else if(f.back()<ff.back())
                {
                    yy=f.back( );
                    f.pop_back( );
                }
                else
                {
                    yy=ff.back( );
                    ff.pop_back( );
                }
                x[ci]=xx.second;
                y[ci]=yy.second;
                ll.first=xx.first-yy.first;
                ll.second=xx.second;
                dead[yy.second]=ci;
                if(f.empty()==1)f.push_back(ll);
                else  if(ll<f.back()) f.push_back(ll);
                else if(ll>f.front())  f.push_front(ll);
                else if(ff.empty()==1)ff.push_front(ll);
                else
                {
                    while(ll>ff.back( )&&!ff.empty())
                    {
                        lei.push(ff.back( ));
                        ff.pop_back();
                    }
                    ff.push_back(ll);
                    while(!lei.empty( ))
                    {
                        ff.push_back(lei.top( ));
                        lei.pop( );
                    }
                }
            }
            ci++;
        }
        for(int i=n-1;i>=1;i--)
        {
            nxt[i]=last[x[i]];
            last[x[i]]=i;
        }
        minn=n;
        int ans=n-1;
        for(int i=n-1;i>=1;i--)
        {
            if((nxt[i]==0||nxt[i]>=minn)&&(dead[x[i]]<minn&&dead[x[i]]!=0))
            {
                minn=i;
                ans=i-1;
            }
        //    cout<<minn<<" ";
        }
        cout<<n-ans<<endl;
        if(t==0)continue;
        else
        {
            int o;
            o=read();
            for(int i=1;i<=o;i++)
            {
                int h,j;
                h=read( );
                j=read();
                a[h]=j;
            }
        }
    }
}

相比与正解而言,这个算法仅仅是添加了一个对错误贪心的暴力处理,相对来说更容易想一点.但是时间并不是很优秀.

u1s1被金钩爷142857cs的数据杀没了

3 3 3 3 3 10 11 13 15 15 16 (每一个数代表这个数重复m次)

对于伪做法的那个使用队列的方法,我们考虑其什么时候会单调性调亡.首先如果此次决斗结束后单调性调亡了,那么这个发起者一定之前至少吃过一个蛇了(因为调亡是因为值一样但序号大的蛇出现在了最后面),并且被吃的那个蛇也一定吃过其他蛇(为什么在下面解释),并且如果进入队列2了说明剩下的那一部分并不是最小值,换句话说发起者是安全的.所以说在这个时候我们就可以终止模拟过程了,因为 被吃的那条蛇一定会在自己可以决策的时候就选择终止整个游戏来保证自己的安全,这样的话过程就算O(n)的啦.

为什么被吃的蛇一定曾经吃过其他蛇呢,因为如果没有吃过 的话我们假设这次是a_{x}吃了a_{y},而上一次进队2的是a_{xx}吃了a_{yy};这样的话我们可以保证