11.16 GRYZ 模拟赛解题报告
期望得分：\(100+60+100 = 260pts\)
实际得分：\(100+60+100=260pts\)
今天没有挂分，这是好的。
但今天前两题都十分降智，这是坏的。
赛事心路历程
T1
转化一下问题就是，找到 \(n\) 段区间，并且要是每段区间的 \(\max - \min\) 在一定范围内。
首先对原数组排序。
然后二分答案，贪心来看，每段区间在数组上都是连续的，所以拿双指针判断即可。
这里我有个降智的地方就是：对一个单调的数组跑单调队列然后还没跑出来。
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<= n;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
K = read(), n = read(), m = read();
for(int i = 1; i <= K; ++i) a[i] = read();
sort(a + 1, a + K + 1);
int l = 0, r = 1000000000, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(Check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
/*
5 2 2
7 5 8 2 3
10 3 3
70 22 24 89 83 81 30 3 75 68
10 3 3
6 9 2 4 5 1 6 1 8 2
*/
T2
显然 DP 有 60。
设 \(f_{i,j}\) 表示到 \(i\) 这个点分了 $j $ 段的最大价值。
\[f_{i,j} = \max_{k其中 \(s_{i,j}\) 表示 \([l,r]\) 这段区间的或和。
时间复杂度 \(\mathcal O(n^3)\) 。
然后你发现这个从后往前枚举的时候，加的权值最多会变化 \(20\) 次，然后你只从变化的位置转移就好了。
时间复杂度 \(\mathcal O(20n^2)\) 。
这个正解代码我没写，放一个 \(60pts\) 的吧
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"< T3
我们考虑枚举这个二叉树的层数
以最底层为 \(0\) 层
假设我们枚举到了第 \(k\) 层，我们有两个点 \(i,j(i < j)\) ，我们算一下他们会造成多少贡献。
我们一共需要 \(2^{k}\) 个点，去掉当前子树内的根节点还剩 \(x = 2^{k}-1\) 个点。
考虑能有多少种情况。
\[\binom{i-1}{x} \times \binom{j-1 - 2^{k}}{x} \]我们要枚举所有的 \(i,j\) ，则总贡献为
\[\sum_{k = 0}^{K - 1}2^{K - k} \times (n - 2^{k + 1})! \times 2^{k}! \times 2^{k}! \times \displaystyle\sum_{i=1}^{n} \sum_{j = i + 1}^{n}\binom{i-1}{x} \times \binom{j-1 - 2^{k}}{x} \times a_i \times a_j \]你如果暴力计算上面那个式子可以获得 \(60pts\) 的好成绩，时间复杂度 \(\mathcal O(k(2^k)^2)\)
然后你把后面这个东西拿出来：
\[\displaystyle\sum_{i=1}^{n} \binom{i-1}{x} \times a_i \sum_{j = i + 1}^{n} \binom{j-1 - 2^{k}}{x}\times a_j \]考虑对后面这个东西做一个后缀和？
对前面这个东西做一个前缀和也可以。
现在他的复杂度应该是 \(\mathcal O(k2^{k})\) ，可以通过。
/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<