题解：P11214 【MX-J8-T2】黑洞
Lumira
·
·
题解
形式化题意
给出 \{m_n\} 和 \{a_n\}，记 a_i=b_{i,0}，m_i-a_i=b_{i,1}，求 \displaystyle{\sum(\min\{b_{1,i_1} , b_{2,i_2} , b_{3,i_3} , ... , b_{n,i_n} \}),\;i_{1,2,3,...,n}\in\{0,1\}}。
前置小芝士：__int128
使用 __int128 可以避免超过数据范围，虽然好像没什么必要。
52 pts 做法
思路
显然可以暴力求解，一共 i_{1,2,3,...,n} 有 2^n 种选法。对于每种选法暴力找出最小值。总复杂度 \Theta(2^nn)。显然可以过掉这些点。
76 pts 做法
思路
显然刚才的暴力朴素算法是不行了，必须将那个指数级的复杂度去掉才行。
我们记 c_{i_1,i_2,i_3,...,i_n}=\min\{b_{1,i_1} , b_{2,i_2} , b_{3,i_3} , ... , b_{n,i_n} \},\;i_{1,2,3,...,n}\in\{0,1\}。显然，b_{n,k} 中对 c_{i_1,i_2,i_3,...,i_n} 影响最大的是 b_{n,k}，c 中不少于一半的数是 b_{n,k} 的最小值。所以我们可以直接求得 b_{n,k} 的最小值的贡献为 \min{b_{n,k}}\times 2^{n-1}。然后不断这样做下去就好了。但是有一点不同：如果此刻选到的 b_{s_0,t_0} 中的 s_0 已经作为先前最小值的 s 出现过了，这时剩下的贡献就都是 b_{s_0,t_0} 给出的了，这点很易于证明，这时我们可以直接跳出循环。由于 n-1 比较大，不能使用 pow() 函数等手段，左移运算符更是远远不够，所以考虑逐次相乘。显然这样的操作需要排序。这样的时间复杂度为 \Theta(n\log n+n^2)。可以丝滑通过这些点。
参考代码
Code
100 pts 做法
实话：拿 76 分的真的很可惜，因为是临门一脚。
数据范围
### 思路
这个数据范围大概率是 $n\log n$ 了。我们注意到刚刚龟速乘方浪费了一个线性的复杂度，于是可以将 $2_{i},i\in[1,2\times10^5],i\in \mathbb{N_+}$ 全部预处理出来，这样复杂度就变成了 $\Theta(n\log n)$。得以通过此题。
以下提供本人赛时挂分思路（虽然赛时没过，但其实是可以过的）：
我们惊奇的发现，76 分的代码在前 16 个测试点的表现很好，换言之其常数很小，那我们压一压这个代码的常数是不是也可以过去呢？
我不禁想到：
某大佬的话：N 方打表过百万，暴力 O2 踩标算。
某洛谷管理说过：实际上，洛谷评测机的速度是足以支持在 1 秒内进行 1.2\times 10^9 次 unsigned long long 类型变量相乘并且自然溢出的。
于是果断卡常！
我们注意到我们只要将龟速乘方的时间复杂度压到 \Theta(\frac{n}{\omega}) 就可以过了。那么我们的思路就应运而生了：打表！
洛谷提交的代码长度不超过 50KB，CCF 的限制则是 100KB（其实这个不必需）。
我们只需要打出一个特定的数字 2^i,i=1,2,...,s，s 是一个特定常数，时间复杂度就降到了 \Theta(n\log n+\frac{n^2}{s})。经测，s=120 即可通过此题。当然我们也可以打到代码最大长度，于是可以得出代码：
Code
Data Maker
写在后面
其实卡常的想法考试的时候已经想到，但是当时只写了 s=60 的做法，导致最后几个点分数没拿到。事实上，本地测试时带上输入输出时间（最后一个大样例）都只用了 0.2s 不到。当时就想着评测的时间应该差不多能卡进去，但是最后没有卡过去，而且差挺多的。去年在考 CSP 的时候也出现过这个问题。CSP 第二轮即将到来，在祝福的同时，也提醒大家注意常数！而且不要卡太死！在估计的时候要考虑 CPU 的速度！并且，要考虑 IPC 的提升（不能仅仅根据频率来估测）。比如本人的英特尔 12 代 CPU 虽然频率低于洛谷的 Intel(R) Xeon(R) Platinum 8369HC CPU @ 3.30GHz，但是由于 Golden Cove 单核大提升，比洛谷的评测机反而会快。如果在 CSP 考场上遇到英特尔 11 代或 AMD 3000 系列或更新的处理器要注意这点（另外一般台式机除服务器和企业用机会自动解锁 TDP 而跑在睿频上，这些点都要注意）。最后祝大家 CSP rp++！