bnu-faraway/2017中国大学生程序设计竞赛 - 女生专场

Info

Date:2018.05.05

Link

Solutions

A Automatic Judge

solved by ghc


ghc’s solution

简单模拟,给status,计算给定队伍的过题数和罚时,了解比赛规则即可。

B Building Shops

solved by ghc


ghc’s solution

首先把classroom按位置从左到右排序。\(dp[i]\)表示如果在第\(i\)个classroom建candy shop的话,\(i\)\(n\)的classroom所产生的最小花费。那么\(dp[i]=c_i+min_{j=i+1}^{n}(dp[j]+i⊕j)\),\(i⊕j\)表示\(i\)\(j\)之间(不含)的所有classroom到\(i\)的距离之和。从右往左\(O(n^2) dp\)即可。

C Coprime Sequence

solved by sk


sk’s solution

预处理前缀gcd和后缀gcd,然后枚举删哪个即可。

D Deleting Edges

solved by sk,ghc


sk’s solution

做单源最短路得出最短路边构成的DAG,统计每个点的入度\(in_i\),根据乘法原理,答案为\(\prod_{i=1}^{n-1}in_i\)

E Easy Summation

solved by sk


sk’s solution

暴力for一下。

F Forgiveness

unsolved

G Graph Theory

solved by sk


sk’s solution

从后往前贪心匹配。如果当前点是第一类点,那么和左边的一个第二类点匹配,如果左边没有第二类点了,那么此时根据剩下点的奇偶性判断是否可行。如果当前点是第二类点且它没有和右边的点匹配到,那么不行。

H Happy Necklace

solved by ghc,sk


ghc’s solution

题目问长度为\(n\)且对于任意长为素数的字串,红珠子数不少于蓝珠子数的红蓝链的种类数(\(mod 1e9+7\))。记这条链子为\(Nec\),若\(Nec[1]\)是红的,则当且仅当\(Nec[2:n]\)合法,\(Nec\)合法;若\(Nec[1]\)是蓝的,则当且仅当\(Nec_2\)\(Nec_3\)都是红的且\(Nec[4:n]\)合法,\(Nec\)合法。所以长度为\(n\)的种类数\(F_n=F_{n-1}+F_{n-3}\),矩阵快速幂。

I Innumerable Ancestors

solved by sk


sk’s solution

建出虚树随便做。

J Judicious Strategy

solved by ghc

Replay

ghc

代码力还是太弱啊。。怎么办啊。。算了交给队友吧

gjy

军训真好玩(谁更的这条,你出来我给你加个BUFF)

sk