2019 ICPC徐州网络赛 题解

已过题：A.B.C.D.E.G.K

终于拿到一次出线名额
网络赛的各位越来越猛

C.Buy Watermelon

前期一直卡 看不懂题意

#include<bits/stdc++.h>
using namespace std;
int main() {
	int w;
	cin>>w;
	if(w % 2 == 0 && w != 2) {
		puts("YES");
	} else
		puts("NO");
	return 0;
}

B. so easy

用unorderd_map + 并查集的写法
每次删除一个位置就给map加一个映射，如果当前查询的位置是被映射过了，则删除映射的位置

unorderd_map的存取查询操作都近似于 $O\left(1\right)$O(1),map是带 $log$log的，而且1e6太大，map会T

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
unordered_map<int, int> mapp;
int find(int x){
	if(mapp.find(x) == mapp.end()){
		return x;
	}else {
		return find(mapp[x]);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q, op, x;
	cin>>n>>q;
	while(q--){
		cin>>op>>x;
		if(op == 1){
			mapp[x] = x+1;
		}else {
			cout<<find(x)<<endl;
		}
	}
	return 0;
}

E. XKC’s basketball team

先对数组每个元素和每个元素+m 进行排序，离散化,并且去重
然后开一个数组标记一下每个元素在值递增的情况下，位置也递增的最大值
然后 $O\left(n\right)$O(n)得出所有答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;

int w[maxn], num[maxn], W[maxn];
vector<int> v;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		v.push_back(w[i]);
		W[i] = w[i] + m;
		v.push_back(w[i] + m);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1; i <= n; i++) {
		w[i] = lower_bound(v.begin(), v.end(), w[i]) - v.begin() + 1;
		W[i] = lower_bound(v.begin(), v.end(), W[i]) - v.begin() + 1;
	}
	for(int i = 1; i <= v.size(); i++) {
		num[i] = 0;
	}
	for(int i = n; i >= 1; i--) {
		num[w[i]] = max(num[w[i]], i);
	}
	int maxx = 0;
	for(int i = v.size(); i >= 1; i--) {
		maxx = max(maxx, num[i]);
		num[i] = max(num[i], maxx);
	}
	for(int i = 1; i <= n; i++) {
		if(i != 1) {
			printf(" ");
		}
		int tmp = num[W[i]];
		if(tmp <= i) {
			printf("-1");
		} else {
			printf("%d", tmp - i - 1);
		}
	}
	return 0;
} 

D. Carneginon

玄学过题

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5+5;
char s[maxn], t[maxn];
int main() {
	int n, q;
	scanf("%s", &t);
	n = strlen(t);
	scanf("%d", &q);
	while(q--){
		scanf("%s", &s);
		int len  =strlen(s);
		if(n > len){
			if(strstr(t, s)){
				puts("my child!");
			}else {
				puts("oh, child!");
			}
		}else if(n < len) {
			if(strstr(s, t)){
				puts("my teacher!");
			}else {
				puts("senior!");
			}
		}else {
			if(strcmp(s, t)){
				puts("friend!");
			}else {
				puts("jntm!");
			}
		}
	}
	return 0;
}

K. Center

既然要中心对称，那么中心一定在某两个点所连的线的中点或者某个点上，于是我用一个map记录点及任意两个点的重复次数最多次的那个点从而得出答案，有个小细节的判断需要特判一下，判断最大次数的位置在给出的点上还是在中点上

#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> ss;
pair<int, int> p[1005];
int maxx;
bool f;
void check(int ans, int i, int j){
	if(i == j){
		if(maxx < ans){
			maxx = ans;
			f = 1;
		}
	}else {
		if(maxx <= ans){
			maxx = ans;
			f = 0;
		}
	}
} 
int main() {
	int n;
	scanf("%d", &n);
	int x, y;
	for(int i = 0; i < n; i++) {
		scanf("%d %d", &x, &y);
		p[i].first = 2*x;
		p[i].second = 2*y;
	}
	f = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			pair<int, int> tmp = make_pair((p[i].first + p[j].first)/2, (p[i].second + p[j].second)/2);
			if(ss.find(tmp) == ss.end()) {
				ss[tmp] = 1;
				check(ss[tmp], i, j);
			} else {
				ss[tmp]++;
				check(ss[tmp], i, j);
			}
		}
	}
	int q = n-2*maxx;
	if(f == 1){
		q++;
	}
	printf("%d\n", q);
	return 0;
}