【HDU ACM Steps刷题记录 Chapter 2】

源代码

https://github.com/stdKonjac/OJ-Submits

刷题记录

2018.9.6

2.1.1 最小公倍数:结论题,最小公倍数(lcm)*最大公约数(gcd)=两数乘积(x*y),反过来lcm=x*y/gcd(x,y)

2.1.2 How many prime numbers:素数判定,对每个数从2到sqrt(x)检查看有没有因子(如果x=2特判即可),有则不是素数,否则是

2.1.3 相遇周期:这哪个神奇出题人出的题,题目解释反了!26501/6335,不是表示转26501圈要6335天,而是26501天能转6335圈……所以行星周期为天数/圈数(得出转一圈需要多少天),然后求两个行星周期的最小公倍数即可。

这里的“分数最小公倍数”,指的是能整除两个分数的最小分数(比如1/6和1/4,最小公倍数就是1/2)。

分数最小公倍数的求法:先把分数化为最简形式,然后最小公倍数即为分子的最小公倍数/分母的最大公约数

还有,本题不用long long的话貌似会WA

2.1.5 又见GCD:说水也水说不水也不水的一道题……最开始直觉以为是c*2就行了,WA了几发,琢磨了一下不对呀,其实很容易举出反例的,比如a=8,c=2,c*2=4 如果b=4,gcd(a,b)=4!=2。但是很显然的b一定是c的倍数,既然b!=c,那么我们就从b=2*c开始一个一个检查直到gcd(a,k*c)=c,答案就是b=k*c

2018.9.7

2.1.4 Cake:挺有意思的一道题。把蛋糕看成一块矩形,首先单独按照p人或者q人均分,画个图就知道要同时满足p人和q人都能平均分得蛋糕,就要保留所有按单独p/q人划分时的划分点,这就是本题的最优划分方案。多测试几组数据发现划分点重合的点个数为gcd(p,q),所以总的划分点数为p+q-gcd(p,q)-1,则答案为划分点数+1=p+q-gcd(p,q)

下面分别为p=3 q=4(无重合划分点,划分为6块)和p=2 q=4(有重合划分点,其中红线为重合处,划分为4块)时的情况,根据图很容易得出结论。

2018.9.8

2.1.6 找新朋友:欧拉函数模板题,关于欧拉函数详见维基百科

https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

2.1.8 Leftmost Digit:需要一点点技巧的数学题。

我们假设\(m={n^n}\),则m一定能用科学计数法表示为\(m=x*{10^y}\),其中\(x\in(1,10)\),y为整数。不难得出,我们想要求的\(n^n\)的最高位就是x的整数部分。

对两边同时取以10为底的对数得\(n\lg{n}=\lg{x}+y\),由于\(x\in(1,10)\),则\(\lg{x}\in(0,1)\),所以y就是\(n\lg{n}\)的整数部分,移项得\(\lg{x}=n\lg{n}-y\),两边同时以10为底得\(x=10^{n\lg{n}-y}\),再取整即可。

PS:学会了使用MathJax来插入LaTex公式真是看起来舒服多了……

2.1.7 The area:考查微积分基本知识的题,只要根据顶点坐标公式\((\frac{-b}{2a},\frac{4ac-b^2}{4a})\),和\(y=ax^2+bx+c\),代入三点中的顶点和其中任意一点解出抛物线方程,然后算出零点。画图进行相应积分就行了,本题数据比较水,只有题意的图中的那种情况,代码写的水一点也能过的……

结论上,我代入的是\(P_1\)和\(P_3\),得出的结果是
$$
\begin{equation}
\left\{
\begin{array}{lr}
a=\frac{y_3-y_1}{{x_3}^2-2x_1x_3-{x_1}^2+2{x_1}^2} \\
b=-2ax_1 \\
c=y_1+a{x_1}^2
\end{array}
\right.
\end{equation}
$$

2.2.1 Fibonacci:这道题有点类似于2.1.8,关于斐波那契数列,深入推导我们熟知的递推公式,可以得出斐波那契数列的通项公式:
$$a_n=\frac{\sqrt{5}}{5}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

(具体证明可看维基百科:https://zh.wikipedia.org/zh/斐波那契数列

而由于在n比较大的情况下,\(\left(\frac{1-\sqrt{5}}{2}\right)^n\)可以忽略不计,所以$$a_n\approx\frac{\sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{2}\right)^n$$因此,我们可以“故技重施”,和2.1.8类似,我们设\(\frac{\sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{2}\right)^n=x*10^y\)为F[n]的科学计数法表示,根据2.1.8结论可知y为左式的整数部分。对两边同时取\(lg\)并将y移到等式左侧,可得$$\lg{\frac{\sqrt{5}}{5}}+n\lg{\left(\frac{1+\sqrt{5}}{2}\right)}-y=\lg{x}$$之后,两边同时以10为底可得$$x=10^{\lg{\frac{\sqrt{5}}{5}}+n\lg{\left(\frac{1+\sqrt{5}}{2}\right)}-y}$$再把x乘1000即可求得前4位。

2018.9.9

2.2.2 Joseph:约瑟夫环问题的变种。显然,我们可以知道要使第一个出圈的人在\([k+1,2k]\)之间,则m只能在\([T*(k+1),T*2k],T\in[1,2,…n]\),由于数据k不大,我们可以枚举m模拟出环过程即可。

至于模拟出环嘛,看厌了网上千篇一律的题解,决定自己写一篇清奇的。约瑟夫问题实际上是可以用线段树解决的,我们将线段树的节点左、右区间分别作为人数编号区间,每个节点的权值作为区间人数。这样的话只需要计算出出环的人在环中的相对位置(不难求得下一个出环人相对位置为\((\text{当前出环人位置}+m-1) \mod \text{总人数}\)),然后如果相对位置小于这个区间左子树区间的人数,就到左子树区间去找,否则减掉左子树区间人数,到右子树去找,最后到叶子节点返回编号即可。之后再判断出环是否符合规则即可。

2.2.4 Wolf and Rabbit:水题一枚。根据题目不难得出,任意一个洞走到第二遍的时候,巡查的路径就已经确定完毕了。如果这时候还有洞没被查到,那就存在安全洞。换言之,在没有洞重复走第二遍之前,我们走的所有洞都是不同的!

下面举两个例子:

假设\(m=3,n=5\),不难得出,我们走\(lcm(3,5)=15\)步之后,就会开始第二遍走已经走过的洞。这个时候我们计算巡查过的洞\(n=15\div3=5\),而总共就只有5个洞,所以不存在安全洞。

假设\(m=4,n=6\),不难得出,我们走\(lcm(4,6)=12\)步之后,就会开始第二遍走已经走过的洞。这个时候我们计算巡查过的洞\(n=12\div4=3\),而总共有6个洞,所以存在安全洞。

因此,我们可以得出若结论:若\(m*n=lcm(m,n)\)则不存在安全洞,否则存在。

进一步地,由\(gcd\)与\(lcm\)的性质可知:\(m*n=lcm(m,n)*gcd(m,n)\),问题便转化为判定\(gcd(m,n)\)是否为1,也就是\( m,n\)是否互质的问题了。

2018.9.11

2.2.6 Number Sequence:取模的题一般都会有规律的,这道题也不例外。由于\(F[i]\)是由\(F[i-1]\)和\(F[i-2]\)得到且会模7,所以每个\(F[i]\)共有7种取值,由于\(F[i]\)只由前两项推导,而前两项共有\(7×7=49\)种情况,所以从第49个数起会开始重复循环(可能不是最小循环节,但是49一定是一个循环节的开始)。

实际上,打打表,暴力找周期会发现49一定是一个循环节的开始。

所以输出\(F[n\%49]\)即可(注意\(n\%49=0\)时\(n=49\))。

2018.9.12

2.2.7 Digital Roots:由于数据可能很大,直接用int或者long long读肯定会爆炸从而导致WA,所以本题读入数据只能采用字符串形式。至于处理,先说结论吧:从左往右一位一位加,如果累加和超过10,就对10取模,再继续进行后续加法。

这么做是不会影响答案的,为什么呢?下面是证明:

首先,我们考虑相邻的三个数字\(a,b,c\),考虑所有情况,分别有:

\(I.a+b<10\)

\((1) a+b+c>10\),此时结果为\((a+b+c)\%10\),根据模运算的性质,\((a+b+c)\%10=[(a+b)\%10+c]\%10\)

\((2) a+b+c<10\),此时结果为\(a+b+c\),显然此时\((a+b)<10\)且\(c<10\),所以有\(a+b+c=[(a+b)\%10+c]\%10\)

\(II.a+b\ge10\)

此时一定有\((a+b+c)\ge10\),根据模运算的性质,\((a+b+c)\%10=[(a+b)\%10+c]\%10\)

综上所述,我们发现对于相邻的三个数,总可以转化成\([(a+b)\%10+c]\%10\)的形式,也就是说,先将各位数字之和求出来后再求Digital Root和一旦超过10就求Digital Root然后再进行后续求和的结果是一样的,所以每两位数相加我们都对10取一次模,获得当前Digital Root再进行后续计算,最终得出答案。

2.2.8 N!Again:大水题,还是那句话,取模的题一定有规律,本题也不例外。大暴力打表,发现除了前40项非零之外后面全是0,所以计算前40项即可。稍微运用一下模运算的性质:\((a*b)\%c=[(a\%c)*(b\%c)]\%c\)来计算前40项即可。

2018.9.13

2.2.5 三角形:第一块三角形放在平面时把平面切分成2个平面,之后每新增一个三角形,这个三角形与已存在的图案每新增一个交点就新增一块划分区域(可参考http://www.mofangge.com/html/qDetail/02/x0/201408/4hcwx0021011542.html)。这样算下来每个新的三角形每条边最多与一个三角形有2个交点,则与前\(n-1\)个三角形共有\(2*(n-1)\)个交点,这个三角形有三条边,则共有\(2*(n-1)*3=6*(n-1)\)个交点,也就是每个三角形最多新增\(6*(n-1)\)块区域,所以我们不难得出递推式子:
$$
\begin{equation}
sum[N]=\left\{
\begin{array}{lcl}
1 & & {N=1} \\
sum[N-1]+6*(N-1) & & {N\ge2}
\end{array}
\right.
\end{equation}
$$

于是提前打好1~10000的表,问题便迎刃而解~

2018.9.14

2.2.3 汉诺塔VII:呃,又是恶心的汉诺塔……

先来回顾一下汉诺塔问题的递归步骤:

①把n-1个盘子以C为过渡柱移动到B

②把第n个盘子从A移动到C

③把n-1个盘子以A为过渡柱移动到C

好了,那么如何判断一个状态是否合法呢?我们逆推之,不难发现,对没有在C上的最大编号的盘(我们称之为目标盘吧),它的最后一步总是从A到C,因此,它在B盘上就是错误的一个序列。如果它在A盘,那上面的n-1个盘一定是经由C移动到B,所以n-1号盘不可能在C上(如果n-1号盘在C上,n号盘在A上,那其余n-2号盘在B上,n-1号盘就只能移回A去了,这显然不是最优移动方案);如果n号盘在C上,那前n-1号盘一定要经由A移动到C,同理,第n-1号盘不可能在A上。综上,我们可以模拟汉诺塔的递归来检验。递归部分比较难写,需要注意判断边界条件(从0开始存,则a[m]=b[p]=c[q]=-1,递归的入口是hanoi(n,a,c,b)),把核心代码贴在下面了:

2018.9.15

2.3.1 A + B Problem II:高精度加法模板题,注意格式问题,两个测试点中间要输出一行空格,最后一行数据下面不用输出空格,不然会PE

2.3.7 Game of Connections:先举几个例子来看:

①\(n=1\)时,1能连接2,共有\(F[1]=1\)种情况

②\(n=2\)时,1能连接2或者4,其中:

1连2时,剩下两个点,即\(n=1\)的情况,3与4连,相当于有\(F[1]*F[0]=1\)种情况

1连4时,剩下两个点,即\(n=1\)的情况,2与3连,相当于有\(F[1]*F[0]=1\)种情况

则共有\(F[2]=F[1]*F[0]+F[0]*F[1]=2\)种情况

③\(n=3\)时,1能连接2或者4或者6,其中:

I .1连2时,3、4、5、6互连,相当于只剩4个点,即\(n=2\)的情况,有\(F[2]*F[0]=2\)种情况

II.1连4时,2与3可以互连,5与6可以互连,即两个\(n=1\)的情况,相当于有\(F[1]*F[1]=1\)种情况

III.1连6时,2、3、4、5互连,相当于只剩4个点,即\(n=2\)的情况,有\(F[2]*F[0]=2\)种情况

则共有\(F[3]=F[2]*F[0]+F[1]*F[1]+F[0]*F[2]=5\) 种情况

综上,我们不难发现规律,假设\(F[0]=0\),只要确定了1某个点相连,则这种连法让整个环分为两部分(1与相邻的点相连相当于其中一部分0个数,另一部分\(2n-2\)个数),假设第一部分对应\(n=k_1\)的情况,第二部分对应\(n=k_2\)的情况,则显然有:\(k_1+k_2=n-1\)且这种连法能够贡献的方法数为\(F[k_1]*F[k_2] \)。为了保证两个部分各有偶数个数,那么1只能与偶数点相连。

因此,我们不难得出递推式:\(F[n]=F[n-1]*F[0]+F[n-2]*F[1]+…+F[1]*F[n-2]+F[0]*F[n-1]\),其中\(F[0]=1\),\(F[1]=1\)。

由于数据较大,本题需要使用到高精度乘法与加法。

直接用递推式暴力算是可以过的,但是从网上还看到一个结论,本题的数列就是一个卡特兰数的数列(卡特兰数第一项对应\(F[0]\))。关于卡特兰数详情可看维基百科:https://zh.wikipedia.org/zh-hans/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*