首页 > 其他分享 >solution-2022 CCPC Guilin J. Permutation Puzzle

solution-2022 CCPC Guilin J. Permutation Puzzle

时间:2024-08-21 15:05:55浏览次数:9  
标签:ch const int MAX Puzzle Guilin solution long define

题解:2022 CCPC 桂林站 J 题题解

模拟赛 T3 放了这道题人均场切了。我没删调试爆零了。

首先按所有限制连边 \(u_i \to v_i\)。题目保证了这是一张有向无环图。

我们肯定是只能按照某种拓扑序来填。

有一个非常显然的策略是在拓扑排序中按照每个点的后继节点的最小值为第一关键字,更小的先填。

这非常符合直觉,也确实是对的。因为无论如何你都要在当前最小值之前到那。

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e5 + 10;

vector <int> g[MAX];
vector <int> g2[MAX];
bool vis[MAX];
int a[MAX];

void dfs(int u){
	vis[u] = 1;
	for(int v : g[u]){
		if(!vis[v])	dfs(v);
		a[u] = min(a[u], a[v]);
	}
}

int deg[MAX];
int deg2[MAX];
int b[MAX];
int to[MAX];
bool fl[MAX];

void solve(){
	int n = read(), m = read();
	for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
	for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
	for(int i = 1; i <= n; i++){
		a[i] = read();
		if(a[i] == 0)	a[i] = inf;
		else b[i] = a[i], to[a[i]] = i;
	}
	for(int i = 1; i <= m; i++){
		int u = read(), v = read();
		g[u].pb(v);
		g2[v].pb(u);
		deg[v]++;
		deg2[u]++;
	}
	queue <int> que2;
	for(int i = 1; i <= n; i++){
		if(!deg2[i])	que2.push(i);
	}
	while(!que2.empty()){
		int u = que2.front();
		que2.pop();
		for(int v : g2[u]){
			deg2[v]--;
			a[v] = min(a[v], a[u]);
			if(!deg2[v])	que2.push(v);
		}
	}
	// for(int i = 1; i <= n; i++){
		// write(a[i]), put();
	// }endl;
	
	priority_queue <pair <int, int> > que;
	
	// write(deg[13]), endl;
	// for(int v : g[13]){
		// write(a[v]), endl;
	// }
	
	for(int i = 1; i <= n; i++){
		// if(b[i] == 700){
			// write(a[13]), endl;
			// for(int v : g2[i])	write(v), put();
			// endl;
		// }
		if(!deg[i]){
			
			if(b[i] == a[i]){
				// if(b[i] == 700)	puts("fjk");
				// write(g[i] == 700)	puts("kf");
				fl[b[i]] = 1;
			}else que.push(make_pair(-a[i], i));
		}
	}
	// write(que.top().first), endl;
	for(int i = 1; i <= n; i++){
		if(to[i]){
			if(!fl[i]){
				// write(i), endl;
				puts("-1");
				
				for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
				for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
				return ;
			}	
			if(!que.empty() and -que.top().first <= i){
				puts("-1");
				
				for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
				for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
				// write(i), put();
				return ;
			}	
			int u = to[i];
			b[u] = i;
			for(int v : g[u]){
				deg[v]--;
				if(!deg[v]){
					if(a[v] == b[v]){
						fl[b[v]] = 1;
					}else{
						que.push(make_pair(-a[v], v));
					}
				}
			}
		}else{
			if(que.empty())	{
				
				puts("-1");
				for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
				for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
				return ;
			}
			int u = que.top().second;
			b[u] = i;
			que.pop();
			for(int v : g[u]){
				deg[v]--;
				if(!deg[v]){
					if(a[v] == b[v]){
						fl[b[v]] = 1;
					}else{
						que.push(make_pair(-a[v], v));
					}
				}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		write(b[i]), put();
	}
	endl;
}

signed main(){
	// freopen("permutation.in", "r", stdin);
	// freopen("permutation.out", "w", stdout);
	int t = read();
	while(t--)	solve();
	return 0;
}

标签:ch,const,int,MAX,Puzzle,Guilin,solution,long,define
From: https://www.cnblogs.com/WRuperD/p/18371659

相关文章

  • [题解]UVA1127 Word Puzzles
    UVA1127WordPuzzles我们对模式串建立AC自动机,然后就比较板子了,只需要把\(8\)个方向都跑一遍匹配就可以了。时间复杂度是\(O(T\times8nm)\)。注意输入是大写字母。点击查看代码#include<bits/stdc++.h>#defineK1010//模式串个数&矩阵长宽#defineN1000010//节点个......
  • 【题解】Solution Set - NOIP2024集训Day10 树的直径、重⼼、中⼼
    【题解】SolutionSet-NOIP2024集训Day10树的直径、重⼼、中⼼https://www.becoder.com.cn/contest/5464「CF516D」DrazilandMorningExercise首先,我们可以换根求出所有点的\(f\)。然后不会了……思考一下,一条直径提供的到底时什么。实际上,一条直径上的点取到\(f\)......
  • Solution - Atcoder ARC171D Rolling Hash
    对于这个\(\operatorname{hash}(A_L,\cdots,A_R)\),一个比较经典的想法是做差分,即令\(s_i=\sum\limits_{j=1}^iA_jB^{i-j}\)。于是\(\operatorname{hash}(A_L,\cdots,A_R)=s_R-s_{L-1}\timesB^{R-L+1}\not=0\)。那么也就是\(s_R\not=s_{L-1}\ti......
  • 杂题 Solution 速通 #1
    [ICPC2021NanjingR]AncientMagicCircleinTeyvat设\(f_x\)表示钦定至少有\(x\)条边的四元子图个数,由容斥我们有一条边都没有的子图个数是\(f_0-f_1+f_2-f_3+f_4-f_5+f_6\),而所有边都有的个数就是\(f_6\)。作差之后只需要求\(f_0,f_1,f_2,f_3,f_4,f_5\)。子图计数只......
  • Solution - Atcoder ABC155F Perils in Parallel
    首先可以按\(a_i\)排序,对于区间\([l_i,r_i]\)可以通过二分确定实际影响到的\(b_i\)的区间。考虑到区间\(i\in[l,r]\)的\(b_i\)都取反影响到的元素过多,考虑去减少影响到的元素。于是可以想到令\(c_i=b_i\oplusb_{i-1}\),那么对于区间\([l,r]\)操作实际影响......
  • 159.302 The 8-Puzzle: Search Algorithms
    159.302ArtificialIntelligenceAssignment#1The8-Puzzle:SearchAlgorithmsMaximumnumberofmemberspergroup:3studentsDeadlineforsubmission:9thofSeptemberInstructionsYourtaskistowriteaC++programthatwillsolvethe8-puzzleprob......
  • 杂题 Solution 速通 #1
    [ICPC2021NanjingR]AncientMagicCircleinTeyvat设\(f_x\)表示钦定至少有\(x\)条边的四元子图个数,由容斥我们有一条边都没有的子图个数是\(f_0-f_1+f_2-f_3+f_4-f_5+f_6\),而所有边都有的个数就是\(f_6\)。作差之后只需要求\(f_0,f_1,f_2,f_3,f_4,f_5\)。子图计数只......
  • 【题解】Solution Set - NOIP2024集训Day2 线段树
    【题解】SolutionSet-NOIP2024集训Day2线段树https://www.becoder.com.cn/contest/5431「CF1149C」TreeGenerator™结论:对于括号序列的一个子段,删去所有的匹配括号之后,剩下的不匹配的括号,按顺序构成树上的一条路径。Why?从括号序列的构造出发。每次(相当于开始遍历......
  • 【题解】Solution Set - NOIP2024集训Day1 数据结构
    【题解】SolutionSet-NOIP2024集训Day1数据结构https://www.becoder.com.cn/contest/5429「CF1428F」FruitSequences线段树是可以维护区间最长子段的1。记固定右端点在\(i\),的答案为\(f_i\)。那么:\(a_i=0\),\(f_i=f_{i-1}\);\(a_i=1\),打一个单调栈维护所有的最长子......
  • 24-MX-WF day 1 contest solution
    赛时:\(70+50+0+20=140\)\(pts\)题目链接\(A\)\(ball\)首先最朴素的思路肯定是暴力,\(70\)\(pts\)拿下。代码实现#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e7+5;lln,m;lla[N];intmain(){ cin>>n>>......