ACGO巅峰赛#28 全题解

亚洲卷王 AK IOI

2025-12-08 19:51:04

发布于：北京

87阅读

0回复

0点赞

ACGO巅峰赛#28 全题解

T1

容易发现，一次合并相当于被动方无变化，增加了主动方的一些代价。

所以我们枚举最终结果是哪一堆 $i$ ，分别考虑 $i$ 左边和 $i$ 右边的最小代价。

显然，如果 $j=1$ ，那么只能左并右；如果 $j=n$ ，那么只能右并左；否则取 $\min$ ；

搞一个前缀和、后缀和就好。

时间复杂度： $O(n)$ 。

空间复杂度： $O(n)$ 。

T2

看到所求内容想到二分。考虑如何写 $\operatorname{check}$ 函数。

我们可以跑最短路，路径长度为使用“硬跨”的次数。

时间复杂度 $O(nm \log nm \log H)$ 。可能卡常一下可以过，我没试。

考虑优化，容易发现每次松弛增加的路径长度为 $0/1$ ，使用 01bfs 即可。

时间复杂度： $O(nm \log H)$ 。

空间复杂度： $O(nm)$ 。

T3

观察到在任意子树中，其根节点在该子树的层序遍历中一定是最早出现的。

假设我们拿到了一个中序遍历区间 $[l,r]$ ，我们需要寻找根节点，然后递归左右子树。

而根据观察，我们需要在区间 $[l,r]$ 内，找到层序位置最小的节点。线段树查询。

时间复杂度： $O(n \log n)$ 。

空间复杂度： $O(n)$ 。

T4

注意到数据范围很小，搞个状压跑博弈论就行。

时间复杂度： $O(nm+k2^k)$ ，其中 $k$ 是可用格子数量。

空间复杂度： $O(nm+k2^k)$ ，其中 $k$ 是可用格子数量。

T5

设 $dp_{i,j}$ 表示 $[i,j]$ 范围内的答案，有一种转移方法是 $dp_{i,j}=\min_{i \leq k<j}(dp_{i,k}+dp_{k+1,j})$ 。

如果 $s_i=s_j$ ，那么我们可以先按照 $dp_{i+1,j-1}$ 操作，然后等最后一步的时候带上 $s_i,s_j$ 一起删除，则 $dp_{i,j}=dp_{i+1,j-1}$ 。

时间复杂度 $O(n^3)$ 。据说可以四边形不等式优化为 $O(n^2)$ ，但是 ACGO 神机过了。

时间复杂度： $O(n^3)$ 或 $O(n^2)$ 。

空间复杂度： $O(n^2)$ 。

T6

设 $dp_{i,j}$ 表示前 $j$ 个元素分成 $i$ 段最小代价， $\operatorname{cost}(i,j)$ 表示 $[i,j]$ 区间的代价，得到 $O(n^3k)$ 转移方程：

$dp_{i,j}=\min_{i-1 \leq k \leq j-1} dp_{i-1,k}+\operatorname{cost}(k+1,j)$

考虑加速 $\operatorname{cost}(k+1,j)$ 的计算。如果新增一个数 $x$ ，那么代价会增加 $\binom{2}{cnt_x+1}-\binom{2}{cnt_x}=cnt_x$ 。同理，删除一个数 $x$ ，代价会减少 $cnt_x-1$ 。

此时我们倒序枚举 $k$ ，同时维护 $\operatorname{cost}(k+1,j)$ 即可做到 $O(n^2k)$ 。

容易发现，对于固定的 $i$ ，最优决策点随着 $i$ 的增加而单调不减，可以使用分治优化 DP 过程。

时间复杂度： $O(kn \log n)$ 。

空间复杂度： $O(nk)$ 。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
ll n,k,l,r,t;
ll a[MAXN],cnt[MAXN],dp[22][MAXN];
inline void moadd(const ll &x){
    t+=cnt[x];
    cnt[x]++;
    return;
}
inline void model(const ll &x){
    cnt[x]--;
    t-=cnt[x];
    return;
}
inline void move(const ll &lll,const ll &rr){
    while(r<rr) moadd(a[++r]);
    while(r>rr) model(a[r--]);
    while(l<lll) model(a[l++]);
    while(l>lll) moadd(a[--l]);
    return;
}
inline void part(const ll &i,const ll &l,const ll &r,const ll &optl,const ll &optr){
    if(l>r) return;
    ll p=optl,mid=l+r>>1,tl=l,tr=r,tt=t;
    for(ll k=optl;k<mid&&k<=optr;k++){
        move(k+1,mid);
        if(dp[i-1][k]+t<dp[i][mid]){
            dp[i][mid]=dp[i-1][k]+t;
            p=k;
        }
    }
    part(i,l,mid-1,optl,p);
    part(i,mid+1,r,p,optr);
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dp,0x3f,sizeof(dp));
    cin>>n>>k;
    for(ll i=1;i<=n;i++) cin>>a[i];
    dp[0][0]=0;
    l=1;
    for(ll i=1;i<=n;i++){
        moadd(a[i]);
        dp[1][i]=t;
    }
    for(ll i=2;i<=k;i++){
        l=1,r=0,t=0;
        memset(cnt,0,sizeof(cnt));
        part(i,i,n,i-1,n-1);
    }
    cout<<dp[k][n];
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

Gragher
占领无人区

2天前来自浙江
0

ACGO巅峰赛#28 全题解

T1

T2

T3

T4

T5

T6

全部评论 1

热门讨论