首页 > 其他分享 >CF1867D Cyclic Operations

CF1867D Cyclic Operations

时间:2023-09-12 12:24:35浏览次数:35  
标签:CF1867D Operations Cyclic int top 100005 ++ dfn low

前言

赛时没调出来,赛后调了一个上午,最后发现是有个地方没清零。

思路

首先对于位置 \(i\),我们必须要保证进行的操作中,最后一次出现 \(i\),\(i\) 的后面一定是 \(a_i\)。

那么我们考虑统计所有位置上的要求,用有向边链接,那么就会出现一个有环有向图(一定有环,因为点数等于边数)。

那么,自然想到缩点。

首先,如果有某个环的长度不为 \(k\)(不讨论长度为 \(1\) 的情况),那么一定无解,因为总会剩几个点没办法改,或者为了改最后几个点而导致把最开始的点改了,自己手玩一下应该很好理解。

那么还有不构成环的,也可以理解成长度为 \(1\) 的情况,我们可以先满足这些边的要求,这样可能会使得环内得答案不正确,但是我们可以最后再处理环,把之前错误的答案改正确。

所以做法就出来了,先建图,然后 tarjan 缩点,统计每个环的长度,长度要么为 \(k\),要么为 \(1\),如果存在不是 \(k\) 也不是 \(1\) 肯定无解,然后再统计长度为 \(k\) 的个数,如果没有也肯定无解,否则就是有解。

另外,还有 \(k=1\) 的特殊情况,这种情况,必须满足 \(a_i=i\),也就是它只能每次选一个值 \(l\),那必定是把 \(a_l\) 改成 \(l\),所以必须满足上述条件。

\(k\neq1\) 则必须满足 \(a_i\neq i\),因为 \(l\) 互不相同。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,k,a[100005],e[100005],ne[100005],h[100005],num,idx=1,dcnt,siz[100005],dfn[100005],low[100005],z[100005],top,in_z[100005],ff,flag;
inline void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u)
{
	dfn[u]=low[u]=++dcnt,in_z[u]=1,z[++top]=u;
	for(int i=h[u];i;i=ne[i])
	{
		if(!dfn[e[i]]) dfs(e[i]),low[u]=min(low[u],low[e[i]]);
		else if(in_z[e[i]]) low[u]=min(low[u],dfn[e[i]]);
	}
	if(dfn[u]==low[u])
	{
		++num;
		while(z[top+1]!=u) in_z[z[top--]]=0,++siz[num];//因为这个写法,可能和上一次的进栈的元素相同,导致错误,所以要初始化z数组。
	}
}
inline bool sol()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n+1;++i) z[i]=siz[i]=h[i]=dfn[i]=0;//因为判断是z[top+1],所以要多预处理一位
   //奇怪的是,我在洛谷这么写都没错,难道是洛谷没卡这种情况?
	idx=1,num=flag=dcnt=top=0;
	if(k==1)
	{
		for(int i=1;i<=n;++i) scanf("%d",&a[i]);
		for(int i=1;i<=n;++i) if(i!=a[i]) return 0;
		return 1;
	}
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i) if(i==a[i]) return 0;else add(i,a[i]);
	for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i);
	for(int i=1;i<=num;++i)
	{
		if(siz[i]!=1&&siz[i]!=k) return 0;
		if(siz[i]==k) flag=1;
	}
	return flag;
}
int main()
{
	scanf("%d",&T);
	while(T--)
		if(sol()) puts("YES");
		else puts("NO");
	return 0;
}
 

标签:CF1867D,Operations,Cyclic,int,top,100005,++,dfn,low
From: https://www.cnblogs.com/One-JuRuo/p/17695827.html

相关文章

  • AtCoder Beginner Contest 292 D - Unicyclic Components
    D-UnicyclicComponents原题链接题意:判断一个连通块的边和点个数是否相同思路:对它使用并查集吧点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=200010,M=N<<1;//维护连通图中点和边的个数intsd[N],se[N],p[N];boolf[N];//谁是祖宗int......
  • CyclicBarrier、CountDownLatch和Semaphore区别
    CyclicBarrier、CountDownLatch和Semaphore都是Java并发编程中常用的同步工具,它们在功能和使用方式上有一些区别。CyclicBarrier:CyclicBarrier用于多个线程之间互相等待,直到所有线程都到达某个屏障点后才继续执行。CyclicBarrier可以重复使用,每次到达屏障时,它的计数器会自动......
  • CyclicBarrier和CountDownLatch的区别
    引言在并发编程中,CyclicBarrier和CountDownLatch是两个常用的同步工具类。它们都可以用于线程之间的等待和协调,但在使用方式和功能上有一些区别。本文将深入探讨CyclicBarrier和CountDownLatch的区别,并给出相应的代码示例。CyclicBarrier和CountDownLatch简介CyclicBarrierCycl......
  • LLMOps(Large Language Model Operations)简介
    LLMOps是一个新兴领域,专注于管理大型语言模型的整个生命周期,包括数据管理、模型开发、部署和伦理等方面。HuggingFace、Humanloop和NVIDIA等公司正在引领这一领域的发展。HuggingFace的Transformers库已成为构建和微调各种NLP任务的大型语言模型的首选开源库。类似地,Humanloop......
  • swagger显示示No operations defined in spec的解决
    背景:Spring2.6集成swagger2.0,启动后访问:http://localhost:80/swagger-ui/index.html,报错:Nooperationsdefinedinspec!查询资料的好几种结果:1.swagger解析的包路径配置错误,需要修改basePackage路径,反复查看是正确的。2.扫描的类或者方法上没有配置:@APIZ或者@ApiOpera......
  • AGC063C Add Mod Operations
    感觉是非常纯的思维题。题意给两个长度为\(n\)的序列\(A,B\)。你可以对\(A\)做不超过\(n\)次操作,形如对于所有元素,先加上\(x\)再对\(y\)取模。其中\(0\lex<y\le10^{18}\)是由你决定的任意整数。给出一种方案将\(A\)变成\(B\),或声明无解。\(1\len\le200......
  • Perkins Engines: Reliable Power in Harsh Environments and High-Strength Operatio
    PerkinsEngines:ReliablePowerinHarshEnvironmentsandHigh-StrengthOperationsHelloeveryone!TodayIwouldliketosharewithyouapowerfulenginedesignedtocopewithharshenvironmentsandhigh-intensityworkingconditions-thePerkinsengine.W......
  • P8271 [USACO22OPEN] COW Operations S 奶牛操作
    P8271[USACO22OPEN]COWOperationsS奶牛操作目录P8271[USACO22OPEN]COWOperationsS奶牛操作[USACO22OPEN]COWOperationsS题目描述输入格式输出格式样例#1样例输入#1样例输出#1提示分析code[P8271USACO22OPEN]COWOperationsS-洛谷|计算机科学教育新生态(......
  • Java高并发之CyclicBarrier简介(转)
    原文:https://juejin.cn/post/7209617649885184058作者:xindoo来源:稀土掘金  Java中的CyclicBarrier是一种同步工具,它可以让多个线程在一个屏障处等待,直到所有线程都到达该屏障处后,才能继续执行。CyclicBarrier可以用于协调多个线程的执行,以便它们可以在某个点上同步执行......
  • 使用Java线程同步工具类CyclicBarrier
    如何使用java.util.concurrent.CyclicBarrier是Java并发并发编程中的线程同步工具类,基于java.util.concurrent.locks.ReentrantLock实现。CyclicBarrier工具类主要应用在如下场景:让一组线程同时到达栅栏位置才能开始执行。应用示例:publicstaticvoidmain(String[]args){......