2021 ICPC 澳门站G Cyclic Buffer （特殊的状压dp）

G Cyclic Buffer

链接：The 2021 ICPC Asia Macau Regional Contest
介绍一种特殊的状态压缩dp（自己取的名字），不同于一般的二进制状压dp。在递推dp中一般转移都是连续的从 $i\to i+1$，而当一些状态相同在题目中时我们就可以跳跃转移 $i\to j$，这中间的状态都被压缩了。详情可以看题解。

题意

给定长度为 $n$ 的排列 $p_i$，可以访问 $1\sim k$ 位置上的任意元素，并且有两个操作，一个是将数组所有元素右移一格，此时 $p_n\to p_1$，或者左移一格，此时 $p_1\to p_n$. 每个操作都需要花费 $1$ 代价。你想要顺序的从 $1\sim n$ 访问所有元素，问最小的代价。

法一（特殊的状压dp）

法一解法参考知乎大佬cup-pyy的博客第46届ICPC东亚洲区域赛(澳门)题解

贪心的不难考虑到，如果当前我需要访问的 $i$ 的位置 $pos\ge k$，那么我们只有两个选择，移动数组使 $i$ 移动到 $1/k$ 位置上，多移动不一定会是最优的，但不移动一定可以转移到最优的，那么此时就有两个状态 $f[i][0/k]$，代表将 $i$ 元素移动到 $1/k$ 位置上的最小花费。

那么还有一个问题，若是当前元素 $i$，在上一个元素 $i-1$ 移动到 $1/k$ 时已经在 $1\sim k$ 上了怎么转移呢，强行转移到 $1/k$ 位置上吗，但可能不动才是最优的。此时就需要将状态压缩一下了，若是我们知道此时 [大于 $i-1$ 的] [最小的] [不在 $1\sim k$ 位置上的] 元素 $j$ 是什么，我们就可以以将 $f[i-1]\sim f[j-1]$ 压缩为同一个状态，直接从 $f[i-1]\to f[j]$.

这样我们需要预处理出 $p[i][0/1]$: 元素 $i$ 移动到 $1/k$ 位置上时，大于 $i$ 的最小的不在 $1\sim k$ 位置上元素 $j$.

可以用线段树维护元素 $i$ 是否在 $1\sim k$ 位置上，查询就是找 $i+1\sim n$ 区间内第一个为 $0$ 的数，数组每次右移一格也只要两次单点修改即可，具体见代码。

/*
f[n][2]:第i个数，恰好在 1/k 位置上取到的最小花费

考虑当将i移动到1/k后，发现数字i+1已经在1~k的位置上如何处理，直接移动到1/k肯定不会最优，但也无法保存状态。
我们考虑一种另类的状压，既然当前数字已经在1~k上那么将其与 f[i][0/k] 合并压缩， 若是后面有很多数字都有这样的情况也都一并压缩
直到出现一个数字j位置pos > k, 那么此时我们就可以转移 f[i][0/k] -> f[j][0/k]

需要预处理出数字i在1/k位置上时，下一个最小的大于i的不在1~k上的数
*/

#include 
using namespace std;

#define ls p << 1
#define rs p << 1 | 1
#define ll long long

const int N = 1e6 + 10, inf = 1e9;
const ll INF = 1e18;

int n, k, a[N], s[N]; // si: i元素的位置
ll f[N][2]; //f:第i个数，恰好在 1/k 位置上取到的最小花费
int p[N][2]; //p:第i个数在1/k上时下一个不在1~k的数字

struct seg_tree{
    int l, r, sum; // 维护区间 [l, r] 中的数位置在 1~k 上的数量 
}tr[N * 4];

void pushup(int p){
    tr[p].sum = tr[ls].sum + tr[rs].sum;
}
void build(int p, int l, int r){
    tr[p] = {l, r, 0};
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(ls, l, mid); build(rs, mid + 1, r);
}

void update(int p, int loc, int x){
    if(tr[p].l == tr[p].r) return void(tr[p].sum += x);
    int mid = tr[ls].r, ans = 0;
    if(loc <= mid) update(ls, loc, x);
    else update(rs, loc, x);
    pushup(p);
}

int query(int p, int l, int r){  // 查询 [l, r] 区间第一个为0的数的位置
    if(tr[p].sum == tr[p].r - tr[p].l + 1) return inf;
    if(tr[p].l == tr[p].r) return tr[p].l;
    int mid = tr[ls].r, ans = inf;
    if(l <= mid) ans = query(ls, l, r);
    if(r > mid && ans == inf) ans = query(rs, l, r);
    return ans;
}

void init(){
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j < 2; j ++) f[i][j] = INF;
    }

    build(1, 1, n);
    int s[3] = {1, k}, l = 1, r = k; // s[0/1]:此时1/k上的元素是什么
    for(int i = 1; i <= k; i ++) update(1, a[i], 1); // 将1~k位置的元素设置为1，代表已经在1~k区间内了
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j < 2; j ++){
            if(a[s[j]] == n) continue ;
            p[a[s[j]]][j] = query(1, a[s[j]] + 1, n);
        }
        // 那么现在在1/k上的数就是之前n/k-1上的数
        update(1, a[s[1]], -1); // 删除
        for(int j = 0; j < 2; j ++){
            s[j] = (s[j] - 1 + n) % n;
            if(!s[j]) s[j] = n;
        }
        update(1, a[s[0]], 1); // 新增
    }
}

int get_dis(int x, int y){ // 从x -> y 需要右移的距离
    return (y - x + n) % n;
}
int get_min(int x, int y){ // 从x -> y 最小移动距离
    if(y < x) swap(x, y);
    return min(y - x, x + n - y);
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; s[a[i]] = i;
    }

    if(k == n){
        cout << "0\n";
        return ;
    }

    init();
    ll ans = INF, sta = 1;
    while(s[sta] <= k) sta ++;
    f[sta][0] = get_min(s[sta], 1);
    f[sta][1] = get_min(s[sta], k);

    for(int i = sta; i < n; i ++){
        for(int j = 0; j < 2; j ++){
            if(f[i][j] == INF) continue ;
            if(p[i][j] > n) ans = min(ans, f[i][j]);
            else{
                int pos = s[p[i][j]] + get_dis(s[i], j==0?1:k);
                if(pos > n) pos -= n;// 根据数组右移的距离算出元素i此时的具体位置
                int d0 = get_min(pos, 1), d1 = get_min(pos, k);
                f[p[i][j]][0] = min(f[p[i][j]][0], f[i][j] + d0);
                f[p[i][j]][1] = min(f[p[i][j]][1], f[i][j] + d1);
            }
        }
    }
    ans = min({ans, f[n][0], f[n][1]});
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

关于这样的特殊状态压缩的递推dp，还推荐一道题 2023年牛客多校第四场的 链接J Qu’est-ce Que C’est?，在博主本人的博客2023牛客暑假多校第四场（补题向题解：J）中的法二就是用了状态压缩的思想。

法二（直接转移）

博主个人的写法，时空复杂度比法一的更优秀，但是却不太会证明，所以还是推荐法一。

思路

关于状态 $f[i][0/k]$ 和法一状态定义相同，博主写题解决元素 $i$ 本来就在 $1\sim k$ 位置上时曾考虑多加一维状态 $f[i][2]$，代表在原地不动，但是这样却无法记录此时数组转动的情况，并且就算能记录转动的距离，$f[i-1][0/1]$ 可能转移出位置不同的两个 $f[i][2]$，这样状态表示肯定不够于是赛时就没做出。

赛后考虑到，若是元素 $i$ 已经落在 $2\sim k-1$ 上时，用 map 记录此时的状态 $first:$数组右移的距离，$second:$最小花费。遍历map的状态进行转移时，若是 $i+1$ 已经在 $2\sim k-1$ 中就继续保留状态，若是落在 $\ge k$ 的位置上就可以转移到 $f[i][0/1]$，从map中删除这一状态。 凭感觉 这样的状态不会很多，转移不会耗费太多时间。具体的转移方程和解法一相同，这里就不再赘述，具体见代码。

#include 
using namespace std;

#define ll long long

const int N = 1e6 + 10; 
const ll inf = 1e18;

int n, k, p[N], s[N];
ll f[N][2]; // 第i个数，恰好在 1/k 位置上取到的最小花费
map<int, ll> mp; // 存处于 1~k 中间的数的状态 右移的距离 + 花费

int get_dis(int x, int y){
    return (y - x + n) % n;
}

int get_min(int x, int y){
    if(y < x) swap(x, y);
    return min(y - x, x + n - y);
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> p[i]; s[p[i]] = i;
    }

    if(k == n){
        cout << "0\n";
        return ;
    }

    mp.clear();
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j < 2; j ++) f[i][j] = inf;
    }

    ll ans = inf, sta = 1;
    while(s[sta] <= k) sta ++;
    f[sta][0] = get_min(s[sta], 1);
    f[sta][1] = get_min(s[sta], k);

    for(int i = sta + 1; i <= n; i ++){
        vector<int> tmp;
        for(auto it = mp.begin(); it != mp.end(); it ++){
            ll d = it->first, v = it->second;
            int pos = s[i] + d; // 根据数组右移的距离算出元素i此时的具体位置
            if(pos > n) pos -= n;
            if(pos > 1 && pos < k) continue ; // 在
            
            if(pos > k){ // 大于k就需要转移到f[i][0/1]去
                int d0 = get_min(pos, 1), d1 = get_min(pos, k);
                f[i][0] = min(f[i][0], v + d0);
                f[i][1] = min(f[i][1], v + d1);
            }   
            else if(pos == 1) f[i][0] = min(f[i][0], v); // 等于1/k 直接转移
            else if(pos == k) f[i][1] = min(f[i][1], v);
            tmp.push_back(it->first);
            // mp.erase(it);
        }
        for(auto x : tmp) mp.erase(x); // 删除转移出 1~k 的状态

        for(int j = 0; j < 2; j ++){
            if(f[i - 1][j] == inf) continue ;
            int dis = get_dis(s[i - 1], j==0?1:k);
            int pos = s[i] + dis;
            if(pos > n) pos -= n;

            if(pos > 1 && pos < k){
                auto it = mp.find(dis);
                if(it == mp.end()) mp[dis] = f[i - 1][j];
                else it->second = min(it->second, f[i - 1][j]);
            }
            else if(pos == 1) f[i][0] = min(f[i][0], f[i - 1][j]);
            else if(pos == k) f[i][1] = min(f[i][1], f[i - 1][j]);
            else{
                int d0 = get_min(pos, 1), d1 = get_min(pos, k);
                f[i][0] = min(f[i][0], f[i - 1][j] + d0);
                f[i][1] = min(f[i][1], f[i - 1][j] + d1);
            }
        }
    }
    int ans = min(f[n][0], f[n][1]);
    for(auto it : mp) ans = min(ans, it.second);
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98