一场简单题之战,就是比做题的速度以及正确率(感觉出题人去看球赛去了)

A. Codehorses T-shirts

一道简单但是题面很难懂的水题,说了半天就是求不同型号的个数而不是需要修改几个字母,用map维护即可
A题代码

B. Light It Up

一道贪心的简单题,插入无非就是两种情况:

  • 在开灯的区间内插入,应该让插入的元素尽可能地靠后
  • 在关灯的区间内插入,应该让插入的元素尽可能地靠前

B题代码

C. Covered Points Count

区间前缀和的经典问题,离散化后求前缀和(值即为覆盖的条数),用离散化之前的值直接计算即可
C题代码

D. Yet Another Problem On a Subsequence

DP经典题目,枚举第一个正整数就得到了区间长度,再暴力枚举区间最后一个值,$O(n^2)$的DP就搞定了
D题代码

E. We Need More Bosses

无向图求割边的模板题,缩点后建立新图DP一下就可以了
对于每条割边,答案都可以为dp[x]+1+dp[y],然后dp[x]=dp[y]+1(合并x和y)
E题代码

F. One Occurrence

一道有意思的线段树题目,维护一个pair值(下一个元素的位置,权值)对其维护最大值(就是影响越持久)
把问题离线处理,按照问题的右端点排序,这样就能满足单调性
输出的时候一定要判断一下first的值是否符合要求
F题代码

G. Two-Paths

作为压轴题,题目描述很长、很难理解
还没写好 QwQ
G题代码