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

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


The 15th Ningbo Institute of Technology, ZJU Programming Contest

出题:tokitsukazewinterzz1teitoku

验题:ConferenceCallProphetStormHeaven_tenderyuzukoDarkcat2014CAIS01TommyShelbyNITGhost

题面修订:doge233tenderDarkcat

——————————————————————————————————————

难度预期:

(1)对于新生:

easy:AJIB

medium:DEK

hard:HFL

very hard:CG

 

(2)对于牛逼网友:

easy:ABDEFHIJKL

medium:C

hard:G

 

下注:

现场赛:1h可能有4题的,rk1应该能有9题。

网络赛:ak的可能会有1,2个。

——————————————————————————————————————

赛前出题:

本来只有几个题题面是星际争霸,然后winterzz1:不然出一套吧。然后就全改成星际争霸了。

第一轮验题,yuzuko:这是什么星际争霸科普赛吗。

验题时普遍反映D和E题面表述不清。于是让doge233第一轮修题面。

第二轮验题,还是反映D和E题面表述不清,于是请了大学语文及格的tender,和她队友:星际玩家Darkcat来修题面。

第三轮验题,没啥毛病,就这样吧。

——————————————————————————————————————

现场赛准备:

本周突变因子:5楼机房,电脑随机蓝屏。给5楼的选手们增加了一些游戏难度。

 

网络赛前一天:

看到西电跟我们撞了,感觉剧本写好了:这什么沙雕学校的沙雕比赛 题还这么长 走了走了 去打西电的了。

——————————————————————————————————————

现场赛:

J居然这么快就被发现了…

紧接着E被秒了…

然后K也很快就被秒了,1h出头就有5题的了…然后发现K不用建树dfs也能做…

接着H也被秒了..

I看来藏的不错。

为什么没人过D??写7层for也能过吧…

有位外校老哥,A签到-33,旁边坐着一个rk2,5题的小学生,被打跑了…

rk2的小学生最后7题,还是rk2。(小学生牛逼)

rk1只有7题。

 

现场赛过题情况:

onsite

——————————————————————————————————————

网络赛:

惊现qls。

qls1h秒了9个。

qls被C卡住了。

qls发现没看见字典序最小。

qls走了。

验题人2014CAIS01拿了G的一血,过分!

G过的似乎有点多。

qls在最后1min1Y了G,跳到了rk1。

看隔壁西电的榜似乎有点惨,还是我们的简单.jpg

似乎成功防住了ak?

网络赛答疑时有人问:为什么非要玩星际争霸呢,玩会儿别的不行么。我不知道回什么,看了一圈常用回复,选择了:不可以哦。(xswl)

 

网络赛过题情况:

online

——————————————————————————————————————

A.StarCraft

Author:tokitsukaze。

ans=n-20+2018

 

B.Fibonacci and Counting

Author:winterzz1。

ans=n+1

证明:

定理:任意相邻两项的斐波那契数互质。
假设F(n)与F(n+1)(n>2)有公约数的话,不妨设为a,应有a大于1。那么再根据F(n+1)=F(n)+F(n-1),a应能整除F(n-1),即a|F(n-1),再结合a|F(n),a|F(n+1),可知a|F(n-2),以此类推,我们会发现a|F(2)和a|F(1),而F(1)=F(2)=1。这是不可能的,假设不成立。所以斐波那契数列邻近项互质。
根据辗转相除法,gcd(a,b)=gcd(b,a%b),而斐波那契数的后一项不大于前一项的2倍,所以这里的模其实就是减法。也就是:gcd(a,b)=gcd(b,a-b)。
观察一下就会发现,这个式子就是斐波那契数列运算的逆运算。所以使用几次斐波那契运算过去,就得使用几次辗转相除回来,再算上第一次调用的一次,答案为n+1。

 

C.LCPS

Author:tokitsukaze。

把第一个串建回文树,回文树的每个节点记录下第一次出现的下标。

第二个串在回文树上匹配,匹配时更新最大长度,并记录下出现的下标。

然后把子串暴力取出来,直接比较字典序即可。因为本质不同的回文串是O(n)的,所以卡不掉暴力比较字典序。

 

D.Campaign

Author:teitoku。

二进制枚举答案,然后维护一个可行的l,r,当可行的l,r包含了输入的个数的时候,就是满足条件的,然后从所有答案中选出最大的就行。

 

E.Build Pylons

Author:winterzz1。

题意:现在有个人在数轴上从左到右依次经过一些点,他每走一步时的花费都是等差数列1,3,5,7,9…然后一旦他经过某个点等差数列就会从1开始重新计数。

根据等差数列求和公式可得走k步的花费总共为k^2,所以先对输入的a数组进行排序。
然后依次计算sum+=(a[i]-a[i-1])*(a[i]-a[i-1])(i>1)即可。
最后再加上最后一个建筑的建造时间就是答案。

 

F.Pylon Link

Author:tokitsukaze。

solution (1):二分答案,check连通性。O(log(1.5e9)*n^2)。

solution (2):n^2建图,求最小瓶颈生成树。prim:O(n^2),kruskal:O(log(n^2)*n^2)。

 

G.Rubik’s Cube

Author:winterzz1。

三阶魔方翻楞公式:MU2M’UMU’M’(F面下侧楞块翻转,D面其他块不变)
三阶魔方翻角公式:RUR’U’RUR’(F面右下角块顺时针旋转单次,D面其他块不变)
所以只要求在一个面上拼数字的话,只要数字不在同一个块中,就一定能够放在同一面上。
一个魔方由8个角块,6个中心块,12个棱块组成。
拼好的一个面上有4个角块,4个楞块,1个中心块。
所以使用分组背包处理一个块中不同面的互斥关系,然后从8个角块中选4个,12个棱块中选4个,6个中心块中选1个放入背包。

 

H.Protoss and Zerg

Author:tokitsukaze。

加法原理与乘法原理,需要会快速幂。(解法在样例解释就给出了)

 

I.Race Sorting

Author:tokitsukaze。

开几个数组直接扫,按题意模拟即可。

 

J.Carrier

Author:tokitsukaze。

if else讨论一下,过样例应该就能过。

 

K.Technology Tree

Author:tokitsukaze。

建树直接dfs即可。

 

L.The Last Stand

Author:winterzz1。

题意:从最左边走到最右边,每个物品可以取或者不取,取东西的时候首先会获得一个val权值,然后接下来会持续的获得或者减少该物品dalta属性的权值。

dp[i]表示取第i个物品能获得的最大权值。然后设置两个虚点0和n+1,这两个虚点的val属性和delta属性均为0
dp转移方程为:dp[i]=max(dp[i],dp[j]+delta[j]*(pos[i]-pos[j])+val[i]);(i>j)
注意条件要求过程中权值不能为负,所以需要先判断是否可以转移再进行状态转移。