M_sea

洛谷5342 [TJOI2019]甲苯先生的线段树
LuoguBZOJLOJ分析不会做.jpg第一问很容易做,直接暴跳即可。假设第一问的答案为 $s$ 。我们把一条路...
扫描右侧二维码阅读全文
31
2019/05

洛谷5342 [TJOI2019]甲苯先生的线段树

Luogu

BZOJ

LOJ

分析

不会做.jpg

第一问很容易做,直接暴跳即可。假设第一问的答案为 $s$ 。

我们把一条路径记做 $(x,l,r)$ ,表示 $x$ 是深度最小的点,往左子树中走了 $l$ 长度,往右子树走了 $r$ 长度。

可以发现,$(x,l,r)$ 的权值和下界是 $\left(2^{l+1}+2^{r+1}-3\right)x+2^r-1$ 。证明的话一直走左儿子即可得到这个值。


先考虑 $x=1$ 怎么做。如果我们在深度为 $d$ 的地方走了右子树,那么就会多出 $2^{d+1}-1$ 的贡献。问题相当于有多少组长为 $l-1$ 和 $r-1$ 的 $0/1$ 串,第 $i$ 位的值为 $2^{i+1}-1$ ,满足这两个字符串的权值和加上权值和下界恰好等于 $s$ 。那么直接数位 $\mathrm{dp}$ / 记搜即可。


考虑 $x\neq 1$ 怎么做。

首先有一条性质:对于不同的 $x$ ,$(x,l,r)$ 的值域没有交。

那么因为权值和是固定的 $s$ ,所以对于某个 $(l,r)$ ,$x$ 是唯一确定的。

考虑枚举 $l,r$ 。设 $k=(2^{l+1}+2^{r+1}-3),b=2^r-1$ ,那么可以得出 $x=\left\lfloor\frac{n-b}{k}\right\rfloor$ 。

那么问题就相当于 $s'=(s-n)\%k,x=1$ 的问题了。


具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

map<ll,ll> f[55][55];

inline ll dfs(int x,int y,ll z) {
    if (x<y) swap(x,y);
    if (z<0||z>(2ll<<x)+(2ll<<y)-x-y-4) return 0;
    if (!x&&!y) return !z;
    if (f[x][y].count(z)) return f[x][y][z];
    return f[x][y][z]=dfs(x-1,y,z)+dfs(x-1,y,z-(1ll<<x)+1);
}

inline int dep(ll x) {
    int res=0;
    while (x) x>>=1,++res;
    return res;
}

int main() {
    int T=read();
    while (T--) {
        int d,op; ll a,b,s=0;
        d=read(),a=read(),b=read(),op=read();
        while (a!=b) {
            if (a>b) s+=a,a>>=1;
            else s+=b,b>>=1;
        }
        s+=a;
        if (op==1) {
            printf("%lld\n",s);
            continue;
        }
        ll ans=0;
        if (dep(s)<=d) ++ans;
        for (re int l=1;l<=d;++l) {
            ll k=(2ll<<l)-1;
            if (k<=s&&dep(s/k)+l<=d)
                ans+=dfs(l,0,s%k);
        }
        for (re int l=1;l<=d;++l)
            for (re int r=1;r<=d;++r) {
                ll k=(2ll<<l)+(2ll<<r)-3,b=(1ll<<r)-1;
                if (k+b<=s&&dep((s-b)/k)+max(l,r)<=d)
                    ans+=dfs(l-1,r-1,(s-b)%k);
            }
        printf("%lld\n",ans-1);
    }
    return 0;
}
最后修改:2019 年 05 月 31 日 04 : 39 PM

发表评论