传送门
原题
题目描述
本题为提交答案题。
后台有一个正整数 \(n\)(你不知道 \(n\) 具体的值)。
你有 \(10^3\) 个变量 \(p_1,p_2,\cdots,p_{10^3}\),初始 \(p_1=n\),\(p_2=p_3=\cdots=p_{10^3}=0\)。
你需要写一个程序完成一些任务,程序包含下面几种语句可供使用:
new x
,令 \(n\gets n+1\),\(p_x\gets n\)。dec x
,令 \(p_x\gets p_x-1\)。assign x y
,令 \(p_x\gets p_y\)。iftry x goto l
,如果 \(p_x \ge 0\),跳转到第 \(l\) 条语句。ifeq x y goto l
,如果 \(p_x = p_y\),跳转到第 \(l\) 条语句。ifneq x y goto l
,如果 \(p_x\neq p_y\),跳转到第 \(l\) 条语句。
对于后三种语句,如果当前语句是第 \(\bm{l_0}\) 条,那么要求 \(\bm{l<l_0}\)。
你不得使用超过 \(1000\) 条语句或是标号超过 \(1000\) 的变量。你的程序实际语句运行次数不得超过 \(10^5\)。
令程序执行前的 \(n\) 值为程序的输入,程序执行后的 \(n\) 值为程序的输出,你需要分别完成下面 \(10\) 个任务:
- 输入 \(n\),输出 \(2n\)。
- 输入 \(n\),输出 \(\binom n2\)。
- 输入 \(n\),输出 \(600\)。
- 输入 \(n\),输出 \(n + 1\)。
- 输入 \(n\),输出 \(n^2 - 1\)。
- 输入 \(n\),输出 \(n + 2000\)。
- 输入 \(n\),输出 \(n + \lfloor \log_2 n\rfloor\)。
- 输入 \(n\),输出 \(n + \left(n \bmod 2\right) + 1\)。
- 输入 \(n\),输出 \(n+\gcd(n, n - 4) + 1\)。
- 输入 \(n\),输出一个满足 \(|x-n\ln n|\le 30\) 的正整数 \(x\)。
注:子任务按长度排序,与难度无关。
输入格式
该题为提交答案型试题,每个测试点对应的任务见【题目描述】。
输出格式
针对给定的 \(10\) 个任务,你需要分别提交你的输出文件 1.out
~ 10.out
。
每个文件需要输出若干行。
第一行一个非负整数 \(L\),代表你使用的语句数量。
接下来 \(L\) 行,每行一个语句。
说明/提示
评分标准
对于每个测试点,其内部会评测若干组测试数据。
若你的输出出现下列情况,那么该测试点不得分:
- 输出与要求不符。
- 实际语句运行次数大于 \(10^5\)。
- 出现无法识别或不合法的语句。
- 使用超过 \(1000\) 条语句或是标号超过 \(1000\) 的变量。
否则设对应子任务的评分标准为 \(L_0\),那么你的得分为:
下面给出各个任务对应的评分标准 \(L_0\):
编号 | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) |
---|---|---|---|---|---|---|---|---|---|---|
\(L_0\) | \(3\) | \(9\) | \(233\) | \(1\) | \(10\) | \(29\) | \(14\) | \(7\) | \(18\) | \(14\) |
数据范围
保证 \(5 \le n \le 100\)。
整理&思路
这道题的AC非我一人所为,搜集了大量的资料和思路(后期回顾的时候才发现自己查到资料里有题解QAQ),整理而成…… 虽然查了很多东西,但是也算是我过的第一道黑题吧!特此纪念
Task 1
输出\(2n\)
循环n次加一。
3
dec 1
new 2
ifneq 1 3 goto 1
Task 2
输出\(\binom n2\)
\(\binom n2 = 1+2+\cdots+n-1=2+\cdots+n-2+n\),换句话说就是从2一直循环到n-2。
9
dec 1
dec 1
dec 1
assign 2 1
dec 2
new 3
iftry 2 goto 5
dec 1
ifneq 1 4 goto 4
Task 3
输出\(600\)
\(600 = n + 600 -n\),构造\(600-n\)次循环, 相反数为\(n-600\),\(600\)也就是\(24\times 25\),开始循环。
35
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
assign 3 2
dec 3
dec 4
assign 5 6
dec 5
dec 1
ifneq 5 3 goto 29
ifneq 4 2 goto 27
dec 6
new 8
ifneq 1 6 goto 33
Task 4
输出\(n+1\)
不必理会。
1
new 1
Task 5
输出\(n^2-1\)
根据平方差公式,可以得到:
嵌套两个次数分别为 x 和 y 的循环,相当于执行 xy 次。所以嵌套两个次数分别为 n−2 和 n+1 的循环即可。
10
assign 2 1
dec 2
dec 2
new 4
dec 1
assign 3 2
dec 3
new 4
ifneq 3 5 goto 7
iftry 1 goto 5
Task 6
输出\(n+2000\)
很显然,\(n+2000=n+2*10*10*10\),相乘即可。
24
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 2
dec 3
dec 3
dec 4
assign 5 8
dec 5
assign 6 8
dec 6
assign 7 8
dec 7
new 9
ifneq 7 2 goto 19
ifneq 6 2 goto 17
ifneq 5 2 goto 15
ifneq 3 4 goto 13
Task 7
输出\(n+\lfloor\log_{2}{n}\rfloor\)
我们让一个变量的初始值设为2,每次都让这个变量 \(p=p\times 2\),令n+1。我们同时可以定义一个计数器,让他初始值为n,如果n为0就跳出循环(iftry)。
13
dec 4
dec 4
dec 1
dec 1
assign 5 4
assign 7 100
dec 5
dec 7
dec 1
ifneq 4 7 goto 7
assign 4 5
new 101
iftry 1 goto 5
Task 8
输出\(n + (n\bmod 2) + 1\)
获取n mod 2的方法我在一道蓝题题解已经说过了。这里不再赘述,详细去看洛谷P2261 [CQOI2007] 余数求和
这道题。
6
dec 1
dec 1
iftry 1 goto 1
new 101
dec 2
ifeq 1 2 goto 4
Task 9
输出\(n + gcd(n-4) + 1\)
很明显,只需要使用Task 8的操作就好了。
18
dec 1
dec 1
dec 1
dec 1
assign 2 1
dec 2
iftry 2 goto 1
dec 3
dec 3
assign 4 3
dec 4
dec 4
new 101
new 101
dec 1
dec 1
ifeq 1 4 goto 14
ifeq 1 3 goto 13
Task 10
输出一个满足 \(|x-n\ln n|\le 30\) 的正整数 \(x\)。
因为\(y = n \ln n\)与\(y = \frac{13n}{3}\)特别相似,所以我们可以直接让n增加\(\frac{10n}{3}\)。此时外面的\(3n\)可以嵌套,里面的\(\frac{n}{3}\)可以让\(p_{1}\)每次减去3得到近似值。
14
dec 2
dec 2
dec 2
dec 3
assign 4 1
new 101
dec 4
ifneq 4 100 goto 6
ifneq 2 3 goto 4
new 101
dec 1
dec 1
dec 1
iftry 1 goto 10
提交
在洛谷提交的时候注意把文件命名为1.out
~ 10.out
,然后打包成.zip
格式再通过文件提交给洛谷。这道题很费时间,但是整出来还是挺有成就感的。
恭喜AC!