A GuGuGu week
好久没更算法周了,由于考研,写代码的时间基本已经没有了,所以现在的状态基本上是有空补补之前比赛的题目,题意和题解写的会比较潦草。
2020KickStart RoundB T2 Bus Routes (10pts, 13pts)
题意:
有n个bus,第i个bus的发车周期为xi,你需要在第D天之前按顺序把所有的bus乘坐,求最晚坐第一班的时间。
题解:倒着贪心即可
1 | /* |
2020KickStart RoundB T3 Robot Path Decoding (11pts, 16pts)
题意:
一个机器人在一个109⋅109的方阵上移动(循环方阵),初始是在(1,1),然后只能往N,W,S,E四个方向移动,给一个移动序列,计算最终机器人所在的位置。除了正常的字符串序列外,还包含X(Y)类似的序列,表示把Y重复X次。
题解:
首先可以知道横竖互不相干,接下来就是计算横和竖分别的情况。对字符串进行拆解可以用balance,即当前操作的次数是最近出现的balance个数字的累乘。但由于方阵是循环的,每次还需将当前数值对109取模。
1 | /* |
2020KickStart RoundC Stable Wall (8pts, 13pts)
题意:
判断一个polyomino 是否坚固,关于polyomino就是只有在色块有支撑的情况下,才能放当前色块,最终能构成的就是坚固的,如果坚固,给出一种顺序来。
题解:
拓扑排序,如果u色块下面有v色块,那么一定是v早于u,连边,跑拓扑排序即可。
1 | /* |
2020KickStart RoundD Candies (14pts, 24pts)
题意:
一个长度为n序列A,两种操作
- Q L R查询[l,r]使得$\sum_{l}^rA_{i}(i-l+1)(-1)^{i-l}$最大。
- U i j把Ai变成j
题解:
两棵树状数组。
第一棵维护$(-1)^{i-1}iA_{i}$
第二棵维护(−1)i−1∗Ai
查询的时候按奇偶讨论
u奇数为: T1.get(u,v)−(u−1)∗T2.get(u,v)
u偶数为:−T1.get(u,v)+(u−1)∗T2.get(u,v)
1 | /* |
Codeforces Round #644 (Div. 3) F. Spy-string
题意:
给定n个长度为m的字符串,求一个等长字符串s使得s与每个字符串最多有一个位置不同。
题解:
我乱搜了一下就过了,时间复杂度???,不过貌似有更好的写法。
1 | /* |
Codeforces Round #644 (Div. 3) G - A/B Matrix
题意:
构造一个n⋅m的01矩阵使得每行a个1,每列b个1。
题解:
写了个贪心,没有证明就过了,首先可以排除叼不能构成的情况即$an!=bm,然后直接按行填,但是要友嫌填列里面1$最少的。
1 | /* |