比赛赛题由于不可以发布到互联网(鬼知道这套题怎么来的) ,因此截图(只是懒得阐述题意)

T1

0分做法

没有memset,乱搞,使用STL被判定为危险行为。

30分做做法

当事人不愿意透露

60分做法

裸01背包即可

100分做法

乱搞搜索(by:手机qyx)

T2

0分做法

$num,x$输出搞反了(比如我)

10分做法

由于$10$分的数据是保证a中有一个值为1,所以num=1,x=n-1,接下来一行输出1即可

30分做法

枚举左右端点,然后枚举k,就好了。

60分做法

$g[i][j]$表示$i,j$内GCD的最小值

$m[i][j]$表示$i,j$内数字的最小值

这个可以n^2预处理的,表达式为

$mp[i][j]=gcd(mp[i][j-1],mp[j][j])$

$g[i][j]=min(g[i][j-1],g[j][j])$

不出意外的大概是两个,我很喜欢本题的推导(其实挺简单的,一句话就可以说出来)

如果$a[l,r]$区间能被$a[k]~(k\in[l,r]) $整除,那么a[k]一定为区间的最小值,并且该区间gcd一定为a[k]

70分做法

线段树调试的时候一些句子没删(比如我)

90分做法

由于gcd,min可以转换成序列操作,所以直接套一个线段树就好了(可是考试的时候ans,x输出搞反了,导致爆零)

100分做法

考虑本题没有太多修改操作,反而查询操作异常多,所以可以想到用更好的离线算法ST表。

*zzq考场上想到了一个单调队列做法,然后去上了个厕所,cyx跟着出去后,回来也想到了单调队列做法。

T3

据说有一种黑科技算法,可以3S内搞出$10^{11}$内所有质数个数,但是才疏学浅,还没打算去搞懂那个算法。

0分做法

1
2
3
4
5
if(n==10) 
{
cout<<4<<endl;
return 0;
}

40分做法

$O(N\sqrt{N})$ 朴素筛法

60分做法

$O(N)$线筛即可

80分做法

1.线筛,考虑开$10^8$的数组,空间在会爆,难以接受,此时两种方案,第一是线筛,可以过去,但是显然$10^8$难以接受,因此着重讲述本人做法。

2.本人做法

刚开始没打算往筛法去想,认为就是一个裸的水题,打个表就可以了,然后,考试的时候

${10^{11}->10^{9},1MB->100KB}$

于是准备T2瞎搞一通就来想办法优化T3,然后没什么思路,于是考虑到本题可能是个规律题,然后打表找规律

于是探讨了以下几种情况

1.每两个质数差值大概是多少

2.每相差10个质数n的差是多少

于是打表看了一下

每两个质数差值大概在10左右

每相差10个质数差值大概在100

因此想办法打表,刚开始想的是对于每个n打表得$ans[n]$,但是大概在2-3W的时候就破了128KJB,只好另外想个办法。

然后想到了对每个质数打表$p[n]$,然后二分查找第一个小于等于n的质数,下标就是答案。

这个在1e5下面应该是可做的,但是还不如不做,因此又开始想其他优化。

瞎搞的时候发现2性质很好用,此时可以想象我们在做一个分块题,$[1,n]$的质数分为$k$个块,对于前k-1个块,我们可以通过打表找到答案,然后剩下一个块逐一进行普通的$O(\sqrt{N})$暴力判断就好了,时间复杂度大概在$O(\sqrt{N}*K)$ 因为$\sqrt{N}\leq 10000$,时间复杂度在$10^8$以内,然后考虑到2性质,这里K取700是比较保险的,时间复杂度很接近$10^8$这个上限,但是不会超过,实测能过80分的点。

100分做法

就是刚才提到的黑科技。

放在最后的东西

cyx:”我考场写了210的保底分!”