2018 ICPC南京赛区网络赛
ACM-ICPC 2018 南京赛区网络预赛
A. An Olympian Math Problem
题意
$S=1×1!+2×2!+⋯+(n - 1) \times (n-1)!(n−1)×(n−1)!$问$Smodn$是多少。
题解
思维题,打表题?答案就是$n-1$证明如下。
看到$n-1$很不爽,那就加一个$(n-1)!$就凑好了。
$S+1!+2!+…+(n-1)!=2!+3!+…+n!$
之后再减掉。
$S=n!-1!$那么对$n$取余$S modn=-1modn=n-1$搞定。
AC代码
1 |
|
B. The writing on the wall
E. AC Challenge
题意
做题目,要按照一定顺序做题目,每个题目有两个值$a,b$,表示做了题目后增加$t*a+b$。
题解
状态压缩+剪枝+拓扑排序。
因为$n$的数据量小于$20$所以可以使用状态压缩。
$S$表示已经做的题目。
$vs$数组存储已知做题的最大值。如果做同样的题值比较小就减掉。
AC代码
1 |
|
G. Lpl and Energy-saving Lamps
题意
一个人去给所有房间换灯泡,每个月都会获得$m$个灯泡,每个房间有$a_i$个灯泡,之后以能换就换的态度每个月从第一个房间开始换,没有能换的房间就停止,把灯泡留到下一个月。换过灯泡就不用再换了。问给定月份中已经换好的房间数和当月剩下的灯泡数。
题解
线段树维护一个区间最小值。
由于线段树遍历是从前往后的,就不用担心顺序问题。
AC代码
1 |
|
I. Skr
题意
给定一个由数字构成的字符串,$n\leq 2000000$。问回文串加起来有多少?
题解
两种做法:
- 马拉车+hash
- 回文树+dfs
AC代码1
1 |
|
AC代码2
1 |
|
L. Magical Girl Haze
题意
给定一个图,问从$1$走到$n$如果可以选择$k$条路为$0$,那么最短的路径是多少。
题解
分层图最短路+堆优化dijistra
每使用一次道路为0,就进入$step+1$的路径比较。比较好的dp思维。对于pair使用了一个小trick,负值就可以不用手写greater和重载小于了。但是现场赛应该还是手写node算了。
dp转移两种状态.
- $dp[v][step+1] = min(dp[v][step+1],dp[u][step])$
- $dp[v][step] = min(dp[v][step],dp[u][step]+val(u,v))$
AC代码
1 |
|