「USACO 2018.01 Platinum」解题报告

A – Lifeguards

先可以想到把所有的包含的区间给去掉,然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单,然而 \(k \leq 200\) 就很麻烦。

继续阅读「USACO 2018.01 Platinum」解题报告

「杂题集」- 2019年12月9日

最近都在学些科技,做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。

子集

首先,我们先考虑奇数长度段的情况(\(\{a_n\}\)已经排序):确定中位数为\(a_{mid}\),则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和,并除以元素个数。欲使价值最大,那么显然右侧需要靠近右端点进行选择, 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化:简化对长度的枚举复杂度。

继续阅读「杂题集」- 2019年12月9日

Codeforces 1174D:Ehab and the Expected XOR Problem 题解

主要思路

这道题还蛮妙的,自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\),根据异或按位处理的性质,显然对于所有的\(S_i\)都会小于\(2^n\)。最后,我们可以把限制变成:

  • 不存在两个相同的前缀和。
  • 不存在一对前缀和,其异或值为\(x\)。

针对\(x\)的大小关系,我们可以分成两种情况:

  • \(x \geq 2^n\),不存在一对\((S_i, S_j)\)的异或为\(x\),因为存在更高的位并不会被消除。
  • \(x < 2^n\),我们发现每选择一个数作为前缀和,整个\(2^n\)中就会少一个对应的可以被选择的数。所以,我们每次选一个作为\(S_i\)的数时,都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

继续阅读Codeforces 1174D:Ehab and the Expected XOR Problem 题解

「2018泉州国庆集训#3」 – 解题报告

A – 人类基因组

这套题全都是暴力出奇迹系列。

我们枚举一个端点,然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\),然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了,太特么傻逼了。

继续阅读「2018泉州国庆集训#3」 – 解题报告