首页 > 其他分享 >题解 P6560 [SBCOI2020] 时光的流逝

题解 P6560 [SBCOI2020] 时光的流逝

时间:2023-11-01 10:34:39浏览次数:39  
标签:int 题解 P6560 100010 SBCOI2020 流逝

题解 P6560 [SBCOI2020] 时光的流逝

首先考虑图上的点为 \(y\) 终点时,或者这个点无法继续向下走,即 \(du_i = 0\) 时,从这个点为起点先手必败,而对于每一个有一条指向先手必败的点的边的点,显然从这个点出发都是先手必胜的,以此类推。

可以考虑建反图,进行拓扑排序,转移状态。

#include<queue>
#include<cstdio>
using namespace std;

int cnt;
int du[100010],head[100010],f[100010],d[100010];
queue<int> q;
struct Node{
	int to,nxt;
}edge[500010];

int read(){
	int res=0;char c=getchar();
	while(c>'9' || c<'0') c=getchar();
	while(c>='0' && c<='9') res=res*10+c-'0',c=getchar();
	return res;
}
int n=read(),m=read(),T=read();

int main(){
	for(int i=1;i<=m;i++){
		int x=read(),y;
		edge[++cnt]=((Node){x,head[y=read()]}),
		head[y]=cnt,du[x]++;
	}
	while(T--){
		int s=read(),t=read();
		for(int i=1;i<=n;i++){
			f[i]=0,d[i]=du[i];
			if(!d[i] || i==t) q.push(i),f[i]=-1;
		}
		while(q.size()){
			int p=q.front();q.pop();
			for(int i=head[p];i;i=edge[i].nxt)
				if(!f[edge[i].to]){
					if(f[p]==1){
						if(!(--d[edge[i].to])) q.push(edge[i].to),f[edge[i].to]=-1;
					}else q.push(edge[i].to),f[edge[i].to]=1;
				}
		}
		printf("%d\n",f[s]);
	}
	return 0;
}

标签:int,题解,P6560,100010,SBCOI2020,流逝
From: https://www.cnblogs.com/Tyrue-blog/p/17802465.html

相关文章

  • 题解 [ARC149B] Two LIS Sum
    题解[ARC149B]TwoLISSum大胆猜结论,按照\(a\)数组为关键字进行排序,求更改后\(b\)的\(LIS\)。证明:每次移动,都有\(a\)中增加一个长度,\(b\)中贡献可能为\(\{-1,0,1\}\),总体贡献为\(\{0,1,2\}\),具体为:\(b\)中排序后大数变到小数前方。\(b\)中排序后小数仍然......
  • CF1872E Data Structures Fan 题解
    CF1872E翻译请把数据加强到\(\sumn\leq10^8\)后重新思考。我们维护全局中被标记的所有点的异或和。发现对于一次\(1\)操作,相当于让答案异或上区间的\(a_i\)异或和,因为这会让被标记的点变成没被标记的,而没被标记的点会产生贡献。查询的话直接查询即可复杂度......
  • P2391 白雪皑皑 题解
    一种很新的区间染色题目传送门题目大意有\(n\)个数初始都为\(0\),有\(m\)次操作,第\(i\)次将\((i\timesp+q)\bmodn+1\)与\((i\timesq+p)\bmodn+1\)之间数都改为\(i\),问\(m\)次操作后每个数分别是多少。其中\(1\len\le10^6,1\lem\le1......
  • P4397聪明的燕姿 题解 & Miller~Rabin 质数判定
    涉及质数的时间复杂度都是玄学的。——题记传送门由整数唯一分解定理:\(\coprod\limits_{i=1}^{k}p_i^{c_i}\)有该正整数的正约数为:\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^j)\)即我们要求有多少个数满足\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^......
  • CF1707 题解
    CF1707题解A考场上1h才出思路...弱智了。我们将参加大于当前智商的行为叫做“摆烂”。我们考虑如果现在摆一次,将来某一次不摆,那么现在不摆,将来那次开摆,中间过程的智商会加1。更优。所以一定一摆就摆到底。而且一定会摆到最后一个。所以我们二分从什么时候开摆,看是否能摆到......
  • 题解:洛谷P3745 期末考试(整数三分)
    题解:洛谷P3745期末考试(整数三分)题目传送门题目大意:给出\(n\)个同学期望出成绩的时间限制\(a_i\)和\(m\)个学科公布成绩的初始时间\(t_i\),1个同学每多等一天就产生A的不愉快度。问通过一番操作后最小的不愉快度之和是多少?操作有两种:1.让学科X的发布时间晚1天,学科......
  • P5404 [CTS2019] 重复 题解
    题目链接观察题目,我们发现直接计算是困难的,先构造单个合法的\(T\)分析其性质。为了构造出\(T\),先考虑构造时\(T\)时什么时候会出现不合法的情况,此时\(T\)会有一段和\(S\)相同的前缀,且这段前缀后面跟着的字符比\(S\)所跟的小。为了避免这种情况出现,我们需要在每次添......
  • CSPRO 历届题目与题解
    官方题目链接:http://118.190.20.162/\(\Huge目录\)201609201612201709202104202109202112202203202206202209202303202305202309\(\Huge\text{CSP201609}\)火车购票问题描述请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。假设一节车厢......
  • AT_abc326_d ABC Puzzle 题解
    AT_abc326_dABCPuzzle题解看题事实上,即使在\(N=5\)的情况下,也只有\(66240\)个网格满足「每行/每列恰好包含一个A、B和C」。——官方题解其实看到这道题,就感觉是搜索,这很显然。但是我们会发现,最最最native的搜索,是\(4^{5\times5}=2^{50}\)的。感觉不大可过,但是......
  • AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
    AT_abc326_eRevengeof"TheSalaryofAtCoderInc."题解一道简单的概率论+动态规划题目(然而我赛时没看这道题题意有一个长度为\(n\)的序列\(A\)、一个\(n\)面骰子,掷若干次骰子,如果这一次掷骰子的点数小于等于上一次的点数,则结束。定义这若干次掷骰子的总的结果为,每次......