首页 > 其他分享 >CodeForces 1508D Swap Pass

CodeForces 1508D Swap Pass

时间:2023-07-03 20:12:35浏览次数:47  
标签:typedef int CodeForces long find maxn Pass 1508D id

洛谷传送门

CF 传送门

先忽略掉所有 \(a_i = i\) 的点。

考虑我们钦定一个点 \(s\),每次与 \(a_s\) 换直到 \(a_s = s\) 为止。不难发现这样相当于在置换环上删掉 \(a_s\) 这个点。这样可以解决 \(s\) 所在的环。

问题是可能会形成很多个环。

我们把其他点按照 \(s\) 极角排序,注意此处 \(s\) 应选取横坐标最小的点,作用是保证不存在两点夹角 \(> \pi\)。排序后如果相邻的点不在同一个连通块就交换它们。容易发现对于不在同一个置换环上的两个点,交换它们的 \(a_i\) 相当于合并这两个环。

交换完一遍后容易发现只存在一个大的置换环。然后我们就做一遍开头所述算法即可。

使用并查集维护连通性即可。

code
// Problem: D. Swap Pass
// Contest: Codeforces - Codeforces Round 715 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1508/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 2020;

ll n, fa[maxn], d[maxn];
struct node {
	ll x, y, id;
	db ang;
} a[maxn], b[maxn], c[maxn];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		fa[x] = y;
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld%lld", &c[i].x, &c[i].y, &d[i]);
		c[i].id = i;
		fa[i] = i;
	}
	for (int i = 1; i <= n; ++i) {
		merge(i, d[i]);
	}
	int tot = 0;
	for (int i = 1; i <= n; ++i) {
		if (d[i] != i) {
			b[++tot] = c[i];
		}
	}
	if (!tot) {
		puts("0");
		return;
	}
	int p = 1;
	for (int i = 2; i <= tot; ++i) {
		if (b[i].x < b[p].x || (b[i].x == b[p].x && b[i].y < b[p].y)) {
			p = i;
		}
	}
	int tt = 0;
	for (int i = p; i <= tot; ++i) {
		a[++tt] = b[i];
	}
	for (int i = 1; i < p; ++i) {
		a[++tt] = b[i];
	}
	for (int i = 2; i <= tot; ++i) {
		a[i].ang = atan2(a[i].y - a[1].y, a[i].x - a[1].x);
	}
	sort(a + 2, a + tot + 1, [&](node a, node b) {
		return a.ang < b.ang;
	});
	vector<pii> ans;
	for (int i = 2; i < tot; ++i) {
		if (find(a[i].id) != find(a[i + 1].id)) {
			ans.pb(a[i].id, a[i + 1].id);
			swap(d[a[i].id], d[a[i + 1].id]);
			merge(a[i].id, a[i + 1].id);
		}
	}
	while (d[a[1].id] != a[1].id) {
		ans.pb(a[1].id, d[a[1].id]);
		swap(d[a[1].id], d[d[a[1].id]]);
	}
	printf("%d\n", (int)ans.size());
	for (pii p : ans) {
		printf("%d %d\n", p.fst, p.scd);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:typedef,int,CodeForces,long,find,maxn,Pass,1508D,id
From: https://www.cnblogs.com/zltzlt-blog/p/17523876.html

相关文章

  • Codeforces 585D Lizard Era: Beginning
    很容易想到可以对于每个任务选不去的那一个人进行搜索,时间复杂度\(O(3^n)\),明显过不了。发现\(n\le25,\lceil\frac{n}{2}\rceil\le13\),且各个任务间不会互相影响,便可以用折半搜索分成\(2\)部分来搜最后来合并。考虑如何合并两部分,令前一部分得到的值分别为\(a,b,c\),后......
  • Codeforces Round 881 Div2 A-F1题解
    codeforcesround881div2题解马上要秋招了,自己本事全丢了,感觉如果这样的话今年就估计要饿死了。先打div3,7月份得开始收心了A.SashaandArrayColoring题意,可以分任意组,每组的贡献是max-min,问最大贡献显然是贪心,从大到小配对一下就行,不想放代码了’B.LongLong给出一......
  • appassembler-maven-plugin useAllDependencies
    http://mojo.codehaus.org/appassembler/appassembler-maven-plugin/assemble-mojo.htmlThefollowingcanbeusedtouseallprojectdependenciesinsteadofthedefaultbehaviorwhichrepresentsruntimedependenciesonly.forgoal:assembleitcanaddothersc......
  • Codeforces Round #877 (Div. 2) A-E
    A代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;boolsolve(){intn;cin>>n;intmx=-2e9,mi=2e9;for(inti=1;i<=n;i++){intx;cin>>x;mi=min(x,mi);......
  • Educational Codeforces Round 151 (Rated for Div. 2)
    Preface期末考终于结束了,终于可以回来写题了这场是刚考完最后一门的那个晚上打的,因为太久没有写代码了所以不是很熟练而且脑子也不太灵光,只能堪堪写到D题而且手速感人上次CF第二个号因为Rating被roll了导致从紫名掉下来了,这场就把它又打上去了,再这样后面兴许要用第三个号打了......
  • Educational Codeforces Round 151 [div.2 #A-C] 赛后总结(contest/1845)
    link\(\textcolor{lightgreen}{A}-\textcolor{yellow}{B}-\textcolor{yellow}{C}-\textcolor{red}{D}-\textcolor{red}{E}-\color{red}{F}\)A给你一个数n,在给你一个数列1~k,其中x不能用,然后用其他的数任意累加,如能得到n,输出所用数字数量和具体数列。一眼分类。先分是......
  • nginx之proxy_pass规则详解
    在nginx中配置proxy_pass代理转发时,如果在proxy_pass后面的url加/,表示绝对根路径;如果没有/,表示相对路径,把匹配的路径部分也给代理走。假设下面四种情况分别用http://192.168.1.1/proxy/test.html进行访问。第一种:location/proxy/{proxy_passhttp://127.0.0.1/;}代......
  • CodeForces 高分段 dp 选做
    选取方式:CF*3000+按通过人数排序。CF1188DMakeEqual记\(cnt(x)\)表示\(x\)二进制下\(1\)的个数,题目等价于求\(x\)使得\[\sum_{x=1}^ncnt(x+a_n-a_i)\]最小。令\(a_i=a_n-a_i\)。从低位到高位考虑,假设当前要决策第\(k\)位,我们需要知道:\(1.\)\(x\)......
  • Educational Codeforces Round 151 F. Swimmers in the Pool
    一.前言本来打算打打这个比赛玩玩,结果同学找我打游戏王去了,就没打现场(逃)因为是一道不错的数学题,来写写补题的题解这里点名批评@HOLIC喂给我的假题意,让我查错大半天,最后发现题意错了还重新推了好多东西,拳头都硬了等会儿顺便分享下假题意的一种做法二.正文简单题意:有n个......
  • CodeForces 1845C Strong Password
    洛谷传送门CF传送门我怎么这么多天没写题解了,快来水一篇。考虑对\(s\)串建子序列自动机后dp。设\(n=|s|\)。建子序列自动机,就是求出\(nxt_{i,j}\)为\([i,n]\)中第一个等于\(j\)的位置,不存在则\(nxt_{i,j}=n+1\)。然后我们设\(f_{i,j}\)为填到密码的......