2021-02-21

2021 HZNU Winter Training Day 17(2018 German Collegiate Programming Contest(GCPC 18))

字数统计: 4.2k字 | 阅读时长: 21分

solved	A	B	C	D	E	F	G	H	I	J	K	L	M
9 / 13	Ø	Ø	O	O	O	O	-	Ø	O	-	-	-	Ø

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

REPLY ：
lllllan:

一个寒假松懈太久，做题状态欠佳。表现为整场都在做A都还没做出来。
在家训练不太严格，开题都是看心情。表现为水题签到的很慢，时间都花在A上面了Orz。
就当作是调整比赛状态和知识点查漏吧。

Sstee1XD：

队内毒瘤，一道题都没有，前半场一直在自闭。

比赛链接

A - Attack on Alpha-Zet

solved by lllllan.(-)

题意： 在一个二维地图上，并提供m个点的坐标，按顺序从一号点走到m号点。求最短距离。

题解：

题图的大小是 $h*w$ ，但是输入的大小却是 $(h+1) * (2 * w)$ 。地图中的一个方格需要两个单位分别表示左边和下边是否有墙。注意数组范围。
Furthermore it is guaranteed that exactly one path exists between any two modules.题面的最后一句话，两点之间仅有一条路径 = 不构成环 = 可以抽象成树。
题目好像就变成了在树上求几个点的距离然后求和。树上点的距离，自然需要用到了LCA。

分析完题目大概思路就是这样了，剩下就是程序中的细节处理了，这个很难讲，自己写过错过才会长记性。

比如数组大小。因为题目比较综合，需要用到很多数组。全都开特别大小心MLE，大小不同那就需要仔细检查了。
矩阵信息转换成树，找到输入的规律可以很快转换。~~我的思维定式是用从一号点去BFS出路径。~~
矩阵中每个点自身携带着二维坐标的信息，抽象到树上的一个点之后，需要重新赋予编号。

AC代码

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

#define pii pair<int,int>
#define fi first
#define se second

int h, w, m;

vector<int> is[maxn * maxn];
char G[maxn][maxn << 1];
int vis[maxn * maxn];
int dep[maxn * maxn];
int s[maxn * maxn];

int find (int x) { return s[x] == x ? x : s[x] = find(s[x]); }
int id (int i, int j) { return (i - 1) * w + j; }

pii V[maxn * 10];
int ans[maxn * 10];

int cnt, head[maxn * maxn];
struct edge { int v, next; } e[maxn * maxn * 2];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}; head[u] = cnt;
	e[++cnt] = {u, head[v]}; head[v] = cnt;
}

void Tarjan (int u, int fa) {
	dep[u] = dep[fa] + 1;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa) continue;
		Tarjan(v, u);
		s[v] = u;
	}
	if (is[u].size()) {
		for (int k : is[u]) {
			int v = id(V[k + 1].fi, V[k + 1].se);
			if (vis[v]) ans[k] = dep[u] + dep[v] - 2 * dep[find(v)];
			v = id(V[k - 1].fi, V[k - 1].se);
			if (vis[v]) ans[k - 1] = dep[u] + dep[v] - 2 * dep[find(v)];
		}
	}
	vis[u] = 1;
}

void init () {
	for (int i = 1; i <= h * w; ++i) s[i] = i;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			int u = id(i, j);
			if (G[i][2 * j] == ' ') add(u, id(i + 1, j));
			if (G[i][2 * j + 1] == ' ') add(u, id(i, j + 1));
		}
	}
}

int main () {
//	freopen("input.txt", "r", stdin);
	
	scanf("%d%d", &h, &w); getchar();
	for (int i = 0; i <= h; ++i) gets(G[i] + 1);
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		V[i] = {x, y};
		is[id(x, y)].push_back(i);
	}
	
	init();	
	Tarjan(id(V[1].fi, V[1].se), 0);
	
	ll sum = 0;
	for (int i = 1; i < m; ++i) sum += ans[i];
	printf("%lld\n", sum);
	return 0;
}

B - Battle Royale

solved by Tryna.(-)

题意： 给出两个点和一大一小的圆，问这两个点之间的最短距离，这个最短距离不能穿过小圆且必须得在大圆内。

题解： 这道题的大圆好像没什么用。分类讨论一下，如果这两条直线的连线本来就没经过小圆，那么最短距离就是这两点距离；否则就是过这两个点分别作小圆的切线，那么最短距离就是两个点分别到他们切点的距离加上两个切点在圆弧上的距离。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-10
const int maxn = 1e4 + 10;
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x + B.x,y + B.y);}
    Point operator - (Point B){return Point(x - B.x,y - B.y);}
    Point operator * (double k){return Point(x*k,y*k);}
    Point operator / (double k){return Point(x/k,y/k);}
};
Point a, b, c, d;
typedef Point Vector;
double Dist(Point A,Point B){
    return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}
double Cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;}
double Dis_point_line(Point p, Point p1, Point p2){     //点到直线的距离
    return fabs(Cross(p - p1, p2 - p1))/Dist(p1, p2);
}
double rc, rd;
void solve() {
	scanf("%lf%lf", &a.x, &a.y);
	scanf("%lf%lf", &b.x, &b.y);
	scanf("%lf%lf%lf", &c.x, &c.y, &rc);
	scanf("%lf%lf%lf", &d.x, &d.y, &rd);
	double len = Dis_point_line(d, a, b);
	if(len >= rd) {
		printf("%.10f\n", Dist(a, b));
	}
	else{
		double d1 = Dist(a, d);
		double d2 = Dist(b, d);
		double l1 = sqrt(d1 * d1 - rd * rd);
		double l2 = sqrt(d2 * d2 - rd * rd);
		double angle1 = acos(len / d1) - acos(rd / d1);
		double angle2 = acos(len / d2) - acos(rd / d2);
		double l3 = (angle1 + angle2) * rd;
		printf("%.10f\n", l1 + l2 + l3);
	}
}
int main() {
	solve();
	return 0;
}

C - Coolest Ski Route

solved by lllllan.(+)

题意： 有向图上求最长路。

有重边。
不限起点和终点。
点不能重复访问。

题解： 既然是有向边，那就从入度为0的点分别DFS。好像有些同学TLE了，然后在DFS中加了剪枝。反正记忆化搜索是平坦A题了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int maxm = 1e4 + 10;

int n, m;
int ans;

int vis[maxn];
int deg[maxn];
int dis[maxn];

int cnt, head[maxn];
struct edge { int v, w, next; } e[maxm];
void add (int u, int v, int w) { e[++cnt] = {v, w, head[u]}; head[u] = cnt; }

void DFS (int u) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (!dis[v]) DFS(v);
		if (dis[v] + w > dis[u]) dis[u] = dis[v] + w; 
	}
}

int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
		deg[v]++;
	}
	
	for (int i = 1; i <= n; ++i) {
		if (deg[i]) continue;
		DFS(i);
		ans = max(ans, dis[i]);
	}
	
	printf("%d\n", ans);
	return 0;
}

D - Down the Pyramid

solved by Tryna 1:11(+2)

题意： 给出 $n$ 个数， $a_1$ ~ $a_n$ 都是非负数，要求构造一个长度为 $n + 1$ 的序列 $b_{n+1}$ ，满足

$b_1 + b_2 = a_1$
$b_2 + b_3 = a_2$
$b_3 + b_4 = a_3$
.
.
.
$b_n + b_{n+1} = a_n$

并且序列 $b_{n+1}$ 的每一项也必须是非负数

题解： 可以化成这样的式子

$b_1 = b_1$
$b_2 = a_1 - b_1$
$b_3 = a_2 - a_1 + b_1$
$b_4 = a_3 - a_2 + a_1 - b_1$

发现序列 $b$ 的每一项都跟 $b_1$ 有关，保证每一项都是非负数即可

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e6 + 10;
int t, n, a[maxn];
void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	ll ans = 0;
	ll maxx = inf, minn = 0;
	for(int i = 1; i <= n; i++) {
		ans = -ans;
		ans += a[i];
		if(i % 2)
			maxx = min(maxx, ans);
		else
			minn = max(minn, -ans);
	}
	if(maxx >= minn) {
		printf("%lld\n", maxx - minn + 1);
	}
	else puts("0");
}
int main() {
	solve();
	return 0;
}

E - Expired License

solve by Tryna & Sstee1XD 3:32(+8)

题意： 给出两个浮点数，问这两个浮点数的比值能不能用两个质数代替，如果答案不唯一输出两个质数和最小的情况

题解： 先将这两个数都乘 $1e5$ 变成整数，然后这两个数的除它们的 $gcd$ ，如果得到的都是质数则答案成立，否则不存在

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e3 + 10;
int t, n;
double a, b;
int x, y;
ll gcd(ll a, ll b) {
	return a == 0 ? b : gcd(b % a, a);
}
bool check(ll x) {
	if(x == 1) return false;
	for(int i = 2; i <= sqrt(x); i++) {
		if(x % i == 0) return false;
	}
	return true;
}
void solve() {
	scanf("%d", &n);
	while(n--) {
		scanf("%lf %lf", &a, &b);
		if(a == b) {
			puts("2 2");
			continue ;
		}
		ll x = a * 100000.0 + 0.5;
		ll y = b * 100000.0 + 0.5;
		ll m = gcd(x, y);
		x = x / m;
		y = y / m;
		if(check(x) && check(y))
			printf("%lld %lld\n", x, y);	
		else 
			puts("impossible");
	}
}
int main() {
	solve();
	return 0;
}

F - Fighting Monsters

solved by Tryna 1:52(+1)

题意： 给出 $n$ 个数，问存不存在这样的两个数 $a, b$ 满足

a = a - b
b = b - a
a = a - b
b = b - a
循环下去直至其中一个数不是正整数，且另外一个数是1

题解： 通过观察样例3中的 $5$ 和 $8$ 可以发现，如果两个数能变成 $5$ 和 $8$ 那么肯定也是可以的，所以就找到了 $8$ 和 $13$ ，一直这么想下去，发现新出现的数字是前两个数字的和，那么就很自然想到了斐波那契数列，那么这道题就变成了求有没有出现两个相邻的斐波那契数列

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e5 + 10;
int t, n, f[maxn], num;
struct node{
	int m, id;
	bool operator < (const node &r)const{
		return m < r.m;
	}
}p[maxn];
void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &p[i].m);
		p[i].id = i;
	}
	sort(p + 1, p + 1 + n);
	for(int i = 1; i <= num; i++) {
		int f1 = 0, f2 = 0, p1 = 0, p2 = 0, pp = 0;
		for(int j = 1; j <= n; j++)  {
			if(p[j].m == f[i]) {
				f1 = 1;
				pp = j;
				p1 = p[j].id;
				break;
			}
		}
		for(int j = pp + 1; j <= n; j++) {
			if(p[j].m == f[i + 1]) {
				f2 = 1;
				p2 = p[j].id;
				break;
			}
		}
		if(f1 && f2) {
			printf("%d %d\n", p1, p2);
			return ;
		}
	}
	puts("impossible");
}
int main() {
	f[1] = 1, f[2] = 1;
	for(int i = 3; i <= 1000; i++) {
		f[i] = f[i - 1] + f[i - 2];
		if(f[i] > 1000000) {
			num = i;
			break;
		}
	}
	solve();
	return 0;
}

H - Hyper Illuminati

solved by lllllan.(-)

题意： 求一个 $<1e16$ 的正整数能否被分解成 $\sum_{i = 0}^{n}x^i$ ，若能，求出x,n。

题解： 无他，但暴力尔。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;

int main () {
	scanf("%lld", &n);	
	for (ll i = 3; i <= 60; ++i) {
		ll ans = 0;
		for (ll j = 1; j <= n; ++j) {
			ll tem = 1;
			for (ll k = 1; k < i; ++k) {
				if (tem * j - n > 0) {
					tem = n + 1;
					break;
				}
				tem *= j;
			}
			if ((ans += tem) > n) break;
			if (n == ans) return (printf("%lld %lld", i, j), 0);
		}
	}
	printf("impossible");
	return 0;
}

I - It’s Time for a Montage

solved by Tryna 2:53(+2)

题意： 英雄对战反派，每一个英雄和反派都有一个力量值，对战的规则是这样的按顺序从 $1$ 到 $n$ 打，只要当前英雄的力量值小于反派就输了；只要当前英雄的力量值大于反派就赢了；如果相等就看下一对，如果所有力量值都相等也算赢。英雄可以训练 $x$ 天来增加 $x$ 点力量值，反派则不增加，问最少需要训练多少天才能赢

题解： 直接O（n）暴力一遍就可以了

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e3 + 10;
int t, n, h[maxn], v[maxn];
void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &h[i]);
	for(int i = 1; i <= n; i++)
		scanf("%d", &v[i]);
	if(h[1] > v[1])
		puts("0");
	else{
		int cnt = v[1] - h[1];
		int f = 0;
		for(int i = 2; i <= n; i++) {
			if(h[i] + cnt < v[i]) {
				printf("%d\n", ++cnt);
				return ;
			}
			else if(h[i] + cnt > v[i]) {
				printf("%d\n", cnt);
				return ;
			}
			else f++;
		}
		if(f == n - 1) printf("%d\n", cnt);
	}
}
int main() {
	solve();
	return 0;
}

M. Mountaineers

Solved by Sstee1XD. (-)

题意：
给你一个最大为 $500*500$ 的矩阵，你可以在矩阵中的点中上下左右移动。接下来最多 $10^5$ 次询问，每次询问两个点，你要从第一个点走到第二个点，使得路程中经过的点权值的最大值最小，问你这个点权值是多少。

思路：
朴素的想法是二分权值，进行 $dfs$ ，但是时间复杂度是 $O(n^2 * q * log10^6)$ 的。后来尝试加记忆化搜索，但是失败了。

既然无法在每次询问时将时间复杂度降下来，那么需要考虑能否将询问一起处理。这道题可以用 $LCA$ 的方法解，大概的方法是优先处理点权较小的点，从四周点权不大于它的点向它建一条有向边，形成一棵树，这样就能保证一路上经过的点的权值最大值最小，并且拥有最大权值的点是它们的 $LCA$ 。然后以权值最大的点为根，每次询问输出两个点的 $LCA$ 的权值就行了。

这里介绍一种并查集启发式合并的方法。我们将所有询问的编号记录在对应的点上。然后优先处理点权较小的点，每次将四周点权不大于它的点与它合并在并查集里，合并的时候看下它们是否有相同的询问编号，如果有，那么这次询问的答案就是当前点的权值。注意在合并的时候，我们要判断两个点拥有的询问数量，将小的合并在大的里面。因为我们在看两个点是否有相同的询问编号时，是需要进行遍历操作的，最坏的情况下时间复杂度还是会达到 $O(n^2 * q)$ 。但如果我们每次都遍历拥有询问数量较小的点，遍历的总次数就会是 $O(q)$ 级别的，所以不加上查询是否有相同的编号时，总时间复杂度降到了 $O(n^2 + q)$ 。为了让各种操作都能方便进行，我们选择 $set$ 来储存询问的信息，时间复杂度大概为 $O(n^2 + qlogq)$ ，但是常数比较大。

AC代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int Q = 1e5 + 7;
const int N = 500 * 500 + 7;

set<int> sz[N];
int n, m, q, w[N], fa[N], res[Q];
int mov[][2] = {0, 1, 0, -1, 1, 0, -1, 0};

bool check(int x, int y) {
    if (x < 1 ||x > n || y < 1 || y > m) return false;
    return true;
}

int ID(int x, int y) {
    return (x - 1) * m + y;
}

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

void merge(int x, int y, int now) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x].size() > sz[y].size()) swap(x, y);

    for (auto i : sz[x]) {
        if (sz[y].count(i)) {
            res[i] = now;
            sz[y].erase(i); // 删除操作，降低空间复杂度的同时也降低了时间复杂度
        } else {
            sz[y].insert(i);
        }
    }
    sz[x].clear();
    fa[x] = y;
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> w[ID(i, j)];
            fa[ID(i, j)] = ID(i, j);
        }
    }

    for (int i = 1, x1, x2, y1, y2; i <= q; ++i) {
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2 && y1 == y2) {
            res[i] = w[ID(x1, y1)];
            continue;
        }
        sz[ID(x1, y1)].insert(i);
        sz[ID(x2, y2)].insert(i);
    }

    vector< tuple<int, int, int> > v;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            v.emplace_back(make_tuple(w[ID(i, j)], i, j));
        }
    }
    sort(v.begin(), v.end());

    for (auto t : v) {
        int ww, xx, yy;
        tie(ww, xx, yy) = t;
        
        for (int i = 0; i < 4; ++i) {
            int fx = xx + mov[i][0], fy = yy + mov[i][1];
            if (check(fx, fy)) {
                if (w[ID(fx, fy)] > w[ID(xx, yy)]) continue;
                merge(ID(xx, yy), ID(fx, fy), ww);
            }
        }
    }

    for (int i = 1; i <= q; ++i) {
        cout << res[i] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (_T--) solve();
    return 0;
}

/*
3 5 3
1 3 2 1 3
2 4 5 4 4
2 1 3 2 2
1 1 3 2
2 4 2 2
1 4 3 4
*/