我的创新题目

题目概览

名称

项目名称 数列 斐波那契数的长度 区间质数 新挑战
英文名称 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

注意事项

  1. 所有文件名、目录名区分大小写,请严格按照题目要求。

  2. C/C++main()函数返回值必须为(int)0

  3. 评测将在Windows下进行,使用CCR-Plus评测。GCC版本6.3.0(标准为C++14),FPC版本3.0.2。


1.数列

题目描述

维护nn个数列,编号[1,n]\in[1,n]初始时为空。给定mm个操作或询问,要求回答询问。

输入格式

第一行包含两个整数n,mn,m

以下mm行,每行一个操作或询问,格式为optopt和若干个操作数

  1. 操作数i,xi,x,要求在第ii个数列末尾插入数xx

  2. 操作数ii,要求删除第ii个数列的末尾

  3. 操作数i,xi,x,要求在第ii个数列首部插入数xx

  4. 操作数ii,要求删除第ii个数列的首部

  5. 操作数i,ji,j,要求输出第ii个数列第jj个位置的数

  6. 操作数ii,要求输出第ii个数列的末尾

强制在线,令上一次答案为lastanslastans,初始时为0.设输入的操作数xx,则实际的操作数为xlastansx\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

数据范围

测试点 nn的范围 修改末尾 修改首部 随机访问 查询末尾
1 n=1n=1 100\le100 100\le100 100\le100 100\le100
2 n=1n=1 106\le10^6 00 106\le10^6 106\le10^6
3 n=1n=1 106\le10^6 106\le10^6 106\le10^6 106\le10^6
4 n10n\le10 100\le100 100\le100 100\le100 100\le100
5 n200n\le200 106\le10^6 00 10\le10 106\le10^6
6 n200n\le200 106\le10^6 106\le10^6 10\le10 106\le10^6
7 n200n\le200 106\le10^6 00 106\le10^6 106\le10^6
8 n500n\le500 106\le10^6 104\le10^4 106\le10^6 106\le10^6
9 n103n\le10^3 106\le10^6 105\le10^5 106\le10^6 106\le10^6
10 n103n\le10^3 106\le10^6 106\le10^6 106\le10^6 106\le10^6

对于100%的数据,i[1,n]i\in[1,n]x109\vert x\vert\le10^9j[1,cnti]j\in[1,cnt_i]


2.斐波那契数的长度

题目描述

我们都很熟悉斐波那契数列,这里规定

fn={1n=1,2fn1+fn2n3f_n=\begin{cases}1&n=1,2\\ f_{n-1}+f_{n-2}&n\ge3\end{cases}

例如f10=55f_{10}=55,现在请求出fnf_n精确位数。

输入格式

一个正整数nn

输出格式

一个正整数LL,表示fnf_n的位数。

输入样例

10

输出样例

2

样例解释

n=10n=10fn=55f_n=55L=2L=2

数据范围

测试点 数据范围 提示
1 n10n\le10 -
2 n90n\le90 保证fnf_n不超出64位整数[^int]
3 double 保证n1000n\le1000不超出双精度浮点数fnf_n
4 n5000n\le5000 -
5 n20000n\le20000 保证fnf_n不超出扩展浮点数[^float]
6 n30000n\le30000 -
7 n105n\le10^5 -
8 n109n\le10^9 -
9 n1018n\le10^{18} -
10 n1018n\le10^{18} -

3.区间质数

题目描述

求出区间[l,r][l,r]之间质数的个数。

输入格式

两个自然数l,rl,r,用一个空格分隔。

输出格式

一个自然数cntcnt,表示区间[l,r][l,r]之间质数的个数。

输入样例

1 100

输出样例

25

样例解释

[1,100][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,972,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=rl=r l,r100l,r\le100
2 l=rl=r l,r106l,r\le10^6
3 l=rl=r l,r109l,r\le10^9
4 rl100r-l\le100 l,r10000l,r\le10000
5 rl1000r-l\le1000 l,r106l,r\le10^6
6 - l,r106l,r\le10^6
7 - l,r2107l,r\le2*10^7
8 - l,r109l,r\le10^9
9 - l,r109l,r\le10^9
10 - l,r109l,r\le10^9

对于100%的数据,l,r1l,r\ge1

4.新挑战

题目描述

规定无符号整数xx的二进制形式中,1出现的次数为f(x)f(x),要求快速求出任意64位无符号整数的函数值。

如233=11101001,f(233)=5f(233)=5

输入格式

由于本题部分输入规模较大,我们用一些特殊的方法输入,先定义以下输入函数(伪代码)

定义函数next_integer(64位无符号整数i,xi,x)

  • 将64位无符号整数tt 赋值为ii左移(ii模64)

  • 返回 xx异或tt

两个无符号整数n,stn,st,用一个空格分隔。令a0=st,ai=next_integer(i,ai1)a_0=st,a_i=next\_integer(i,a_{i-1}),其中i1..ni\in1..n

输出格式

由于本题部分输出规模较大,我们用一些特殊的方法输出,先定义以下输出函数(伪代码)

定义函数output_arr(无类型指针a,ba,b,64位无符号整数nn)

  • 如果 n模8 不等于0

    • 输出-1
  • aa'等于 指针aa强制转换为64位无符号整数指针

  • bb'等于 指针bb强制转换为64位无符号整数指针

  • 令64位无符号整数ansans等于 nn

  • 令64位无符号整数ii 从1循环到nn

    • ansans 赋值为ansans异或(aia'_i左移bib'_i)
  • 输出 ansans

i1..n\forall i\in1..n,令bi=f(ai)b_i=f(a_i),调用output_arr(a,b,n)即可。

输入样例

5 233

输出样例

29781

样例解释

ii aia_i aia_i的二进制形式 bib_i ansans
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

aia_i的二进制形式只给出了低8位。

数据范围

测试点 数据范围
1 n107n\le10^7
2 n2107n\le2*10^7
3 n3107n\le3*10^7
4 n5107n\le5*10^7
5 n108n\le10^8
6 n2108n\le2*10^8
7 n4108n\le4*10^8
8 n5108n\le5*10^8
9 n8108n\le8*10^8
10 n109n\le10^9

[^int]: Pascal中的int64或C++中的long long

[^float]: Pascal中的extended或C/C++中的long double