首页 > 其他分享 >P1543 [POI2004] SZP 题解

P1543 [POI2004] SZP 题解

时间:2024-08-20 10:05:35浏览次数:8  
标签:int 题解 P1543 监视 SZP POI2004

P1543 [POI2004] SZP 题解

传送门。

题目简述

有 \(n\) 个人,每个人都会监视另一个人,要求选出尽可能多的同学,使得选出的每一名同学都必定会被监视到。且选出的同学不可再监视其他人。

思路简述

因为任意一个人只能被另一个人管,那么就想到,如果没人管的同学就不能被选(不被监视)。

若某个人有多个人监视,且监视他的有至少一个专门监视(监视他的那个人没人监视)则他不得不去。

那么再看看如果出现环咋办。

不如画个图理解。

上图即为一个环:\(1\) 监视 \(2\),\(2\) 监视 \(3\),\(3\) 监视 \(1\)。

那么不妨枚举一下。

如果派出 \(1\),则 \(3\) 可以监视到,而 \(2\) 也可以监视到 \(3\),完美符合题意。

但是,若取出了 \(1\) 和 \(2\),\(2\) 则会没人监视(本来监视他的 \(1\) 号走了)。

所以可以得出结论:若遇到环,设 \(s\) 为环的节点个数,则取出的个数为 \(\lfloor\frac{s}{2}\rfloor\)。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,to[N],ans,cnt_ring,in[N];
bool gone[N]/*被选中了吗*/,vis_ring[N]/*遍历过了吗*/;
queue<int > q;//注意:这里的q可不是说进队列了就得被选中
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&to[i]);
		++in[to[i]];//入度+1
	}
	for(int i=1;i<=n;i++)
		if(!in[i])//拓扑排序老板子
			q.push(i);
	while(!q.empty())
	{
		int t=q.front();q.pop();
		vis_ring[t]=true;//判断是否遍历过
		if(gone[t])//他走了,他监视的同学就看看情况
		{
			if((--in[to[t]])==0)
				q.push(to[t]);
		}
		else//他没走,他监视的孩子可就遭老罪喽
		{
			if(!gone[to[t]])//孩子没走
			{
				++ans;
				gone[to[t]]=true;//给我走
				q.push(to[t]);
			}
		}
	}
	for(int i=1;i<=n;i++)//开始判环
	{
		if(!vis_ring[i]&&in[i])
		{
			cnt_ring=0;//作用如其名
			for(int j=i;!vis_ring[j];j=to[j])
			{
				++cnt_ring;
				vis_ring[j]=true;
			}
			ans+=cnt_ring/2;//刚说的,不过C++自动向下取整
		}
	}
	printf("%d\n",ans);
	return 0;
}

标签:int,题解,P1543,监视,SZP,POI2004
From: https://www.cnblogs.com/Atserckcn/p/18368888

相关文章

  • 题解:[TJOI2018] 游园会
    所谓dp套dp,实际上就是在说求解一个dp的过程中,我们用另一个dp求解出他应该从某个状态转移到另一个状态。考虑一下这道题,首先求LCS的dp如下:\[dp_{i,j}=\max\{dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+[s_i==t_j]\}\]显然,当\(i\)固定的时候,\(dp_{i,j}\)是单调不降的,且相邻两......
  • 【LGR-196-Div.4】洛谷入门赛 #26 题A - H 详细题解--优化思路简洁代码(C++,Python语
    前言:    觉得这个比赛很有意思的,都是暴力题,涉及一些细节,难度比较适合刚学编程语言的,可以很好的锻炼基础还有手速,最后两题也是比较有意思,之后也准备更新atc的比赛题解和洛谷的一些高质量比赛题解(算法网瘾就是想参加各种比赛)   如果觉得有帮助,或者觉得我写的好,......
  • [NOI]2024 登山 题解
    好像在洛谷题解区里还没人和我做法一样,,?考场做法,只用到了倍增和线段树,感觉挺好写。考场上从开题到过题只用了2h。最底下有省流版(?)。以下是我考场里比较详细的思路,所以比较长。先考虑如何\(O(n^2)\)做,然后再想优化。容易先想到一个状态数是\(O(n^2)\)的DP,即记录起点,并将向......
  • AGC002 题解
    目录A-RangeProductB-BoxandBallC-KnotPuzzleA-RangeProduct分情况讨论:\(a\le0\leb\)时,乘积一定为\(0\);否则:\(0<a\leb\)时,乘积一定为正;否则,负数的个数有\(b-a+1\)个,判断这个数是否为奇数,若是,乘积为负,否则为正。#include<bits/stdc++.h......
  • P10423题解
    P10423[蓝桥杯2024省B]填空问题先贴上答案#include<iostream>usingnamespacestd;intmain(){stringans[]={"1204","1100325199.77",};charT;cin>>T;cout<<ans[T-'A']......
  • P10155题解
    1题意给定一个排列ppp,每次可以选择一个数pi......
  • AT_abc027_b题解
    说明需要掌握贪心算法。这么简单为什么是黄题啊?题意给定一个长度为的非负整数序列,你可以进行若干次操作,每次操作都可以选择一个长度为的子串,花费的代价,将其中的每个数都变成该子串的平均值,现在你必须将每个数都变成相同的,你必须同时保证每个数为非负整数。分析先算......
  • 题解:「ROI 2017 Day 2」存储器
    题目信息题目链接LuoguP10653、LOJ2770题目描述给定一个字符串\(S\),设其长度为\(n\),每个字符要么是+要么是-。定义一个片段为\(S\)的一个子串\(S[l,r]\)满足下面三个条件:\(l=1\)或者\(S_{l-1}\neS_l\)。\(r=n\)或者\(S_{r+1}\neS_r\)。\(S_l=S_{l+1}=......
  • P6218 [USACO06NOV] Round Numbers S 题解
    题面题目传送门如果一个正整数的二进制表示中,00的数目不小于11的数目,那么它就被称为「圆数」。例如,99的二进制表示为10011001,其中有22个00与22个11。因此,99是一个「圆数」。请你计算,区间[l,r][l,r]中有多少个「圆数」。前置芝士1.数位dp相关的题:P4317花神......
  • [题解]UVA1127 Word Puzzles
    UVA1127WordPuzzles我们对模式串建立AC自动机,然后就比较板子了,只需要把\(8\)个方向都跑一遍匹配就可以了。时间复杂度是\(O(T\times8nm)\)。注意输入是大写字母。点击查看代码#include<bits/stdc++.h>#defineK1010//模式串个数&矩阵长宽#defineN1000010//节点个......