题解 CF1080D 【Olya and magical square】
ouuan
2018-11-25 10:20:50
首先我们可以发现，题目要求的这条通路在哪是无所谓的，所以不如就先从左下角走到右下角，再从右下角走到右上角。
先考虑无法进行 $k$ 次操作的情况，为判断这种情况，需要计算将一个 $2^n\times 2^n$ 的正方形全部变成 $2^{n-i}\times2^{n-i}$ 的正方形需要的操作次数 $a_i=1+4+16+\cdots+4^{i-1}$，可以快速预处理出来。而且 $a_{31}>10^{18}$，所以只用计算 $a_{1..31}$ 。
还需要预处理的是造出一条由 $2^{n-i}\times2^{n-i}$ 的正方形构成的通路需要的最少操作数 $b_i=1+3+7+\cdots+(2^i-1)$。 同样可以快速预处理出来。
那么，是不是只要 $b_i\le k\le a_n$，就可以输出 `YES n-i` 了呢？并不是。造出由 $2^{n-i}\times2^{n-i}$ 的正方形构成的通路进行的操作数是有上限的，实际上就是先造出这条通路，再将除这条通路外的正方形全部分割成 $1\times1$ 的正方形，总共需要的操作数： $a_i+a_{n-i}\times(2^i-1)^2$。其中 $a_i$ 代表先将 $2^n\times 2^n$ 的正方形全部变成 $2^{n-i}\times2^{n-i}$ 的正方形，$a_{n-i}$ 是将每个 $2^{n-i}\times2^{n-i}$ 的正方形分割成 $1\times1$ 的正方形，$(2^i-1)^2$ 是 $2^{n-i}\times2^{n-i}$ 的正方形的个数。
所以..看代码吧：
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
long long i,t,n,k,a[40],b[40];
int main()
{
cin>>t;
a[1]=1;
b[1]=2;
for (i=2;i<=32;++i)
{
a[i]=a[i-1]*4;
b[i]=b[i-1]*2;
a[i-1]+=a[i-2];
b[i-1]+=b[i-2]-1;
}
while (t--)
{
cin>>n>>k;
if (n>31)
{
cout<<"YES "<<n-1<<endl; //由于a[31]>1e18，n>31时一定可以先分割一次，剩下的操作全部用来分割左上角的正方形
}
else if (k>a[n])
{
puts("NO");
}
else
{
for (i=1;i<=n;++i)
{
if (k>=b[i]&&k<=a[i]+a[n-i]*((1<<i)-1)*((1<<i)-1))
{
break;
}
}
if (i>n)
{
puts("NO"); //实际上这种情况有且仅有n=2,k=3
}
else
{
cout<<"YES "<<n-i<<endl;
}
}
}
return 0;
}
```