「Bzoj 5299」「CQOI2018」解锁屏幕 (状压DP)

发表于 | 分类于 | | + s

BZOJ 5299
题意：见上。

可以用连接个数来划分阶段。
那么我们设$dp(S,i)$为已经连过的点的集合，最后一次连在$i$点的方案数。
然后转移即可。复杂度$O(2^n n^2)$，复杂度跑不满可以过
然后我们还要满足两个点之间的连线不能「跨过」另一个点，那么我们预处理出来两个点之间点的集合，转移时判断即可。

这个集合可以$O(n^3)$来做，就是枚举两个点$i,j$求他们的之间点集合$S_{i,j}$
那么我们再枚举一个$k$点，判下斜率相等即可确定

还可以$O(nx)$做。先求出$\Delta x = b_x - a_x, \Delta y = b_y - a_y$，我们发现整点数只会在$(a_x + \frac{\Delta x}{\gcd (\Delta x, \Delta y)}, a_y + \frac{\Delta y}{\gcd (\Delta x, \Delta y)})$
，直接找坐标是否存在给定点即可，这里用了map，其实可以用桶。可以发现这个步数不超过$\max(x,y)$

最后统计答案统计$S$二进制下$1$个数大于等于$4$的

知识点：
1、状压的空间预留不要开太大，特别是尾数

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MO = 100000007, MAXN = 20 + 1;

    int gcd(int a, int b) {return b != 0 ? gcd(b, a % b) : a;}

    int n, dp[(1 << 20) + 2][MAXN], s[MAXN][MAXN];
    struct pos {
        int x, y;
        bool operator < (const pos &rhs) const {
            return x == rhs.x ? y < rhs.y : x < rhs.x;
        }
    } p[MAXN];
    map<pos, int > ma;

    void clean() {
        ms(dp, 0), ms(s, 0);
    }
    int solve() {

        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i].x, &p[i].y), ma[p[i]] = i;
        for (int u = 1; u <= n; ++u) {
            for (int v = 1; v <= n; ++v) if (u != v) {
                int dx = p[v].x - p[u].x;
                int dy = p[v].y - p[u].y;
                int g = gcd(dx, dy); g = (g < 0 ? -g : g);
                if (g != 0) dx /= g, dy /= g;
                int nowx = p[u].x, nowy = p[u].y;
                while (!(nowx == p[v].x && nowy == p[v].y)) {
                    if (ma[(pos){nowx, nowy}]) s[u][v] |= (1 << (ma[(pos){nowx, nowy}] - 1));
                    nowx += dx, nowy += dy;
                }
                s[u][v] |= (1 << (u - 1));
                s[u][v] |= (1 << (v - 1));
            }
        }

        for (int i = 1; i <= n; ++i) dp[(1 << (i - 1))][i] = 1;

        for (int S = 0; S < (1 << n); ++S) {
            for (int i = 1; i <= n; ++i) if (S & (1 << (i - 1))) {
                for (int v = 1; v <= n; ++v) if (i != v && (S & (1 << (v - 1)))) {
                    if ((S & s[i][v]) == s[i][v])
                        dp[S][i] = (dp[S ^ (1 << (i - 1))][v] + dp[S][i]) % MO;
                }
            }
        }

        int ans = 0;

        for (int S = 0; S < (1 << n); ++S) {
            int tmp = S, cnt = 0;
            do {++cnt, tmp &= (tmp - 1);} while (tmp);
            if (cnt < 4) continue ;
            for (int i = 1; i <= n; ++i) ans = (ans + dp[S][i]) % MO;
        }

        cout << ans;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------