转载请注明出处:http://tokitsukaze.live/

比赛链接:https://ac.nowcoder.com/acm/contest/308


Nowcoder Practice Contest 33

出题:tokitsukazewinterzz1

验题:calabash_boymeopass_0v0Heaven_tenderyuzukoapplese


赛前:

验完题感觉A和E太水了,本来想换,想想还是算了,A就当个签到,E就当个hash练习题好了。

本场代码量最大的估计是C。

当时缺个F,winterzz1提供了F的1e6版本,我嫌太水,就加了3个0,m改为100。

结果验题时,calabash_boy:一个大大的矩阵快速幂。m^3*log1e9,似乎刚刚好?

牛客那边派出了牛逼网友zzq验题,zzq:半小时ak。

预测:估计至少有30个ak吧。

 

赛后:

验题人calabash_boy把F一血拿了,过分!

这个A是什么情况…其他的不说,怎么有一堆tle的。

C过了100个,感觉海星。

只有16人ak。

board


A.tokitsukaze and Counting

Author:tokitsukaze。

题解:

ans=r/x-(l-1)/x

 

B.tokitsukaze and RPG

Author:tokitsukaze。

题解:

数数xi的个数,用埃筛的方式计数。然后for一遍找到最大值,再for一遍统计最大值数量即可。

时间复杂度O(nlogn)。

 

C.tokitsukaze and Number Game

Author:tokitsukaze。

题解:

首先一个结论:若后三位能被8整除,那么这个数就能被8整除。

那么做法就是贪心,前面的数尽量大,后三位的每位都尽量小,而且排列后能被8整除。

实现方式比较多(?),这里仅说一下std做法。

特判掉只有1位和2位,这里注意不能直接判能不能被8整除,比如23->32。

预处理后3位能被8整除的所有情况,每种情况按字典序降序后,再总体按字典序升序。

比如:104->410,112->211。字典序211<410。

然后数数每个数字的个数。从小到大(指的是字典序)枚举预处理的3位数,看看数字够不够拼,够就用这3位当末尾的3位。(都不够就是-1了)

然后把这3位取出来。其他的数从大到小sort。这3位做个全排列,取个最大能被8整除的数,拼起来就是答案。

 

D.tokitsukaze and Inverse Number

Author:tokitsukaze。

题解:

先树状数组求逆序数,然后有个结论。

结论:1到n的排列,任意交换两个数,逆序数奇偶性发生改变。

ans=(操作前的序列的逆序数+需要交换多少次才能变成操作后的序列(不需要求最小操作次数))%2。

证明:prove

 

E.tokitsukaze and Similar String

Author:tokitsukaze。

题解:

hash练习题。

预处理所有26种变化的hash表,用hash表来判断子串是否相等。

假设x的第i种变化与y相等,ans=min(i,26-i)。

都不相等就-1。

 

F.tokitsukaze and Unlimited Array

Author:

winterzz1(牛客练习赛34出题人),n=1e6。

tokitsukaze:n=1e6 —> n=1e9。

题意:给你一个最高项为n的多项式数列,问你它的第n+1阶差分数组非0项的和是多少

题解:
通过暴力程序可以找到规律,答案等于A*n!,A为最高项的系数。
1e9!可以用分块打表实现。
暴力打表,存下1e7,2e7,3e7,…,1e9-1e7,1e9。总共100个数。
然后比如要求(2e7-1)!,那就从表中2e7开始往下接着算。
时间复杂度为O(1e7)。

证明:
多项式数列求差分可以类比一下多项式求微分。
我们先看一下多项式函数求微分的过程。
△y=f(x+△x)-f(x)=f(x)’△x+o(△x)
然后lim △x->0的时候o(△x)/△x充分小所以等于0,因为o(△x)对于△x是高阶无穷小。
也就是△y=f(x)’△x。这个也就是微分公式。
然后离散条件下△x=1。
这时候虽然△y≠f(x)’△x,因为在△y=f(x)’△x+o(△x)这一步的时候,△x不充分小(等于1),o(△x)不可忽略。
但是我们也可以把它写成△y=f(x)’△x+o(△x)的形式,把△x=1代入得△y=f(x)’+α。余项α是一个最高项的幂次小于f(x)’最高项幂次的多项式。
那么在利用△y=f(x)’+α迭代求差分的时候,余项α先比f(x)’差分成0。也就是不用考虑α对第n阶差分产生的贡献。
则最终产生贡献的式子为△y=f(x)’。
答案的贡献就是n阶多项式的n阶导数,记为f(x)^(n)。由多项式高阶求导公式得f(x)^(n)=A*n!。