2021牛客暑期多校训练营1

题解
字数统计: 2.9k   |   阅读时长≈ 14 分钟

A-Alice and Bob

题目大意

有两堆石头，两个人轮流进行操作，往任意一堆石头中拿走k个，往任意一堆石头中拿走$s\times k(s\geq 0) $个，谁先不能操作谁就输，问先手赢还是后手赢。

解题思路

暴力SG函数打表，复杂度$O(n^3logn)$。

枚举所有拿的情况，从必败点开始推。

数组可以用bitset优化，可以比bool数组快几百ms。

完整代码

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
const int N = 5005;
bitset<N> sg[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	rep(i, 0, 5000) {
		rep(j, 0, 5000) {
			if (!sg[i][j]) {
				for (int k = 1; k + i <= 5000; k++) {
					for (int g = 0; j + g * k <= 5000; g++)
						sg[i + k][j + g * k] = 1;
				}
				for (int k = 1; k + j <= 5000; k++) {
					for (int g = 0; i + g * k <= 5000; g++)
						sg[i + g * k][j + k] = 1;
				}
			}
		}
	}
	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		if (!sg[n][m])	cout << "Bob" << endl;
		else cout << "Alice" << endl;
	}
	return 0;
}

B-Ball Dropping

题目大意

给你一个球，下面有一个等腰梯形，问你这个球能否穿过这个等腰梯形，告诉你求球的半径以及梯形的上底、下底和高。

解题思路

高中几何数学。

图这里不好画就不画了，用等比例来求。

完整代码

1
2
3
4
5
6
7
8
9
10
11
int main() {
	double r, a, b, h; cin >> r >> a >> b >> h;
	if (2 * r > b) {
		double H = (a*h)/(a-b);
		cout << "Stuck" << endl;
		double h1 = H-2*r*sqrt(a*a/4+H*H)/a;
		printf("%.6lf\n",h-h1);
	}
	else cout << "Drop" << endl;
	return 0;
}

D-Determine the Photo Position

题目大意

给你一个$n\times m$的01矩阵，给你一个$1\times k$的图形，问把这个图形插入01矩阵中的0中，最多有多少种可能。

解题思路

输入的时候，统计一下连续的0有多长，对于每一段计算一下贡献即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	int ans = 0;
	rep(i, 1, n) {
		int len = 0;
		rep(j, 1, n) {
			cin >> Map[i][j];
			if (Map[i][j]=='0') len++;
			else {
				if (len >= m)	ans += len - m + 1;
				len = 0;
			}
		}
		if (len >= m)	ans += len - m + 1;
	}
	string s; cin >> s;
	cout << ans << endl;
	return 0;
}

E-Escape along Water Pipe

题目大意

给你一个$n\times m$的水管图，总共有六种水管，在进入下一个水管之前，你可以进行任意多次操作，每次能够旋转除你所在的水管以外的任意的水管旋转${0°,90°,180°,270°}$，问你能否到达终点。

解题思路

模拟加BFS。

因为题目要求是可以对于你要去的点进行旋转的，所以整个图是啥样只和水管的类型有关系（弯和直），只需要输出答案的时候对点的状态进行更新和计算。

搜索的时候，记录点的x，y，以及点进来的方向，为了输出答案，需要记录一下路径。

输出答案的时候，需要从终点开始递归输出答案，对于前一个点和现在这个点的方向，你能够确定前一个点的水管的状态，然后计算出水管旋转的角度，为了方便，可以让所有点都旋转一次，这样答案次数就是点的个数的两倍。

完整代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int Map[1005][1005], vis[1005][1005][4], n, m;
int typ[][4] = {
	{5,1,-1,0},
	{3,4,0,-1},
	{-1,2,5,3},
	{2,-1,1,4}
};

struct node {
	int x, y, dir;
}pre[1005][1005][4];

void print(int x, int y, int dir, int step) {
	if (x == 1 && y == 1 && !dir) {
		cout << step * 2 << endl;
		return;
	}
	node t = pre[y][x][dir];
	int tx = t.x, ty = t.y, tdir = t.dir;
	print(tx, ty, tdir, step + 1);
	int tmp = typ[tdir][dir];
	if (tmp < 4) printf("1 %d %d %d\n", (tmp - Map[ty][tx] + 4) % 4 * 90, ty, tx);
	else printf("1 %d %d %d\n", (tmp - Map[ty][tx] + 2) % 2 * 90, ty, tx);
	printf("0 %d %d\n", ty, tx);
	Map[ty][tx] = tmp;
}

int check(int x, int y, int dir) {
	if (x == m && y == n + 1 && !dir)	return 1;
	if (x > m || y > n || x < 1 || y < 1 || vis[y][x][dir])	return 0;
	return 1;
}


int bfs() {
	queue<node> q;
	q.push({ 1,1,0 });
	vis[1][1][0] = 1;
	while (!q.empty()) {
		int x = q.front().x, y = q.front().y, dir = q.front().dir;
		q.pop();
		if (x == m && y == n + 1 && !dir)	return 1;
		if (Map[y][x] < 4) {
			int tdir = (dir + 1) % 4, tx = x + dx[tdir], ty = y + dy[tdir];
			if (check(tx, ty, tdir)) {
				q.push({ tx,ty,tdir });
				vis[ty][tx][tdir] = 1;
				pre[ty][tx][tdir] = { x,y,dir };
			}
			tdir = (dir + 3) % 4, tx = x + dx[tdir], ty = y + dy[tdir];
			if (check(tx, ty, tdir)) {
				q.push({ tx,ty,tdir });
				vis[ty][tx][tdir] = 1;
				pre[ty][tx][tdir] = { x,y,dir };
			}
		}
		else {
			int tdir = dir, tx = x + dx[tdir], ty = y + dy[tdir];
			if (check(tx, ty, tdir)) {
				q.push({ tx,ty,tdir });
				vis[ty][tx][tdir] = 1;
				pre[ty][tx][tdir] = { x,y,dir };
			}
		}
	}
	return 0;
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		rep(i, 1, n) {
			rep(j, 1, m)	cin >> Map[i][j], memset(vis[i][j], 0, sizeof(vis[i][j]));
		}
		if (bfs()) {
			cout << "YES" << endl;
			print(m, n + 1, 0, 0);
		}
		else cout << "NO" << endl;
	}
	return 0;
}

F-Find 3-friendly Integers

题目大意

定义一个数字含有任意一个子串能够被3整除，称为3友好，给你一个区间L~R，问你这个区间内有多少数是3友好的。

解题思路

根据鸽笼原理，只要位数不少于 3 位，必然出现一组前缀和 %3 相同的位置，所以他们这段区间必然 %3 = 0。

所以只需要判断一下小于100的数即可。

完整代码

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
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		ll l, r; cin >> l >> r;
		ll ans = 0;
		if (r < 100) {
			rep(i, l, r) {
				if (check(i))	ans++;
			}
		}
		else {
			if (l < 100) {
				ans++;
				rep(i, l, 99) {
					if (check(i))	ans++;
				}
				ans += r - 100;
			}
			else ans = r - l + 1;
		}
		cout << ans << endl;
	}
	return 0;
}

G-Game of Swapping Numbers

题目大意

给你两个数组a和b，你需要恰好交换a中的数k次，求$\sum \limits_{i=1}^{n}|a_i-b_i|$的最大值。

解题思路

不得不说这个题解的思路真的很巧妙。

你可以把绝对值拆开，理解成是给$a_i$和$b_i$赋正负号，满足总的+的数量=总的-的数量，最后的结果就是每个数乘上符号的和。

那么答案就是给ai和bi中大的那个赋正号，小的那个赋负号。

为了方便，将A数组记为大数组，B数组记为小数组，即A数组为正，B数组为负。

因为答案是绝对值，所以我们可以任意交换A数组和B数组同一位置的值。

对于交换来说，虽然题目要求是只能交换a数组的值，但是因为答案求的是绝对值，所以其实我们可以任意交换A数组和B数组里的值。

为了最大化和，当减的数组中某个值比加的数组中某个值要大的时候，我们交换他们的符号，这样才能提高和的值，答案增加$2\times(b[i]-a[i])$。

所以只需要把A数组和B数组排序，如果B数组中有大于A数组的，进行交换即可。

注意2单独需要特判一下

完整代码

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
const int N = 5e5 + 5;
int a[N], b[N];

int main() {
	int n, k; cin >> n >> k;
	ll ans = 0;
	rep(i, 1, n)	cin >> a[i];
	rep(i, 1, n)    cin >> b[i];
	if (n == 2) {
		if (k & 1)	cout << abs(a[1] - b[2]) + abs(a[2] - b[1]) << endl;
		else cout << abs(a[1] - b[1]) + abs(a[2] - b[2]) << endl;
	}
	else {
		rep(i, 1, n) {
			if (a[i] < b[i])	swap(a[i], b[i]);
			ans += a[i] - b[i];
		}
		k = min(n, k);
		sort(a + 1, a + 1 + n);
		sort(b + 1, b + 1 + n);
		rep(i, 1, k) {
			if (b[n - i + 1] > a[i])	ans += 2 * (b[n - i + 1] - a[i]);
			else break;
		}
		cout << ans << endl;
	}
	return 0;
}

H-Hash Function

题目大意

定义一个集合S，保证集合S中每一个数都不重复，现在你需要找到最小的整数seed，使集合S中每个数模完seed之后任然不重复。

解题思路

对于任意的i和j，$a_i%seed \neq a_j%seed$，即$|a_i-a_j|% seed\neq 0$，即任意两数的差值都不能被seed整除。

即seed不能是任意差的因子。

所以我们需要快速的找到一个最小的不是任意差的因子的整数，所以我们需要先求出$|a_i-a_j|$的集合，这里就用到了FFT来加速。

具体的应用看大佬的证明。

求出这个集合之后，从小到大枚举看这个数是不是某个差的因子即可，最大枚举到$5e5+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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
typedef complex<double> CP;
const double Pi = acos(-1);
const int N = 5e5;
const int maxn = 1 << 21;
CP a[maxn], b[maxn];
int vis[maxn], n;

void FFT(CP * x, int lim, int inv)
{
    int bit = 1, m;
    CP stand, now, temp;
    while ((1 << bit) < lim) ++bit;
    for (int i = 0; i < lim; ++i)
    {
        m = 0;
        for (int j = 0; j < bit; ++j)
            if (i & (1 << j)) m |= (1 << (bit - j - 1));
        if (i < m) swap(x[m], x[i]);
    }
    for (int len = 2; len <= lim; len <<= 1)
    {
        m = len >> 1;
        stand = CP(cos(2 * Pi / len), inv * sin(2 * Pi / len));
        for (CP* p = x; p != x + lim; p += len)
        {
            now = CP(1, 0);
            for (int i = 0; i < m; ++i, now *= stand)
            {
                temp = now * p[i + m];
                p[i + m] = p[i] - temp;
                p[i] = p[i] + temp;
            }
        }
    }
    if (inv == -1)
        for (int i = 0; i < lim; ++i)
            x[i].real(x[i].real() / lim);
}

int check(int x) {
    for (int i = x; i <= N + 1; i += x) {
        if (vis[i])  return 0;
    }
    return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
    rep(i, 1, n) {
        int x; cin >> x;
        a[x].real(1);
        b[N - x].real(1);
    }
    int lim = 1 << 20;
    FFT(a, lim, 1);
    FFT(b, lim, 1);
    rep(i, 0, lim - 1)    a[i] *= b[i];
    FFT(a, lim, -1);
    rep(i, 0, lim - 1) {
        int x = (int)floor(a[i].real() + 0.5);
        if (x > 0) vis[abs(i - N)] = 1;
    }
    rep(i, n, N + 1) {
        if (check(i)) {
            cout << i << endl;
            break;
        }
    }
	return 0;
}

K-Knowledge Test about Match

题目大意

给定一个a数组为${0,1,\dots,n-1}$，给你一个b数组，你能够任意的交换b数组的顺序，给你一个匹配函数，函数为sqrt，你需要输出和标准的匹配函数误差不超过4%的b数组。

解题思路

举几个例子你会发现，${1,2,3}, {0,1,2}$，$(0,3),(1,1),(2,2)$是最优解，所以我们可以贪心，使差值小的尽可能的多，所以枚举差值即可。

（其实正解是需要小数据KM，大数据贪心的，但是我没学KM

完整代码

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
int num[1010], cnt[1010];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		memset(cnt, 0, sizeof(cnt));
		memset(num, -1, sizeof(num));
		rep(i, 1, n) {
			int x; cin >> x;
			cnt[x]++;
		}
		rep(i, 0, n - 1) {
			rep(j, 0, n - 1) {
				if (cnt[j]) {
					if (j + i < n && num[j + i] == -1) {
						cnt[j]--;
						num[j + i] = j;
					}
					if (cnt[j] > 0 && j - i >= 0 && num[j - i] == -1) {
						cnt[j]--;
						num[j - i] = j;
					}
				}
			}
		}
		rep(i, 0, n - 1) {
			cout << num[i] << ' ';
		}
		cout << endl;
	}
	return 0;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信