2018年7月 – MXG's blog

Archive七月 2018

[bzoj2466]:[中山市选2009]树

Description

给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。

开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。

阅读更多

[bzoj4084]:[Sdoi2015]双旋转字符串

Description

给定两个字符串集合$ S$ 和 $T$ 。其中 $S$ 中的所有字符串长度都恰好为 $N$ ,而 T 中所有字符串长度都恰好为 $M$ 。

且 $N+M $恰好为偶数。如果记 $S$ 中字符串全体为 $S_1,S_2…S_{TotalS}$ ,而 T 中字符串全体为 $T_1,T_2…T_{TotalT}$ 。现在希望知道有多少$i,j$ ,满足将 $S_i$ 和 $T_j$ 拼接后得到的字符串 $S_i+T_j$ 满足双旋转性。

一个长度为偶数字符串$ W $可以表示成两段长度相同的字符串的拼接,即 $W=U+V$。如果 $V$ 可以通过$U$旋转得到,则称$ W $是满足双旋转性的。

比如说字符串 U=“vijos”可以通过旋转得到“ijosv”,“josvi”,“osvij” 或“svijo”
。那么“vijosjosvi”就是满足双旋转性的字符串。

阅读更多

[bzoj3143]:[Hnoi2013]游走

Description

一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

阅读更多