2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20)

按难度排序

F. Icebergs

题意：给定几块不相交的多边形，问面积和。

直接抄板子即可，面积由向量叉乘得到，注意得到的是有向面积，可能为负，要绝对值。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
struct Point{
	double x, y;
	Point(double x = 0, double y = 0) :x(x), y(y) {  }
};
typedef Point Vector;
Vector operator-(Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
Point p[N];
double Poly(Point* p, int n) {
	double ans = 0;
	for (int i = 1; i < n - 1; i++) {
		ans += Cross(p[i] - p[0], p[i + 1] - p[0]);
	}
	return ans / 2;
}
double ans;
int n, m;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &m);
		for (int j = 0; j < m; j++)scanf("%lf%lf", &p[j].x, &p[j].y);
		ans += fabs(Poly(p, m));
	}
	printf("%lld\n", (ll)ans);
	return 0;
}

A. Environment-Friendly Travel

题意：平面上有几个点，要从起点到终点，满足总距离不超过B，每条边有一个单位花费，总花费为每条边的单位花费乘距离，要最小化花费。

直接从起点bfs到终点，不同的是bfs时把距离超过B的去掉，并要使得花费最小，而不是距离最小。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e3 + 10;
int T, n, B;
int d[N][210], sx, sy, dx, dy, x[N], y[N], dis[N][N], c[N], l[N];
struct X
{
	int u, di, w;
	bool operator<(const X& b)const {
		return w > b.w;
	}
};
struct E
{
	int v, t;
};
vector<E>G[N];
int bfs(int s) {
	memset(d, 0x3f, sizeof(d));
	priority_queue<X>q;
	d[s][0] = 0;
	q.push(X{ s,0,0 });
	while (!q.empty()) {
		X tp = q.top(); q.pop();
		int u = tp.u, di = tp.di, w = tp.w;
		if (w > d[u][di])continue;
		if (u == n + 1)return w;
		for (E& e : G[u]) {
			int ndi = di + dis[u][e.v], nw = w + dis[u][e.v] * c[e.t];
			if (ndi > B)continue;
			if (d[e.v][ndi] > nw) {
				d[e.v][ndi] = nw;
				q.push(X{ e.v,ndi,nw });
			}
		}
	}
	return -1;
}
int dist(int xi, int yi, int xj, int yj) {
	return (int)ceil(sqrt(1.0*(xi - xj)*(xi - xj) + 1.0*(yi - yj)*(yi - yj)));
}
int main() {
	scanf("%d%d%d%d%d%d%d", &sx, &sy, &dx, &dy, &B, &c[0], &T);
	for (int i = 1; i <= T; i++)scanf("%d", &c[i]);
	scanf("%d", &n);
	x[n] = sx, y[n] = sy; x[n + 1] = dx, y[n + 1] = dy;
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &x[i], &y[i], &l[i]);
		for (int j = 0; j < l[i]; j++) {
			int v, t;
			scanf("%d%d", &v, &t);
			G[i].push_back(E{ v,t });
			G[v].push_back(E{ i,t });
		}
	}
	for (int i = 0; i < n + 2; i++) {
		G[n].push_back(E{ i,0 });
		G[i].push_back(E{ n + 1,0 });
	}
	for (int i = 0; i < n + 2; i++) {
		for (int j = 0; j < n + 2; j++) {
			dis[i][j] = dist(x[i], y[i], x[j], y[j]);
		}
	}
	if (dist(sx, sy, dx, dy) > B) { puts("-1"); return 0; }
	
	printf("%d\n", bfs(n));
	return 0;
}

K. Birdwatching

题意：给定有向图，终点T，如果从u到T必定经过边 (u,T) ，则输出点u。

把存在到T的边的点视为可能的点，如果一个可能的点能到另一个可能的点，则第一个点必定不行。把所有必定不行的点都去掉，就是答案。

本来可以直接dfs得到，如果当前点可能，且能达到可能的点，则当前点必定不行，但是由于可能有环，所以强连通分量缩点后dfs，同一个强连通分量里如果有两个可能的点，则这个分量里所有点都不行。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int n, m, t;
vector<int>G[N], vc, GG[N];
int die[N], gd[N], GD[N], Die[N];
int low[N], dfn[N], clk, B, bl[N], cnt[N];
vector<int> bcc[N];
void tarjan(int u) {
	static int st[N], p;
	static bool in[N];
	dfn[u] = low[u] = ++clk;
	st[p++] = u; in[u] = true;
	for (int& v : G[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		++B;
		while (1) {
			int x = st[--p]; in[x] = false;
			bl[x] = B; bcc[B].push_back(x); cnt[B] += gd[x];
			if (gd[x])GD[B] = 1;
			if (x == u) break;
		}
	}
}
int vis[N];
void dfs(int u) {
	vis[u] = 1;
	for (int v : GG[u]) {
		if (!vis[v])dfs(u);
		if (Die[v])Die[u] = 1;
		if (GD[v])Die[u] = 1;
	}
	if (Die[u]) {
		for (int v : bcc[u]) {
			die[v] = 1;
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (v == t)gd[u] = 1;
		else if (u != t)G[u].push_back(v);
	}
	for (int i = 0; i < n; i++)if (!dfn[i])tarjan(i);
	for (int i = 1; i <= B; i++) {
		if (cnt[i] < 2)continue;
		for (int u : bcc[i]) {
			die[u] = 1;
		}
	}
	for (int u = 0; u < n; u++) {
		for (int v : G[u]) {
			if (bl[u] != bl[v]) {
				GG[bl[u]].push_back(bl[v]);
			}
		}
	}
	for (int i = 1; i <= B; i++)if (!vis[i])dfs(i);
	int ans = 0;
	for (int i = 0; i < n; i++)if (gd[i] && !die[i])ans++;
	printf("%d\n", ans);
	for (int i = 0; i < n; i++)if (gd[i] && !die[i])printf("%d\n", i);
	return 0;
}

G. Swapping Places

题意：有一群动物排成一队，属于几种种族，有几对种族之间如果相邻则可以交换位置。要使得队伍的字典序最小。

拓扑排序

考虑等价条件。

如果两个动物不能交换，则它们的相对位置是固定的，而也容易推得在满足这一条件的情况下，其它位置可以任意改变。所以这是个等价条件。

那么只要向拓扑排序一样找到所有动物的父节点，仅当父节点都排完之后，才能轮到它。而在所有能轮到的动物中贪心选择字典序最小的。

要注意相同种群的可能在安排时顺序改变，导致有些动物的父亲早早地用掉，而轮到它，但是如果把所有相同地动物都作为它的父亲，那么边数又太多，所以还要限定种族相同时先用位置靠前的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int s, m, n;
int a[N];
string ss, tt;
vector<string>vc;
vector<int>p[210], G[N];
int vis[210][210], deg[N];
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii> >q;
int main() {
	cin.tie(0); cout.tie(0);
	scanf("%d%d%d", &s, &m, &n);
	for (int i = 1; i <= s; i++) {
		cin >> ss;
		vc.push_back(ss);
	}
	sort(vc.begin(), vc.end());
	for (int i = 0; i < s; i++) {
		vis[i][i] = 1;
	}
	for (int i = 0; i < m; i++) {
		cin >> ss >> tt;
		int u = lower_bound(vc.begin(), vc.end(), ss) - vc.begin();
		int v = lower_bound(vc.begin(), vc.end(), tt) - vc.begin();
		vis[u][v] = vis[v][u] = 1;
	}
	for (int i = 1; i <= n; i++) {
		cin >> ss;
		a[i] = lower_bound(vc.begin(), vc.end(), ss) - vc.begin();
		p[a[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		int u = a[i];
		for (int j = 0; j < s; j++) {
			if (!vis[u][j]) {
				int pos = upper_bound(p[j].begin(), p[j].end(), i) - p[j].begin();
				if (pos == 0)continue;
				else {
					deg[i]++;
					G[p[j][pos - 1]].push_back(i);
				}
			}
		}
		if (!deg[i])q.push(pii(a[i], i));
	}
	while (!q.empty()) {
		int u = q.top().second; q.pop();
		cout << vc[a[u]] << ' ';
		for (int v : G[u])if (--deg[v] == 0)q.push(pii(a[v], v));
	}
	return 0;
}