Yet Another Problem About Pi(数学问题)

Yet Another Problem About Pi

题意:

​ 平面上有无穷个长,宽为w,d的矩形方格。你有一条长度为Π的曲线可以任意弯折,起点任意,求曲线最多经过的方格数目(不计边界)

思路:

​ 先考虑最坏情况:对应max(w,d)>PI时,我们不能越过任何一个方格,此时我们的最佳方案应该是以四个矩形方格的交点为起点,向周围走一圈,最小结果为4

  • 如果我们能够越过方格,我们可以认为以下的所有情况都是有上方(结果为4)的情况推广而来,因为上述拿法是开局最佳。并且因为Yet Another Problem About Pi(数学问题)是无限循环小数,我们可以认为折线极其微小,但是真实存在,此时可以忽略折线的长度,我们有两种方案:
    • 走直线:取Yet Another Problem About Pi(数学问题),走长度更小的一侧必然更优,此时每越过一个格子增加贡献为2
    • 走曲线:取Yet Another Problem About Pi(数学问题),每越过一个格子增加贡献为3(即斜对角方格和其旁边紧挨两格)
  • 可见的是,我们要协调上述两种操作,使得最后的贡献最多。并且可以知道的是:在使用上述操作时,仅有边界情况会影响操作的选择是否需要改变(如走直线变成走曲线)。所以这种变换操作最多存在两次(可以类比回退一步求更优值),所以直接枚举上述两种操作的存在次数,对res取最大值即可

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const double PI = acos(-1);
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
    	double n,m;
    	cin>>n>>m;
    	int res=0;
    	double xie=sqrt(n*n+m*m);
    	double mi=min(n,m);
    	for(int i=0;i<3;i++){
    		if(i*mi<=PI){
    			res=max(res,(int)(4+i*2+floor((PI-i*mi)/xie)*3));
			}
    		if(i*xie<=PI){
    			res=max(res,(int)(4+i*3+floor((PI-i*xie)/mi)*2));
			}
		}
		cout<<res<<endl;
	}
    return 0;
}
上一篇:Daily Coding Problem: Problem #959


下一篇:/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: No such file or directory 报错解决