Codeforces Round 972 (Div. 2) E2. Subtangle Game (Hard Version)（博弈+双指针 sg函数思想）

题目

思路来源

稲葉廻代码

题解

这个题比easy version的数据范围大了比较多，

不能再直接dp[i][j][k]表示数组a的第i个做开始局面时，位置(j,k)为起点时的获胜情况了

当然你把第一维压到bitset里，然后前缀和优化一下，还是可以通过的，这里先不讨论这个方法

期望dp和博弈都类似dag，都可以考虑从终态局面往回推，

那么对于序列a的最后一个元素，考虑所有获胜位置，

就是每行的最靠右，且其右下方没有与之相同元素的位置

如果一行内出现了两个相同元素，选左边的那个肯定是不优的，

给对手的下一步留了更多的操作空间（选右边的那个时下一步的操作空间是选左边的真子集）

’

对于所有颜色v都处理出这样的位置集合，记为win[v]，表示v作为最后一步时的所有获胜位置

这个位置序列，是一个第一维增序，第二维降序的序列，形如(1,4)(2,3)(3,2)这种

然后考虑倒着遍历a数组，求出最后一步win[a[l]]了之后，

考虑求出倒数第二步win[a[l-1]]的所有获胜位置，

只要能走到win[a[l]]内任意一个元素的都是必败的，否则就是必胜的

这个用双指针维护，

一个指针控制第一维，找到下一个vector内第一维比当前位置(x,y)第一维大的最右右端点r，

另一个指针控制第二维，找到下一个vector内第一维比当前位置(x,y)第二维大的最小左端点l，

那么，如果l<=r且[l,r]内有下一个vector内必胜(sg=1)的元素，当前局面就必败(sg=0)

反过来，则必胜(sg=1)

逆推到第一个元素，然后判断第一个元素对应的vector内是否有必胜元素即可

这题主要时间花在读入上了，scanf 2s交c++20直接T了，交c++17少了一点时间AC了

c++20对关同步cin有特殊优化，导致关同步cin比scanf快，但是快读还是最快的，1s不到

代码

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<array>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
//#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
namespace fastIO
{
    static char buf[100000],*h=buf,*d=buf;//缓存开大可减少读入时间，看题目给的空间
    #define gc h==d&&(d=(h=buf)+fread(buf,1,100000,stdin),h==d)?EOF:*h++//不能用fread则换成getchar
    template<typename T>
    inline void sci(T&x)
    {
        int f = 1;x = 0;
        register char c(gc);
        while(c>'9'||c<'0'){
            if(c == '-') f = -1;
            c=gc;
        }
        while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;
        x *= f;
    }
    template<typename T>
    void output(T x)
    {
        if(x<0){putchar('-');x=~(x-1);}
        static int s[20],top=0;
        while(x){s[++top]=x%10;x/=10;}
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
}
using namespace fastIO;
const int N=1505;
int t,l,n,m,a[N],b[N][N],sg[N],nsg[N],mn[N*N];
vector<P>win[N*N];
void sol(){
    sci(l);sci(n);sci(m);
    rep(i,1,l){
        sci(a[i]);
    }
    rep(i,1,n){
        rep(j,1,m){
            sci(b[i][j]);
        }
    }
    rep(i,1,n*m)win[i].clear(),mn[i]=0;
    per(i,n,1){
        per(j,m,1){
            int v=b[i][j];
            if(j>mn[v]){
                win[v].pb(P(i,j));
                mn[v]=j;
            }
        }
    }
    memset(sg,0,sizeof sg);
    memset(nsg,0,sizeof nsg);
    per(i,l,1){
        vector<P>&now=win[a[i]],&nex=win[a[i+1]];
        int p=SZ(now),q=(i==l?0:SZ(nex)),l=0,r=-1;
        rep(j,0,p-1){
            P v=now[j];
            while(r+1<q && nex[r+1].fi>v.fi)r++;//[0,r] >v.fi
            while(l<q && nex[l].se<=v.se)l++;//[l,q) >v.se
            nsg[j+1]=(sg[r+1]-sg[l]<=0);//[l,r]
        }
        sg[0]=nsg[0],nsg[0]=0;
        rep(j,1,p)sg[j]=sg[j-1]+nsg[j],nsg[j]=0;
        if(i==1){
            printf("%c\n","NT"[sg[p]>0]);
            return;
        }
    }
}
int main(){
    sci(t);
    while(t--){
        sol();
    }
    return 0;
}

原文地址：https://blog.csdn.net/Code92007/article/details/142310086

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！