P9752 题解

rainygame · 2023-11-04 14:54:50 · 题解

这个小丑 CSP-S 160 \rightarrow 80。

可以发现这道题就是求 n 个密码锁通过两种状态转移到的状态的集合的并集。而且我们可以发现状态数量只有 10^5 种。

考虑十进制状压，状压后我们用一个 bitset 来表示答案的集合。一开始答案集合是全集，对于每种状态，求助它转移出来的 81 种状态，并求出答案和它的并集，将其设为新的答案。

最后使用 bitset.count() 即可求出答案数量。

令 k=10^5，代码时间复杂度为 O(\frac{kn}{\omega})。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define get_hash() (a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4])

int n;
int a[5];
bitset<100000> ans;

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

    cin >> n;
    ans.set();
    while (n--){
        for (int i(0); i<5; ++i) cin >> a[i];
        bitset<100000> tmp;
        for (int i(0); i<5; ++i){
            for (int j(1); j<=9; ++j){
                int t(a[i]);
                a[i] = (a[i] + j) % 10;
                tmp.set(get_hash());
                a[i] = t;
            }
        }

        for (int i(0); i<4; ++i){
            for (int j(1); j<=9; ++j){
                int t1(a[i]), t2(a[i+1]);
                a[i] = (a[i] + j) % 10;
                a[i+1] = (a[i+1] + j) % 10;
                tmp.set(get_hash());
                a[i] = t1;
                a[i+1] = t2;
            }
        }
        ans &= tmp;
    }
    cout << ans.count();

    return 0;
}