bnu-faraway/ACM-ICPC 2018 徐州赛区网络预赛

Info

Date:2018.09.09

Link

Solutions

A Hard to prepare

solved by sk


sk’s solution

递推,方法很多,\(O(n)\)或者推出公式直接快速幂\(O(logn)\)

B BE, GE or NE

solved by gjy


C Cacti Lottery

solved by sk


sk’s solution

按题意模拟,枚举排列

D Easy Math

solved by gjy


gjy’s solution

E End Fantasy VIX

upsolved by gjy


gjy’s solution

首先注意到最后答案的情形一定是,不开BUFF,开BUFF,不开BUFF这样的(其中左右两段有可能为空),而BUFF不开够\(T\)时间一定是不优的,这是一个经典问题

\(设A_{i,i}=v_i,E_{i,j}=v_j,那么中间一段即为D = A \ast G^{T-1}\)

接下来考虑将原图拆成分层图,\((u,0),(u,1)分别表示点u在第一段和第三段的状态\)

那么考虑分层图的邻接矩阵\(E'= \left[ \begin{array}{c|c} E& D-V \\ \hline *& E \end{array} \right]\)

对这个图再做一次矩阵快速幂即可,需要注意的是走分层图间的边是不花时间的,所以需要把时间\(+1\)

F Features Track

solved by sk


sk’s solution

扫一下,用map维护

G Trace

solved by gjy

H Ryuji doesn’t want to study

solved by sk


sk’s solution

线段树或树状数组维护\(a_i\)的和,以及\(i*a_i\)的和,分别记为\(sum_1\)\(sum_2\),答案是\((r+1)sum_1(l,r)-sum_2(l,r)\)

I Characters with Hash

solved by gjy

J Maze Designer

solved by gjy

K Morgana Net

solved by sk


sk’s solution

矩阵快速幂,bitset优化,时间复杂度\(O(T64^2logt)\)。据说不用bitset也可以过,矩阵乘法的时候遇到0就continue。

Replay

ghc

gjy

手滑比较多,每次需要再读一读代码读一读题再交

sk

切简单题比较稳,贡献两发CE