hubeikemi的个人博客
0%

CF2040C

发表于 分类于
本文字数： 4.5k 阅读时长 ≈ 4 分钟

简单二进制状压

Problem - C - Codeforces

打表：

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
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
    
const int N=1e9+5;
    
void solve(){
    
    ll n; cin >> n;
    vector<int> a(n + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = i;
        ans += i * (n - i + 1);
    }
    int cnt = 0;
    do {
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            int mn = 0x3f3f3f3f;
            for (int j = i; j <= n; ++j) {
                mn = min(mn, a[j]);
                sum += mn;
            }
        }

        if (sum == ans){
            ++cnt;
            cout << "\033[0m" << cnt << ": ";
            for (int i = 1; i <= n; ++i) {
                if (a[i] == 3)  cout << "\033[32m" << a[i] << " ";
                else cout << "\033[31m" << a[i] << " ";
            }
            cout << endl;
        }
    }while(next_permutation(a.begin() + 1, a.end()));
    
}
    
int main(){
    
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    while(_--)
    solve();
    system("pause");
    return 0;
    
}

输入5为例:

1763829785661

1763829837661

不难发现：一半1，一半1里有一半2，一半2里又有一半3…

超过半数往后站，不过半往前站

因此有解:

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
#include<bits/stdc++.h>
using ll = long long;
using namespace std;

void solve(){
    
    ll n, k; cin >> n >> k;
    ll m = n;
    vector<int> a(n + 1);

    ll sum = 1LL;
    for (int i = 1; i < n; ++i) {
        sum <<= 1LL;
        if (sum >= 1e12) {
            sum = 1e12;
            break;
        }
    }

    if (k > sum) {
        cout << -1 << endl;
        return;
    }

    int l = 1, r = n;
    ll ls = 0LL, rs = sum;
    for (int i = 1; i <= n; ++i) {
        ll mid = ((ls + rs) >> 1LL);
        if (k <= mid) {	
            a[l] = i;	//不过半往前站
            ++l;
            rs = mid;	//集中前半段
        }
        else {
            a[r] = i;	//超过半数往后站
            --r;
            ls = mid;	//集中后半段
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
    
}

int main(){
    
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)
    solve();
    return 0;
    
}

但是，这么解是错的，让我们听听AI怎么说。

对于

1
2
3
4
5
6
7
输入：
1 
60 2 

我输出的是： 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 40 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 39 

正确答案是： 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 60 59

为什么错了？

你把 sum = 2^(n-1) 人为截断成 1e12。
当 n=60 时真实的 $2^{n-1}=2^{59}≈5.76e17$，而你把它设成 1e12。以后你用 [ls,rs) 以二分区间把 k 映射成“左右选择”的逻辑 依赖 rs-ls 恰好是 2^(remaining) 的幂次。截断后这个不再成立，映射就被彻底破坏了 —— 因此决策在第 ~39 次才从“放左”变成“放右”，产生你看到的 1..38 然后一大段乱序的结果。

什么意思，原本sum很长很长，可以截很多个二分，但因为原本sum太长太长了，long long存不下，我把它截成 1e12（k的最大值），导致截的二分数变少了，mid很快扰乱了如下代码的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 1; i <= n; ++i) {
    ll mid = ((ls + rs) >> 1LL);
    if (k <= mid) {	
        a[l] = i;	//不过半往前站
        ++l;
        rs = mid;	//集中前半段
    }
    else {
        a[r] = i;	//超过半数往后站
        --r;
        ls = mid;	//集中后半段
    }
}

不妨想一下：

二进制状压

我们这样打表：

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
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
    
const int N=1e9+5;
    
void solve(){
    
    ll n; cin >> n;
    vector<int> a(n + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = i;
        ans += i * (n - i + 1);
    }
    int cnt = 0;
    do {
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            int mn = 0x3f3f3f3f;
            for (int j = i; j <= n; ++j) {
                mn = min(mn, a[j]);
                sum += mn;
            }
        }

        if (sum == ans){
            ++cnt;
            cout << "\033[0m" << bitset<4>(cnt - 1)<< ": "; //以5为例(0 ~ 15) 16种情况
            for (int i = 1; i <= n; ++i) {
                if (a[i] == 1)  cout << "\033[32m" << a[i] << " ";
                else cout << "\033[31m" << a[i] << " ";
            }
            cout << endl;
        }
    }while(next_permutation(a.begin() + 1, a.end()));
    
}
    
int main(){
    
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    while(_--)
    solve();
    system("pause");
    return 0;
    
}

img

我们可以想到，我们之前的步骤中，每一次二分相当于消去最高位，观察下一位，如果该位是0，往前站，该位是1，往后站，最后剩下的一位，填最后一位（n）。

假设n = 5, 当前位置为k = 8，由于从0计数，所以减1，得7，二进制为0111，于是，我们有：

1
2
3
4
5
6
0111: 1
 111: 1       2 
  11: 1     3 2
   1: 1   4 3 2

最后：1 5 4 3 2

完美！

我们可以反过来，从n到1填，毕竟从低位到高位遍历数位要容易很多，不断除2就行。填数就用双端队列一个个往里挤，很方便。

代码如下：

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
#include<bits/stdc++.h>
using ll = long long;
using namespace std;

void solve(){
    
    ll n, k; cin >> n >> k;
    ll m = n;
    vector<int> a(n + 1);

    ll sum = 1LL;
    for (int i = 1; i < n; ++i) {
        sum <<= 1LL;
        if (sum >= 1e12) {
            sum = 1e12;
            break;
        }
    }

    if (k > sum) {
        cout << -1 << endl;
        return;
    }
    
    ll b = k - 1;	//从0计数，减1
    deque<ll> dq;
    dq.push_back(n);
    for (ll x = n - 1; x >= 1; --x) {
        if (b & 1LL) dq.push_back(x);
        else dq.push_front(x); 
        b >>= 1;
    }

    while(!dq.empty()) {
        cout << dq.front() << " ";
        dq.pop_front();
    }
    cout << endl;
    
}
    
int main(){
    
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)
    solve();
    return 0;
    
}

AC了！

那你可能会想：前面说那么多，不还是观察出来的吗？

是的。