2020 Multi-University Training Contest 3

http://acm.hdu.edu.cn/contests/contest_show.php?cid=881

1007 - Tokitsukaze and Rescue

 

题意：n 个点的完全无向图，要求删掉k条边，使得剩下的图上的从 1 到 n 的最短路最长。$(3≤n≤50,1≤k≤min(n−2,5))$

杭电似乎有道题是删掉 1 条边，要最短路最长，需要先求出最短路，再遍历最短路上所有边，比较删掉哪个后新的最短路最长。

本题也类似，只是要dfs k 次，每次都求最短路，再删最短路上边。

但是这样复杂度就是 $O(n^2c^k)$ （Dij完全图 $n^2$ 求最短路）。

其实说白了就是暴搜，所以复杂度是个问题。

出题人大佬说：假设一条路长度A，另一条长 B，A > B，然而 A 成为最短路，说明 A 上所有边权和 $sum_A$ 大于 B 上所有边权和 $sum_B$，而 $sum_A=\sum_{i=1}^A rand(),sum_B=\sum_{i=1}^Brand()$，且两处随机都是均匀分布，且值域相同，则必定发生的概率很小。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int T;
int n, k;
int G[100][100], d[100], f[100][100], vis[100];
int ans;
void dfs(int dep) {
	int u;
	fill(d, d + n + 1, INF);
	fill(vis, vis + n + 1, 0);
	d[1] = 0;
	while (true) {
		u = 0;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && (!u || d[i] < d[u]))u = i;
		}
		if (!u)break;
		vis[u] = 1;
		for (int i = 1; i <= n; i++) {
			if (d[i] > d[u] + G[u][i]) {
				d[i] = d[u] + G[u][i];
				f[dep][i] = u;
			}
		}
	}
	if (dep == 0) {
		ans = max(ans, d[n]);
		return;
	}
	u = n;
	int fa = f[dep][u], tmp;
	while (fa) {
		tmp = G[u][fa];
		G[u][fa] = G[fa][u] = INF;
		dfs(dep - 1);
		G[u][fa] = G[fa][u] = tmp;
		u = fa;
		fa = f[dep][u];
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		memset(G, 0x3f, sizeof(G));
		for (int i = 1; i <= n * (n - 1) / 2; i++) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			G[u][v] = G[v][u] = w;
		}
		ans = 0;
		dfs(k);
		printf("%d\n", ans);
	}
	return 0;
}

 

1008 - Triangle Collision

 

题意：给定一个等边三角形，内有一点，有一初速度，碰到三角形边则反弹，方向符合反射定律，大小不变。问多久后刚好反弹了 k 次。

二分+计算几何

很好的一道题。

反射其实并不需要真的反射，而是可以视为进入了另一个镜像的三角形内方向不变地继续前进，所以问题可以变成在一个铺满了三角形的无限大平面上始终保持一个方向，速度不变地运动，穿过了几条边。

二分答案，就要计算在给定时间内能穿过几条边。

先考虑平行于 x 轴的那条边，穿过这样的边的边数就是 $abs(\lfloor \frac{y}{h}\rfloor)$，其中 y 为最终点的 y 坐标，h 为等边三角形的高。

再看斜着的边。其实旋转坐标轴后可以就当作平行于 x 轴的边算了，坐标轴绕等边三角形的中心顺时针旋转 120°，240°。也就相当于最终坐标绕等边三角形的中心顺时针旋转240°，120°。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int T;
double L, x, y, vx, vy, h;
double base = 2 * PI / 3;
int k;
pair<double, double> Point(const pair<double, double>& p, double rad) {
	double x = p.first, y = p.second;
	return make_pair(x*cos(rad) - (y - h / 3)*sin(rad), (y - h / 3)*cos(rad) + x * sin(rad) + h / 3);
}
ll ck(double t) {
	ll res = 0;
	res += (ll)abs(floor(Point(make_pair(x + vx * t, y + vy * t), 0).second / h));
	res += (ll)abs(floor(Point(make_pair(x + vx * t, y + vy * t), base).second / h));
	res += (ll)abs(floor(Point(make_pair(x + vx * t, y + vy * t), base * 2).second / h));
	return res;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lf%lf%lf%lf%lf%d", &L, &x, &y, &vx, &vy, &k);
		h = sqrt(3.0) / 2 * L;
		double L = 0, R = 1e10;
		while (R - L > eps) {
			double mid = (L + R) / 2;
			if (ck(mid) >= k)R = mid;
			else L = mid;
		}
		printf("%.8lf\n", (L + R) / 2);
	}
	return 0;
}

 

1006 - X Number

 

题意：定义一个数的众数为各个位上的数字中出现次数最多的那个。问在 $[l,r]$ 范围内有多少数的众数为 $d$。

数位dp

本题前导零不能算作真正的0，所以是/否前导零需要记录。

和普通数位dp一样，当非前导0，非上限时组合数学直接计算并记录；其它情况下直接dfs。

但是记录的状态有些特别，当一个数字成为众数时，其它9个数字可能有不同的情况，这些情况都要记录下来，所以用一个一维为长度10的array的map作为dp数组。

下面考虑如何直接计算。

要计算让 d 成为众数的方案数，那么必然要枚举 d 出现的次数，累加其中能成为众数的情况。

在确定了 d 出现次数的条件下，还要枚举另外9个数字的出现次数，当然不能再dfs了，所以考虑dp。

再另外设置一个dp数组 $f[i][j]$ 表示前 i 个数字 $(0,1,2,\cdots, i-1)$ 共出现了 j 次的方案数，枚举 i，枚举时要保证这个数字的出现次数小于 d 的出现次数。再枚举 j，再枚举 当前数字出现的次数以便计算，设当前数字出现了 $q$ 次，前 i 个数字共出现了 $k$ 次，则 方案数 = 之前的方案数 $f[i-1][k-q]$ * 还剩余位数 $rest-k+q$ 中选择 $q$ 位。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int T;
ll l, r; int d;
int a[100];
ll C[100][100];
ll f[30][30];
array<int, 10>arr;
map<array<int, 10>, ll>dp[30];
ll dfs(int pos, int lim, int lead) {
	if (pos == -1) {
		for (int i = 0; i < 10; i++)if (i != d && arr[i] >= arr[d])return 0;
		return 1;
	}
	if (!lim && !lead) {
		if (dp[pos].count(arr))return dp[pos][arr];
		int rest = pos + 1;
		int nd = 0;
		for (int i = 0; i < 10; i++)if (i != d)nd = max(nd, arr[i] + 1);
		ll res = 0;
		for (int i = nd; i <= arr[d] + rest; i++) {
			int tmp = rest - i + arr[d];		//除d外其它数字还可放的个数
			f[0][0] = 1ll;
			for (int j = 1; j <= 10; j++) {
				if (j - 1 == d) {
					for (int k = 0; k <= tmp; k++)f[j][k] = f[j - 1][k];
					continue;
				}
				for (int k = 0; k <= tmp; k++) {
					f[j][k] = f[j - 1][k];			//不放j-1
					for (int q = 1; q <= k; q++) {	//放q个j-1
						if (arr[j - 1] + q >= i)break;
						f[j][k] += f[j - 1][k - q] * C[rest - k + q][q];
					}
				}
			}
			res += f[10][tmp];
		}
		return dp[pos][arr] = res;
	}
	ll res = 0;
	int up = lim ? a[pos] : 9;
	for (int i = 0; i <= up; i++) {
		if (i == 0 && lead) {					//继续前导0
			res += dfs(pos - 1, lim&&i == up, 1);
		}
		else {
			arr[i]++;							//dfs
			res += dfs(pos - 1, lim&&i == up, 0);
			arr[i]--;
		}
	}
	if (!lim && !lead)dp[pos][arr] = res;
	return res;
}
ll sol(ll r) {
	for (int i = 0; i < 20; i++)dp[i].clear();
	for (int i = 0; i < 10; i++)arr[i] = 0;
	int cnt = 0;
	while (r) {
		a[cnt++] = r % 10;
		r /= 10;
	}
	return dfs(cnt - 1, 1, 1);
}
int main() {
	for (int i = 0; i < 30; i++)C[i][0] = C[i][i] = 1ll;
	for (int i = 1; i < 30; i++) {
		for (int j = 1; j < i; j++)C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
	}
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%d", &l, &r, &d);
		printf("%lld\n", sol(r) - sol(l - 1));
	}
	return 0;
}