51nod分析假设答案位置在某条边上，感性理解可得答案关于答案位置与这条边的某个端点的距离是单谷函数。枚举答案在哪条边上并三分，问题变为求最远点。显然某个点到达边上某个位置一定是先到达一个端点再走过来，因此 Floyd 预处理两两之间的最短路即可。代码// =================================== // author: M_sea // website:...
LuoguLOJ分析设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。这样子可能过不了，考虑一些优化。我们预处理出每艘...
Luogu分析可以猜测，存活天数关于买外卖次数的图像是单峰的。证明不会，但是可以感性理解一下：买外卖次数少显然存活天数不会多，买外卖次数多时钱不够因此存活天数也不会多。于是我们可以三分买外卖次数。那么现在需要解决的问题变为给定买外卖次数，求最多存活天数。首先，如果存在一个保质期长、价格便宜的食品，那么我们一定不会买保质期短、价格贵的食品。因此我们可以先把所有食品按保质期排序，然后用单调栈筛掉...
LuoguBZOJ分析猜想一波：最长的天数-购买外卖的总次数的函数图像是单峰的。于是可以三分这个总次数。考虑如何求出这个最长的天数。首先把所有外卖按价格排序，因为显然我们会购买尽量多的便宜的没有过期的外卖。假设对于最便宜的外卖，过期的天数是 $s$ ，那么我们一定会每次买 $s$ 份。其它外卖类似。具体实现及细节见代码。代码// ===============================...
Luogu算法三分套三分的板子？考虑固定点$E$，可以发现，此时的时间是关于$F$的单峰函数。证明不会然后再考虑动点$E$。可以发现，时间关于$E$也是一个单峰函数。那么三分套三分即可。代码重载了$Point$，所以很短。代码#include <bits/stdc++.h> #define re register #define EPS 1e-6 using namespace ...