本文最后更新于 1100 天前,其中的信息可能已经有所发展或是发生改变。
A. Two 0-1 Sequences
题目大意
- 给定只包含和的字符串和
- 对进行操作:
- 将,并删除,使得变为新的
- 将,并删除,使得变为新的
- 上述操作不限次数,求最终是否可以使得
思想
-
由于我们只能对
a[1], a[2]
进行操作 -
观察
string a, b
,发现:-
先将
a
和b
的最左端对齐 -
与
b[0]
对其的a[4]
不相等,b[0]
之后对齐的与a[4]
之后的元素均相等 -
若使得
a == b
,则a[4]
之前的元素中,必然存在某元素a[i] == b[0]
,才可通过相关操作使得a[4] == b[0]
-
-
由此可知,我们设
b[0]
与a[k]
对齐 -
从
a[k + 1]
开始构造a
的字串s1
,从b[1]
开始构造b
的字串s2
-
若
s1 == s2
:- 若
b[0] == a[k]
说明必然可以使得a == b
- 若
b[0] != a[k]
,则当k
之前存在a[i] == b[0]
时可以使得a == b
,反之不行
- 若
-
若
s1 != s2
,则无论如何操作都无法使得a == b
代码
B. Luke is a Foodie
题目大意
- 对于和固定的
- 有可以变成任意整数的,使得
- 遍历数组,求最小变化的次数
思想
- 由可知
- 故对于
a[i]
,必然存在满足的区间[l,r]
,l = a[i] - x, r = a[i] + x
- 设
a[i + 1]
的区间[l',r']
,l = a[i + 1] - x, r = a[i + 1] + x
- 若
[l,r]
与[l',r']
有公共区间时,v
可以不用发生改变,并将区间更新为其公共区间 - 若
[l,r]
与[l',r']
无公共区间时,v
将发生改变,并将区间变为[l',r']
- 公共区间存在判断:
max(l,l') <= min(r,r')
说明存在公共区间
代码
C. Virus
题目大意
- 的房屋围成一圈
- 给出初始感染病毒的房屋编号
- 每天可选择未感染的房屋进行保护,可使其永久不被感染
- 每天已感染的房屋其左右邻居都会受到感染
- 求最优策略下,最终感染的房屋数量
思想
- 贪心
- 每次选择未感染的最长区间进行保护
- 对于被保护的区间
[l,r]
:- 经过第一天:
- 保护
[l,r]
的一个端点,设保护a[l]
a[l]
不会感染,a[r]
会被感染- 其他所有未受到保护的区间
[l',r']
里,a[l']
和a[r']
被感染 - 经过第二天:
- 保护
[l,r]
的另一个端点a[r]
,由于第一天a[r]
被感染,故只能保护a[r - 1]
- 其他所有未受到保护的区间
[l',r']
里,a[l' + 1]
和a[r' - 1]
被感染 - 即对于选择保护的区间
[l,r]
,a[r]
被感染,我们只能保护到[l,r - 1]
这一段,且其余所有未受到保护的区间[l',r']
里a[l'],a[r'],a[l' + 1],a[r' - 1]
受到感染,感染后的区间变为[l' + 2, r' - 2]
- 综上可知,我们优先保护最长的未被感染的区间,即可实现最优策略
- 由于选择保护的区间端点可以任选,故只需要考虑区间长度,不需要维护额外的信息
- 注意不要忽略首尾相连的区间
代码
D. Magical Array
题目大意
- 对于一个长度为的数组,构造个与相同的的数组
- 对于数组现有操作:
- 操作1:首先将,然后将
- 操作2:首先将,然后将
- 选择某一个数,使得为特别数组
- 非特别数组只能执行操作1若干次
- 特别数组只能执行操作2若干次
- 给出这些操作后的数组,找出其中的特别数组的编号,及其执行了多少次操作2
思想
对于c_t(1\le t \le n)\\\\ \begin{aligned} (一)\\\\ 对于&c_{i-1},c_i,c_j,c_{j+1},可以得到c_{i−1}×(i−1)+c_i×i+c_j×j+c_{j+1}×(j+1)\\\\ &化简得:i×(c_{i−1}+c_i)+j×(c_j+c_{j+1})−c_{i−1}+c_{j+1}①\\\\ 对于&c_{i-1},c_i,c_j,c_{j+1}执行操作1:\\\\ &(c_{i−1}+1)×(i−1)+(c_i-1)×i+(c_j-1)×j+(c_{j+1}+1)×(j+1)\\\\ &化简得:i×(c_{i−1}+c_i)+j×(c_j+c_{j+1})−c_{i−1}+c_{j+1}②\\\\ &可知①=②,即操作1不会改变c_i\times i的和 \\\\ \end{aligned}\\\\ \begin{aligned} (二)\\\\ 对于&c_{i-1},c_i,c_j,c_{j+1},c_{j+2},可以得到c_{i−1}×(i−1)+c_i×i+c_j×j+c_{j+1}×(j+1)+c_{j+2}\times (j+2)\\\\ &化简得:i×(c_{i−1}+c_i)+j×(c_j+c_{j+1}+c_{j+2})−c_{i−1}+c_{j+1}+2\times c_{j+2}③\\\\ 对于&c_{i-1},c_i,c_j,c_{j+1},c_{j+2}执行操作2:\\\\ &(c_{i−1}+1)×(i−1)+(c_i-1)×i+(c_j-1)×j+c_{j+1}×(j+1)+(c_{j+2}+1)\times (j+2)\\\\ &化简得:i×(c_{i−1}+c_i)+j×(c_j+c_{j+1}+c_{j+2})−c_{i−1}+c_{j+1}+2\times c_{j+2}+1④\\\\ &可知③=④+1,即操作1会改变c_i\times i的和,使其加1\\\\ \end{aligned}\\\\ 综上可知:对每一个数组c,求S_f = \sum c_i\times i\\\\ 与其他数组c的S_f不同的数组即为特别数组,记为S_p\\\\ 其操作2的次数为S_p-S_f\\\\代码
后记
- 题一开始没找到规律,找到规律后居然没有把错思路的代码删掉,狠狠的吃
WA
的铁头娃 - 题读懂题意就很简单了,没什么好说的,就是判断公共区间
- 题一直在想着怎么维护端点的信息,最后发现根本不需要,只要长度就行了QAQ
- 题没时间了,太抽象了也看不懂,补题看题解发现证明的想法实在是妙极了,根本想不到
- 最后还是没能上绿,
我是废物