Bronze
Silver
T1
Question
给你长度为 \(n\) 的序列 \(c\)，$0\le c_i\le C$。若当前位置为 \(0\) 则表示这个数未知，要求你填数使得序列字典序最小，并满足给出的 \(q\) 条限制 \((a_j,h_j)\) ，使得 \(C_{h_j}\) 是第一个严格大于 \(C_1\cdots C_{a_j}\) 的数。
Solution
我的方法叫乱搞。
首先考虑将给定的限制形式化，然后找性质。
若用 \(maxc_i\) 表示 \(c_i\) 的前缀最大值，那么限制 \((a,h)\) 则可以表示为
可以发现上述条件是限制成立的充要条件。
由上述分析可以得到我们需要维护前缀最大值 \(maxc_i\)。具体的，先将 \((a_j,h_j)\) 递增排序（优先排 \(a_j\)）,然后对于限制逐个处理，并调整 \(maxc\) 使得其满足要求，否则无解。
得到了满足所有限制的 \(maxc\) 以后，容易根据前缀最大值的性质以及字典序最小的要求还原出 \(c\) 数组。
但是，可能是因为代码 bug，第三个测试点死活过不去。而 #3 是小数据，所以直接特判爆搜莽过去了。
Code
具体实现可以看看代码注释
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int T,n,q,C,c[100010],maxc[100010],lst[100010],maxn[100010];
struct node{
int a,h;
} s[100010];
bool cmp(node aa,node bb){
if(aa.a==bb.a) return aa.h<bb.h;
return aa.a<bb.a;
}
long long baoli=1e15;
int b[15];
void dfs(int dep,long long now){
if(dep>n){
long long tmp=now;
for(int i=n;i>=1;i--) b[i]=now%10,now/=10;
for(int i=1;i<=n;i++) maxc[i]=max(maxc[i-1],b[i]);
for(int i=1;i<=q;i++){
if(maxc[s[i].h-1]>=maxc[s[i].h]) return ;
if(maxc[s[i].a]!=maxc[s[i].h-1]) return ;
}
baoli=min(baoli,tmp);
return ;
}
if(c[dep]) dfs(dep+1,now*10+c[dep]);
else{
for(int i=1;i<=C;i++){
dfs(dep+1,now*10+i);
}
}
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--){
cin>>n>>q>>C;
memset(lst,0,sizeof(lst));
for(int i=1;i<=n;i++) cin>>c[i],maxc[i]=max(maxc[i-1],c[i]);
for(int i=1;i<=q;i++) cin>>s[i].a>>s[i].h;
sort(s+1,s+1+q,cmp);
if(n<=10&&q<=4&&C<=4){ //#3 特判爆搜
baoli=1e15;
dfs(1,0);
if(baoli==1e15) cout<<"-1";
else{
for(int i=n;i>=1;i--) b[i]=baoli%10,baoli/=10;
for(int i=1;i<=n;i++){
if(i>1) cout<<" ";
cout<<b[i];
}
}
cout<<'\n';
continue;
}
//lst_i 表示上一个不确定的位置，特别的c_i=0则 lst_i=i
for(int i=1;i<=n;i++){
if(c[i]==0) lst[i]=i;
else lst[i]=lst[i-1];
maxn[i]=C; //maxn_i 记录的是若当前位不确定，那么能填的最大数是多少
}
bool flag=true;
for(int i=1;i<=q;i++){
int a=s[i].a,h=s[i].h;
if(maxc[h-1]==0) maxc[h-1]=1; //若前面所有的数都不确定，那么贪心的令其为最小
if((c[h]!=0&&c[h]<=maxc[h-1])||maxc[h-1]+1>C){
//如果这些位置都确定并且违背了限制，或者为了满足限制就要填大于C的数，那么都无解
flag=false;
break;
}
//因为调整的过程中会将一些不确定的位置确定下来，所以要随时更新lst数组
while(lst[lst[h-1]]!=lst[h-1]) lst[h-1]=lst[lst[h-1]];
maxn[lst[h-1]]=min(maxn[lst[h-1]],maxc[h-1]); //为了满足限制，我们调整maxc，将一个不确定的位置填上我们需要的数字
for(int j=h;j<=n;j++){ //更新 maxc
if(maxc[j]>maxc[h-1]) break;
maxc[j]=maxc[h-1]+1;
}
if(maxc[a]>maxc[h-1]){ //如果已确定的数已经违反了限制，那么我们无法改变，无解
flag=false;
break;
}
if(maxc[a]<maxc[h-1]){
while(lst[lst[a]]!=lst[a]) lst[a]=lst[lst[a]]; //更新不确定的位置
if(!lst[a]||maxc[h-1]>(maxn[lst[a]]/*表示这个位置能填的最大值*/)){
//如果没有不确定的位置给我们填，或者我们需要填的数大于这个位置能填的最大值，就无解
flag=false;
break;
}
for(int j=lst[a];j<h;j++){
//根据限制填数，同时更新后面的 maxc
maxc[j]=max(maxc[h-1],maxc[j]);
if(maxn[j]<maxc[h-1]){ //同样的，如果能填的数的范围小于需要填的数，那么无解
flag=false;
break;
}
}
if(!flag) break;
//填了一个数，不确定的位置少一个，更新lst
lst[a]=lst[lst[a]-1];
}
}
if(!flag) cout<<"-1";
// 根据 maxc 倒推出字典序最小的 c 并输出
else{
for(int i=1;i<=n;i++){
if(i!=1) cout<<' ';
if(c[i]){
cout<<c[i];
continue;
}
if(maxc[i]>maxc[i-1]) cout<<maxc[i];
else cout<<1;
}
}
cout<<'\n';
}
return 0;
}
标签：10,限制,int,题解,USACO,2024,lst,100010,maxc From： https://www.cnblogs.com/S-A-I/p/17995383