CYSYOI 2022 Round #1 赛后题解报告

我是个 大聪明，一个 200 分的蒟蒻忍泪前来写题解和赛后报告。/kk

赛后题解

T1 CHT去挖矿

题目详情

算法解析

好的，一道大模拟。直接上代码吧。

AC Code

#include <bits/stdc++.h>

using namespace std;

long long n, k;
long long klp, js;

int main() {
	// freopen("mine.in", "r", stdin);
	// freopen("mine.out", "w", stdout);

	cin >> n >> k;

	js = ((n * 4) - k) / (4 - 2);
	klp = n - js;

	cout << klp << " " << js << endl;
	return 0;
}

T2 MKX挖钻石

题目详情

算法解析

好的又是一道大模拟。直接上代码。

AC Code

#include <bits/stdc++.h>

using namespace std;

long long n, v, s, w;
long long a, b;
long long blood, ans;

int main() {
	// freopen("diamond.in", "r", stdin);
	// freopen("diamond.out", "w", stdout);

	cin >> n >> v >> s >> w;
	blood = s;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		blood = blood - (b * v);
		if (blood <= 0) break;
		ans += a;
		blood = blood + (a * w);
		if (blood > s) blood = s;
	}
	cout << ans << endl;
	return 0;
}

T3 CXY的传送阵

题目详情

看到这题其实我已经眼前一黑了，时间计算是什么东西啊喂当时有两种思路：

1. 一层层判断，会很丑陋（然后我真就这样写了）
2. 全部转换成秒

其实官方题解给的也是这个思路，所以实际上我是蒟蒻……

算法解析

官方题解的思路是使用 string来输入，这可以保证输入的格式，然后进行转换，也就是将 string 转换为 int。
然后就是细节了，如果 h 是 20开头，那就直接输出 Now；如果是 21 开头那就只能 m == 0 && s == 0 才能输出 Now了。
接下来就只剩下不是 Now 的情况了：

1. 转换成秒来处理
2. 如果 h 是 20 之前的，那就直接计算 \(20 \times 60 \times 60 - 当前时间\)
3. 如果 h 是 21 之后的，那就需要 \(24 \times 60 \times 60 - (当前时间 - 20 \times 60 \times 60)\)。Tips：分两段，24 时前和 24 时后。
   最后输出的时候再重新转换成 hh-mm-ss 的格式去输出。

AC Code

#include <bits/stdc++.h>

using namespace std;
#define ll long long

ll t;

int main()
{
	// freopen("teleport.in", "r", stdin);
	// freopen("teleport.out", "w", stdout);
	scanf( "%lld", &t );
	while ( t-- )
	{
		string a;
		cin >> a;
		ll h, m, s;
		h = (a[0] - '0') * 10 + (a[1] - '0');     /* 转化 */
		m = (a[3] - '0') * 10 + (a[4] - '0');
		s = (a[6] - '0') * 10 + (a[7] - '0');
		if ( h == 20 || (h == 21 && m == 0 && s == 0) ) /* 范围内 */
		{
			cout << "Now" << endl;
			continue;
		}
		ll ans = 0, sec;
		sec = h * 3600 + m * 60 + s;                    /* 每天的第几秒 */
		if ( sec < 20 * 3600 )
			ans = 20 * 3600 - sec;
		else ans = 24 * 3600 - (sec - 20 * 3600);
		h = ans / 3600;
		m = ans % 3600 / 60;
		s = ans % 60;                             /* 转化 */
		if ( h < 10 )
			cout << 0 << h;
		else cout << h;
		cout << ":";
		if ( m < 10 )
			cout << 0 << m;
		else cout << m;
		cout << ":";
		if ( s < 10 )
			cout << 0 << s;
		else cout << s;
		cout << endl;
		/*
		 * 输出
		 * 输出代码
		 */
	}
	return(0);
}

T4 CYH烧矿

题目详情

算法解析

贪心 + 模拟。

我们应该让尽可能多地机器进行工作，如果把燃料全部投入到少数几个机器上，那么很容易到达上限。而燃料越分散，则越不容易达到上限。为什么每次思路总是和题解一样写总是写不出来啊awa

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, m, k, q, t, ans;

int main() {
	// freopen("firing.in", "r", stdin);
	// freopen("firing.out", "w", stdout);

	cin >> n >> m >> k >> q >> t;

	if (m / n >= k) {		// 都有煤可烧
		ans += min((m / n + 1) * (m % n) * t, (m % n) * q);
		ans += min((m / n) * (n - m % n) * t, (n - m % n) * q);
		cout << ans << endl;
		return 0;
	}
	if (m / n < k) {		// 没有都分有煤
		ll cbs = m / k, cba = m % k / cbs, left = m % k % cbs;
		ans += min((cbs - left) * (k + cba) * t, (cbs - left) * q);
		ans += min(left * (k + cba + 1) * t, left * q);
		cout << ans << endl;
		return 0;
	}
	return 0;
}

还有数学总结版的

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, m, k, q, t, ans;

int main() {
	// freopen("firing.in", "r", stdin);
	// freopen("firing.out", "w", stdout);

	cin >> n >> m >> k >> q >> t;
	ll size = m / k;
	
	if (size <= n) cout << min(t * m, size * q);	// 如果机器总数在 n 的范围内，那就是在这两者中取最小值即可
	else cout << min(n * q, t *m);		// 如果机器总数大于 n，那就是在n * q 和 t * m 取最小值即可

	return 0;
}

赛后总结

比赛看到第三题是时间计算就慌神了，写不出来后就滚去做 T4，T4 只能想到 \(\mathcal{O(n)}\) 的朴素做法，怕超时，就又滚去做 T3，然后写到最后想起来还有个东西叫 %02d 的东西可以补齐 0，然而因为没有看时间最后也写不出来，写了个骗分就交上去了。

所以最近要多练习一下大模拟，复习一下基础算法，然后继续学习数据结构！

Ja，MaDaRaNe~