Kalorona

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;
}

 

2018 末 · 雅礼集训

终于来到了之前一直非常期待的长沙市雅礼中学。我来到雅礼的机房之后并没有非常的兴奋，因为在此之前我就做好了准备——是的，我就是过来陪跑的。看着周边的神仙们都在看那些难懂的 WC2019 模拟题，我突然意识到他们也是高一。想起之前 NOIp 2018 的惨败，我在机房里的情绪平稳的低。我没有非常的丧或者说是颓废，我只是能清晰地认识到我和神仙们的差别。他们从初中开始学，我没有；他们已经写了很多题，我没有；他们学校有江西几乎是最好的教练，我们没有。我看着他们在热闹的讨论一些神仙东西，心想：热闹是他们的，而我什么也没有。我只是一介蒟蒻罢了。

这几天也没有看 WC2019 神仙模拟赛的打算：太难了，根本不懂是什么意思。所以我就跟着我自己的节奏写题，以最大的效能去思考和解题。我不想被旁人所打扰，我觉得自己的节奏对于我的水平反而是有一定好处的。

掌握新算法和巩固旧算法于我而言是永恒的矛盾，自从失利之后我就害怕这个会发生失衡。最终，由于我在对我自己的极度不信任的情况下，选择直接跟《算法竞赛进阶指南》走。太菜的我确实无法做出准确的判断，所以我就做现成的决定。

这两周希望码力 max！

POJ1167:「IOI 1994」The Buses 题解

思路

用结构体\(gap\)来维护每一个时间间隔进行搜索即可，具体看注释吧。

代码

// POJ1167.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 500;
int n, tmp, siz, ans = 17;
struct gap
{
    // gaps: the value of this interval;
    // sttime: the start of the circular time;
    // stats: the number of the points hit following;
    int gaps, sttime, stats;
} ints[maxn];
bool cmp(gap a, gap b)
{
    return a.stats > b.stats;
}
int vis[maxn];
// check(start, interval): check if it is valid;
bool check(int start, int interval)
{
    for (register int i = start; i < 60; i += interval)
        if (!vis[i])
            return false;
    return true;
}
// dfs(st, dep, remain): search the intervals from ints[st:];
inline void dfs(int st, int dep, int remain)
{
    if (remain / ints[st].stats + dep >= ans)
        return;
    if (!remain)
    {
        ans = min(ans, dep);
        return;
    }
    for (register int i = st; i <= siz; i++)
        if (check(ints[i].sttime, ints[i].gaps))
        {
            for (register int tim = ints[i].sttime; tim < 60; tim += ints[i].gaps)
                // set the times of visiting;
                vis[tim]--;
            dfs(i, dep + 1, remain - ints[i].stats);
            for (register int tim = ints[i].sttime; tim < 60; tim += ints[i].gaps)
                // recover the times of visiting;
                vis[tim]++;
        }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &tmp), vis[tmp]++;
    for (int i = 0; i < 30; i++)
        for (int j = i + 1; i + j < 60; j++)
            if (check(i, j))
            {
                ints[++siz].gaps = j, ints[siz].sttime = i;
                // calc the stations upnext;
                for (int k = ints[siz].sttime; k < 60; k += ints[siz].gaps)
                    ints[siz].stats++;
            }
    sort(ints + 1, ints + 1 + siz, cmp);
    dfs(1, 0, n);
    printf("%d\n", ans);
    return 0;
}

CH2601:电路维修题解

思路

我们可以把整个电路系统想成是一个无向图，如果从点\(A(x_1,y_1)到B(x_2,y_2)\)且这个路上的方格的电路时符合走向的，那么认定这条路的边权为\(0\)，如果与走向相悖，那么边权为\(1\)。为了做一个合理的优化，我们可以使用双端队列，优先处理边权为\(0\)的边，然后确保每个点只经过一次即可。复杂度比较低，看代码吧。

Continue reading →

POJ3322:Bloxorz I 题解

思路

这道题就是一道比较典型的 BFS 搜索题。我们可以先预处理好一些数组来帮助我们进行移动。使用一个结构体来存放每一个步骤的位置和方块躺下的方式，然后把它们放入队列中等待。这道题搞清楚位置的存放之后就应该比较清晰了。下面是代码：

Continue reading →