K Yet Another Problem About Pi
链接:K-Yet Another Problem About Pi_2021牛客暑期多校训练营8 (nowcoder.com)
题意:平面上有无穷个长,宽为的矩形方格。你有一条长度为的曲线可以任意弯折,起点任意,求曲线最多经过的方格数目(不计边界)
先考虑最坏情况:对应时,我们不能越过任何一个方格,此时我们的最佳方案应该是以四个矩形方格的交点为起点,向周围走一圈,最小结果为4
如果我们能够越过方格,我们可以认为以下的所有情况都是有上方(结果为4)的情况推广而来,因为上述拿法是开局最佳。并且因为是无限循环小数,我们可以认为折线极其微小,但是真实存在,此时可以忽略折线的长度,我们有两种方案:
- 走直线:取,走长度更小的一侧必然更优,此时每越过一个格子增加贡献为2
- 走曲线:取,每越过一个格子增加贡献为3(即斜对角方格和其旁边紧挨两格)
可见的是,我们要协调上述两种操作,使得最后的贡献最多。并且可以知道的是:在使用上述操作时,仅有边界情况会影响操作的选择是否需要改变(如走直线变成走曲线)。所以这种变换操作最多存在两次(可以类比回退一步求更优值),所以直接枚举上述两种操作的存在次数,对取即可
#include <bits/stdc++.h> #define endl '\n' typedef long long ll; typedef unsigned long long ull; using namespace std; const double PI = acos(-1); signed main() { int t; scanf("%d", &t); while(t--) { double w, d, tmp, dis; ll ans = 0; scanf("%lf%lf", &w, &d); tmp = min(w, d); dis = sqrt(w * w + d * d); for(int i = 0; i <= 2; ++i) { //枚举直线数目 if(i * tmp <= PI) ans = max(ans, (ll)(4 + 2 * i + floor((PI - tmp * i) / dis) * 3)); // 枚举斜线数目 if(i * dis <= PI) ans = max(ans, (ll)(4 + 3 * i + floor((PI - dis * i) / tmp) * 2)); }printf("%lld\n", ans); } return 0; }