【 Codeforces Round #524 (Div. 2) D. Olya and magical square】 模拟

D. Olya and magical square

题意

给你一个$2^n?2^n$的方块，每一次选一个正方形把他分成四块，一共k步问最后是否可以让最后的左下角方块的大小等于右上角方块的大小，而且可以从左下角沿着同样大小的方块走到右上角

做法

最后的路径一定可以是沿着边界走到右上角，只要路径上大小固定，就可以算出其它块可以分裂的次数，所以只要动态维护当前分裂次数a和可以分裂的次数b，如果当前分裂次数已经>k则不满足，否则如果出现a<=k&&a+b>=k说明有满足情况的答案。

动态维护分裂的过程需要维护好多个变量，首先要维护路径的长度，这样也就知道去除路径剩多少个可分裂的块。还要维护左下角块的大小，也就知道可分裂次数。之后动态维护a,b就可以了。

代码

#include<stdio.h>
typedef long long ll;
int main()
{
    int t;ll n,k;scanf("%d",&t);while(t--){
    scanf("%lld%lld",&n,&k);ll a=1,b=0;// a 已用次数，b 可分解次数ll tt=n-1;//左下角块的大小ll lu=3;//路径上块数int flag=0;int ff=0;ll cnt=0;ll tm=1;for(int i=0;i<=n-2;i++){
    cnt+=tm;b+=tm;if(cnt>=k){
    ff=1;break;}tm=tm*4;}while(true){
    if(tt==-1) break;if(ff==1||a>k) break;if(a<=k&&a+b>=k){
    ff=1;break;}a+=lu;ll tmp=lu*4;//tmp 是去掉路径上的点余下的块tt--;lu=2LL*lu+1;tmp-=lu;tm=tm/4;cnt-=tm;b+=cnt*tmp;}if(tt>=0&&ff==1)  printf("YES %lld\n",tt);else printf("NO\n");}return 0;
}