《记每次打完模拟赛都很想扇自己一巴掌这件事》
复盘:
7
:
50
−
8
:
00
7 : 50 - 8 : 00
7:50−8:00
本来是想先看完所有题面的 , 但是看完
T
1
T1
T1后就知道怎么写了。性质很显然 , 先做一遍转换 , 然后把每一个i和它当前所在的位置连起来(其实都不用连 , 直接开数组记录一下就行了)。然后会发现,这一定是一个环 , 然后用
k
k
k模上环长 , 再跑一遍就行了。(然而因为我连边连反了 , 人就没了)。
8
:
30
−
9
:
30
8 : 30 - 9 : 30
8:30−9:30
写完
T
1
T1
T1后 , 看
T
2
T2
T2,看了一会儿发现自己不会写 , 然后就开始看
T
3
T3
T3。一开始
T
3
T3
T3看错题了 , 以为是DP,写完后发现可以来回跑,然后就改图论了。手推了几组数据 , 发现每个点只要连它左右两边最近的权值为
1
−
m
1-m
1−m的点就行了。(然而 , 这个结论似乎是错的 , 但这也没啥 , 主要是我连边少连了,
70
p
t
s
70pts
70pts就缩水到了
30
p
t
s
30pts
30pts o(╥﹏╥)o)。
9
:
30
−
10
:
30
9:30 - 10 : 30
9:30−10:30
继续啃
T
2
T2
T2 , 想了想暴力怎么写 , 然后就发现了一条性质:当你确定了一个
26
26
26字母的顺序 , 那么 , 只要第
i
i
i位的字母排名在它前一个字母的前面 , 那么
a
n
s
+
+
ans++
ans++,所以就可以用状压写了。时间复杂度:
O
(
400
∗
2
20
)
O(400 * 2 ^ {20})
O(400∗220) , 虽说还可以优化 , 但这样其实就已经能过了。(然而因为我是
s
b
sb
sb,专门加了个离散化 , 预处理错了QWQ)。
11
:
00
−
12
:
00
11 : 00 - 12 : 00
11:00−12:00
T
4
T4
T4是真的不会写了,于是就写了
25
p
t
s
25pts
25pts的暴力 。
失分项:
1.
1.
1.
T
1
T1
T1丢了
100
p
t
s
100pts
100pts , 数组用错了。QWQ , 直接哭死。
2.
2.
2.
T
2
T2
T2丢了
50
p
t
s
50pts
50pts,预处理出错了。o(╥﹏╥)o
3.
3.
3.
T
3
T3
T3丢了
40
p
t
s
40pts
40pts,连边连少了。o(╥﹏╥)o