题解：P12949 [GCJ Farewell Round #1] ASCII Art

· · 题解

题目传送门

思路：

看到题解区有找规律的和倍增结合二分的，那我太菜了就不得不拿出暴力做法了。

看数据范围发现 T\le100 且 n \le 10^{12}，那直接 O(Tn) 显然不可取，但是注意到第 i 组的字母总数为 26i，这样显然比暴力模拟快很多，而且求得在某一组后显然能 O(1) 确定答案，所以考虑不枚举 n，而枚举组数 k，则能满足 \frac{k(26+26k)}{2} \le n，当 n 取最大值 10^{12} 时且 k 为整数时，解得 k \le 277349，那么我们的复杂度就变成了 O(Tk)，其中 k\le277349，极限下 T \times k=27734900，显然可以通过此题了。

然后实现稍微有一点点细节，可以看代码。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const long long ma=1000000000000;
long long zh[300005];
int main(){
    zh[0]=0; 
    long long s=0,px;
    for(int i=1;i<=1145141919;i++){
        s+=i*26;
        zh[i]=s;
        if(s>ma){
            px=i;
            break;
        }
    }
    long long t,x;
    cin>>t;
    for(int i=1;i<=t;i++){

        cin>>x;
        x--;
        int u;
        for(int j=1;j<=px;j++){
            if(zh[j]>=x){
                u=j;
                break;
            }
        }
        cout<<"Case #"<<i<<": ";
        if(zh[u]==x) cout<<"A\n"; 
        else if(u==1) cout<<char(x+'A')<<endl;
        else cout<<char(((x-zh[u-1])/u)+'A')<<endl;
    }
    return 0; 
}