2020-10-01

2018-2019 ICPC Northwestern European Regional Programming Contest (NWERC 2018)

字数统计: 4k字 | 阅读时长: 20分

solved	A	B	C	D	E	F	G	H	I	J	K
8 / 11	Ø	Ø	Ø	·	·	·	Ø	O	O	Ø	O

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

总结：

反向思维。B题是一个简单的拓扑排序，如果能想到反向建图，那就是一道裸题。当然正向建图也只要加一个dfs，只能怪自己太菜。
读题速度。K题时做出来人数最多的，但是我们花了很久很久很久很久很久才看懂。英语水平有待提高。

比赛链接

A. Access Points

solved by Sstee1XD.(-)

题意： 给你n个网点的坐标，你要放n个横纵坐标都不为降序的点，与对应的网点连线，求最短距离平方和。

题解： 题目的意思可以写成这样的数学公式。

\sum_{i=1}^n {(X_i - x_i)^2} + \sum_{i=1}^n {(Y_i - y_i)^2}

所以就分解成了横纵坐标的两个子问题，我们接下来以横坐标为例。
如果网点的各个横坐标也是非降序的，那么每个点就安排到网点上，距离和就为 $0$ 。如果有两个点，后面的点的坐标比前面的小，这时发现两个点重合才能让距离和最小。我们土想一下，觉得取两个值的中间值能让距离和最小。在数理上，我们设重合点的坐标为d，网点的坐标为 $X_1，X_2$ ，那么他们的距离平方和为 ${(X_1 - d)}^2$ + ${(X_2 - d)}^2$ 。因为 $X_1，X_2$ 已知，我们可以看成一个一元二次方程，易得当 $d = \frac{(X_1 + X_2)}{2}$ 时取得最小值。推广到一般式，设总共有n个数字，得 $d=\frac{\sum_{i=1}^n{(X_i)}}{n}$ ，证明猜想正确。
接下来我们只用判断后面的网点的坐标是否比前一个坐标小就行了。如果小，就进行合并操作。同时注意到一次可能会向前合并多个点，所以维护一个单调栈。判断坐标大小时，用 $\frac{坐标和}{合并的点的数量}$ 进行比较，稍微做下乘法减小误差即可。

AC代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1e5 + 7;
 
#define fi first
#define se second
typedef long long ll;
 
template<class T> inline int read(T &x) {
    int f = 0;x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if (f) x = -x;
    return x;
}
 
int n, x[maxn], y[maxn];
double ans;
 
void gao(int a[]) {
    stack<pair<ll, int>> st;
    st.push({a[1], 1});
    for (int i = 2; i <= n; ++i) {
        ll s = a[i];
        int num = 1;
        while (!st.empty() && st.top().fi * num >= st.top().se * s) {
            s += st.top().fi;
            num += st.top().se;
            st.pop();
        }
        st.push({s, num});
    }
    for (int i = n; i >= 1; --i) {
        double ave = double(st.top().fi) / st.top().se;
        int num = st.top().se;
        st.pop();
        while (num--) {
            ans += (ave - a[i]) * (ave - a[i]);
            i--;
        }
        i++;
    }
}
 
void solve(){
    for (int i = 1; i <= n; ++i) read(x[i]), read(y[i]);
    gao(x);
    gao(y);
    printf("%.8f\n", ans);
}
 
int main() {
    read(n);
    solve();
    return 0;
}

B. Brexit Negotiations

solved by lllllan.(-)

题意： 需要开n个会议，一些特定会议开始之前需要先完成别的特定会议，并且在开始之前需要话k分钟总结先前完成的k场会议，每场会议都有原本需要的时长T_i。求单场耗时最长的会议的最小值。

题解： 某些会议必须在完成某些会议之后才能开始，显然是拓扑排序。如果正向建图，肯定会将可以开始的会议中挑选耗时最长的先开始，但是这样的话，可能会碰到一些极端情况无法处理：
第二和第三个会议需要在第一个会议之后，而一到三个会议的耗时分别为1，2， 1。第四个会议需要在第三个会议之后，时长为100。如果按照简单的贪心思想，结束第一个会议之后，会从二三中间选择时间较长的二号会议先开始，而原本耗时最长的四号会议则会被置为最后。

DFS + 拓扑排序： 从入度为零的会议开始dfs，记录每条递归路线之后，出现过的耗时最长的会议。在进行拓扑排序时，若遇到可以同时在多个会议中选择一个先开始，则以这个dfs结果为依据，将存在较大耗时的路线先开始。
反向建图 + 拓扑排序： 如果一开始就建反图，那么几乎就是一道裸题了：

DFS + 拓扑排序

#include<bits/stdc++.h>
#define bug cout << "bug********************************\n"
 
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
 
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
 
const int N = 4e5 + 10;
int tim[N], deg[N], tag[N];
vector<int> V[N];
struct node{
	int id, time, tag;
	node(int a, int b, int c){id = a; time = b; tag = c;}
	bool operator<(const node &A)const{
		if(A.tag == tag)	return A.time > time;
		return A.tag > tag;}
};
priority_queue<node>Q;

int dfs(int u){
	if(tag[u])	return tag[u];
	int ta = tim[u];
	for(int i = 0; i < V[u].size(); i++){
		int v = V[u][i];
		tag[v] = dfs(V[u][i]);
		ta = max(ta, tag[v]);
	}
	return ta;
}

void run(int n){
	int maxt = 0;
	int R = 0;
	for(int i = 1; i <= n; i++)
		if(deg[i] == 0)
			tag[i] = dfs(i);
	for(int i = 1; i <= n; i++)
		if(deg[i] == 0)
			Q.push(node(i, tim[i], tag[i]));
	while(!Q.empty()){
		node s = Q.top(); Q.pop();
		int u = s.id;
		int t = s.time + R;
		R++;
		maxt = max(maxt, t);
		for(int i = 0; i < V[u].size(); i++){
			int v = V[u][i];
			deg[v]--;
			if(deg[v] == 0)	Q.push(node(v, tim[v], tag[v]));
		}
	}
	printf("%d\n", maxt);
}
 
int main(){
	int n = read();
	for(int i = 1; i <= n; i++){
		tim[i] = read();
		int d = read();
		for(int j = 0; j < d; j++){
			int u = read();
			V[u].push_back(i);
			deg[i]++;
		}
	}
	run(n);
	return 0;
}

反向建图 + 拓扑排序

#include<bits/stdc++.h>
#define bug cout << "bug********************************\n"
 
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
 
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
 
const int N = 4e5 + 10;
int tim[N], deg[N];
vector<int> V[N];
struct node{
	int id, time;
	node(int a, int b){id = a; time = b; }
	bool operator<(const node &A)const{
		return A.time < time;}
};
priority_queue<node>Q;
void run(int n){
	int maxt = 0;
	int R = n - 1;
	for(int i = 1; i <= n; i++){
		if(deg[i] == 0)	Q.push(node(i, tim[i]));
	}
	while(!Q.empty()){
		node s = Q.top(); Q.pop();
		int u = s.id;
		int t = s.time + R;
		maxt = max(maxt, t);
		R--;
		for(int i = 0; i < V[u].size(); i++){
			int v = V[u][i];
			deg[v]--;
			if(deg[v] == 0)	Q.push(node(v, tim[v]));
		}
	}
	printf("%d\n", maxt);
}
 
int main(){
	int n = read();
	for(int i = 1; i <= n; i++){
		tim[i] = read();
		int d = read();
		for(int j = 0; j < d; j++){
			int u = read();
			V[i].push_back(u);
			deg[u]++;
		}
	}
	run(n);
	return 0;
}

C. Circuit Board Design

solved by Sstee1XD.(-)

题意： 给你树上点之间的相邻关系，让你安排每个节点的二维坐标，要求每条边边长为 $1$ ，各点各边之间有一定距离。

题解： 因为只有 $1000$ 个点，计算一下把半圆分成 $1000$ 份也是可以的，直接写就行了。注意要半圆，不然极端情况下线会有交叉。

AC代码

#include <bits/stdc++.h>
 
using namespace std;
 
#define pie acos(-1.0) / 1010
 
const int maxn = 1007;
 
int n;
double x[maxn], y[maxn];
vector<int> G[maxn];
int f;
 
int dfs(int u, int fa) {
	for (auto v : G[u]) {
		if (v == fa) continue;
		x[v] = x[u] + cos(f * pie), y[v] = y[u] + sin(f * pie);
		f++;
		dfs(v, u);
	}
	return f + 1;
}
int main(){
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; ++i) {
		printf("%.8f %.8f\n", x[i], y[i]);
	}
}

G. Game Design

solved by Sstee1XD.(-)

题意： 小球在二维坐标系上滚动，遇到障碍物后停止，之后可以转换方向。 $(0,0)$ 点是一个洞，小球滚进去后就不能再移动了。现在给你小球的运动轨迹，请输出一种可能的开始点的坐标，障碍物的数量以及各个障碍物的坐标。

题解： 因为小球滚进洞后就不能移动了，所以最后的答案如果有形如 RLR 之类的三次反复横跳就是不合法的。我们假设小球从 $(0,0)$ 点出发，最后整个运动轨迹进行平移就可以得到答案。我们再假设小球滚动的单位长度为 $dis$ ，如果小球在反复横跳，就不扩大 $dis$ 的距离，否则进行扩大，最后卡出答案。

AC代码

#include <bits/stdc++.h>
 
using namespace std;
 
map<char, int> re;
set<pair<int, int>> st;
int num[2];
char s[30];
 
void Init() {
	re['U'] = 'D', re['D'] = 'U', re['R'] = 'L', re['L'] = 'R';
}
 
void solve() {
	int len = strlen(s);
	if (len >= 3 && re[s[len - 1]] == s[len - 2] && re[s[len - 2]] == s[len - 3]) {
		puts("impossible");
		return;
	}
	int x = 0, y = 0, dis = 5;
	for (int i = 0; i < len; ++i) {
		if (s[i] == 'U') y = dis, st.insert({x, y + 1});
		if (s[i] == 'D') y = -dis, st.insert({x, y - 1});
		if (s[i] == 'R') x = dis, st.insert({x + 1, y});
		if (s[i] == 'L') x = -dis, st.insert({x - 1, y});
		if (s[i + 1] != re[s[i]]) {
			dis += 5;
		}
	}
	printf("%d %d\n", -x, -y);
	printf("%d\n", int(st.size()));
	for (auto v : st) {
		printf("%d %d\n", v.first - x, v.second - y);
	}
}
 
int main() {
	Init();
	scanf("%s", s);
	solve();
}

H. Hard Drive

solved by Sstee1XD.00:40(+2)

题意： 构造一个01序列，其中有b个位置一定为0，其中最后一位一定为0，第一位永远不会一定为0，最终要使这个序列01变换c次。

题解： 若第一位为1，只能提供1次贡献。别的地方只要10这样填就能一个1贡献两次。所以先判断一下c是否为奇数，决定第一位是否为1，然后让c成为偶数填就行了。

AC代码

#include<bits/stdc++.h>
#define bug cout << "bug********************************\n"
 
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
 
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
const int maxn = 5e5 + 7;
int n, c, b;
int a[maxn], bro[maxn];
 
void run(){
	int v;
	for (int i = 1; i <= b; ++i) {
		v = read();
		bro[v] = 1;
	}
	int head = 2;
	if (c & 1) a[1] = 1, c--, head = 3;
	if (!c) return;
	for (int i = head; i <= n; ++i) {
		int len = 0, l = i;
		while (!bro[i] && i <= n) {
			len++;
			i++;
		}
		for (int j = l; j < l + len; j += 2) {
			a[j] = 1;
			c-= 2;
			if (!c) return;
		}
	}
}
 
int main(){
	scanf("%d %d %d", &n, &c, &b);
	run();
	for (int i = 1; i <= n; ++i) printf("%d", a[i]);
	return 0;
}

I. Inflation

solved by Tryna. 0:55(+1)

题意：给出n个容量为1-n的气球和n个含有气体的体积，问在使气球不爆炸的情况下，使每个气球都能填充到最大的体积比。

AC代码

#include<bits/stdc++.h>
#define bug cout << "bug********************************\n"
 
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
 
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
const int maxn = 200010;
int n;
double a[maxn],b[maxn],maxx;
 
int main(){
	scanf("%d",&n);
	int flag = 0;
	for(int i = 1;i <= n;i++){
		scanf("%lf",&a[i]);
		if(a[i] == 0) flag = 1;
		b[i] = i;
	}
	sort(a+1,a+1+n);
	maxx = inf;
	for(int i = 1;i <= n;i++){
		double f = a[i]/b[i];
		if(f>1){
			flag = 2;
			break;
		}
		else{
			if(f < maxx) maxx = f;
		}
	}
	if(flag == 2) printf("-1\n");
	else if (flag == 1) printf("0\n");
	else printf("%.7f\n",maxx);
	return 0;
}

J. Jinxed Betting

solved by Sstee1XD.(-)

题意： 给你 $n$ 个数，第一个数为Julia的积分，其他的为其他人的积分，保证Julia的积分是最大的（并不严格最大）。他们进行betting游戏，赢的人获得一积分。Julia每次选择和除她以外的拥有最高积分的人相同的选项，如果存在多个人，就选择最多人选择的选项，问Julia的积分至少能保持几轮最大。

题解： 我们构造一下发现每次选积分最多的人中的一半的人赢，能让积分增长得最快。设积分最多的人总共有 $n$ 个，那么能在 $log_2(n) + 1$ 次操作后让这群人的积分都增长 $log_2{n}$ 。同时要注意到这时可以让所有剩下的积分不是最高的人都增长积分，并且若积分排名第二的人群与积分第一的人群积分差只有 $1$ 的话，进行完这轮积分增加后就能合并进积分第一的人群，重复操作直至积分超过Julia，即可得到答案。注意要进行一些计算的操作来减少时间复杂度。

AC代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

typedef long long ll;

const int maxn = 1e5 + 7;
int n;
ll a[maxn];

struct Node{
	ll num;
	ll d;
}node[maxn];

void solve() {
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(2 + a, a + n + 1, greater<ll>());
	if (a[1] == a[2]) {
		cout << a[1] - a[3] << endl;
		return;
	}
	int f = 1;
	for (int i = 2; i <= n; ++i) {
		ll cnt = 1;
		while (i < n && a[i] == a[i + 1]) {
			i++;
			cnt++;
		}
		node[f++] = {a[i], cnt};
	}
	ll maxx = a[2], tot = node[1].d, ans = 0, step = 0;
	int nxt = 2;
	while (maxx + log2(tot) <= a[1]) {
		ll go = log2(tot) + 1;
		ll add = log2(tot);
		step += go;
		if (nxt >= f) {
			ll mul = (a[1] - maxx) / add;
			ans += mul * go;
			maxx += mul * add;
			break;
		}	
		ll t = maxx + add - step - node[nxt].num;
		if (t > 0) {
			if (maxx + (t + 1) * add > a[1]) {
				ll mul = (a[1] - maxx) / add;
				ans += mul * go;
				maxx += mul * add;
				break;
			}
			else {
				add += t * add;
				step += go * t;
				go += t * go;
			}
		}
		maxx += add;
		tot += node[nxt++].d;
		ans += go;
	}
	ans += a[1] - maxx;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n;
	solve();
}

K. Kleptography

solved by Tryna. 2:29(+)

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300;
int n,m;
char k[maxn],a[maxn],b[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    cin>>(k + m - n);
    cin>>b;
    for(int i = m - 1;i >= n; i--){
        a[i] = b[i] - k[i] + 'a';
        if(a[i] < 'a') a[i] += 26;
        k[i - n] = a[i];
    }
    cout<<k<<endl;
    return 0;
}