主页

Educational Round 165 E. Unique Array 首先有一个贪心，对于一个区间 $[l, r]$ 我修改其中任何一个数，整个序列就会被这个数分成不包含这个数的左半部分和右半部分。所以，如果我从左向右考虑，找到了一个不unique的区间，那么我肯定是更改区间最右端的数。现在，我们只需要从左向右扫一遍，考虑从上一个更改过的下标一直到当前下标（左开右闭）有没有不满足unique的区间。 有一个经典trick，如果我想判断一个区间里的数是否存在unique的数，我只需要从左向右扫一遍，第一次遇到某个数时 cnt++，第二次遇到某个数时 cnt--，如果最后 cnt==0，那么就是不unique的。有点类似扫描线。 现在，我们维护每个数字最后出现的位置 $las...

Educational Round 165 C. Minimizing the Sum 这是一道区间dp题。 $f_{i,j}$ 表示到第 $i$ 个下标为止使用 $j$ 次操作所能获得的最小的前缀和，不考虑 $i$ 右侧的数。 由于总的操作次数很有限 $(k\leq10)$，我们可以考虑对后 $t$ 个数全部操作，也就是把 $a_{i-t},…,a_i$ 全部变为他们之中的最小值。然后答案由 $f_{i - t - 1,j - t}$ 转移过来。 状态转移的瓶颈在区间最小值，可以动态地维护，也可以使用ST表。 Submission #301206954 - Codeforces D. Shop Game Bob显然是白嫖最贵的 $k$ 件物品。我们考虑Alice，假...

Educational Round 170 D. Attribute Checks 注意到m的值比较有限，只有5000，那么 $O(m^2)$ 是可以接受的。并且，从一个0到下一个0的过程中，能够通过的检查点是一个确定的值，如果我们知道此时的智力和力量值，并且预先对这些检查点做一些前缀和的预处理的话，可以在 $O(1)$ 时间内算出。那么我们只需枚举在每个0时的智力值然后进行状态转移即可。设 $dp_{i, j}$ 表示在第 $i$ 个0加点完成后拥有 $j$ 点智力，在到达第 $i + 1$ 个0之前能够通过的检查点的总数。然后考虑转移即可。受到空间限制，需要写int而不是long long，可以在原地处理前缀和来节省空间。 Luogu P1641 生成字符串 这是一...

Educational Round 166 D. Invertible Bracket Sequences 括号匹配题，除了用栈来考虑外，还有一个经典trick，可操作性更强。从左往右考虑，如果遇到左括号就+1，遇到右括号就-1，如果这个值在遍历整个串时一直大于等于0且在最后等于0就说明这个括号序列是合法的。如果画出一个图会更清晰，如下(抄自一篇洛谷题解）： 这张图对应的括号序列为：(())((((())()))) 现在，我们反转某一区间的括号，相当于把这张图上的一段曲线向下翻折。我们要保证的是： 这段曲线在翻折后依旧是连续的 不能翻折到第四象限 第一点要求我们取两个 $y$ 坐标相同的地方进行翻折；第二点要求我们翻折的区间的最大值 $y_{max}$ 不能...

Educational Round 166 C. Job Interview 最初想从后往前枚举缺失的人，这样前缀是不变的，只需要考虑后缀，但是后缀的变化不容易做。然后又想通过一个数据结构来在 $O(log{n})$ 时间内做出一个序列的值，发现不会。后面想到可以按照编程和测试来归类进行排序，多出来的一个人直接放到测试。排序之后再来枚举缺失的人，发现变化是可以 $O(1)$ 解决的。 Submission #300875473 - Codeforces Round 996 (Div. 2) C. The Trail 我一开始以为是n+m个方程n+m+1个未知数，有无穷多组解因此第一个数怎么填都行。后面发现无法通过第一个样例。其实，题目给出的并不是n+m个方程，而是n+m...

Edu Round 168 C. Even Positions 从左向右考虑，为使每个括号对的贡献尽量小，每当能填右括号时就填右括号，否则填左括号。最后统计答案。 codeforces.com/contest/1997/submission/300593589 D. Maximize the Root 注意到答案具有单调性，考虑二分答案，使用dfs来check，维护一个当前累积需要减少的数，每当一个数小于0，就把它强行加到0，然后更新需要减少的数，递归子树。当遇到叶子节点时，判断是否可以满足要求。 本题出错是因为这个累计需要减小的值会爆long long，甚至用了__int128_t也不行。考虑到叶子节点的点权是整数范围，当这个累计值超过INT_MAX时其实就已经可以r...

Edu Round 173 C. Sums on Segments 至多有1个数不是1或-1，分开考虑。首先，对于只有1和-1的数组，它们所能表示的数是一段连续的含0的区间。这是因为，每添加一个1或者-1，就相当于对于已经能表示的区间整体+1或-1，然后再添加一个0进去。我们用 $l$ 和 $r$ 来记录考虑当前下标及其左侧所能表示的区间，然后历史的 $l_{min}$ 和 $r_{max}$ 就是所有能表示的数。其次，对于存在不是正负1的数 $x$ 的情况，对其左右两段区间单独考虑，考虑其左侧的后缀和右侧的前缀所能表示的两段区间，由于区间包含0，直接将区间两端点相加，再加上 $x$ 就是含 $x$ 的区间。 另外，由于有些数可能重复考虑，鉴于数据范围并不是很大，一个简单的方法...

跨年特效网页 跨年倒计时 00 天 00 小时 00 分钟 00 秒 祝你新年快乐！