P9859 [CCC 2008 S2] Pennies in the Ring 题解

· · 题解

怎么没找到 T 的数据范围啊？在这里钦定 1\leq T\leq 25000 吧。

根据初中数学可以得出，原问题等于求： x^2+y^2\leq n^2 的整数对 (x,y) 的有序对数。

这题我想了 1h 的线性做法，然后发现好像没有。

这题我们显然可以打一个 O(Tn^2) 的暴力出来：

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[25001];
int main(){
    while(cin>>n&&n){
        if(!a[n]){
            sum=0;
            for(int i=1;i<=n;i++){
                for(int j=1;i*i+j*j<=n*n;j++) sum++;
            }
            a[n]=4*sum+4*n+1;
            cout<<4*sum+4*n+1<<endl;
        }
        else cout<<a[n]<<endl;
    }
}

这样显然是不行的，T 取 25000 然后每个 n 不同分分钟可以给你卡到 n^3 级别，根本过不了。

哎？怎么过了？肯定是因为数据水，我们接着考虑怎么优化：

容易发现每次的内层循环中，i^2 的值是一定的，j^2 的值可以通过预处理整出来，然后每次二分求解，所以内层可以被优化到 \log n 级别。

时间复杂度 O(Tn\log n)。

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[25001],b[25001];
int main(){
    for(int i=1;i<=25000;i++) b[i]=i*i;
    while(cin>>n&&n){
        if(!a[n]){
            sum=0;
            for(int i=1;i<=n;i++){
                int l=0,r=25000;
                while(l<r){
                    int mid=l+r+1>>1;
                    if(b[mid]<=n*n-i*i) l=mid;
                    else r=mid-1;
                }
                sum+=l;
            }
            a[n]=4*sum+4*n+1;
            cout<<4*sum+4*n+1<<endl;
        }
        else cout<<a[n]<<endl;
    }
}

然而这种做法似乎也过不去，因为还是那样，如果 T 取 25000 然后每个 n 不同分分钟可以给你卡满，而卡满的情况下大约需要跑 10^{10} 次，也过不了。

哎？怎么又过了？肯定是因为数据水，我们接着考虑怎么优化：

这时候肯定就有人说了：你前面说没有线性做法，现在又说单 \log 过不去，难道除了线性有什么东西比单 \log 还快吗？

确实没有，但是我们充分发扬人类智慧，直观感受一下：

我们感觉到：在矩形中，包含在圆里的点的数量一定比不包含在圆里的点的数量多很多，也就是说，设 m=n\times 2+1，最终的答案一定是 m^2-4\times 一个很小的数字。

我们考虑枚举每一个不在圆里的点，也就是找出那个很小的数字，这个跟那个暴力差不多，时间复杂度 O(Tn^2)，但是严重跑不满，最终过了。

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[25001];
int main(){
    while(cin>>n&&n){
        if(!a[n]){
            sum=0;
            for(int i=1,j=n;i<=n;i++){
                j=n;
                while(i*i+j*j>n*n) sum++,j--;
            }
            a[n]=(n*2+1)*(n*2+1)-4*sum;
            cout<<(n*2+1)*(n*2+1)-4*sum<<endl;
        }
        else cout<<a[n]<<endl;
    }
}

附极限数据一组，供大佬们调试用。