「Codeforces 1080D」Olya and magical square

发表于 | | 阅读次数:
字数统计: 707 字

Description

题目链接：Codeforces 1080D

给你一个大小为 $2^n\times 2^n$ 的正方形，每次可以把一个正方形切割成 $4$ 个相同的正方形（田字形切割）。求是否可以切割恰好 $k$ 次，使得最终的图形可以从左下角经过若干相同边长的正方形走到右上角（只能往上和往右走）。如果可以，输出 YES 和 $\log_2{\text{路径上正方形的边长}}$（任意一个解）；否则输出 NO。

本题 $T$ 组数据。

数据范围：$1\le T\le 10^3$，$1\le n\le 10^9$，$1\le k\le 10^{18}$

Solution

我们首先可以观察到一个性质：如果 $n>31$，那么我们可以对整个正方形切割一次，再对左上角的正方形随意切割，显然左上角的正方形的能够被切割的次数一定不小于 $10^{18}$。因此当 $n>31$ 时直接输出 YES 和 $n-1$ 即可！

对于 $1\le n\le 31$ 的情况，我们枚举路径上的正方形的边长 $2^i$，计算出最少的切割次数 $L$ 和最多的切割次数 $R$，可以证明 $[L,R]$ 这个区间内的所有切割次数都可以被构造出来。只要有任何一个 $i$ 使得 $L\le k\le R$ 的时候则有解；否则无解。

如何计算最少的切割次数：考虑只切割出我们要走的路径的格子。每次只对边缘那一圈的格子切割，第一次需要切割 $1$ 次，第二次需要切割 $3$ 次，第三次需要切割 $7$ 次……因此最少的切割次数为 $\sum_{j=1}^{n-i}2^j-1$。

如何计算最多的切割次数：对于每个边长为 $2^i$ 的正方形预处理出它的最多切割次数，递推式为 $f(i)=4\times f(i-1)+1$，那么当路径上正方形边长为 $2^i$ 时，最多的切割次数为 $f(n)-(2\times 2^{n-i}-1)\times f(i)$ 即 $f(n)-(2^{n-i+1}-1)\times f(i)$（其中 $2\times 2^{n-i}-1$ 表示路径上的正方形个数）。

时间复杂度：$O(TN^2)$（其中 $1\le N\le 31$）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <cstdio>

long long pw[35];

int check(int n,long long k) {
    for(int i=0;i<n;++i) {
        int p=n-i;
        long long l=0;
        for(int j=1;j<=p;++j) l+=(1LL<<j)-1;
        if(l>k) continue;
        long long r=pw[n]-((1LL<<(p+1))-1)*pw[i];
        if(r<k) continue;
        return i;
    }
    return -1;
}
int main() {
    int T;
    for(int i=1;i<=32;++i) pw[i]=4LL*pw[i-1]+1;
    for(scanf("%d",&T);T--;) {
        int n;
        long long k;
        scanf("%d%I64d",&n,&k);
        if(n>31) {
            printf("YES %d\n",n-1);
        } else {
            int ans=check(n,k);
            if(ans<0) puts("NO"); else printf("YES %d\n",ans);
        }
    }
    return 0;
}
0%