题解 P13509 [OOI 2024] Almost Certainly

cjh20090318 · 2025-10-05 11:00:16 · 题解

提供一个考场思路。

分析

子任务 1：N \le 100

两个多重集完全等价时，需要的操作次数即为 \sum\limits_{i=1}^n a_i - b_i。

几乎等价的条件允许了 a 中有一个元素不进行操作，即存在一对 a_i,b_j 不同，去掉后剩下的序列有解，即一一对应的 a \ge b。答案为满足条件的 a_i - b_j 最大值。

对于每个前缀序列排序后询问，枚举 a_i,b_j，O(n) 判断剩下的是否可行，总体时间复杂度 O(n^4)。

子任务 2：N \le 500

同样的对于每个前缀序列排序后询问。

同样的对于每个前缀序列排序后询问。

为了让 a_i - b_j 尽可能大，i-j 也要尽可能的大。

所以找到每一个满足 a_x \ge b_{x+1} 的极长区间，所有极长区间答案的最大值一定是最大的，O(n) 扫一遍即可。

总体时间复杂度 O(n^2 \log n) 或 O(n^2)，取决于排序方式。

子任务 4：a_i < b_{i+1}

根据限制得到 b_i \le a_i < b_{i+1} \le a_{i+1}，保证前缀序列有序，无需再排序。

极长区间即为 [1,i)，最大值为 a_i - b_1，时间复杂度 O(n)。

子任务 5：a_i \le a_{i+1}, b_i \le b_{i+1}

保证前缀序列有序，无需再排序。

但该子任务并没有保证极长区间。

只需要维护和当前 i 相连的极长区间端点 b 值，新添加的 a 和端点相减更新答案，时间复杂度 O(n)。

综合以上可以获得 80 分。

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long LL;
int n;
int a[MAXN],b[MAXN];
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    LL ans=0;//完全等价的代价。
    int ret=0,la,lb=1;//分别表示
    for(int i=1;i<=n;i++){
        ans+=a[i]-b[i];
        if(i>1&&a[i]>=a[i-1]&&b[i]>=b[i-1]){//已经有序则无需排序。
            a[i-1]<b[i]&&(lb=max(lb,i));//不满足条件，更新极长区间起点。
            ret=max(ret,a[i]-b[lb]);
        }
        else{
            inplace_merge(a+1,a+i,a+i+1),inplace_merge(b+1,b+i,b+i+1);//懒得手写排序，所以直接归并。
            la=lb=ret=0;
            for(int j=i;j>0;--j)
                (j>=i||a[j]<b[j+1])&&(la=a[j]),ret=max(ret,la-b[j]),a[j-1]<b[j]&&(lb=max(lb,j));
        }
        printf("%lld ",ans-ret);
    }
    putchar('\n');
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve(); 
    return 0;
}

子任务 6：无特殊限制。

考试时败在了最后 20 分。

考虑将每个极长区间表示为 [b,a] 的区间。

如果两个区间有交集，则可以合并为同一个区间。

证明是容易的，如果区间 [b_1,a_1] 和 [b_2,a_2] 有交必然有 a_1 \ge b_2 或 a_2 \ge b_1，即边界满足条件可以进行合并。

如果区间被已有区间完全包含，就不必合并，也不必加入，因为不会产生更大的答案。

所求为所有区间的长度最大值。

于是直接用 std::set 维护区间，时间复杂度 O(n \log n)。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int n;
int a[MAXN],b[MAXN];
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    LL ans=0;
    int ret=0;
    set<PII> S;
    for(int i=1;i<=n;i++){
        ans+=a[i]-b[i];
        PII c(b[i],a[i]);
        bool fl=1;
        while(!S.empty()){
            auto it=S.lower_bound(c);
            if(it!=S.end()&&it->first==c.first&&it->second>=c.second){fl=0;break;}//区间被完全包含，合并后不产生贡献，退出。
            if(it!=S.begin()&&prev(it)->second>=c.second&&prev(it)->first<=c.first){fl=0;break;}
            if(it!=S.end()&&it->first<=c.second)
                c.second=max(c.second,it->second),S.erase(it);//向右侧合并。
            else if(it!=S.begin()&&(--it)->second>=c.first)
                c.first=min(c.first,it->first),S.erase(it);//向左侧合并。
            else break;//没有区间有交集了，退出。
        }
        if(fl) S.insert(c),ret=max(ret,c.second-c.first);
        printf("%lld ",ans-ret);
    }
    putchar('\n');
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve(); 
    return 0;
}