1887

Problem - D - Codeforces Split - 洛谷 我现在水平好烂，再做下去自信心就全败没了 先考虑 \(Q=1\) 怎么做？ 两种做法： 暴力枚举分界点，左右判断 暴力枚举 \(\max\limits_{i=l}^{x} a_i\)，找到最靠右边的分界点位置 \(x\)，判断是 ......

Problem - 1887C - Codeforces Minimum Array - 洛谷 有点被降智了/ll 首先区间修改显然先转化成差分序列单点修改。 显然对于相同的操作序列，\(a_i\) 的取值对答案无影响，因此我们可以先让 \(a_i\) 全部取 \(0\)，最后再加回来即可 假如说操 ......

萌萌交互题。 对网格图进行二分图建模，左部 \(n\) 个点表示每一行，右部 \(n\) 个点表示每一列。若格子 \((i,j)\) 被染成 \(c\) 色，就连接 \((L_i,R_j,c)\) 的边。 由抽屉原理易证，在初始局面中至少有一个各边颜色均不同的偶环。获胜条件相当于存在一个各边颜色均不 ......

洛谷传送门 CF 传送门 \(a_l, a_{l + 1}, \ldots a_r\) 是好的当且仅当 \(\exists k \in [l, r - 1], \max\limits_{i = l}^k a_i < \min\limits_{i = k + 1}^r a_i\)，称此时的 \(k\) ......

左侧最大值小于右侧最小值，其实就是左侧的值全部小于右侧，即，我们可以在区间 \([l,r]\) 内找到一个阈值 \(x\) 和一个位置 \(i<r\)，满足 \(\forall j\in[l,i],a_j\le x\) 且 \(\forall j\in(i,r],a_j> x\)。 考虑刻画出所有 ......

一个很直接的思路是，维护当前可行决策集合 \(S\in\{0,\dots ,q\}\)，从 \(1\) 到 \(n\) 分别考虑每一个 \(a\)，排除一些决策，最终得到答案。 既然要排除决策，我们当然需要知道对于当前的 \(a_i\)，前 \(j\) 个操作之后的值都是多少，如果能得到这个，且这些 ......

矩形的四个角颜色不同是个很难描述的条件，不妨利用行列二元关系转化，将 \((x,y)\) 颜色为 \(c\) 改为在 \(x\) 和 \(y\) 之间连接边权为 \(c\) 的边，则四角颜色不同就被我们转化为了，存在一个边权各不相同的四元环。 此时把特殊条件【初始给定 \(2n\) 个格子 \(2n ......

早到可以选择停留在原地，所以我们一定会尽早地到达每一个节点，这样一定不劣。 考虑若我们最早可以在 \(t_u\) 时刻到达节点 \(u\)，则对于边 \((u,v)\)，我们一定会在它最早的解锁时刻由 \(u\) 向 \(v\) 扩展。实现时可以使用 dijkstra，并对每张图的出现时刻用 set ......

CF1887C Minimum Array 小丑做法。 首先差分一下，转化成两次单点加。每次考虑前 \(i\) 位，然后一直维护当前合法的时刻区间，这个东西怎么做呢？可以离线下来记录每个点被那些操作波及，然后算一遍前缀和，对于合法的区间区间打标记。需要支持区间加 \(1\) 和查询最大值，用线段树维 ......

A1. Dances (Easy version) 把 \(a,b\) 序列都从小到大排序，\(a\) 贪心删大的，\(b\) 贪心删小的，二分答案并 \(O(n)\) \(\text{check}\)。 Code ```cpp const int N=1e5+5; int T,n,m; int a ......