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

POJ3322:Bloxorz I 题解

思路

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

Continue reading →

POJ3074:Sudoku 题解

神仙思路

这道题用的方式非常之神仙，用位运算来判断数字的选与不选。首先我们先来构造几个辅助数组，以便把映射数组\(X,Y,Box\)的值预先求出，然后再处理几个位运算的辅助数组。由于做法过于神仙，难以解释，看代码就好。

Continue reading →

P1141:01迷宫题解

思路

在我思考了很久之后~~（其实是理解题解）~~，我解决了这道题的做法。主要就是并查集的一个扩展和预处理。我们在读取01迷宫时，就检测左边的点和右边的点是否连通。如果是连通的话，在并查集中合并，并且在并查集中把连通块个数相加即可。

还有一个主要的思想就是映射。在并查集中我们的数组是一维的（mem[]），我们只需要一个计算函数把（x,y）转换成数字即可。（具体的：ret = x*n + y;）

代码

// P1141_ufs.cpp
#include <iostream>

using namespace std;

const int maxm = 10000000;
const int maxn = 1010;
char map[maxn][maxn];
int n, m;

struct UFS
{
    int mem[maxm];
    int mem_h[maxm];

    UFS()
    {
        for (int i = 0; i < maxm; i++)
            mem[i] = i, mem_h[i] = 1;
        for (int i = maxm; i < maxn; i++)
            mem_h[i] = 1;
    }

    int Find(int a)
    {
        if (mem[a] == a)
            return a;
        return mem[a] = Find(mem[a]);
    }

    void Unite(int a, int b)
    {
        if (Find(a) != Find(b))
            mem_h[Find(a)] += mem_h[Find(b)], mem[Find(b)] = Find(a);
    }
} u;

int hashcode(int a, int b)
{
    return a * n + b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
            // left;
            if (j != 1 && map[i][j - 1] != map[i][j])
                u.Unite(hashcode(i, j), hashcode(i, j - 1));
            // up;
            if (i != 1 && map[i - 1][j] != map[i][j])
                u.Unite(hashcode(i, j), hashcode(i - 1, j));
        }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << u.mem_h[u.Find(hashcode(a, b))] << endl;
    }
    return 0;
}

代码我喜欢强格式化（vscode）所以行数可能比较多。