CF1552G A Serious Referee 题解

题目链接

点击打开链接

题目解法

感觉很神奇的题

首先把序列当成排列做

首先发现只要当成 \(01\) 序列做就是对的
为什么？
你假设有数 \(x<y\)，你把 \(\le x\) 的数设成 \(0\), \(>x\) 且 \(\le y\) 的数设成 \(1\)，\(>y\) 的数设成 \(2\)，然后做题目中的排序操作，如果最终序列形成逆序对，则不合法，但这样因为需要枚举 \(0,1,2\)，所以是 \(O(3^n)\) 的
但你发现，只要枚举 \(x,x+1\) 的位置就好了，因为一个没有排好序的序列一定存在数 \(x,x+1\) 的位置是逆序对
所以只需要枚举 \(0,1\) 即可

接下来的一步我想不到啊
考虑当前到第 \(i\) 个操作，前面操作未设计到的位置不填 \(01\)，当前一步只会把前缀变 \(0\)，后缀变 \(1\)，我们这样暴力填
这个是时间复杂度是什么？
令 \(x_i\) 为第 \(i\) 步操作的位置与前 \(i-1\) 步操作未操作到的位置的交集的大小
则复杂度为 \(O(n\prod(x_i+1))\le O((\frac{n+k}{k})^k)\)，这是可以过的

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=50,K=20;
int n,k,cnt[K];
bool uns[K][N];
int len[K],op[K][N];
vector<LL> way;
void dfs(int i,LL cur){
    if(i>k){
        if(cur!=(1ll<<n)-(1ll<<(n-__builtin_popcountll(cur)))){ puts("REJECTED");exit(0);}
        return;
    }
    int res=0;
    F(j,1,len[i]) if(cur>>op[i][j]&1) cur^=1ll<<op[i][j],res++;
    DF(j,len[i]+1,1){
        if(j<=len[i]) cur|=1ll<<op[i][j];
        if(res<=len[i]-j+1&&len[i]-j+1<=res+cnt[i-1]) dfs(i+1,cur);
    }
}
int main(){
    read(n),read(k);
    if(n==1){ puts("ACCEPTED");exit(0);}
    F(i,1,k){
        read(len[i]);
        F(j,1,len[i]) read(op[i][j]),op[i][j]--;
    }
    F(i,0,n-1) uns[0][i]=1;
    F(i,1,k){
        F(j,0,n-1) uns[i][j]=uns[i-1][j];
        F(j,1,len[i]) uns[i][op[i][j]]=0;
    }
    F(i,0,n-1) if(uns[k][i]){ puts("REJECTED");exit(0);}
    F(i,0,k-1) F(j,1,len[i+1]) if(uns[i][op[i+1][j]]) cnt[i]++; 
    dfs(1,0);
    puts("ACCEPTED");
    return 0;
}