最近作死的用JavaScript去试着做Codeforces上的题,在一道数据范围比较极限的题上栽了跟头(Codeforces Round #354 (Div. 2) - D. Theseus and labyrinth).一道简单的广搜题,结果不是tle就是mle.最后各种调整,终于算是搞过去了,也给我留下了一些关于JS语言上的疑问,希望以后能有时间看看JS引擎,解决这些谜题.
广搜一般的实现方法就是使用一个队列存放接下来要搜的点,然而我使用JS中的队列方法shift()居然tle了.由于实在不了解shift()具体实现是怎样的,抱着试一试的心态自己实现了一个队列才解决了tle的问题.难道shift()要移动后面所有的元素,使得其复杂度是O(n)?如果用类似C++的容器实现方式应该会很高效啊.
这套题就感觉很神.像C这种如果以前遇到过就觉得简单,没遇到过还真不太好想.
题目给定3个数$a, b, c ( - 10^9 ≤ a, b, c ≤ 10^9)$,用$a$和$c$形成一个序列$s$,使得$s_1 = a$且$s_i - s_{i-1} = c$ 问$b$是否在序列$s$中.
水题,直接根据$b - a$的差值看$c$是否能够整除就行了,但是要注意$c = 0$的情况以及除得的结果需要是正数.
给一个$3 × 3$的格子和$n, a, b, c, d (1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n)$,在格子中填数字,每个数字$i$范围为$(1 ≤ i ≤ n)$.现在要给格子填数字,问有多少种填法满足任意$2 × 2$的格子和相等.
不难看出中间的格子取任意满足范围的值都行,只要计算4个角上的数与其相邻的两个数的和,如果4个和是一样的,那么中间的数取任何值都满足条件.
简单的做法就是枚举左上角的值,判断要符合相等条件的话另外三个角的值是不是在合法范围内,如果在,那么最后结果就会多n种(中间的数取1到n).当然,也可以根据大小关系直接算出左上角取值能有多少种,然后乘以n就可以了.