P9378 [THUPC 2023 决赛] 物理实验

字典序/次幂贪心模型

显然从 ，我们选择的答案是一个前缀状态，保住一个胜过后面所有的

问题等价于，当前有答案集合 ，求加入元素 是否合法

判定就是枚举每一轮宇宙射线

我们考虑到已经有 了，我们可以直接找出来每轮宇宙射线轰掉哪个，即未被轰掉，未被保护的第一个元素

此时可以得到另一个性质 ， 中的每一个元素都必须要在被轰掉之前做完，判定时候即可求出每一个元素最晚的做掉时间，

问题等价于，我们填序列 ，要填 位，是否能够满足每一个元素不被轰掉

从小到大排序 ，直接判定 ，这样一定最优，考虑任意交换更劣

从小到大枚举 ，，判定 ，总复杂度

#include<bits/stdc++.h>
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb push_back
#define go(it) for(auto &it:as[x])
using namespace std;

const int N=610;
int n,m,cnt;
int a[N],p[N][N],S[N],T[N],dead[N],now[N];

int fr(){
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
void fw(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
bool cop(int a,int b){return T[a]<T[b];}

bool check()
{
    memset(T,0x3f,sizeof T);
    memset(dead,0,sizeof dead);
    
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            int x=p[i][j];
            if(S[x]) T[x]=min(T[x],a[i]);
            else if(!dead[x]) {dead[x]=1;break;}
        }
    
    int idx=0;
    for(int i=1;i<=n;i++)
        if(S[i]) now[++idx]=T[i];
    sort(now+1,now+1+idx);
    for(int i=1;i<=idx;i++)
        if(i>now[i]) return 0; 
    return 1;
}

int main()
{
    n=fr(),m=fr();
    for(int i=1;i<=m;i++) a[i]=fr();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=fr();
    for(int i=1;i<=n;i++)
        S[i]=1,S[i]=check();
    check(); //怕最后一次check失败T不对
    int idx=0;
    for(int i=1;i<=n;i++)
        if(S[i]) now[++idx]=i;
    sort(now+1,now+1+idx,cop);
    for(int i=1;i<=idx;i++) fw(now[i]),pt;
    return 0;
}