bnu-faraway/2018 USP Try-outs

Info

Date:2018.10.03

Link

Solutions

A Studying level curves

solved by sk


sk’s solution

对于每个小于180度的外角可以确定一个不行的斜率范围,然后离散化出来,询问就二分一下看对应的区间是否可行。

在cf上过了,但是后来发现有一个case还不会解决,比如“凹”“凸”的形状,如果是斜率为0的直线去切,答案是不一样的。

B Aesthetics in poetry

solved by sk


sk’s solution

枚举+模拟

C Promenade by the lake

solved by gjy,sk


gjy,sk’solution

考虑需要将奇度点变成偶度,那么需要将一个联通块内的奇度点两两连接,这里对这个联通块作欧拉遍历,在遍历过程中标记哪些边选即可。

D Maximizing Advertising

solved by gjy


gjy’solution

枚举一下分界线,上下左右分别做一次就好。

E Group work

solved by sk


sk’s solution

签到,答案是\(2^n-n-1\)

F Optimizing Transportation in Portugal

upsolved by sk


sk’s solution

删边最短路,bzoj原题。

G Running a penitentiary

solved by sk


sk’s solution

线段树签到。

H Wine Production

I A story about tea

solved by sk


sk’s solution

汉诺塔,简单的分奇偶讨论一下

J Meme Wars

solved by gjy


gjy’solution

递归一下就好。

K Portuguese Pastimes

upsolved by gjy


gjy’solution

题目描述:给出置换\(p\),求置换\(q\)的数量,其中\(q^k=p\)

若当前置换\(p=q^k\),考虑将\(q\)分解为不相交的循环,那么\(q^k\)的不同循环相互独立,一个循环只会拆分成若干个大小相等的循环。

现在考虑拆分的逆过程,先处理出\(p\)的型,由上述结论,我们知道只有循环大小相等才有机会合并,可以对大小不等的循环分开处理,将答案相乘。

现考虑\(t\)个大小为\(a\)的循环的合并,则需要\(t|k\)(否则不能使这些循环闭合),\(gcd(\frac{k}{t},a)==1\)(否则会分解成更小的循环)。

现在已知\(t_i(i=1,2,3......)\)个循环可以合并,则贡献为\(a^{t_i-1} * (t_i-1)!\),dp一下即可。

Replay

ghc

gjy

sk