A.Jumping Buildings (单调栈)
思路
对于每个位置通过单调栈可以得出右边第一个比他高的位置。复杂度$O(n)$
代码
1 |
|
B.Divples (因数分解)
思路
很简单的签到了把。直接枚举a的因子判断是否是b的倍数即可 复杂度$O(sqrt(n))$
代码
1 |
|
C.Rectangles (离散化预处理后暴力)
思路
关键点就是中间和线上不能有点,那么我们可以考虑枚举一行的两个点,(可以知道这两个点必须是相邻的) 然后我们再在下面的几行中找是否有和这两个点可以组成矩形的点,
同时注意要保证不能矩形中间和线上出现点 复杂度$O(n^2)$
代码
1 |
|
D.Guessing Messages (签到)
思路
直接两个指针正着做就行了 复杂度$O(max(n,m))$
代码
E Chi’s performance (简单DP)
思路
首先我们需要感性得知道放在两边的数必须是最大或者最小值(请自行证明,不难的)
但是有可能两边都方最大值会更优,所以我们就需要存储次大值。
之后我们就可以总结出,对于每一个ID 只有四个元素会有贡献,所以我们对于每一个ID只要存这四个值就行,然后我们暴力DP 每个位置前面放什么数字后面放什么数字
代码
1 |
|
G.Log Concave Sequences (矩阵快速幂)
思路
首先手动推一下 发现后面一个字符可以填什么只会跟最后面两个字符有关系。所以我们可以考虑存储后面两个字符的状态总共有$3*3=9$种 我们假设一个简单的方法,
$dp[n][pos] $ 表示长度为N最后面两个状态为$pos$的字符串个数 那么这个答案可以直接从$dp[n-1][pos*]$ 得来,但是题目的N有$1e18$ 所以我们考虑矩阵快速幂,矩阵快速幂的矩阵怎么推出来代码中有,请自行理解。
1 |
|
I.Left or Right? How about neither? (最短路 dij)
思路
题目相当于一个状态可以有三种状态转移
1.跳到左边
2.跳到右边
3.跳到相同的数字
如果就这样一直走的话复杂度会很爆炸,但是我们发现跳到相同的数字这个条件很特殊
可以猜到相同的数字只会跳一次,比如你现在是数字3你跳到相同的数字3的位置,那么你以后都不会再跳,因为答案不可能更优。所以我们这样复杂度就降下来了。
1 |
|
J.Houston, Are You There? (优雅暴力)
思路
看到这题n只有8所以脑子里应该要有点冲动的想法把。
我们考虑暴力出所有的状态。首先每个牌都可以翻转是把?所以我们现在有总共有
$2^8$种状态,这里可以考虑用二进制状压来遍历记录。
其次每个牌都可以对调位置是把?是不是有$A_{n}^{n}$ 种情况,这里我们用全排列来记录
所以总状态数为$2^8 ×8!$ 种情况 自己用电脑算算复杂度会不会超。然后我们还需要$O(n)$的时间来判断是否合法
代码
1 |
|
K.Dahlia The Champion (gcd)
思路
首先会不会被盖住是不是说明他们的角度(叉积)不同,但是这个叉积是double类型的会有误差很难存是把, 所以我们可以考虑用$gcd$ 来缩小范围,比如点$(4,6)$ 和点$(2,3)$ 他们肯定会被盖住是把。那么点$(4,6)$ 其实可以变成点$(2,3)$ ….想想。
于是我们就可以把压缩后的点存起来,注意四个向量怎么区别。
代码
1 |
|