挖土机 CSP-J 模拟赛 ~ 第十六场

先给个简易题解，完整题解标程晚些给出

水浒

显然答案为 $a-\lfloor \frac{a}{b}\rfloor \times b$，为了避免细节推错了，更好的做法是在 $\lfloor \frac{a}{b}\rfloor$ 周边看看要不要调整。

#include <bits/stdc++.h>
using namespace std;
double a, b;
int main()
{
    freopen("shui.in", "r", stdin);
    freopen("shui.out", "w", stdout);
    cin >> a >> b;
    double k = floor(a / b);
    while (a <= k * b)
        k -= 1;
    while (a > (k + 1) * b)
        k += 1;
    cout << fixed << setprecision(12) << a - k * b;
    return 0;
}

三国

本身是个简单的模拟题，但要注意 $m\text{MiB}$ 最后可以到 $2^{63}\text{Byte}$，所以要用 unsigned long long，假设数组空间大小为 $s$，显然 $s$ 也能到这个级别，那直接乘以 $2$ 是有可能超过 unsigned long long 的范围的，所以可以把 $s\times 2$ 和 $m$ 的比较改为 $s$ 和 $\frac{m}{2}$ 的比较

#include <bits/stdc++.h>
using namespace std;
int n;
unsigned long long m;
int main()
{
    cin >> n >> m;
    m = m * 1024 * 512; // 一半的空间Byte
    unsigned long long sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int ri;
        cin >> ri;
        unsigned long long now = 1;
        for (int j = 1; j <= ri; j++)
        {
            unsigned long long aij;
            cin >> aij;
            now = now * aij;
        }
        sum += now * 4;
    }
    if (sum <= m)
        cout << "No\n";
    else
        cout << "Yes\n";

    return 0;
}

西游

• 第一题给两个奇数即可
• 第二题需要输出两个相加会炸 int 的数据，输出两个 ${10}^{18}$ 就好了
• 第三题没有考虑 $1$ 的情况，输出 $1$ 即可
• 第四题主要没考虑输入数据的类型可能会超 int，以及朴素的质数判断会不会超时的问题，给个很大的质数就好

#include <bits/stdc++.h>
using namespace std;
int main()
{
	freopen("xi.in", "r", stdin);
	freopen("xi.out", "w", stdout);
	int n;
	cin >> n;
	if (n == 1)
		cout << "1 1";
	if (n == 2)
		cout << "1000000000000000000 1";
	if (n == 3)
		cout << "1";
	if (n == 4)
		cout << "2147483648";
	return 0;
}

红楼

看完题后容易发现，直接输出 $n$ 个 Miao; 就能拿到 $60$ 分了。

满分的 $n$ 比较大，我想的做法是找到一个倍增的构造方法，即 $(((1\times 2+1)\times 2+0)\times 2+0)\times 2+0=24$ 类似的方式，显然只需要 $logN$ 层就能完成，可以用一个位置存当前的数，然后把他放两次到末尾，再执行一次 ADD，再放回来，再 POP 就完成了 $\times 2$了。$+0$ 不用管，$+1$ 就再放回来之前再放个 $1$ 过去 ADD 就好了。

还有更多别的构造方法，比如初始允许 ${10}^4$ 个 $Miao$ 和最多 $1000$ 项，因此可以给个 $2000$ 然后输出多次 $2000$（显然最多 ${10}^6÷2000=500$ 次），然后剩下的部分再来给一个固定的哪个数字就可以了。

当然你也可以利用减法和 JE 实现一个循环，但是这个就有点麻烦了。大家可以想想怎么实现循环。这实际上就是一个简陋的汇编语言了。如果列表可以无限长，那么是图灵完备的。

下面给出倍增的构造方法。

#include <bits/stdc++.h>
using namespace std;
// 1: +1
// 2: *2
string ops;
string ans_num;
int main()
{
	freopen("hong.in", "r", stdin);
	freopen("hong.out", "w", stdout);
	int n;
	cin >> n;
	while (n > 1)
	{
		if (n % 2 == 1)
			ops += "1";
		ops += "2";
		n /= 2;
	}
	// 跳转到程序部分
	ans_num += "83";
	// 数据初始是 1
	ans_num += "1";
	// 开始程序，若干个 E[2]*=2 和 E[2]+=1
	for (int i = (int)ops.size() - 1; i >= 0; i--)
	{
		if (ops[i] == '2')
			ans_num += "42426523";
		if (ops[i] == '1')
			ans_num += "42216523";
	}
	ans_num += "4213";
	for (int i = 0; i < ans_num.size(); i++)
	{
		for (int j = 0; j < ans_num[i] - '0'; j++)
			cout << "Miao";
		cout << ";";
	}
	return 0;
}
/*
程序规划
E[0],E[1] 用来跳转到程序的部分 (JMP 3)
E[2] 来存储当前的数

E[3] 开始存储程序部分
翻倍操作：LOAD E[2] LOAD E[2] ADD SAVE E[2] POP
		 4    2    4    2    6   5    2    3
加1操作：LOAD E[2] PUSH 1 ADD SAVE E[2] POP
		4    2    2    1 6   5   2     3
打印 E[2]: LOAD E[2] MEOW POP
		   4    2    1    3
*/