Luogu P3007 奶牛议会

这篇具有很好参考价值的文章主要介绍了Luogu P3007 奶牛议会。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

观前须知

本题解使用 CC BY-NC-SA 4.0 许可
同步发布于 Luogu 题解区。
更好的观看体验 请点这里

笔者的博客主页

正文

Luogu P3007 【USACO11JAN】 The Continental Cowngress G

前置知识:2-SATTarjan
(应该没有人会 2-sat 不会 tarjan 吧)

DAG DP 朴素做法

这道题除去输出 '?' 的部分是一道 2-SAT 的纯版子题。
其他题解基本使用了 DFS 来判断该情况。
这里提供一份 bitset 优化的 DAG DP 解法。
凭借着 bitset 强大的优化,成功跑到 34ms,轻松 rk1。

由于这道题的前半部分就是 2-SAT 的板子题,所以不再过多赘述。
感兴趣可见 Luogu P4782 【模板】2-SAT

那么考虑什么情况下可选也可不选,
发现当且仅当 \(x\)(表示法案 \(x\) 通过)和 \(x'\)(表示法案 \(x\) 不通过)不连通时可选可不选。
因为我们已经有了一个 DAG,可以求出它的拓扑序
那么不连通也就是拓扑序靠后的那一个节点的祖先中没有它的反节点。
强连通分量题做得多的 dalao 们应该已经想到这道题可以 DP 了。

小 trick:
Tarjan 求出的强连通分量编号是缩点后的图的 拓扑逆序
从 Tarjan 递归过程的角度思考一下很好证明。
……
不卖关子啦。
其实就是在搜索树上,由于递归类似于,是先进后出的,
所以一个节点后代节点可在搜索树上后搜到,回溯时,后代节点先被统计强连通分量。
所以后代节点一定在祖先节点之前被统计,得到的顺序就是拓扑逆序了。

具体的 DP 方式是这样的:
缩点后,对于每个节点(这里是原图的强连通分量),维护一个 \(vis_u\) 数组,
\(vis_{u,v}=1\) 表示 \(v\)\(u\) 的祖先节点中出现过,反之表示未出现过。
转移就是如果 \(v\)\(u\) 的祖先节点出现过,则它肯定在 \(son(u)\) 的祖先节点中出现过。
特别地,\(vis_{u,u}=1\)
具体转移方式见代码:

// co[0] 存储强连通分量个数
// 这里使用了强连通分量是拓扑逆序的小 trick
for (int u = co[0]; u; u--) {
    vis[u][u] = true;
    for (int i = head[u]; i; i = e[i].nxt) 
        for(int j = 1; j <= co[0]; j++)
            vis[e[i].v][j] |= vis[u][j];
}

那么如果一个法案可选也不可选,即不连通时有:\(vis_{u,v}=0\),其中 \(u\) 为拓扑序靠后的节点,\(v\)\(u\) 的反节点
判断的具体代码如下:

for (int i = 1; i <= n; i++) {
    // i 表示通过,i+n 表示不通过
    // 判断拓扑序靠后的是哪个节点,vx=0 为 i,vx=1 为 i+n
    // co[u] 表示 u 节点所属的强连通分量
    vx = co[i] > co[i + n];
    // 利用三目运算简化语句
    // 若有祖先关系则输出 Y 或 N
    if (vis[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
    // 否则输出 ?
    else putchar('?');
}

好的那么现在我们已经有了一个 \(O(n^2)\) 的算法了。
但是还不够。

bitset

接下来我们来介绍今天的主角:bitset
我们知道,平常我们使用 bool 数组的时候,像是 bool vis[N]; 是要使用 \(8N\) bit 的空间的。
然而一个 bool 实际上也就是一个 0/1 的值,能不能只占 \(1\) bit 空间呢?
可以!我们写成 bitset<N> vis 就可以了!
这里的 N 是 bitset 的位数,要求必须是整型常量。
bitset 同 bool 数组一样,支持形如 vis[u] 的访问和赋值。
然而它同时支持与、或、左/右移等操作。
可以理解为 bitset 是一个大的二进制数。

由于篇幅有限,bitset 的详细用法不会过多赘述,这里只介绍用来优化的部分。
更多内容可见这篇文章: C++ std::bitset

等一下,它支持或?
我们发现,我们程序中有这么一个操作:

for(int j = 1; j <= co[0]; j++)
    vis[e[i].v][j] |= vis[u][j];

这个操作相当于把 vis[e[i].v] 这个数组整体或上一个 vis[u]
那么我们就可以用 bitset 优化了!
开一个 bitset<M> b[N]; 的数组,M 表示强连通分量个数上限,则我们的程序可以改写为:

bitset<M> b[N];

for (int u = co[0]; u; u--) {
    b[u][u] = true;
    // 利用 bitset 的或操作快速转移
    for (int i = head[u]; i; i = e[i].nxt) b[e[i].v] |= b[u];
}

/*...*/

// 因为 bitset 支持类似 bool数组 的操作,所以这段代码除了一个变量名外没有变化
for (int i = 1; i <= n; i++) {
    vx = co[i] > co[i + n];
    if (b[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
    else putchar('?');
}

那么我们就用 bitset 做完了这道题目。
那么问题来了,优化后的空间复杂度肯定小了,时间复杂度呢?
直接给结论:
bitset 的单次整体与、或等操作复杂度为 \(\mathcal O(\frac{n}{w})\)
这里,\(n\) 指 bitset 的长度,\(w\) (不是 \(\omega\))为计算机字长,一般为 \(32\)
那么整体时间复杂度就是 \(\mathcal O(\frac{n^2}{w})\) 了,相当于在原先的复杂度上除了一个比较大的 \(\log\)
这样的时间复杂度就是非常优的了。

bitset 优化可以优化 floyd求传递闭包 等算法。
往往 \(10^4\) 的数据,\(\mathcal O(n^2)\) 无法通过,而 \(\mathcal O(\frac{n^2}{w})\) 就可以通过了。
所以说,bitset 的优化真的非常强大

剩下的一些小细节放在代码的注释里了:
本代码 34ms 的提交记录。

#include<bits/stdc++.h>

using namespace std;

class FD {
private:
    inline static int Read() {
        int r = 0, f = 0, c = getchar();
        while ((c < '0' || c > '9') && ~c) { f |= c == '-', c = getchar(); }
        while (c >= '0' && c <= '9') { r = (r << 1) + (r << 3) + (c ^ 48), c = getchar(); }
        return f ? -r : r;
    }

    static constexpr int AwA = 2e3 + 10;
    static constexpr int QwQ = 8e3 + 10;
    //这里是强连通分量个数,开这么大就能ac
    static constexpr int PwP = 360;

    struct Edge {
        int nxt, v;
    } e[QwQ << 1];
    int head[AwA << 1], ecnt;

    inline void AddEdge(int u, int v) { e[++ecnt] = {head[u], v}, head[u] = ecnt; }

    int n, m;
    int dfn[AwA], low[AwA], co[AwA], stk[AwA];
    bitset<PwP> b[AwA];

    void Tarjan(int u) {
        stk[++stk[0]] = u;
        dfn[u] = low[u] = ++dfn[0];
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
            else if (!co[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            co[u] = ++co[0];
            while (stk[stk[0]] != u) co[stk[stk[0]--]] = co[0];
            stk[0]--;
        }
    }

public:
    inline void Main() {
        n = Read(), m = Read();
        int x, y;
        bool vx, vy;
        //三目运算简化
        while (m--) {
            x = Read(), vx = getchar() == 'N';
            y = Read(), vy = getchar() == 'N';
            AddEdge(vx ? x : x + n, vy ? y + n : y);
            AddEdge(vy ? y : y + n, vx ? x + n : x);
        }
        for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) Tarjan(i);
        //判无解
        for (int i = 1; i <= n; i++) if (co[i] == co[i + n]) return void(puts("IMPOSSIBLE"));
        //建新图,这里直接用旧图开新节点的方式处理了
        for (int u = 1; u <= 2 * n; u++)
            for (int i = head[u]; i; i = e[i].nxt)
                if (co[e[i].v] != co[u]) AddEdge(co[u] + n * 2, co[e[i].v]);

        //DAG DP
        for (int u = co[0]; u; u--) {
            b[u][u] = true;
            for (int i = head[u + 2 * n]; i; i = e[i].nxt) b[e[i].v] |= b[u];
        }
        //输出答案
        for (int i = 1; i <= n; i++) {
            vx = co[i] > co[i + n];
            if (b[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
            else putchar('?');
        }
        putchar('\n');
    }
} Fd;

int main() {
    Fd.Main();
    return 0;
}

完结,撒花!~文章来源地址https://www.toymoban.com/news/detail-848772.html

到了这里,关于Luogu P3007 奶牛议会的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 计算机程序安装及使用须知_kaic

       本文件夹中的“PowerDesigner建模”目录下包含三个可运行文件TMS1.cdm,TMS.cdm,TMS.pdm分别为TMS系统的实体关系简图、实体关系图和数据库模型,使用PowerDesigner集成开发环境打开任意一个文件即可运行。  本安装说明以Microsoft SQL Server 2000中文开发版为例来阐述的,对于Micros

    2023年04月25日
    浏览(47)
  • “暗网议会”如今已成为现实

    图片来源:Marcin Balcerzak 最近,“暗网议会”已经成为了网络犯罪分子试图证明自己影响力的最新流行语,安全内部人士对这个词也很感兴趣。 上周五,臭名昭著的亲俄黑客组织Killnet在其电报威胁帖子中使用了这个词语。随后,twitter吸引来了很多安全人员,都表示对这个黑客

    2024年02月10日
    浏览(35)
  • 奶牛用餐 优先队列 java

    👨‍🏫 奶牛用餐 约翰的农场有 n n n 头奶牛,编号 1 s i m n 1 \\\\sim n 1 s imn 。 每天奶牛们都要去食堂用餐。 食堂一共有 k k k 个座位,也就是说同一时间最多可以容纳 k k k 头奶牛同时用餐。 已知,第 i i i 头奶牛到达食堂的具体时刻为 s _ i s_i s _ i ,用餐所需花费的时间为 t

    2024年02月13日
    浏览(34)
  • 奶牛排队 java 思维题

    👨‍🏫 5133. 奶牛排队 题目描述 约翰的农场有 n n n 头奶牛,每一头奶牛都有一个正整数编号。 不同奶牛的编号不同。 现在,这 n n n 头牛按某种顺序排成一队,每头牛都拿出一张纸条写下了其前方相邻牛的编号以及其后方相邻牛的编号。 注意: 这些奶牛并没有记下自己的

    2024年02月14日
    浏览(41)
  • 5465: 【搜索】奶牛干饭

    农场主John把农场分为了一个 r 行 c 列的矩阵,并发现奶牛们无法通过其中一些区域。此刻,Bessie 位于坐标为 (1,1) 的区域,并想到坐标为 (r,c) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至相邻的四个区域之一,如果奶牛吃不到饭就会大哭。 第一行两个

    2024年03月21日
    浏览(37)
  • 【P1824 进击的奶牛】

    Farmer John 建造了一个有 N N N ( 2 ≤ N ≤ 1 0 5 2 leq N leq 10 ^ 5 2 ≤ N ≤ 1 0 5 ) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是 x 1 , x 2 , ⋯   , x N x _ 1, x _ 2, cdots, x _ N x 1 ​ , x 2 ​ , ⋯ , x N ​ ( 0 ≤ x i ≤ 1 0 9 0 leq x _ i leq 10 ^ 9 0 ≤ x i ​ ≤ 1 0 9 )。 他的 C C C ( 2 ≤

    2024年02月05日
    浏览(37)
  • Luogu P3294 背单词

    本题解使用 CC BY-NC-SA 4.0 许可 。 同步发布于Luogu题解区。 更好的观看体验 请点这里 。 笔者的博客主页 Luogu P3294 【SCOI2016】背单词 笔者在刷题的时候看到了这道好题。 花了四十分钟切掉以后,看了一下题解。 发现自己的想法不太一样。 所以想做一篇适合我这样的蒟蒻看的

    2024年04月08日
    浏览(45)
  • 洛谷p1824 进击的奶牛

    Farmer John建造了一个有N(2=N=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0=xi=1,000,000,000)。 他的C(2=C=N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相邻两

    2024年02月11日
    浏览(42)
  • 【Luogu】 P5445 [APIO2019] 路灯

    点击打开链接 转化很妙 考虑关路灯 x x x 的操作 令左边第一个未关的路灯为 L L L ,右边第一个未关的路灯为 R R R ,那么这一次会影响的区间即为 l ∈ [ L + 1 , x ] ,    r ∈ [ x , R − 1 ] lin[L+1,x],;rin[x,R-1] l ∈ [ L + 1 , x ] , r ∈ [ x , R − 1 ] ,既然有 2 个限制,那么我们把限制

    2024年02月10日
    浏览(74)
  • 【Luogu】 P6076 [JSOI2015]染色问题

    点击打开链接 可以一个一个条件考虑 只考虑条件 1 1 1 答案即为 ( c + 1 ) n m (c+1)^{nm} ( c + 1 ) nm 考虑条件 1 , 2 1,2 1 , 2 对每一行的方案数减去 1 1 1 答案即为 ( ( c + 1 ) m − 1 ) n ((c+1)^m-1)^n (( c + 1 ) m − 1 ) n 考虑条件 1 , 2 , 3 1,2,3 1 , 2 , 3 考虑容斥 容斥至少有 i i i 列未被染色,即为

    2024年02月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包