P12949 [GCJ Farewell Round #1] ASCII Art 题解
题目传送门
我的博客
前言
倍增+二分
思路
-
首先第一步，我们肯定要去求第 \(n\) 个字符位于第几个循环里。
-
第二步，求第 \(n\) 个字符在这个循环里的位置。
-
不难发现，解决第一步后，第二步也就迎刃而解了。
首先第一步。
第 \(k\) 个循环里面一共有 \(26k\) 个字符。那么前 \(k\) 次循环就一共有 \(\sum_{i=1}^k 26i\) 个字母。记为 \(f(i)\)。
化简可得
\[f(i) = 26 \times \sum_{i=1}^k k
\]
运用等差数列求和公式，可以进一步化简为
\[f(i) = 26 \times \frac{i \times (i+1)}{2}
\]
即
\[f(i) = 13 \times i \times (i+1)
\]
那么我们要求的 \(k\) 就需要满足
\[f(k-1) \leq n \leq f(k)
\]
暴力计算显然会T，于是考虑倍增求出大致范围，再用二分确定具体 \(k\) 值。
第二步。
由第一步我们可以求出具体 \(k\) 值，于是第 \(k\) 次循环就有 \(26k\) 个字母。也就是说每个字母都出现 \(k\) 次且顺序出现。则第 \(k\) 次循环的起始位置就是 \(f(k-1)+1\)。假设 A 是第 \(0\) 个字母,那么第二步的答案就呼之欲出了——
\[\lfloor \frac{n-(f(k-1)+1)}{k} \rfloor
\]
代码
#include<cstdio>
#include<iostream>
using namespace std;
#define int long long
inline int Read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-48;c=getchar();}return x*f;
}
inline void Write(int x){if(x<0){x=-x;putchar('-');}if(x>9) Write(x/10);putchar(x%10+'0');
}
int T,n;
int calc(int x){//计算f函数return 13*x*(x+1);
}
signed main(){T=Read();for(int o=1;o<=T;o++){//别忘了输出格式n=Read();int l=1,r=1,ans=0;while(calc(r-1)<n) l=r,r<<=1;//倍增求大体范围while(l<=r){//二分求具体范围int mid=(l+r)>>1;if(calc(mid)>=n) r=mid-1,ans=mid;else l=mid+1;} int st=calc(ans-1)+1;//起始位置ans=(n-st)/ans;//最终答案printf("Case #%lld: ",o);printf("%c\n",(char)ans+'A');//别忘了强制类型转换，否则输出为数字}return 0;
}