• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF 1535-Playoff Tournament

开发技术 开发技术 5小时前 4次浏览

CF 1535-Playoff Tournament

题意

给定深度为(k)的完全二叉树,每个节点有一个值(0/1/?),其中(0)代表选左值,(1)代表选右值,(?)代表二者都选。初始情况下,叶子结点下的节点值为(1)
问每次修改一个节点后,根节点的值为多少。

解法

先根据初始状态建成一颗树,然后每次单点修改,时间复杂度(O(m * k))

小记

XX,完全自己想出来然后debug出来一道1800分的题目好有成就感(虽然好像原来就应该这样),不管了,睡觉睡觉。,开心。

Code


const int N = 1 << 21;

/*
构建一颗深度为k的完全二叉树,节点保存0/1/?,然后从根节点递归枚举当前可能的结果。
单点修改就可以,时间复杂度O(q * 18);
*/


int n;
char s[N];
char tr[N];
int nn ;
int cnt[N],ppp;


inline int ls(int u) {
    return u << 1;
}
inline int rs(int u) {
    return u << 1 | 1;
}

void modify(int pos,char x) {
    int tmp = nn;
    while(tmp) {
        int now = (1 << (tmp - 1));
        int num = now;
        if(num  < pos) pos -= num;
        else {
            ppp = now + pos - 1;
            tr[now + pos - 1] = x;return ;
        }
        --tmp;
    }
}

ll query(int u) {
    if(u >= n) {
        cnt[u] = 1;
        return 1;
    }
    if(tr[u] == '?') {
        cnt[u] = query(ls(u)) + query(rs(u));
        return cnt[u];
    }else if(tr[u] == '1') {
        cnt[u] = query(rs(u));
        query(ls(u));
        return cnt[u];
    }else if(tr[u] == '0') {
        cnt[u] = query(ls(u));
        query(rs(u));
        return cnt[u];
    }

}

void update() {
    int tmp = ppp;
    if(tr[ppp] == '?') {
        cnt[ppp] = cnt[ls(ppp)] + cnt[rs(ppp)];
    }else if(tr[ppp] == '1') {
        cnt[ppp] = cnt[rs(ppp)];
    }else if(tr[ppp] == '0') {
        cnt[ppp] = cnt[ls(ppp)];
    }
    tmp >>= 1;
    while(tmp) {
        //cnt[tmp] = cnt[ls(tmp)] + cnt[rs(tmp)];
        if(tr[tmp] == '?') cnt[tmp] = cnt[ls(tmp)] + cnt[rs(tmp)];
        else if(tr[tmp] == '1') cnt[tmp] = cnt[rs(tmp)];
        else if(tr[tmp] == '0') cnt[tmp] = cnt[ls(tmp)];
        tmp >>= 1;
    }
}


void solve() {
    cin >> n >> (s + 1);
    int tmp = n;
    nn = n;
    n = 1 << n;
    int idx = 1;
    while(tmp) {
        int now = (1 << (tmp - 1));
        int num = 1 << (tmp - 1);
        while(num--) {
            tr[now++] = s[idx++];
        }
        --tmp;
    }
    int m;cin >> m ;
    query(1);
    while(m--) {
        int pos;char x;cin >> pos >> x;
        modify(pos,x);
        update();
        cout << cnt[1] << endl;
    }
}

程序员灯塔
转载请注明原文链接:CF 1535-Playoff Tournament
喜欢 (0)