主要思路
佛了。
让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数，用莫队搞即可；如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数，这个可以 \(\Theta(n)\)，如果是 \(5\) 那就把 \(0, 5\) 染色即可。
Continue reading →佛了。
让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数，用莫队搞即可；如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数，这个可以 \(\Theta(n)\)，如果是 \(5\) 那就把 \(0, 5\) 染色即可。
Continue reading →先可以想到把所有的包含的区间给去掉，然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单，然而 \(k \leq 200\) 就很麻烦。
最近都在学些科技，做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。
首先，我们先考虑奇数长度段的情况（\(\{a_n\}\)已经排序）：确定中位数为\(a_{mid}\)，则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和，并除以元素个数。欲使价值最大，那么显然右侧需要靠近右端点进行选择， 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化：简化对长度的枚举复杂度。
这道题还蛮妙的，自己比较顺利的思考出来了。
考虑设置前缀异或和\(\{ S_i \}\)，根据异或按位处理的性质，显然对于所有的\(S_i\)都会小于\(2^n\)。最后，我们可以把限制变成：
针对\(x\)的大小关系，我们可以分成两种情况：
结合一下就可以了。
这套题全都是暴力出奇迹系列。
我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。
然后用 sb 线段树搞下就行了，太特么傻逼了。