Knots

Subtract: 给定一个绳环构成的图形,求这个绳环能否通过拓扑变换变为一个环。绳环被二维展开在一个平面内,有若干个交点,每个交点处的绳子恰好两根。交点个数不大于​。

Ideas: 一个比较简单的想法是,我们模拟人解绳子的过程。具体怎么解呢?

  • 1.如果我们发现,通过平移某一段绳子可以使交点个数减少,那么我们就这么操作。

  • 2.如果我们发现,通过翻转某一段绳子可以使交点个数减少,那么我们就这么操作。

仔细想想,在人解绳子的过程中,貌似再没有任何其它高级的操作,因此我们可以认为以上两种操作可以解开任何可以解开的绳子。同时,题目中也说,任何一个合法绳环都可以这样生成。

对于第一个操作,我们可以这样判定:如果存在两段绳子​,​完全在​的上方,并且两段绳子都从交点​开始,到交点​结束,不经过其它任何交点。那么我们可以直接删除这两个交点,因为通过平移​,这两个交点可以消失。

对于第二个操作,如果有一段绳子的左右端点重合于交点​,且不经过任何其它交点,我们可以删除交点​,因为我们可以通过翻转这一段绳子使这个交点消失。

实现的方法,可以是一条链表。

TIPS:我在做这道题时遇到过这么几个问题:1.误认为操作1只要满足其中一条绳子不经过任何其它交点即可,不难通过反例证伪。2.没有合格的数据生成器保证生成出的绳环可以展开在二维平面内,使得对拍遇到困难。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 25005

using namespace std;

template <typename T> void read(T& x)
{
    bool f = 0; x = 0; char c = getchar();
    while(!isdigit(c) && c!='-') c = getchar();
    if(c == '-') f = 1, c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
    if(f) x = -x;
}

int pre[MX], suf[MX], usd[MX], top[MX], but[MX], pos[MX], ops[MX], vis[MX];
int n, m, cnt;

void input()
{
    cnt = 0;
    read(n), read(m);
    for(int i=1; i<=m; i++)
    {
        read(top[i]);
        read(but[i]);
        usd[++cnt] = top[i];
        usd[++cnt] = but[i];
    }
    sort(usd+1, usd+cnt+1);
    cnt = unique(usd+1, usd+cnt+1) - usd - 1;
    for(int i=1; i<=m; i++)
    {
        top[i] = lower_bound(usd+1, usd+cnt+1, top[i]) - usd;
        but[i] = lower_bound(usd+1, usd+cnt+1, but[i]) - usd;
        pos[top[i]] = 2;
        pos[but[i]] = 1;
        ops[top[i]] = but[i];
        ops[but[i]] = top[i];
    }
    for(int i=1; i<=cnt; i++)
    {
        suf[i] = i%cnt+1;
        pre[i%cnt+1] = i;
        vis[i] = 0;
    }
}

void del(int x)
{
    vis[x] = 1;
    suf[pre[x]] = suf[x];
    pre[suf[x]] = pre[x];
}

bool check(int x, int y)
{
    if(pos[x]==pos[y] && (suf[ops[x]]==ops[y] || suf[ops[y]]==ops[x]))
        del(x), del(y), del(ops[x]), del(ops[y]), cnt -= 4;
    else if(x == ops[y])
        del(x), del(y), cnt -= 2;
    else return 0;
    return 1;
}

bool work()
{
    int beg = 1;
    while(cnt)
    {
        int fail = 1, x, y;
        while(vis[beg]) beg++;
        fail &= (!check(beg, suf[beg]));
        for(int i=suf[beg]; fail&&i!=beg; i=suf[i])
            fail &= (!check(i, suf[i]));
        if(fail) break;
    }
    return cnt == 0;
}

int main()
{
    int cas = 0;
    read(cas);
    for(int i=1; i<=cas; i++)
    {
        input();
        if(work()) printf("Case #%d: YES\n", i);
        else printf("Case #%d: NO\n", i);
    }
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *