[数据结构与算法]Codeforces Global Round 15

A - Subsequence Permutation

题意

问要最少选择多少个字符在选择的区域内排序使得排完序之后成为字典序

题解

我们可以对所有的字符进行排序，在于原来的进行比较，那么原本就成为答案的位置就不需要动了，只需要选择原来不在答案上的就可以

Code

// Problem: A. Subsequence Permutation
// Contest: Codeforces - Codeforces Global Round 15
// URL: https://codeforces.com/contest/1552/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Edited on 2021-08-02 17:54:16

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int T;
int n;
char s[50];
char ss[50];

int main(){
	cin >> T;
	while(T--){
		cin >> n;
		scanf("%s", s + 1);
		
		
		for(int i = 1; i <= n; i++){
			ss[i] = s[i];
			// cout << ss[i];
		}
		// cout << Endl;
		
		sort(ss + 1, ss + 1 + n);
		int ans = 0;
		for(int i = 1; i <= n; i++){
			if(ss[i] != s[i]){
				ans ++;
			}
		}
		
		cout << ans << endl;
	}
	return 0;
}

B - Running for Gold

题意

题意很长，简单来说就找一个“最强”的来当冠军

题解

如果存在，就跟我们在学语法的时候储存最大值就是一个做法

当出现矛盾的时候呢？即答案要是-1呢？

就如样例给的那个-1的那个样例

构成了一个三角克制的关系

我们如果先确定好一个基准，如果根据这个基准得到的答案是正确的答案，那么显然无论从以哪个为基准，正解一定就是刚才求出那个答案，不存在顺序的问题。

如果存在有方向的克制关系，就以样例为举例来说，以1位基准，从2到n，第二个比第一个差，第三个比第一个好，那么得到的答案是3，但是2比3好这显然也是不合理的；以n为基准，从n-1到1，那么按照刚才那个做法来计算答案，答案应该是1。所以说，只要存在环装的矛盾结构，以不同的基准来得到答案结果应该是不一样的

Code

// Problem: B. Running for Gold
// Contest: Codeforces - Codeforces Global Round 15
// URL: https://codeforces.com/contest/1552/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Edited on 2021-08-02 17:54:20

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

int T;
int n;
int r[50010][10];

int main(){
	cin >> T;
	while(T--){
		
		cin >> n;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= 5; j++){
				cin >> r[i][j];
			}
		}
		
		if(n == 1){
			cout << 1 << endl;
			continue;
		}
		
		int ans = 1;
		
		for(int i = 2; i <= n; i++){
			int cnt = 0;
			for(int j = 1; j <= 5; j++){
				if(r[i][j] < r[ans][j]){
					cnt++;
				}
			}
			if(cnt >= 3){
				ans = i;
			}
		}
		
		int backup = ans;
		ans = n;
		
		for(int i = n - 1; i >= 1; i--){
			int cnt = 0;
			for(int j = 1; j <= 5; j++){
				if(r[i][j] < r[ans][j]){
					cnt++;
				}
			}
			if(cnt >= 3){
				ans = i;
			}
		}
		
		if(ans != backup){
			cout << -1 << endl;
		}
		else cout << ans << Endl;
	}
}

C - Maximize the Intersections

题意

在圆上给定2n个点，k条已经连好的边；每个点只能用一次，也就是只能作为一条边的顶点，问剩下的 2*(n - k) 个点怎么连使得最后交点个数最多，最多是多少

思路

大佬都说这是结论题，愣是看了三份题解才看懂

我们首先考虑怎么才能判断两个线是不是相交呢？

这个也没有什么可以证的，如果遇到这种问题应该首先多画图找找规律，我这里直接放代码理解了，建议看完画图验证一下

int xj(PII x, PII y){
	if(x.x > y.x) swap(x, y);
	return x.y > y.x && x.y < y.y;
}

那么剩下的没有用过的点，我们考虑他们的相对位置，也就是剩下的点本质上我们让他交点个数最大就可以保证最后的交点个数最多，也就是成为一个星形的结果是最大的，证明星形可以去看官方的题解，我不是很能看懂但我觉得星型是对的。（不用考虑原来已经给出的，因为从给出的线 中的交点数已经固定好了。）

那么怎么构造星型呢？画图可以得出来，当有2n个点的时候，构成的点对是 (i, i + n) 的时候是星形的。那么还有2(n - k)个点，就是(i, i + n - k)

Code

// Problem: C. Maximize the Intersections
// Contest: Codeforces - Codeforces Global Round 15
// URL: https://codeforces.com/contest/1552/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Edited on 2021-08-02 17:54:23

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"
#define x first
#define y second
#define pb push_back

using namespace std;

typedef pair<int, int> PII;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int T;
int n, k;
bool vis[510];
vector<PII> save;
vector<int> unsave;

int xj(PII x, PII y){
	if(x.x > y.x) swap(x, y);
	return x.y > y.x && x.y < y.y;
}

int main(){
	cin >> T;
	while(T--){
		cin >> n >> k;
		for(int i = 1; i <= k; i++){
			int a, b;
			cin >> a >> b;
			
			if(a > b) swap(a, b); // 统一格式，方便处理
			
			vis[a] = 1;
			vis[b] = 1;
			
			save.pb({a, b});
		}
		
		for(int i = 1; i <= 2 * n; i++){ // 找出没有用过的点
			if(!vis[i]) unsave.pb(i);
		}
		
		for(int i = 0; i < n - k; i++){ //  把新的要连线的点连起来
			save.pb(make_pair(unsave[i], unsave[i + n - k]));
		}
		
		int ans = 0;
		
		for(int i = 0; i < n; i++){ // 统计答案
			for(int j = i + 1; j < n; j++){
				ans += xj(save[i], save[j]);
			}
		}
		
		cout << ans << Endl;
		
		save.clear();
		unsave.clear();
		memset(vis, 0, sizeof(vis));
	}
}

D 待补