首页 algorithm 算法竞赛 新生赛

本以为比赛的时候会 “坐牢 “，没想到做了 7 个题，还是新生赛适合我鸭

以及 纪念一下因为 double 比大小 WA 了六发的 A

# A 期末复习

A - 期末复习_华中师范大学 - 菜鸟杯程序设计竞赛

显然对于一个矩形

  1. 如果 n == 1 || m == 1 那么一定画不成 “L”

  2. 如果 n == 2 || m == 2 那么一定能用至多两个填满整个矩形，如下图

  3. 在其他的情况下，显然直接画大 “L” 就是最优的，如下图

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k;
bool check(int t)
{
	int x =  ((2 * n - t) * (t + 1) + (2 * m - t) * (t + 1)) / 2 - t - 1;
	int y = n * m;
	return double(x) / y >= 0.6; 
} 
void solve()
{
	cin >> n >> m >> k;
	if(n == 1 || m == 1)
	{
		cout << -1 << '\n';
		return;
	}
	int l = 0, r = min(n - 2, m - 2), mid;
	while(l < r)
	{
		mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;	
	} 
	if(check(l) && l <= min(n - 2, m - 2)) cout << k * (l + 1) << '\n';
	else cout << 2 * k << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--) solve();
	return 0;
}

# B 洛杉矶的火

B - 洛杉矶的火_华中师范大学 - 菜鸟杯程序设计竞赛

对于这个题目，我们发现只有最后一个点是特殊的，即它只需要 “上”，不需要 “下”，也就是说它在 y 方向上只用走一遍。

那么我们可以先忽略掉它的特殊性，让所有的点（除了开始的点）都在 y 方向上走两遍，那么问题就转换成了，我选择哪个点减去它 y 轴走的距离，加上它 x 轴走的距离，这个值是最小的。

显然我们可以将题目划分成两种情况

  1. 终点在开始点的左边

    那么我们就需要先往右走到头，再往左走到头，再返回到左边的终点

    我们就可以当成是先让起点横向走到最右边，然后从右向左遍历；最后的 nowx = 最左边节点的x, nowy = h

    然后遍历求谁的 - abs(y - nowy) + abs(x - nowx) 最小，谁就是终点

  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
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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int n, h, x0, y0;
	cin >> n >> h >> x0 >> y0;
	vector<pair<int, int>> v;
	for(int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		v.push_back({x, y});
	}
	sort(v.begin(), v.end(), [&](pair<int, int> a, pair<int, int> b) {
		return a.first < b.first; 
	});
	//从右往左走 
	int ans1 = abs(h - y0);
	int nowx = x0;
	for(int i = n - 1; i >= 0; i--)
	{
		ans1 += abs(nowx - v[i].first) + 2 * abs(h - v[i].second);
		nowx = v[i].first;
	} 
	int tmp = ans1;
	for(int i = 0; i < n; i++)
	{
		ans1 = min(ans1, tmp + abs(v[i].first - nowx) - abs(v[i].second - h));
	}
	//从左往右走
	int ans2 = abs(h - y0);
	nowx = x0;
	for(int i = 0; i < n; i++)
	{
		ans2 += abs(nowx - v[i].first) + 2 * abs(h - v[i].second);
		nowx = v[i].first;	
	}
	tmp = ans2;
	for(int i = 0; i < n; i++)
	{
		ans2 = min(ans2, tmp + abs(v[i].first - nowx) - abs(v[i].second - h));
	}
	cout << min(ans1, ans2) << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t--) solve();
	return 0;
}

# C 好数

C - 好数_华中师范大学 - 菜鸟杯程序设计竞赛

经过枚举我们可以发现，如果一个数不能被表示成 l + (l + 1) + ... + r 的形式，那么这个数是 2 的整数次幂

于是问题转换成 [l, r] 区间内有多少个 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool check1(int x, int l)
{
	if((1ll << x) >= l) return true;
	return false;
}
bool check2(int x, int r)
{
	if((1ll << x) <= r) return true;
	return false;
}
void solve()
{
	int l, r;
	cin >> l >> r;
	int left = 0, right = 60, mid;
	while(left < right)
	{
		mid = (left + right) / 2;
		if(check1(mid, l)) right = mid;
		else left = mid + 1;
	}
	int minn = left;
	left = 0, right = 60;
	while(left < right)
	{
		mid = (left + right + 1) / 2;
		if(check2(mid, r)) left = mid;
		else right = mid - 1;
	}
	int maxx = right;
	cout << r - l + 1 - (maxx - minn + 1) << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--) solve();
	return 0;
}

# E 交换 offer

E - 交换 offer_华中师范大学 - 菜鸟杯程序设计竞赛

显然我们要会写快速幂，这里就不再赘述

这个概率也似乎很显然 错排数/(n−1)n错排数/(n - 1)^n

那么错排数如何计算呢？这就是高中数学了

我们来一项项看：

假设对于 i ，它的错位排序数为 M(i)

n = 1 ， M(1) = 0

n = 2 ， M(2) = 1

n = 3 ， M(3) = 2

n = 4

对于 1 它有 3 种选择，分别是位置 2 3 4 ，假设它选择位置 3

那么接着分配数字 3 的位置，那么 3 可以总体分为两种选择

  1. 3 放在 1 的位置上， 那么剩下的 2 4 5 ，相当于要求一个 n = 3 的错位排列，即 M(3)
  2. 3 不放在 1 的位置上，那么相当于剩下的 2 3 4 5 ，要求 2 不在 2 上， 3 不在 1 上， 4 不在 4 上， 5 不在 5 上，那么我们可以把 3 看成 1 ，即求 1 ~ 4 的全错位排列，即 M(4)

那么我们可以很容易总结出序列 1 ~ n 的全错位排列的个数是 M(n - 1) + M(n - 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
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int p = 998244353, N = 2e6 + 1;
int f[N];
int qmi(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = res * a % p;
		b >>= 1;
		a = a* a % p;
	}
	return res;
}
void Init()
{
	f[1] = 0, f[2] = 1, f[3] = 2;
	for(int i = 4; i < N; i++)
	{
		f[i] = (i - 1) * (f[i - 2] + f[i - 1]) % p;
	} 
}
void solve()
{
	int n;
	cin >> n;
	int x = f[n];
	int y = qmi(n - 1, n);
	cout << x % p * qmi(y, p - 2) % p << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	Init();
	int t; cin >> t;
	while(t--) solve();
	return 0;
}

# F 植树节

F - 植树节_华中师范大学 - 菜鸟杯程序设计竞赛

博弈论问题

把特殊节点度为 1 的情况单拎出来，讨论

其余的情况，因为它们都不希望达到让特殊节点度为 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int d[N];
void solve()
{
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		d[x]++, d[y]++;
	}
	int x;
	cin >> x;
	if(d[x] == 1)
	{
		cout << "xiaonian wins!";
		return;
	}
	if((n - 1) % 2 == 0) cout << "coldtree wins!";
	else cout << "xiaonian wins!";
} 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

# G 逻辑门

G - 逻辑门_华中师范大学 - 菜鸟杯程序设计竞赛

模拟即可

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<int> a;
	for(int i = 0; i < n; i++) a.push_back(s[i] - '0');
	vector<int> ans; 
	ans.push_back(a[0] ^ a[1]); 
	if(n == 2) 
	{
		ans.push_back(a[0] & a[1]);
		for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
		return;
	}
	int last = a[0] & a[1];
	ans.push_back((a[2] ^ a[3]) ^ last);
	if(n == 4)
	{
		ans.push_back((a[2] & a[3]) | (last & (a[2] ^ a[3])));
		for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
		return;
	}
	last = (a[2] & a[3]) | (last & (a[2] ^ a[3]));
	for(int i = 4; i < n - 1; i += 2)
	{
		ans.push_back((a[i] ^ a[i + 1]) ^ last);
		last = (a[i] & a[i + 1]) | (last & (a[i] ^ a[i + 1]));
	}
	cout << last;
	for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
} 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

# I 找出躺赢狗

I - 找出躺赢狗_华中师范大学 - 菜鸟杯程序设计竞赛

签到题

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<double, string> PII; 
bool cmp(PII a, PII b)
{
	string x = a.second, y = b.second;
	if(a.first != b.first) return a.first < b.first;
	else 
	{
		for(int i = 0; i < min(x.size(), y.size()); i++)
		{
			if(x[i] < y[i]) return 1;
			else if(x[i] > y[i]) return 0; 
		}
		return x.size() < y.size();
	}
}
vector<PII> v;
void solve()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		string x;
		double y;
		cin >> x >> y;
		v.push_back({y, x});
	}
	sort(v.begin(), v.end(), cmp);
	vector<string> ans;
	for(auto t: v)
	{
		if(t.first <= 3.0) ans.push_back(t.second);
		else break;
	}
	cout << ans.size() << '\n'; 
	for(auto t: ans)
	{
		cout << t << '\n';
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; 
	while(t--) solve();
	return 0;
}

# J 音名

J - 音名_华中师范大学 - 菜鸟杯程序设计竞赛

签到题

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<char, int> mp;
void solve()
{
	char a, b;
	cin >> a >> b;
	if(mp[a] > mp[b]) cout << a << '\n';
	else cout << b << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	mp['C'] = 1;
	mp['D'] = 2;
	mp['E'] = 3;
	mp['F'] = 4;
	mp['G'] = 5;
	mp['A'] = 6;
	mp['B'] = 7;
	int t; cin >> t;
	while(t--) solve();
	return 0;
}