「杂题集」- 2019年9月19日

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

继续阅读「杂题集」- 2019年9月19日

[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

A – 家族

这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。

考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。

继续阅读[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

[Fortuna OJ]Mar 4th – Group A 解题报告

A – 漆黑列车载运数个谎言

这道题应该是并查集域的裸题,不讲。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    while (m--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0)
            unite(x, y), unite(x + n, y + n);
        else if (opt == 1 || opt == 2)
            unite(x, y + n), unite(x + n, y);
        else if (find(x) == find(y) || find(x + n) == find(y + n))
            puts("1");
        else
            puts("0");
    }
    return 0;
}

继续阅读[Fortuna OJ]Mar 4th – Group A 解题报告

POJ1417:True Liars 题解

这道题好毒瘤啊…本来想着可以直接写个并查集 A 掉没想到还需要背包 DP。我们一段一段来讲。

// POJ1417.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 400, maxm = 2010;
int n, p1, p2, fa[maxm], tot, cnt[maxm], cur;
int dp[1205][maxn];
vector<int> T;
bool pre[1205][maxn];
struct team
{
    int sam, diff;
} nodes[maxm];
bool init()
{
    scanf("%d%d%d", &n, &p1, &p2);
    if (n == 0 && p1 == 0 && p2 == 0)
        return false;
    tot = p1 + p2;
    for (int i = 0; i < maxm; i++)
        fa[i] = i;
    return true;
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

首先是声明数组和变量们,并且做初始化。之后我们写一个 solve 函数:

while (n--)
{
    int u, v;
    char opt[10];
    scanf("%d%d%s", &u, &v, opt);
    if (opt[0] == 'n')
        fa[find(u)] = find(v + tot), fa[find(u + tot)] = find(v);
    else
        fa[find(u)] = find(v), fa[find(u + tot)] = find(v + tot);
}

我们可以推理得出,如果操作为\(yes\),那么他们就是同类,亦而反之。在这里,就可能会形成一个并查集森林:有多余\(2\)个的类型,所以我们需要用背包 DP 来计算能不能凑出唯一的天使和恶魔配比。在此之前,我们先要找出这些森林中的树:

cur = 0;
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= tot; i++)
{
    int root = find(i);
    if (cnt[root] == 0 && root <= tot)
        nodes[++cur] = (team){root, find(i + tot)};
    cnt[root]++;
}

找到没有被访问过的树,顺便统计子树大小。之后我们进行背包 DP。

memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= cur; i++)
    for (int j = 0; j <= p1; j++)
        if (dp[i - 1][j])
        {
            if (j + cnt[nodes[i].sam] <= p1)
            {
                dp[i][j + cnt[nodes[i].sam]] += dp[i - 1][j];
                pre[i][j + cnt[nodes[i].sam]] = true;
            }
            if (j + cnt[nodes[i].diff] <= p1)
            {
                dp[i][j + cnt[nodes[i].diff]] += dp[i - 1][j];
                pre[i][j + cnt[nodes[i].diff]] = false;
            }
        }

叠加可能的次数,最终如果答案为\(1\),意味着有唯一解。我们需要筛除多解和无解的情况,然后统计答案。

if (dp[cur][p1] != 1)
{
    puts("no");
    return;
}
int C = p1;
for (int i = cur; i >= 1; i--)
    if (pre[i][C])
        C -= cnt[nodes[i].sam], T.push_back(nodes[i].sam);
    else
        C -= cnt[nodes[i].diff], T.push_back(nodes[i].diff);
for (int i = 1; i <= tot; i++)
{
    int rt = find(i);
    if (find(T.begin(), T.end(), rt) != T.end())
        printf("%d\n", i);
}
T.clear();
printf("end\n");

最后完整代码附上:

// POJ1417.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 400, maxm = 2010;
int n, p1, p2, fa[maxm], tot, cnt[maxm], cur;
int dp[1205][maxn];
vector<int> T;
bool pre[1205][maxn];
struct team
{
    int sam, diff;
} nodes[maxm];
bool init()
{
    scanf("%d%d%d", &n, &p1, &p2);
    if (n == 0 && p1 == 0 && p2 == 0)
        return false;
    tot = p1 + p2;
    for (int i = 0; i < maxm; i++)
        fa[i] = i;
    return true;
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
// 1 divine, 2 devil
void solve()
{
    while (n--)
    {
        int u, v;
        char opt[10];
        scanf("%d%d%s", &u, &v, opt);
        if (opt[0] == 'n')
            fa[find(u)] = find(v + tot), fa[find(u + tot)] = find(v);
        else
            fa[find(u)] = find(v), fa[find(u + tot)] = find(v + tot);
    }
    cur = 0;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= tot; i++)
    {
        int root = find(i);
        if (cnt[root] == 0 && root <= tot)
            nodes[++cur] = (team){root, find(i + tot)};
        cnt[root]++;
    }
    memset(dp, 0, sizeof(dp));
    //memset(pre, 0, sizeof(pre));
    dp[0][0] = 1;
    for (int i = 1; i <= cur; i++)
        for (int j = 0; j <= p1; j++)
            if (dp[i - 1][j])
            {
                if (j + cnt[nodes[i].sam] <= p1)
                {
                    dp[i][j + cnt[nodes[i].sam]] += dp[i - 1][j];
                    pre[i][j + cnt[nodes[i].sam]] = true;
                }
                if (j + cnt[nodes[i].diff] <= p1)
                {
                    dp[i][j + cnt[nodes[i].diff]] += dp[i - 1][j];
                    pre[i][j + cnt[nodes[i].diff]] = false;
                }
            }
    if (dp[cur][p1] != 1)
    {
        puts("no");
        return;
    }
    int C = p1;
    for (int i = cur; i >= 1; i--)
        if (pre[i][C])
            C -= cnt[nodes[i].sam], T.push_back(nodes[i].sam);
        else
            C -= cnt[nodes[i].diff], T.push_back(nodes[i].diff);
    for (int i = 1; i <= tot; i++)
    {
        int rt = find(i);
        if (find(T.begin(), T.end(), rt) != T.end())
            printf("%d\n", i);
    }
    T.clear();
    printf("end\n");
}
int main()
{
    while (init())
        solve();
    return 0;
}

 

P2898:[USACO08JAN]haybale猜测题解

思路

这又是一道抄题解的题目。我们先来简要分析一下触发矛盾的几种情况:

  • 给定两个区间\(A, B\),有\(A \cap B \neq \emptyset \),而\(A_{min} \neq B_{min}\),这种情况是矛盾的。
  • 给定两个区间\(A, B\),有\(A \subset B\),而\(A_{min} \neq B_{min}\),这种情况也是矛盾的。

之后我们就可以用并查集来进行集合操作。而数据范围非常的大,而答案只需要一个最早解,那么我们就可以尝试二分答案。

继续阅读P2898:[USACO08JAN]haybale猜测题解