复习一下 2-SAT,感觉核心还是记住了的。 题目背景 狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是,小 L 在玩游戏之余,还精于研究游戏的设计,因此他有着与众不同的游戏策略。 题目描述 ...
tarjan
Codeforces Round #545 (Div. 2) 题解
题目链接 A. Sushi for Two 题意 在一个 01 序列中找出长为偶数的连续的一段使得它前一半和后一半内部分别相同,而前一半和后一半不同。 $ 2\le n\le 100\ 000$ 题解 令共有 $ k$ 段连续的区间,第 $ i$ 段...
洛谷 P3119 [USACO15JAN]草鉴定Grass Cownoisseur 题解【tarjan】【SPFA】
Description In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently number...
洛谷 P2403 [SDOI2010]所驼门王的宝藏 题解【tarjan】【拓扑排序】
一个比较经典的做法,学tarjan时间比较长了,甚至还忘了怎么拓扑排序…… 题目描述 在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也...
bzoj 4998 星球联盟 题解【LCT】【tarjan】
疯狂Find()就好啦。 Description 在遥远的$ S$星系中一共有$ N$个星球,编号为$ 1\dots N$。其中的一些星球决定组成联盟,以方便相互间的交流。但是,组成联盟的首要条件就是交通条件。初始时,在这$ N$...
POJ 3648/UVA 11294 Wedding 题解 【2-SAT】【tarjan】
需要先读懂题……然后套上2-SAT,还得注意细节。 Description Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The b...
2-SAT问题【学习笔记】
2-SAT问题是用于解决当每个元素有两个状态(0或1),且有约束关系时的问题。 首先分析一下问题模型:给定3个元素,需要从中选出几个,其中 \(A,B\)同时被选或同时不选; \(B\)和\...
洛谷 P1073 NOIp2009提高组 最优贸易 题解【拓扑排序】【tarjan】
万年巨坑终于被填上了…… 题目描述 \(C\)国有\(n\)个大城市和\(m\)条道路,每条道路连接这\(n\)个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这\(m\)条道路中有一部...
洛谷 P2272/bzoj 1093 [ZJOI2007]最大半连通子图 题解【tarjan】【贪心】【树形DP】
一个比较难想的贪心+方案统计顺带树形DP。 题目描述 一个有向图$ G=(V,E)$称为半连通的(Semi-Connected),如果对于:$ \forall u,v\in V$,满足$ u\rightarrow v$或$ v\rightarrow u...
NOIp模拟赛18/7/20 种树 题解【tarjan】【割点】【树】
tarjan求割点的变形。 题目背景 $ \mathrm{Fanvree}$很聪明,解决难题时他总会把问题简单化。 例如,他就整天喜欢把图转化为树。但是他不会缩环,那他怎么转化呢? ...