【1】做题心得 - 2025 NOIP #67 - T3【Ad-hoc】

ExFish · 2025-11-24 14:34:08 · 题解

我们发现从一个点开始钦定一个特殊点往后走一定是最优的，具体原因就是多选多错，直接这样做然后优化一下就正确了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=5;
int n,d,k,a[N][5],l,r,ma;
int t[M*N],tc;
int vis[N*M];
void dfs(int p,int flg,int len){
    if(p>n){
        if(len>ma){
            ma=len;
            l=p-len+1,r=p-1;
        }
        return;
    }
    int has=0;
    for(int i=1;i<=d;i++)if(vis[a[p][i]]==1)
        { has=1;break; }
    if(has){ dfs(p+1,flg,len+1);return; }
    if(!has&&flg==k){
        if(len>ma){
            ma=len;
            l=p-len+1,r=p-1;
        }
        return;
    }
    for(int i=1;i<=d;i++)if(vis[a[p][i]]!=-1){
        vis[a[p][i]]=1;
        dfs(p+1,flg+1,len+1);
        vis[a[p][i]]=0;
    }
    return;
}
int main(){
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=d;j++) cin>>a[i][j], t[++tc]=a[i][j];
    sort(t+1,t+tc+1);
    tc=unique(t+1,t+tc+1)-t-1;
    for(int i=1;i<=n;i++)for(int j=1;j<=d;j++)  
        a[i][j]=lower_bound(t+1,t+tc+1,a[i][j])-t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=d;j++) vis[a[i-1][j]]=-1;
        dfs(i,0,1);
        for(int j=1;j<=d;j++) vis[a[i-1][j]]= 0;
    }
    cout<<l<<" "<<r;
    return 0;
}