FluffyBunny

分类

题解(12)

/ 注册

全部文章（共12篇）

题解 | #Look, BABA IS YOU#

问题在推箱子的规则上，额外增加一些文本块。若主谓宾紧挨着连成一条线，则该规则生效。要求按照指定指令序列模拟游戏过程。题解模拟即可。吐槽这题能吐槽的可多嘞。 Idea来源自益智游戏"BABA IS YOU"中的部分游玩方式，但不完全一样，需要选手仔细读题。让内榜全军覆没和让外榜挂了好多次的...

2021-12-27

3 368

题解 | #Koishi in Wetland Park#

问题给定一张无向图，每个时刻边权会由(a,b)(a,b)(a,b)变为(b,a mod b)(b,a \; mod \;b)(b,amodb)，如果b为0则不变，点有点权。会以pi∑pk\frac{p_i}{\sum p_k}∑pkpi的概率选择i作为起点，每次会等概率选择，走到n结束。...

2021-12-27

3 298

题解 | #Join TB's Party#

问题给定一棵边带权树，有MMM人从根节点出发，去各节点拿一把椅子回到根节点。每个人经过一条边需要一定时间，每个节点提供的椅子有数量上限CiC_iCi，每个节点提供两把椅子的时间至少相差PiP_iPi。问所有人拿一把椅子回到根节点至少需要多少时间。题解本题具有二分性预处理每个节点iii到根...

2021-12-27

5 412

题解 | #Invasion of Sjkmost#

问题给个网格，每个格子是0或1，你至少需要把多少0变成1才能通过走1的四联通从网格一边走到另一边？题解每个点可以和他的相邻的点连一条边考虑最短路如果某个点是1，那么到他不需要代价，否则需要1的代价（把这个点变成1）添加一个起始点，和第一行的点连边，添加一个终点，和最后一行的点连边考虑0...

2021-12-27

2 282

题解 | #Here Comes Chao Man#

问题给定序列aia_iai和常数EEE，问有多少种将其划分为若干非空段的方案，使得相邻两段的最小值至少相差EEE。题解设fif_ifi表示，已经考虑a1…aia_1\dots a_ia1…ai的划分，且aia_iai为其所在段的首个最小值，有多少合法划分方案（aia_iai所在段可...

2021-12-27

2 384

题解 | #Gorgeous Andrea#

问题给定长度为 n 数组a,b,c，求最大非空子序列使得∑i=1kcpi+∑i=2kapi⋅bpi−1\sum_{i=1}^{k}c_{p_i}+\sum_{i=2}^{k} a_{p_{i}}\cdot b_{p_{i-1}}∑i=1kcpi+∑i=2kapi⋅bpi−1最大（p...

2021-12-27

3 299

题解 | #Fix a Weird Speaker#

问题给定文本串SSS和模式串TTT，求SSS的一个最长子串，使得其为TTT重复其某个子区间的结果。题解 KMP 对SSS正向做一次TTT的匹配，记录SSS每个前缀preipre_iprei尾部能匹配到的TTT最长的前缀，记做fif_ifi。对SSS逆向做一次TTT的匹配，记录SSS每个后缀...

2021-12-26

4 358

题解 | #Eager for Tea#

题目询问期望随机选择几次 [0,x][0,x][0,x] 中的实数进行累加后，结果不小于1。答案 e1xe^{\frac{1}{x}}ex1 解答期望为 ∑i=1∞i∗((1x)i∗(1−1i)∗(1(i−1)!)+(1x)i−1∗(1−1x)∗1(i−1)!)\sum_{i=1}^{\in...

2021-12-26

4 433

题解 | #Dengsh Loves Kebab#

问题给定 N 个长度为 M 的字符串，每次等概率随机抽取一个，问至少知道前多少位可以确定字符串是哪一个。思考对于每个字符串，当知道它和其他所有串的最大的LCP+1位时可以确定。题解做法一：对于每个字符串枚举其他所有字符串算LCP取最大值。时间复杂度O(n2m)O(n^2m)O(n2m) ...

2021-12-26

2 328

题解 | #Cknight and String#

问题给定仅由字符ab组成的字符串s，问最小修改字符个数使得不存在子串“ab” 题解需要s中不存在子串“ab”,只需枚举分界线，使得分界线前都是字符'b',分界线后都是字符'a'. 取修改次数最小值即可复杂度O(n)O(n)O(n) 吐槽这题数据有点锅……大概是造的数据比题面的数据范围略大了一...

2021-12-26

2 365