我的创新题目 题解和标程

1.数列

概述

维护多个数列,要求每个数列支持修改首部、尾部,支持随机访问。而且时间复杂度应该为O(1)O(1)O(logn)O(\log n)(需要卡常?)

非正解

测试点#1~#3

如果只有一个数列,那么问题就非常简单了。

只要维护一个头指针和尾指针,开始时在数组中间。这样可以轻松地插入、删除、随机访问了。

期望得分:30

离线方法

有了处理一个数列的方法,我们只需对所有操作排序,依次处理每个数列即可。

链表维护

我们可以维护nn个链表,那么插入、删除操作都是O(1)O(1)的,但是随机访问是O(n)O(n)的。

可以使用std::list,也可以自己实现链表。

期望得分:40

std::vector维护

std::vector也可以用来维护数列,其中修改尾部和随机访问操作是O(1)O(1)的,修改首部操作是O(n)O(n)的(但是比数组快,有人认为接近于n\sqrt n)。

期望得分:60(其中测试点#8就利用了std::vector的快速修改首部操作)

分段骗分

综合一个数列、链表和std::vector,按照测试点特征选择方法,其中有的测试点可以用多种方法通过。

期望得分:80(很良心吧)

正解(欢迎补充)

std::deque

这其实是我最初的目的,数列维护的其实就是deque(double end queue,双端队列)。要求的所有操作都是O(1)O(1)的,实际运行也最快。

std::map

考虑最早的一个数列的解法,由于没有空间开所有的数列,所以不能做多个数列的情况。

而我们可以用std::map来作为数组,以节省空间。这样所有操作都是O(logn)O(\log n)的,但是可以通过本题,虽然是最慢的。

hash

既然可以用平衡树,那么也可以用hash来作为数组,除了手写以外,还有一下方法:

  • std::unordered_map(c++11) 速度较快

  • __gnu_pbds::cc_hash_table 速度很快,但是gp_hash_table无法通过本题

  • __gnu_cxx::hash_map(deprecated) 不建议使用

理论所有操作的时间复杂度也是O(1)O(1)的,但是比std::deque慢。

关于I/O

数据规模

这题的输入和输出数据都很大,有41064*10^6个操作,输入文件最大有78.6MiB,输出文件最大有21.8MiB。

解决方法

必须使用I/O优化,可以使用逐字符读写(可能无法用std::map卡过),也可以用fread/fwrite更加高效(标程使用)。函数原型如下:

1
2
std::size_t fread( void* buffer, std::size_t size, std::size_t count, std::FILE* stream );
std::size_t fwrite( const void* buffer, std::size_t size, std::size_t count, std::FILE* stream );

其中buffer为I/O缓冲区,对于文本文件size应该为1,count为缓冲区大小,stream为待操作的文件流。

Pascal

Free Pascal中也有类似的过程BlockRead/BlockWrite

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure BlockRead(var f: File; var Buf; count: Int64;var Result: Int64)
procedure BlockRead(var f: File; var Buf; count: LongInt;var Result: LongInt)
procedure BlockRead(var f: File; var Buf; count: Cardinal;var Result: Cardinal)
procedure BlockRead(var f: File; var Buf; count: Word; var Result: Word)
procedure BlockRead(var f: File; var Buf; count: Word;var Result: Integer)
procedure BlockRead(var f: File; var Buf; count: Int64)

procedure BlockWrite(var f: File; const Buf; Count: Int64;var Result: Int64)
procedure BlockWrite(var f: File; const Buf; Count: LongInt;var Result: LongInt)
procedure BlockWrite(var f: File; const Buf; Count: Cardinal;var Result: Cardinal)
procedure BlockWrite(var f: File; const Buf; Count: Word;var Result: Word)
procedure BlockWrite(var f: File; const Buf; Count: Word;var Result: Integer)
procedure BlockWrite(var f: File; const Buf; Count: LongInt)

其实这两个过程在Turbo Pascal中就存在,但是没有Result。其中f必须为无类型文件,Result保存成功的大小。必须指定Result,或者使用{$I-}。

获取输入文件大小

有时我们无法计算输入文件大小,可以用以下的方法来获取:

1
2
3
4
fseek(fin,0,SEEK_END);//将文件流定位到结尾处
long fsize=ftell(fin);//获取当前位置
pin=bufin=new char [fsize+1];//分配缓冲区 pin为输入指针 bufin为输入缓冲区起始位置
rewind(fin);//将文件流定位到开始处

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<deque>
#include<cctype>
using namespace std;
FILE *fin,*fout;
char *bufin,*bufout,*pin,*pout;
inline void read(int& x)
{
for(;isspace(*pin);pin++);
int sign=1;
if(*pin=='-')
sign=-1,pin++;
x=0;
for(;isdigit(*pin);pin++)
x=x*10+*pin-'0';
x*=sign;
}
int d[15];
inline void writeln(int x)
{
if(x<0)
*pout++='-',x=-x;
int cnt=0;
do
d[++cnt]=x%10;
while(x/=10);
for(;cnt;cnt--)
*pout++=d[cnt]+'0';
*pout++='\n';
}
int main()
{
fin=fopen("list.in","r");
fout=fopen("list.out","w");
fseek(fin,0,SEEK_END);
long fsize=ftell(fin);
pin=bufin=new char [fsize+1];
rewind(fin);
fread(bufin,1,fsize,fin);
bufin[fsize]='\0';
int n,m;
read(n);read(m);
pout=bufout=new char [m*12];
deque<int> *a=new deque<int> [n+1];
int lastans=0;
while(m--)
{
int opt,i,j;
read(opt);
switch(opt)
{
case 1:
read(i);read(j);
a[i^lastans].push_back(j^lastans);
break;
case 2:
read(i);
a[i^lastans].pop_back();
break;
case 3:
read(i);read(j);
a[i^lastans].push_front(j^lastans);
break;
case 4:
read(i);
a[i^lastans].pop_front();
break;
case 5:
read(i);read(j);
writeln(lastans=a[i^lastans][(j^lastans)-1]);
break;
case 6:
read(i);
writeln(lastans=a[i^lastans].back());
break;
}
}
delete [] a;
fwrite(bufout,1,pout-bufout,fout);
fclose(fin);fclose(fout);
delete [] bufin;
delete [] bufout;
return 0;
}

2.斐波那契数的长度

概述

计算斐波那契数的位数。

非正解

测试点#1~#5

使用题目提示的类型,最高为扩展精度浮点数。

期望得分:50

矩阵快速幂

我实现了一种用于计算位数的浮点数bigfloat(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct bigfloat
{
static const double LIMIT=1e150;
static const int DIGITS=150;
double d;
long long overcnt;
bigfloat()
{
d=overcnt=0;
}
bigfloat(double x,long long oc=0):d(x),overcnt(oc){};
inline void adjust()
{
if(d>LIMIT)
{
overcnt++;
d/=LIMIT;
}
}
bigfloat operator+(const bigfloat& b)const
{
if(overcnt>b.overcnt)
return *this;
if(overcnt<b.overcnt)
return b;
bigfloat res(d+b.d,overcnt);
res.adjust();
return res;
}
bigfloat operator+=(const bigfloat& b)
{
return *this=*this+b;
}
bigfloat operator*(const bigfloat& b)const
{
bigfloat res(d*b.d,overcnt+b.overcnt);
res.adjust();
return res;
}
};

由于双精度浮点数的运算速度比扩展精度快,所以使用double保存。d保存尾数和部分阶码,而overcnt保存溢出部分的计数。表示的数的位数等于log10(d)+1+overcnt*bigfloat::DIGITS

然而这种方法存在严重的精度问题,主要由矩阵快速幂引起。

期望得分:50

正解

公式

可以得出斐波那契数列的通项公式,参考https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97:

fn=(1+52)n(152)n5f_n=\frac{(\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)^n}{\sqrt5}

当计算位数时,可以简化为fn=(1+52)n5f_n=\frac{(\frac{1+\sqrt5}2)^n}{\sqrt5}

因此,答案为(lg1+52)nlg5+1\left\lfloor(\lg\frac{1+\sqrt5}2)*n-\lg\sqrt5\right\rfloor+1

精度问题

请使用扩展精度浮点数以避免精度问题,其实浮点数精度问题并不玄学,可以这样解释(假设一般使用双精度浮点数):

  • 双精度浮点数尾数有52位,可以连续精确表示的最大整数为2531910152^{53}-1\approx9*10^{15}

  • 扩展精度浮点数尾数有63位,可以连续精确表示的最大整数为26411.810192^{64}-1\approx1.8*10^{19}

此外,单精度浮点数只有23位尾数,而Turbo Pascal中的real有40位尾数。

标程

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<fstream>
#include<cmath>
using namespace std;
ifstream fin("fiblen.in");
ofstream fout("fiblen.out");
int main()
{
long long n;
fin>>n;
fout.precision(0);
fout<<fixed<<floor(log10((1.0L+sqrt(5.0L))/2.0L)*n-log10(sqrt(5.0L)))+1<<endl;
return 0;
}

浮点数后缀L表示long double类型。

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define __USE_MINGW_ANSI_STDIO 1
#include<stdio.h>
#include<math.h>
int main()
{
FILE *fin=fopen("fiblen.in","r");
FILE *fout=fopen("fiblen.out","w");
long long n;
fscanf(fin,"%lld",&n);
fprintf(fout,"%.0Lf\n",floorl(log10l((1.0L+sqrtl(5.0L))/2.0L)*n-log10l(sqrtl(5.0L)))+1.0L);
fclose(fin);
fclose(fout);
return 0;
}

注意定义__USE_MINGW_ANSI_STDIO宏是为了在Windows下使用%lld和%Lf,默认不支持;在其他平台没有影响。注意对于long double,必须使用带l后缀的数学函数(C++有函数重载)。

Pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
program fiblen;
uses
math;
var
n:int64;
begin
assign(input,'fiblen.in');
reset(input);
assign(output,'fiblen.out');
rewrite(output);
read(n);
writeln(trunc(log10((1+sqrt(5))/2)*n-log10(sqrt(5)))+1);
close(input);
close(output);
end.

Free Pascal默认以extended作为浮点数类型。

计算更高的精度

使用__float128

在i386和x86_64体系下,GCC支持四精度浮点数__float128,包括数学函数和I/O函数。__float128有112位尾数。

这些函数定义在<quadmath.h>中,数学函数以q为后缀;I/O函数包含strtoflt128和quadmathsnprintf。使用这些函数必须连接libquadmath.\_float128常量使用Q后缀。

1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
#include<quadmath.h>
int main()
{
__float128 n;
char buf[50];
scanf("%s",buf);
n=strtoflt128(buf,NULL);
quadmath_snprintf(buf,sizeof(buf),"%.0Qf",floorq(log10q((sqrtq(5.0Q)+1.0Q)/2.0Q)*n-log10q(sqrtq(5.0Q)))+1.0Q);
printf("%s\n",buf);
return 0;
}

使用GNU MPFR

MPFR是一个多精度浮点数库,基于GMP库。以下的示例使用了一种C++接口MPFR C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
#include<mpreal.h>
using namespace std;
using namespace mpfr;
int main()
{
string s;
cin>>s;
mpreal::set_default_prec(digits2bits(s.length()+10));
mpreal n(s),sqrt5(sqrt(mpreal(5.0)));
cout.precision(0);
cout<<fixed<<floor(log10((sqrt5+1.0)/2.0)*n-log10(sqrt5))+1<<endl;
return 0;
}

3.区间质数

概述

求出区间的质数个数。

非正解

朴素判断质数

时间复杂度为O(nn)O(n\sqrt n)

期望得分:50

筛数

使用埃氏筛法或欧拉筛法,能通过测试点#6,使用bitset可以通过测试点#7。

期望得分:70(在前一种方法的基础上)

正解

分块打表,选择适当的块大小和适当的判断质数的方法。

标程选择块大小为51055*10^5,那么每次最多需要判断10610^6个数是否为质数。显然使用朴素方法无法通过,所以使用Miller Rabin算法,能在大约O(logn)O(\log n)的时间内判断一个数是否为质数。

但是如果选择不当,该算法有一定概率出错。但是对于题目要求的范围,只要判断2,7,61就可以保证正确性了。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<fstream>
using namespace std;
ifstream fin("prime.in");
ofstream fout("prime.out");
const int k=500000,ans[]={41538,...};
//因长度所限,请自行打表
int qmod(int a,int b,int p)
{
long long ans=1,now=a;
do
{
if(b&1)
ans=(ans*now)%p;
now=(now*now)%p;
}
while(b>>=1);
return ans;
}
bool mr_test(int n,int a)
{
if(n==2)
return true;
if(!(n&1))
return false;
int d=n-1;
while(!(d&1))
d>>=1;
long long t=qmod(a,d,n);
while(d!=n-1&&t!=n-1&&t!=1)
{
t=t*t%n;
d<<=1;
}
return t==n-1||(d&1);
}
bool miller_rabin(int x)
{
if(x<2)
return false;
int a[]={2,7,61};
//enough for unsigned int
for(int i=0;i<3;i++)
{
if(x==a[i])
return true;
if(!mr_test(x,a[i]))
return false;
}
return true;
}
int cntrange(int l,int r)
{
int ans=0;
for(int i=l;i<=r;i++)
ans+=miller_rabin(i);
return ans;
}
int main()
{
int l,r;
fin>>l>>r;
int cnt=0;
for(int i=l/k;i<=r/k;i++)
cnt+=ans[i];
fout<<cnt-cntrange(l/k*k,l-1)-cntrange(r+1,r/k*k+k)<<endl;
return 0;
}

注意标程中块的范围为[kx,kx+k)[kx,kx+k)