首页 > 其他分享 >洛谷 P8405 [COCI2021-2022#6] Naboj 题解

洛谷 P8405 [COCI2021-2022#6] Naboj 题解

时间:2024-03-31 22:35:44浏览次数:25  
标签:GCC COCI2021 洛谷 题解 哨兵 pragma 操作 逆序

题意简述

给定一张无向图,每条边有个哨兵,初始在边的中间。你可以把某个结点旁边的哨兵全部吸引或远离这个结点。给出最后每个哨兵在边的哪一端,请构造出一种可能的操作方案或报告无解。多种情况输出任意解,你不需要最小化操作步数

题目分析

发现一个哨兵和且仅和最后一次关联这条边的操作有关,考虑使用“浮水法”反转操作,即假定一个哨兵在被定向后就不会再发生变化,那么把这样的方案倒序输出就是原问题答案了。

那么如何求解这个问题呢?发现一开始操作的点一定是哨兵最终要全部靠近或远离这个点的,为简化讨论,不妨令一开始操作的点连出的所有边,哨兵都在这个点一侧。那么给它设为吸引哨兵后,它对其他节点就没有了影响。所以考虑删去这个点和其连出的边,循环此过程。

发现这就是在跑一个拓扑排序。既然是拓扑排序,无解的时候当且仅当出现了环,也就是最后还有的边不能被确定。

于是这道题就愉快地过掉啦。

代码(已略去快读快写)

目前最优解 rank1

//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include <iostream>
#include <cstdio>
#define debug(a) cerr << "Line: " << __LINE__ << " " << #a << endl
#define print(a) cerr << #a << "=" << (a) << endl
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define main Main(); signed main(){ return ios::sync_with_stdio(0), cin.tie(0), Main(); } signed Main
using namespace std;

int n, m;

struct Graph{
	struct node{
		int to, nxt;
	} edge[500010 << 1];
	int eid, head[500010];
	inline void add(int u, int v){
		edge[++eid] = {v, head[u]};
		head[u] = eid;
	}
	inline node & operator [] (const int x){
		return edge[x];
	}
} xym;

int du[500010], Q[500010], top;
int ans[500010], tot;

signed main(){
	read(n, m);
	for (int i = 1, u, v; i <= m; ++i) read(u, v), xym.add(u, v), ++du[v];
	for (int i = 1; i <= n; ++i) !du[i] && (Q[++top] = i);
	while (top){
		int now = Q[top--]; ans[++tot] = now;  // 给这个点设为吸引哨兵
		for (int i = xym.head[now]; i; i = xym[i].nxt)
			if (!--du[xym[i].to]) Q[++top] = xym[i].to;  // 拓扑排序
	}
	for (int i = 1; i <= n; ++i) du[i] && (write(-1), exit(0), yzh_i_love_you);
	// 无解当且仅当最后出现了环
	write(tot, '\n');
	for (int i = tot; i >= 1; --i) write(ans[i], ' ', 1, '\n');  // 逆序输出
	return 0;
}

总结 & 后话

对于这种最终结果依赖于最后一次操作的时候,考虑使用“浮水法”,反转操作顺序,它被操作后就不再变化了,而实际操作顺序就是新操作顺序的逆序。

标签:GCC,COCI2021,洛谷,题解,哨兵,pragma,操作,逆序
From: https://www.cnblogs.com/XuYueming/p/18107392

相关文章

  • [ABC347] AtCoder Beginner Contest 347 题解
    [ABC347]AtCoderBeginnerContest347题解A模拟。BSA模板,把所有子串丢进哈希表里即可。C逆天题,这个分讨并不显然。考虑计算所有天数到今天的偏移量,然后如果最远的和最近的天数的距离\(\leA\)肯定可以,否则可以把所有天向右平移一段距离,然后使得最远的天到达第二周的......
  • CF1942E Farm Game 题解
    我们先默认第一头牛是John的,另一种情况本质相同,最后答案乘上\(2\)就可以了。先说结论:我们将相邻两头牛配对,那么最终答案即满足至少一对牛间隔了奇数个空位的方案数。证明很简单,分\(3\)种情况讨论:每对牛间都间隔了奇数个空位。那么John开始时让所有牛往右行动,在Nhoj行......
  • [题解]P2516 [HAOI2010] 最长公共子序列——求LCS个数
    P2516[HAOI2010]最长公共子序列总的来说,这道题确实很精妙,难度也不小,耗费了不少时间去调。本来想过用容斥的思想,却因为当时理解不深没有继续思考就放弃了。学会了思路后对\(LCS\)有了更深层次的理解。题意简述给定\(A,B\)两个字符串(以.结尾),求它们的最长公共子序列的长度和个数......
  • 0324-0331题解反思
    最近我突然发现,写题解是常常会遗忘的,然而题目中的一些技巧才是永恒的,那么接下来的题解,我应该对以前的题目含有的这些技巧进行一些深刻的复盘。知识点模块1.当我们要实现一个图形的字符串的倒置,比如把福倒过来,我们可以进行以下的操作:先进行行的交换,在进行列的倒置,我们需要用到s......
  • 【C++实验1】学生成绩信息管理系统题解
    【问题描述】编写一个基于结构体得学生成绩信息管理系统。主要功能如下:1.用结构体存放所有数据。2.每个功能都用函数实现。3.输入10个学生的学号和三门课程的成绩。4.计算每个学生的总分。5.按总分从高到低排序。6.加上名次一列。7.输出最后的二维表格样式的成......
  • 洛谷P1102 A-B数对
    双指针做法:  反过来,从后往前看也是一样的:#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<cmath>#defineFor(i,j,n)for(inti=j;i<=n;++i)usingnamespacestd;constintN=2e5+5;int......
  • 题解 P9981 [USACO23DEC] Minimum Longest Trip G
    【洛谷专栏】题意\(N\)个点\(M\)条边的有向无环图,对于每一个点\(i\)你需要求出一条从\(i\)出发的最长路径且路径上边权组成的序列字典序最小。求每一条路径的长度和边权和。分析最长的路径很好求,在DAG上拓扑排序后动态规划即可。(具体的实现可以参考OI-Wiki)现在的......
  • Minlexes题解
    \(\texttt{ProblemLink}\)简要题意在一个字符串\(s\)中,对于每个后缀,任意删掉一些相邻的相同的字符,使得字符串字典序最小。注意:删掉之后拼起来再出现的相邻相同字符不能够删除。思路倍增好题。发现存在局部最优解(最优子结构),并且可以转移到其它结点,可以考虑使用dp。那就......
  • Tomcat启动失败,窗口一闪而过问题解决
    在启动Tomcat时窗口一闪而过,解决方法:在Tomcat安装目录\bin下启动cmd,或在C盘启动后跳转到Tomcat安装目录\bin,输入startup.bat(一定要先做这步,确保具体问题,再根据具体问题百度,不然又是配置JRE,又是配置Tomcat环境变量,最后做了无用功),如果显示如下:先确保java环境变量没问题,我的java......
  • 题解:AT_arc175_b [ARC175B] Parenthesis Arrangemen
    前言警示后人:字符串最大长度为\(65535\),会\(RE\)!!!\(10^7\)会爆栈!!!题意给出一个括号序列\(s\),有两种操作方式,交换两个字符需要花费\(A\),直接修改一个字符需要花费\(B\),求使这个序列合法需要的最小花费。分析我们可以先将\(s\)中能匹配的括号序列消除掉(即括号匹配......