Day1T3小w的魔术扑克——图论

为什么不搞\(T2\)???
因为我太菜了,那题我是真的搞不出来

题目描述

链接:https://ac.nowcoder.com/acm/contest/1100/C
来源:牛客网
小\(w\)喜欢打牌,某天小\(w\)与\(dogenya\)在一起玩扑克牌,这种扑克牌的面值都在\(1\)到\(n\),原本扑克牌只有一面,而小\(w\)手中的扑克牌是双面的魔术扑克(正反两面均有数字,可以随时进行切换),小\(w\)这个人就准备用它来出老千作弊。小\(w\)想要打出一些顺子,我们定义打出一个\(l\)到\(r\)的顺子需要面值为从\(l\)到\(r\)的卡牌各一张。小\(w\)想问问你,他能否利用手中的魔术卡牌打出这些顺子呢?

输入描述:

首先输入一行2个正整数\(n\),\(k\),表示牌面为\(1\)~\(n\),小\(w\)手中有\(k\)张魔术扑克牌。
然后输入\(k\)行,每行两个数字,表示卡牌的正面和反面的面值。
接下来输入一行一个正整数\(q\),表示\(q\)组查询,然后每组占一行查询输入两个整数\(l\),\(r\)。表示查询小\(w\)能否打出这么一个\(l\)到\(r\)的顺子。

输出描述:

对于输出"\(Yes\)"表示可以,"\(No\)"表示不可以。(不含引号)
每个查询都是独立的,查询之间互不影响。

题解

我在考试的时候看出来这是个图了,也想过正反面连边了,但是一些操作没想到,这题还是没能搞出来……

首先我们可以考虑一个事儿,就是我们不判自环重边的时候,有几张牌,就会连几条边
那一个数字可以使用的要求是什么呢,就是它的出度不为零(无向图
因为我们每张牌的正反面都要互相连边,假如说某个数字的出度为零,那么就说明这个数字没有在任意一张牌上出现过
那么我们就可以想到连完边以后,看一下图中各个连通块里有多少条边,就可以知道包含这个连通块里的某数字的牌一共有几张
举个栗子:
我们有三张牌,第一张两面是\(1,2\),第二张是\(2,3\),第三张是\(4,4\)
我们先找\(1\)所在连通块有几条边几个点,发现有两条边三个点,那么就说明只有两张牌包含这三个数字,这三个数字就一定不能同时出现
此时如果我们再加一张\(1,3\)的牌,就可以了
那么我们就可以发现,如果一个连通块是一棵树,那么它包含的数字一定不可能同时出现
我们就可以判一下有几个连通块是树
我们再考虑一个事儿,树上的数字一定不能被使用吗?
不是,只要我们不同时选用树上的所有点就可以使用
那么我们就可以记录一下每个树里的最大值和最小值,如果有一个顺子包含最小值,那么它不能包含最大值,否则它一定包含整棵树
如果一个顺子不包含最小值,那么这个连通块里的数字我们随便用
所以我们可以设一个数组\(r[i]\),记录以\(i\)为最小值的树的最大值是多少
从头到尾扫一遍每个查询区间,看有没有出现\(r[i]\)小于等于右端点的情况

我最后还特判了一下是不是每张牌的正反面都相等,不然找连通块会炸
可能是我的代码常数太大???反正别人做法跟我一样但是不用特判

话说考场上这题默认正反面相同写个暴力能拿50分……

宁康康代码:

#include<bits/stdc++.h>
using namespace std;
#define rint register int
int n, q, k, cnt, tag, b, minn, maxn, num, nump;
int head[100010], r[100010], vis[100010], t[100010], add[100010];
struct edge{
    int nxt, to;
}a[200010];
inline void addedge( int x, int y ){
    a[++cnt].nxt = head[x];
    a[cnt].to = y;
    head[x] = cnt;
}
inline int read( void ){
    int re = 0, f = 1; char ch = getchar();
    while( ch > '9' || ch < '0' ){
        if( ch == '-' ) f = -1;
        ch = getchar();
    }
    while( ch >= '0' && ch <= '9' ){
        re = re * 10 + ch - '0';
        ch = getchar();
    }
    return re * f;
}
inline void dfs( int now, int fa ){
    maxn = max( maxn, now );
    minn = min( minn, now );
    vis[now] = 1;
    nump++;
    for( rint i = head[now]; i; i = a[i].nxt ){
        int v = a[i].to; num++;
        if( v == fa || vis[v] ) continue ;
        dfs( v, now );
    }
}
int main( void ){
    n = read(); k = read();
    for( rint i = 1; i <= k; i++ ){
        int u, v; u = read(); v = read();
        addedge( u, v ); addedge( v, u );
        t[u] = 1; t[v] = 1;
        if( u != v ) b = 1;
    }
    memset( r, 0x3f, sizeof( r ) );
    if( !b ){
        for( rint i = 1; i <= n; i++ ) add[i] = add[i - 1] + t[i];
        q = read();
        for( rint i = 1; i <= q; i++ ){
            int u, v; u = read(); v = read();
            if( add[v] - add[u] == v - u ) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        return 0;
    }
    for( rint i = 1; i <= n; i++ ){
        if( !vis[i] ){
            maxn = 0, minn = 0x3f3f3f3f;
            num = 0; nump = 0;
            dfs( i, i );
            if( num / 2 < nump ){
                r[minn] = maxn;
            }
        }
    }
    q = read();
    //for( rint i = 1; i <= n; i++ ) cout << r[i] << ' ';
    for( rint i = 1; i <= q; i++ ){
        tag = 0;
        int u, v; u = read(); v = read();
        for( rint j = u; j <= v; j++ ){
            if( r[j] <= v ){
                cout << "No" << endl;
                tag = 1; break;
            }
        }
        if( !tag ) cout << "Yes" << endl;
    }
    return 0;
}
上一篇:osu合集(期望dp)


下一篇:【LuoguP4719】动态DP模板-树链剖分+线段树+矩阵乘法