正睿OI 24noip十连测day3总结

A.茵蒂克丝

题意：

给定两个序列 \(a,b\) ，每次询问 \([l,r]\) 内选出一个长度不小于 \(k\) 的子区间 \([l',r']\) ，使得 \(\frac{\sum_{i=l'}^{r'} a_i}{\sum_{i=l'}^{r'} b_i}\) 尽可能大。其中 \(k\) 为定值。

\(n,q≤1e6,k≤20\)

题解：

有结论，区间长度一定小于 \(2\times k\) ，这是显然的。如果区间长度大于这个值，不如从中间劈成两半选较大的那一部分。

有了这个结论我们可以维护以每个位置为起点，长度大于等于 \(k\) 并且小于 \(2\times k\) 的区间中值最大的一个，再套一个 \(ST\) 表。

但是我们发现最后距离 \(r\) 小于 \(2 \times k\) 的数是选不到较长的长度的，所以再对每一个数维护以这个数为起点，长度不超过 \(i\) 的最大值(其中 \(i \in [k,2k)\) )，总时间复杂度为 \(O(nk+qk)\)。

总结：

考场上傻逼了后面一部分没有预处理时间假成了 \(O(nk+qk^2)\)，还开了个没必要的 \(long long\) 导致 \(85\) 都没有。

期望得分：\(100\) ，实际得分：\(70\)

B.御坂美琴

题意：

给定一张有向图，每一条边有两个信息，经过这条边需要的硬币数量 \(r_i\) 和经过后会获得的硬币数量 \(p_i\) 。

对于每一个点询问以该点为起点，初始至少需要多少个硬币能无限游走。无解输出 \(-1\)。

\(r_i,p_i≥0 ,n<=2e5,m<=2e5\)

题解：

考虑先搞掉 \(-1\) ，出度为 \(0\) 的点显然无解，所以可以跑一个类似于拓扑排序的东西。

记 \(ans_i\) 为点 \(i\) 的答案，那么答案有这样两种来源：

\(r_i \rightarrow ans_x\)

\(max(ans_x-p_i,r_i) \rightarrow ans_y\)

第一种来源是一条边限制一个点经过它，对于第二种来源，我们建的是反图，若存在一条 \(x\) 到 \(y\) 的边，那么 \(y\) 是可以选择走到 \(x\) 去的，这一条边和 \(x\) 的答案都会限制它。

不难发现这两种转移都是有大到小转移，所以可以按边的 \(r_i\) 排序计算。具体实现上来说，从大到小枚举边（建的边是反边，这很重要），把它的起点转移了（第一种转移），加入队列里面。对于队列里的每一个点，删除连出去的每一条边，顺便用这些边更新别的点，把他们加入队列。

总结：

之前竟然写过原题，好像是贺的，纯小丑。

期望得分：\(15\) ，实际得分：\(40\)。

C.欧提努斯

题意：

欧提努斯有 \(n\) 块积木，第 \(i\) 块的长度为 \(1，\)高度为 \(h_i\)（可以看做在二维平面，于是不考虑宽度）。

欧提努斯可以将这些积木以任意顺序排列，形成一个容器，接着往这个容器中装入尽可能多的水。

欧提努斯想知道，在所有可能的排列方案中，所有能装入的水量分别是多少。

\(2≤n≤2000，1≤hi≤50\)。

题解：

同样考场上没怎么想，但感觉这题是很好的 dp 题。 题目明示我们找到最大值，然后发现题目问的是能凑出多少，这引导我们去推或者猜一些结论和性质。而我们找出最大值，再将两边归并排序，这样就能保证对于每种可能的结果都能构造一种方案使得最大值在结尾，这样会好做很多。 接下来我们可以进行 dp。直接做 01dp 是不好做的，我们发现我们可以排序再做。 我们从小到大考虑，当前这个数如果存在有别的前缀最大值，那么我们需要将它放到一个集合，然后这个数还可以做别的数的前缀最大值。

所以我们设 \(f_{i,j,k}\) 表示考虑到第 \(i\) 个数，集合中有 \(j\) 个数，能否凑出 \(k\) 的 01 状态，转移是显然的，\(f_{i,j,k}\rightarrow f_{i+1,j+1,k}\)，和 \(f_{i,j,k}\rightarrow f_{i+1,j-t,h_{i+1}\times(t+1)}\)。 为什么是 \(t+1\) 呢？因为我们 \(h_{i+1}\) 也会被放入集合中，然而如果 \(t=0\) 是毫无意义的。

然后观察这个过程，发现当前的时间瓶颈在第二个转移，然后我们注意到这正是背包形式的转移，对于 \(f_{i,j}\)，我们可以从集合中掏出一个数交给 \(h_{i+1}\) ，就能转移到 \(f_{i,j-1}\)。这样子大大减少了转移次数，但发现仍然通过不了这道题。 现在两种转移是同级的，我们首先发现 \(h\) 范围很小，然而对于相同的 \(h_i\)，我们发现只有最后一个是有效的转移，为什么？

我们考虑对于一个状态，我们假设 \(h_i\) 是最后一个，那么 \(h_{i}\) 的转移显然会包含 \(h_{i-1}\) 的转移，然后我们第二个转移又得到了优化。再看第一个转移，注意到 \(i,j\) 的相对位置不变，我们可以改变状态意义解决！我们开始是 \(|S|=j\)，而现在我们将 \(j\) 改为 \(i-|S|\)，那么我们发现我们不需要理会第一个转移了。 这个转移也有有趣的地方，我开始使用的是在最后处整体转移，而后面我发现大家的代码都是用前面的存在的数与当前数转移，本质上都是一样的。

总结：

直接写了暴力，没想到 \(bitset\) ，气死了。

期望得分：\(20\) ，实际得分：\(20\)。

D.食蜂操祈

哎呀不会

总结：

期望得分：\(10\) ，实际得分：\(10\)。