https://ac.nowcoder.com/acm/contest/9925

H - Rice Arrangement

 

题意：给定一个有 n 个位置的圆桌，其中 k 个位置上有人，k 个位置上有饭，饭放在桌上的转盘上，每次可以顺时针或逆时针旋转一格，当一碗饭与一个人在同一位置时，这个人可以吃也可以不吃。要求旋转最少次数使得每个人都有饭吃。

枚举+思维

只可能：始终顺时针转，始终逆时针转，先顺时针再逆时针转，先逆时针转再顺时针转。最多只会改变一次方向。

枚举起点，之后的人按顺序吃对应的饭，则需要顺时针转的角度为所有人需要顺时针转的角度的最大值。逆时针类似。

再考虑改变方向的情况。枚举在变成逆时针转之前，顺时针转的角度，那么需求量小于等于这个角度的人都吃到饭了，只剩下大于这个角度的人。他们需要逆时针转的角度为它们 n - 顺时针转的角度的最小值。

先逆时针再顺时针类似。

实现方法非常巧妙，只需要按照顺时针转的角度排序即可，因为排序后，没有吃到饭的人的“顺时针转的角度的最小值”就是下一个值。

需要注意如果顺时针转的角度为 0，逆时针需要转的角度也应该是0，而不是 n。但是这一点在实现时会在先顺时针再逆时针的情况中被解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
int n, k;
int a[N], b[N], c[N];
int ans;
void solve(int s) {
	for (int i = 0; i < k; i++) {
		c[i] = (a[(i + s) % k] - b[i] + n) % n;
	}
	sort(c, c + k);
	ans = min(ans, c[k - 1]);
	ans = min(ans, n - c[0]);
	for (int i = 0; i < k - 1; i++) {
		ans = min(ans, 2 * c[i] + n - c[i + 1]);
		ans = min(ans, 2 * (n - c[i + 1]) + c[i]);
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		for (int i = 0; i < k; i++)scanf("%d", &a[i]);
		for (int i = 0; i < k; i++)scanf("%d", &b[i]);
		sort(a, a + k);
		sort(b, b + k);
		ans = INF;
		for (int i = 0; i < k; i++) {
			solve(i);
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

I - Sky Garden

 

题意：给定 nn 个同心圆，第 ii 个的半径为 ii，有 mm 条直线穿过圆心，把每个圆均匀分成 2m2m 分，对圆上每一对交点，计算出距离，并求和。

dp

本题难点在于同一个圆上的两点并不一定是从圆上走最短。

dp[i][j]dp[i][j] 表示第 ii 个圆，按照极角排序后从第 00 个点走到第 jj 个点的最短距离。

则 dp[i][j]dp[i][j] 可以直接在第 ii 个圆上走过去，也可以走到第 i−1i-1 个圆上，再走 dp[i−1][j]dp[i-1][j]，再走出到第 ii 个圆。

答案包括走到圆心，走到不同圆上的点，走到同一个圆上的点。

注意如果 m=1m=1，则圆心不是交点，不要走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
int n, m;
double ans;
double dp[510][1010];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		double res = 0;
		if (m > 1)res += i;
		for (int j = 1; j < i; j++) {
			for (int k = 0; k < 2 * m; k++) {
				res += (i - j) + dp[j][k];
			}
		}
		for (int j = 1; j < 2 * m; j++) {
			dp[i][j] = min(dp[i - 1][j] + 2, 2 * PI*i*min(0.5*j / m, 1.0 - 0.5*j / m));
			res += 0.5*dp[i][j];
		}
		ans += 2 * m*res;
	}
	printf("%.12lf\n", ans);
	return 0;
}

 

L - Traveling in the Grid World

 

题意：给定 n,mn,m，有一个 n∗mn*m 的网格，要从 (0,0)(0,0) 走到 (n,m)(n,m)，可以沿两点的连线走，但是连线上不能有格点，且连续两次走的方向不能共线，问最短距离。

枚举

首先能够发现两点连线没有格点等价于 gcd⁡(n,m)=1\gcd(n,m)= 1，此时直接两点连线。

否则暴力枚举连线周围的格点，对于符合条件的计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
ll n, m;
int dx[]{ 0,0,-1,1};
int dy[]{ -1,1,0,0};
double dis(ll n, ll m) {
	return sqrt(1.0*n*n + 1.0*m*m);
}
double ans;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &n, &m);
		if (__gcd(n, m) == 1) {
			printf("%.12lf\n", dis(n, m));
			continue;
		}
		ans = 1e18;
		for (int i = 0; i < 4; i++) {
			if (__gcd(n + dx[i], m + dy[i]) == 1) {
				ans = min(ans, 1 + dis(n + dx[i], m + dy[i]));
			}
		}
		for (ll i = 1; i < n; i++) {
			ll t1 = max(1ll, m * i / n - 1), t2 = min(m - 1, (ll)ceil(1.0*m*i / n) + 1);
			for (ll j = t1; j <= t2; j++) {
				if (__gcd(i, j) == 1 && __gcd(n - i, m - j) == 1 && i*m != j * n) {
					ans = min(ans, dis(i, j) + dis(n - i, m - j));
				}
			}
		}
		printf("%.12lf\n", ans);
	}
	return 0;
}

 

C - Sum of Log

 

题意：给定两个非负整数 X,YX,Y，求 ∑i=0X∑j=[i=0]Y[i&j=0]⌊log⁡2(i+j)+1⌋\sum\limits_{i=0}^X\sum\limits_{j=[i=0]}^Y[i\&j=0]\lfloor\log_2(i+j)+1\rfloor.

数位dp

[i&j=0][i\&j=0] 表明 i,ji,j 不可能在某一位同时为 11，所以 i+ji+j 其实就是 i⊕ji\oplus j，那么其实就是求当最高位为第 kk 位时，i,ji,j 的方案数，而 i,ji,j 可以看作把以第 kk 位为最高位的数 xx 中的每个 11 分给 ii 或者 jj。

这里有 X,YX,Y 两个限制，所以dp中也要有两个限制。

还要有前导零限制，因为只有当之前都是零，且当前位为 11 时，当前位才是最高位，才应该计入答案。

要开 dp[pos][lim1][lim2][lead]dp[pos][lim1][lim2][lead] 四维，否则会T。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
ll x, y;
int a[N], b[N];
ll dp[50][2][2][2];
ll ans;
ll dfs(int pos, int lim1, int lim2, int lead) {
	if (pos == 0) {
		return 1;
	}
	if (dp[pos][lim1][lim2][lead] != -1)return dp[pos][lim1][lim2][lead];
	int up1 = lim1 ? a[pos] : 1;
	int up2 = lim2 ? b[pos] : 1;
	ll res = 0;
	for (int i = 0; i <= up1; i++) {
		for (int j = 0; j <= up2; j++) {
			if (i + j == 2)continue;
			ll tmp = dfs(pos - 1, lim1&(i == up1), lim2&(j == up2), lead&(i + j == 0));
			if (i + j == 1 && lead)ans = (ans + pos * tmp%mod) % mod;
			res = (res + tmp) % mod;
		}
	}
	return dp[pos][lim1][lim2][lead] = res;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &x, &y);
		for (int i = 1; i <= 30; i++) {
			a[i] = (x >> (i - 1) & 1);
			b[i] = (y >> (i - 1) & 1);
		}
		memset(dp, -1, sizeof(dp));
		ans = 0;
		dfs(30, 1, 1, 1);
		printf("%lld\n", ans);
	}
	return 0;
}