Educational DP Contest : O – Matching 题解

解法

这道题看数据范围可以联想到状压 \(DP\)。考虑设计一个状态:\(dp[S]\)代表女人的集合,其中集合长度\(|S|\)提供了另外一个信息,换句话说,\(dp[S]\)代表了考虑前\(|S|\)个男人对应的女人集合的转移个数。不难推出下面的式子:

\[ dp[S] = \sum_{(i, |S|) \in compatible} dp[S’], S’ \cup i = S \]

继续阅读Educational DP Contest : O – Matching 题解

[Fortuna OJ]Feb 15th – Group B 解题报告

A – 魏传之长坂逆袭

一道水的不得了的题目,两边线性的深搜合并距离即可。

// A.cpp
// Complexity: O(n)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 500200;
int head[MAX_N], current, n, tmpx, tmpy, paths[MAX_N];
ll tmpz, goal = 0, answer;
struct edge
{
    int to, nxt;
    ll weight;
} edges[MAX_N << 1];
void addpath(int src, int dst, ll weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
void dfs_1(int u, int fa, ll dis)
{
    ll ans = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs_1(edges[i].to, u, dis + edges[i].weight), ans = max(paths[edges[i].to] + edges[i].weight, ans);
    goal = max(goal, dis), paths[u] = ans;
}
void tune(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            tune(edges[i].to, u), answer += paths[u] - paths[edges[i].to] - edges[i].weight;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d%d%lld", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
    dfs_1(1, 0, 0), tune(1, 0);
    printf("%lld", answer);
    return 0;
}

B – 蜀传之单刀赴会

这道题有点失误,写了一个暴力忘记判断不能超过\(t\)这个限制然后就送掉了 30 分,暴力状压 DFS 可拿到 60 分。正解其实就是最短路缩图 + 状压 DP,方程非常好想,设\(f[stat][i]\)为要经过\(stat\)集合中的点且最后一次经过了点\(i\)的最短路径,显然可以得出:

\[ f[stat \cup j][j] = min\{ f[stat][i] + map[i][j] \}, i \in stat, j \not\in stat \]

// B.cpp
// Complexity: O(n log m + 2^(k+1)*k^2) = O(2^(k+1)*k^2)
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, int>
using namespace std;
const int MAX_N = 10010, MAX_M = 50010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, t, head[MAX_N], current, tmpx, tmpy, tmpz, mp[20];
ll dist[20][MAX_N], neomap[20][20], f[(1 << 17)][20];
bool vis[MAX_N];
struct edge
{
    int to, nxt, weight;
} edges[MAX_M << 1];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].weight = weight;
    edges[current].nxt = head[src], head[src] = current++;
}
int getOnBit(int num)
{
    int ans = 0;
    while (num)
        if (num & 1)
            ans++, num >>= 1;
        else
            num >>= 1;
    return ans;
}
void djisktra(int u)
{
    memset(vis, false, sizeof(vis));
    priority_queue<pr> q;
    int org = mp[u];
    q.push(make_pair(0, org)), dist[u][org] = 0;
    while (!q.empty())
    {
        int curt = q.top().second;
        q.pop();
        if (vis[curt])
            continue;
        vis[curt] = true;
        for (int i = head[curt]; i != -1; i = edges[i].nxt)
        {
            int to = edges[i].to;
            if (dist[u][to] > dist[u][curt] + edges[i].weight)
                dist[u][to] = dist[u][curt] + edges[i].weight, q.push(make_pair(-dist[u][to], to));
        }
    }
}
int main()
{
    memset(dist, 0x3f, sizeof(dist)), memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &k, &t);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
    for (int i = 0; i < k; i++)
        scanf("%d", &tmpx), mp[i] = tmpx;
    mp[k] = n, mp[k + 1] = 1;
    for (int i = 0; i <= k + 1; i++)
        djisktra(i);
    for (int i = 0; i <= k + 1; i++)
        for (int j = 0; j <= k + 1; j++)
            neomap[i][j] = dist[i][mp[j]];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= k; j++)
            f[(1 << i)][j] = neomap[k + 1][i];
    for (int stat = 1; stat < (1 << (k + 1)); stat++)
        for (int i = 0; i <= k; i++)
            for (int j = 0; j <= k; j++)
                if ((((stat >> i) & 1) == 1) && (((stat >> j) & 1) == 0))
                    f[stat | (1 << j)][j] = min(f[stat | (1 << j)][j], f[stat][i] + neomap[i][j]);
    ll ans1 = 0, ans2 = INF;
    for (int stat = 1; stat < (1 << (k + 1)); stat++)
    {
        if (getOnBit(stat) < ans1 || ((stat >> k) & 1) == 0)
            continue;
        ll tmp = INF;
        for (int i = 0; i <= k; i++)
            if (((stat >> i) & 1) == 1)
                tmp = min(tmp, f[stat][i] + neomap[i][k + 1]);
        if (tmp != INF && tmp <= t)
            ans2 = (ans1 < getOnBit(stat)) ? tmp : min(ans2, tmp), ans1 = getOnBit(stat);
    }
    printf("%lld %lld", ans1 - 1, ans2);
    return 0;
}

最后一直卡在 80 分,发现忘了判断\(t\)的限制,凉飞了。

C – 吴传之火烧连营

心态崩了,这道题本身 trie 树空间开对了,最后标记的空间忘了开大就凉了,亏我还特意计算了要有多少各节点。

这道题就是一道傻* Trie 树摸板题,贪心沿着树走即可。

// C.cpp
// Complexity: O(32n + 32m)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 100;
int trie[MAX_N * 64][2], mark[MAX_N * 64], tot = 1, tmp;
void insert(int num, int mk)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        if (trie[p][bit] == 0)
            trie[p][bit] = ++tot;
        p = trie[p][bit];
    }
    mark[p] = mk;
}
int query(int num)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1, desire = bit ^ 1;
        if (trie[p][desire] != 0)
            p = trie[p][desire];
        else
            p = trie[p][bit];
    }
    return mark[p];
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &tmp), insert(tmp, i);
    for (int i = 1; i <= m; i++)
        scanf("%d", &tmp), printf("%d\n", query(tmp));
    return 0;
}

P2831:愤怒的小鸟题解

思路

这一题是一道状压 DP(见数据范围)。我们把猪的死活压缩起来作为状态,整个程序从\(0\)开始计数,可以推出以下几个方程:\(f[stat|(1<<i)] = min(f[stat|(1<<i)], f[stat] + 1)\)和\(f[stat|dotset[i][j]] = min(f[stat|dotset[i][j]],f[stat]+1)\),其中dotset为经过点\(i,j\)的抛物线的点集。这个算法是\(O(Tn^2 2^n)\),不够优秀。我们可以使用一个方法把\(n^2\)化为\(n\)。我们可以预先处理出每一个状态下第一个健在猪的编号,然后我们只要转移这一只猪即可,因为未来的猪都会被处理,所以可以直接降维。

代码

// P2831.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define pr pair<double, double>
using namespace std;
const double eps = 1e-8;
int T, n, dotset[19][19], dp[(1 << 19)], lbit[(1 << 19)], m;
pr prs[20];
void solve(double &x, double &y, double a1, double b1, double c1, double a2, double b2, double c2)
{
    y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
    x = (c1 - b1 * y) / a1;
}
int main()
{
    for (int i = 0; i < (1 << 18); i++)
    {
        int bit = 0;
        for (; bit < 18 && (i & (1 << bit)) ; bit++)
            ;
        lbit[i] = bit;
    }
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        memset(dp, 0x3f, sizeof(dp)), memset(dotset, 0, sizeof(dotset));
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &prs[i].first, &prs[i].second);
        // process the curves;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (fabs(prs[i].first - prs[j].first) < eps)
                    continue;
                double a, b;
                solve(a, b, prs[i].first * prs[i].first, prs[i].first, prs[i].second,
                      prs[j].first * prs[j].first, prs[j].first, prs[j].second);
                if (a > -eps)
                    continue;
                for (int k = 0; k < n; k++)
                    if (fabs(a * prs[k].first * prs[k].first + b * prs[k].first - prs[k].second) < eps)
                        dotset[i][j] |= (1 << k);
            }
        dp[0] = 0;
        for (int stat = 0; stat < (1 << n); stat++)
        {
            int esspt = lbit[stat];
            dp[stat | (1 << esspt)] = min(dp[stat | (1 << esspt)], dp[stat] + 1);
            for (int k = 0; k < n; k++)
                dp[stat | dotset[esspt][k]] = min(dp[stat | dotset[esspt][k]], dp[stat] + 1);
        }
        printf("%d\n", dp[(1 << n) - 1]);
    }
    return 0;
}

P2915:[USACO08NOV]奶牛混合起来题解

思路

这道题观察数据范围和题干,可以得知这是一道状压dp的题目。我们先来设计状态:在本题中,可以类比互不侵犯的那一题(互不侵犯题解),设计成当前状态和上一状态相关的元素。可以想出,dp[当前牛的存在情况][当前加入的牛的编号] += dp[上一次加入后的状态][上一次加入的牛的编号];

基本上完成了思考,现在我们先来搞定预处理。我们把只有cowId在队列里的方案数初始化为1。

for (int cowId = 0; cowId < n; cowId++)
        dp[1 << cowId][cowId] = 1;

之后我们就可以进行dp了。详细见代码:

for (int lastState = 0; lastState < (1 << n); lastState++)
    for (int lastCow = 0; lastCow < n; lastCow++)
        if (lastState & (1 << lastCow))
            for (int nowCow = 0; nowCow < n; nowCow++)
                if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
                    nowState = lastState | (1 << nowCow),
                    dp[nowState][nowCow] += dp[lastState][lastCow];

最后方案数叠加,在满员的状态下枚举最后一头牛的id。

ll ans = 0;
for (int i = 0; i < n; i++)
    ans += dp[(1 << n) - 1][i];
cout << ans;

代码

// P2915.cpp
#include <iostream>
#include <cmath>
using namespace std;

#define ll unsigned long long
const int maxn = 16;
ll dp[1 << maxn][maxn];
int n, k, nowState;
int seq[maxn];

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> seq[i];
    for (int cowId = 0; cowId < n; cowId++)
        dp[1 << cowId][cowId] = 1;
    for (int lastState = 0; lastState < (1 << n); lastState++)
        for (int lastCow = 0; lastCow < n; lastCow++)
            if (lastState & (1 << lastCow))
                for (int nowCow = 0; nowCow < n; nowCow++)
                    if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
                        nowState = lastState | (1 << nowCow),
                        dp[nowState][nowCow] += dp[lastState][lastCow];
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans;
    return 0;
}

P1896:[SCOI2005]互不侵犯题解

思路

这是一道状压dp的题目,在此之前我没有学过状压dp,今天上午在dalao lornd的讲解下我理解了状压dp。然而我的能力有限,不能广义上来总结状压dp这个骚操作。状压dp的精髓就在于把多个状态合并为二进制数,然后再进行子集生成。我们这里设计一个状态,这个状态包含了当行棋子的摆放方式。比如,01110代表中间三个位置放置了棋子,为了简便,我们把这个状态可以直接压缩成14这个十进制的数字。这就是状态压缩

强烈建议读者学习完位运算的基本知识之后再来阅读状态压缩的文章,这样理解起来才能事半功倍。

之后我们搞懂了如何压缩状态之后,我们来进行dp。首先我们先要来预处理,预处理的几个目标是:计算单行的状态,计算两行之间的状态,计算每个状态的棋子数量

计算单行和棋子的数量的状态比较简单,在[0,2^32)之间枚举出状态,判定是否有两个1相邻。如果有的话,那么在状态表中设置成false,表示这个状态不能被利用,即不能被纳入计算。具体代码如下:

for (int i = 0; i < MAX; i++)
    {
        // check if there are pairs of 1;
        if (i & (i >> 1))
            continue;
        // checked and set it true;
        sigLine[i] = true;
        // get the number of 1 within the state and record them;
        for (int j = 1; j <= i; j <<= 1)
            if (j & i)
                king[i]++;
    }

其中我们设置MAX = 1 << n,即状态的上限。至于为什么小于MAX而不是小于等于MAX,读者可以思考这两者是否有区别。

之后我们要计算两行之间的状态,我们开一个数组叫\(doubleLine[1<<maxn][1<<maxn]\),其中如果\(doubleLine[x][y]==true\),说明第一行的状态为x且第二行状态为y是可以存在的,可以被纳入计算的。这样的话,不难想出用暴力的方法来进行预处理:

// the first line;
    for (int i = 0; i < MAX; i++)
        if (sigLine[i])
            // the second line;
            for (int j = 0; j < MAX; j++)
                // check if these two are valid.
                if (sigLine[j] && !(i & j) && !(i & (j << 1)) && !(i & (j >> 1)))
                    // set!
                    doubleLine[i][j] = true;

我们预处理工作差不多了,接下来我们来进行动态规划的递推编写了。首先我们先来设计方程,不难想出方程:

\(dp[前n行数][累计w个棋子][本行的状态] = 当前状态数\)

\(dp[i+1][w+king[next]][nextLine] = dp[i][w][currentLine]\)

最后,我们把在n行上、棋子数量为k的所有状态枚举一边,便可以累计得出答案。特别注意的是,这道题目需要long long的数据范围,小心溢出。

代码

// P1896.cpp
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 11;
#define ll long long
int MAX;
int n, k;
bool sigLine[1 << maxn];
bool doubleLine[1 << maxn][1 << maxn];
int king[1 << maxn];
ll dp[maxn][100][1 << maxn];

int main()
{
    cin >> n >> k;
    MAX = 1 << n;
    for (int i = 0; i < MAX; i++)
    {
        // check if there are pairs of 1;
        if (i & (i >> 1))
            continue;
        // checked and set it true;
        sigLine[i] = true;
        // get the number of 1 within the state and record them;
        for (int j = 1; j <= i; j <<= 1)
            if (j & i)
                king[i]++;
    }
    // the first line;
    for (int i = 0; i < MAX; i++)
        if (sigLine[i])
            // the second line;
            for (int j = 0; j < MAX; j++)
                // check if these two are valid.
                if (sigLine[j] && !(i & j) && !(i & (j << 1)) && !(i & (j >> 1)))
                    // set!
                    doubleLine[i][j] = true;
    for (int i = 0; i <= MAX; i++)
        if (sigLine[i])
            dp[1][king[i]][i] = 1;
    for (int i = 1; i < n; i++)
        for (int poss = 0; poss < MAX; poss++)
            if (sigLine[poss])
                for (int nextLine = 0; nextLine < MAX; nextLine++)
                    if (sigLine[nextLine] && doubleLine[poss][nextLine])
                        for (int w = king[poss]; w + king[nextLine] <= k; w++)
                            dp[i + 1][w + king[nextLine]][nextLine] += dp[i][w][poss];
    ll ans = 0;
    for (int i = 0; i < MAX; i++)
        ans += dp[n][k][i];
    cout << ans;
    return 0;
}