12807 我有一个梦想

思路

首先判断能否进行k次切割,边长为2^n的正方形可以进行1+4+4^2+…+4^{n-1}\sum_{i=1}^n 4^{n-1}次切割,如果k大于这个数则无法切割。如果n对应的切割次数超过k的上限1e18,则一定可以进行切割。
然后求出用最少次数切割成更小正方形的方案。显然,在上一个最小方案每次尽量切割当前路径上每一个最小正方形为最优方案。
一张丑的很的图
如上图,第一次切割为黑线,第二次切割为蓝线,第三次切割为红线,容易发现这是最优方案,切割次数每次为上次切割次数\times2+1

注意

如果当前切割次数不满足切割成更小的正方形的方案,就要把切割次数用在剩余的部分(不能影响当前正方形最小的那条路径),因此剩余部分需要可以切割,答案才成立。
当n=2,k=3时,如下图,维持红色正方形为正方形大小相等的路径,需要再进行一次切割,但剩余部分无法继续切割,故需要特判此状况为No

对于其他情况,不难证明,剩余部分可切割次数的增长速度比路径上正方形个数的增长速度要快,并且n=3时均可切割,所以其他情况都有满足题意的切割方案。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int a[N],b[N];
ll pow4[100],sum4[100],pow2[200];
int main()
{
    pow2[0]=pow4[0]=sum4[0]=1;
    int q=0;
    for(int i=1;i<100;i++,q++)
    {
        pow4[i]=pow4[i-1]*4;
        sum4[i]=sum4[i-1]+pow4[i];
        pow2[2*i-1]=pow2[2*i-2]*2;
        pow2[2*i]=pow2[2*i-1]*2;
        if(pow4[i]>=ll(1e18)) break;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,k;
        scanf("%lld%lld",&n,&k);
        if(n==2&&k==3)
        {
            printf("No\n");
            continue;
        }
        if(n-1<q&&k>sum4[n-1])
        {
            printf("No\n");
            continue;
        }
        ll tmp=1;
        if(k==0)
        {
            printf("Yes %lld\n",n);
            continue;
        }
        int f=1;
        while(n>0&&k>=tmp)
        {
            n--;
            k-=tmp;
            tmp=tmp*2+1;
        }
        printf("Yes %lld\n",n);
    }
    return 0;
}