我的创新题目
题目概览
名称
| 项目名称 | 数列 | 斐波那契数的长度 | 区间质数 | 新挑战 |
|---|---|---|---|---|
| 英文名称 | list | fiblen | prime | newchal |
| 可执行文件名称 | list.exe | fiblen.exe | prime.exe | newchal.exe |
| 输入文件 | list.in | fiblen.in | prime.in | newchal.in |
| 输出文件 | list.out | fiblen.out | prime.out | newchal.out |
| 每个测试点时限 | 3s | 1s | 1s | 1s |
| 内存限制 | 512MiB^size | 512MiB | 16MiB | 512MiB |
| 测试点数量 | 10 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 | 10 |
时限仅供参考，请以标程运行时间计算
源文件文件名
| 语言名称 | 数列 | 斐波那契数的长度 | 区间质数 | 新挑战 |
|---|---|---|---|---|
Pascal |
list.pas | fiblen.pas | prime.pas | newchal.pas |
C |
list.c | fiblen.c | prime.c | newchal.c |
C++ |
list.cpp | fiblen.cpp | prime.cpp | newchal.cpp |
编译指令
| 语言名称 | 数列 | 斐波那契数的长度 | 区间质数 | 新挑战 |
|---|---|---|---|---|
Pascal |
fpc list.pas -O2 |
fpc fiblen.pas |
fpc prime.pas |
fpc newchal.pas -O2 |
C |
gcc -o list list.c -lm -static -O2 |
gcc -o fiblen fiblen.c -lm -static |
gcc -o prime prime.c -lm -static |
gcc -o newchal newchal.c -lm -static -O2 |
C++ |
g++ -o list list.cpp -lm -static -O2 |
g++ -o fiblen fiblen.cpp -lm -static |
g++ -o prime prime.cpp -lm -static |
g++ -o newchal newchal.cpp -lm -static -O2 |
注意事项
-
所有文件名、目录名区分大小写，请严格按照题目要求。
-
C/C++中main()函数返回值必须为(int)0。 -
评测将在
Windows下进行，使用CCR-Plus评测。GCC版本6.3.0(标准为C++14)，FPC版本3.0.2。
1.数列
题目描述
维护$n$个数列，编号$\in[1,n]$，初始时为空。给定$m$个操作或询问，要求回答询问。
输入格式
第一行包含两个整数$n,m$
以下$m$行，每行一个操作或询问，格式为$opt$和若干个操作数
-
操作数$i,x$，要求在第$i$个数列末尾插入数$x$
-
操作数$i$，要求删除第$i$个数列的末尾
-
操作数$i,x$，要求在第$i$个数列首部插入数$x$
-
操作数$i$，要求删除第$i$个数列的首部
-
操作数$i,j$，要求输出第$i$个数列第$j$个位置的数
-
操作数$i$，要求输出第$i$个数列的末尾
强制在线，令上一次答案为$lastans$，初始时为0.设输入的操作数为$x$，则实际的操作数为$x\oplus lastans$。
输出格式
对于每个询问输出一行一个数，表示答案
输入样例
2 7
1 1 3
3 2 5
3 1 1
5 1 1
6 3
4 4
5 4 4
输出样例
1
5
3
样例解释
实际输入样例
2 7
1 1 3
3 2 5
3 1 1
5 1 1
6 2
4 1
5 1 1
过程
| 编号 | 数列1 | 数列2 | 输出 |
|---|---|---|---|
| 0 | |||
| 1 | 3 | ||
| 2 | 3 | 5 | |
| 3 | 1,3 | 5 | |
| 4 | 1,3 | 5 | 1 |
| 5 | 1,3 | 5 | 5 |
| 6 | 3 | 5 | |
| 7 | 3 | 5 | 3 |
数据范围
| 测试点 | $n$的范围 | 修改末尾 | 修改首部 | 随机访问 | 查询末尾 |
|---|---|---|---|---|---|
| 1 | $n=1$ | $\le100$ | $\le100$ | $\le100$ | $\le100$ |
| 2 | $n=1$ | $\le10^6$ | $0$ | $\le10^6$ | $\le10^6$ |
| 3 | $n=1$ | $\le10^6$ | $\le10^6$ | $\le10^6$ | $\le10^6$ |
| 4 | $n\le10$ | $\le100$ | $\le100$ | $\le100$ | $\le100$ |
| 5 | $n\le200$ | $\le10^6$ | $0$ | $\le10$ | $\le10^6$ |
| 6 | $n\le200$ | $\le10^6$ | $\le10^6$ | $\le10$ | $\le10^6$ |
| 7 | $n\le200$ | $\le10^6$ | $0$ | $\le10^6$ | $\le10^6$ |
| 8 | $n\le500$ | $\le10^6$ | $\le10^4$ | $\le10^6$ | $\le10^6$ |
| 9 | $n\le10^3$ | $\le10^6$ | $\le10^5$ | $\le10^6$ | $\le10^6$ |
| 10 | $n\le10^3$ | $\le10^6$ | $\le10^6$ | $\le10^6$ | $\le10^6$ |
对于100%的数据，$i\in[1,n]$，$\vert x\vert\le10^9$，$j\in[1,cnt_i]$
2.斐波那契数的长度
题目描述
我们都很熟悉斐波那契数列，这里规定
$$f_n=\begin{cases}1&n=1,2\ f_{n-1}+f_{n-2}&n\ge3\end{cases}$$
例如$f_{10}=55$，现在请求出$f_n$的精确位数。
输入格式
一个正整数$n$。
输出格式
一个正整数$L$，表示$f_n$的位数。
输入样例
10
输出样例
2
样例解释
$n=10$，$f_n=55$，$L=2$
数据范围
| 测试点 | 数据范围 | 提示 |
|---|---|---|
| 1 | $n\le10$ | - |
| 2 | $n\le90$ | 保证$f_n$不超出64位整数[^int] |
| 3 | double |
保证$n\le1000$不超出双精度浮点数$f_n$ |
| 4 | $n\le5000$ | - |
| 5 | $n\le20000$ | 保证$f_n$不超出扩展浮点数[^float] |
| 6 | $n\le30000$ | - |
| 7 | $n\le10^5$ | - |
| 8 | $n\le10^9$ | - |
| 9 | $n\le10^{18}$ | - |
| 10 | $n\le10^{18}$ | - |
3.区间质数
题目描述
求出区间$[l,r]$之间质数的个数。
输入格式
两个自然数$l,r$，用一个空格分隔。
输出格式
一个自然数$cnt$，表示区间$[l,r]$之间质数的个数。
输入样例
1 100
输出样例
25
样例解释
$[1,100]$之间的质数有$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$，共有25个。
数据范围
| 测试点 | l,r关系 | 数据范围 |
|---|---|---|
| 1 | $l=r$ | $l,r\le100$ |
| 2 | $l=r$ | $l,r\le10^6$ |
| 3 | $l=r$ | $l,r\le10^9$ |
| 4 | $r-l\le100$ | $l,r\le10000$ |
| 5 | $r-l\le1000$ | $l,r\le10^6$ |
| 6 | - | $l,r\le10^6$ |
| 7 | - | $l,r\le2*10^7$ |
| 8 | - | $l,r\le10^9$ |
| 9 | - | $l,r\le10^9$ |
| 10 | - | $l,r\le10^9$ |
对于100%的数据，$l,r\ge1$。
4.新挑战
题目描述
规定无符号整数$x$的二进制形式中，1出现的次数为$f(x)$，要求快速求出任意64位无符号整数的函数值。
如233=11101001，$f(233)=5$。
输入格式
由于本题部分输入规模较大，我们用一些特殊的方法输入，先定义以下输入函数(伪代码)
定义函数next_integer(64位无符号整数$i,x$)
-
将64位无符号整数$t$ 赋值为$i$左移($i$模64)
-
返回 $x$异或$t$
两个无符号整数$n,st$，用一个空格分隔。令$a_0=st,a_i=next_integer(i,a_{i-1})$，其中$i\in1…n$。
输出格式
由于本题部分输出规模较大，我们用一些特殊的方法输出，先定义以下输出函数(伪代码)
定义函数output_arr(无类型指针$a,b$，64位无符号整数$n$)
-
如果 n模8 不等于0
- 输出-1
-
令$a’$等于 指针$a$强制转换为64位无符号整数指针
-
令$b’$等于 指针$b$强制转换为64位无符号整数指针
-
令64位无符号整数$ans$等于 $n$
-
令64位无符号整数$i$ 从1循环到$n$
- 将$ans$ 赋值为$ans$异或($a’_i$左移$b’_i$)
-
输出 $ans$
$\forall i\in1…n$，令$b_i=f(a_i)$，调用*output_arr(a,b,n)*即可。
输入样例
5 233
输出样例
29781
样例解释
| $i$ | $a_i$ | $a_i$的二进制形式 | $b_i$ | $ans$ |
|---|---|---|---|---|
| 0 | 233 | 11101001 | 5 | 5 |
| 1 | 235 | 11101011 | 6 | 15045 |
| 2 | 227 | 11100011 | 5 | 9893 |
| 3 | 251 | 11111011 | 7 | 23333 |
| 4 | 187 | 10111011 | 6 | 30181 |
| 5 | 27 | 00011011 | 4 | 29781 |
$a_i$的二进制形式只给出了低8位。
数据范围
| 测试点 | 数据范围 |
|---|---|
| 1 | $n\le10^7$ |
| 2 | $n\le2*10^7$ |
| 3 | $n\le3*10^7$ |
| 4 | $n\le5*10^7$ |
| 5 | $n\le10^8$ |
| 6 | $n\le2*10^8$ |
| 7 | $n\le4*10^8$ |
| 8 | $n\le5*10^8$ |
| 9 | $n\le8*10^8$ |
| 10 | $n\le10^9$ |
[^int]: Pascal中的int64或C++中的long long
[^float]: Pascal中的extended或C/C++中的long double