头像

wxy_




在线 



wxy_
6天前
#include <iostream>

namespace wxy{
    const int N = 1e5 + 5;
    int a[N],n,m;
    long long b[N];
    inline int lowbit(int x){return x & -x;}
    inline void add(int x,long long a){
        for (;x <= n; x += lowbit(x)) b[x] += a;
    }
    inline long long ask(int x){
        long long res = 0;
        for (int i = x;i;i -= lowbit(i))
            res += b[i];
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for(int i = 1; i <= n; i++) std::cin >> a[i];
        for (int i = n; i >= 1; i--) a[i] = a[i] - a[i - 1];
        for (int i = 1; i <= n; i++) add(i,a[i]);
        for (int i = 1; i <= m; i++){
            char op[1];
            int a,b;
            long long c;
            std::cin >> op;
            std::cin >> a;
            if (op[0] == 'Q') std::cout << ask(a) << std::endl;
            else{
                std::cin >> b >> c;
                add(a,c);
                add(b + 1,-c);
            }
        }
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
7天前
#include <iostream>

namespace wxy{
    const int N = 1e5 + 5;
    int a[N],n,m;
    long long b[N];
    inline int lowbit(int x){return x & -x;}
    inline void add(int x,long long a){
        for (;x <= n; x += lowbit(x)) b[x] += a;
    }
    inline long long ask(int x){
        long long res = 0;
        for (int i = x;i;i -= lowbit(i))
            res += b[i];
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for(int i = 1; i <= n; i++) std::cin >> a[i];
        for (int i = n; i >= 1; i--) a[i] = a[i] - a[i - 1];
        for (int i = 1; i <= n; i++) add(i,a[i]);
        for (int i = 1; i <= m; i++){
            char op[1];
            int a,b;
            long long c;
            std::cin >> op;
            std::cin >> a;
            if (op[0] == 'Q') std::cout << ask(a) << std::endl;
            else{
                std::cin >> b >> c;
                add(a,c);
                add(b + 1,-c);
            }
        }
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
12天前

众所周知noip暴力分暴多

$Case\ 1$

考虑第一个数据点和第二个数据点,显然当且仅当$S_i=T_i=u$时,才会对点$u$产生贡献,因此在标记后线性扫描每个点即可。

复杂度$O(n+m)$

期望得分:$10\ pts$

$Case\ 2$

显然当且仅当$u=S_i$时,才会对点$u$产生贡献,标记所有起点线性扫描每个点即可。

复杂度$O(n+m)$

期望得分:$20\ pts$

$Case\ 3$

考虑暴力枚举每条链,对其进行树上差分后依次枚举每个点,该链对点$u$产生贡献当且仅当该点在链上且$dis(S_i,u)=w_u$。

复杂度$O(mn+m\ log\ n)$

期望得分:$25\ pts$

$Case\ 4$

该题退化为链的方式比较特殊。

我们发现,当按所叙述方式退化为链时整个问题转化为线性序列上的问题:

给出一个序列$a$与$m$个区间,求对于序列$a$第$i$个位置前面第$a[i]$个位置上有几个$S_j$满足其对应的$T_j\ge i$。

对于每个位置开一个$vector$,保存其$S_i$恰好为这个位置所对应的所有$T_i$,递增排序后每次二分查找即可。

复杂度$O(n\ log\ n)$

期望得分:$40pts$

$Case\ 5$

当所有的$S_i$为根节点时。

显然当且仅当$T_i$在以$x$为根的子树内时,链$[HTML_REMOVED]$才会经过$x$。

因此直接$DFS$一遍,统计每个节点到根节点的距离$dis(u)$,如果$dis(u)=w_u$,那么其节点$u$的答案即子树内$T_i$的数量,否则为$0$。

对于$T_i$的数量,直接打标记后$DFS$一遍即可求得。

复杂度$O(n)$

期望得分:$60pts$

$Case\ 6$

我们发现,当终点在根节点时。

其等价于求在以点$u$为根的子树内有多少$S_i$,满足$dis(u,S_i)=w_u$。

我们设点$u$的深度为$deep[u]$,那么即等价于在点$u$的子树内,深度为$deep[u]+w_u$的这一层内有多少$S_i$。

把原树用$DFS$序重编号,按层拆成若干份使用$vector$存储。

对于每个$S_i$对其进行序列单点加之后求前缀和。

在$deep[u]+w_u$这一层的$DFS$序中二分点$u$ $DFS$序所对的区间查询区间和。

复杂度$O(n\ log\ n)$。

期望得分:$80pts$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

namespace wxy{
    const int N = 3e5 + 5,inf = 5e5 + 5;
    int ans[N];
    int head[N],fail[N << 1],edge[N << 1],w[N],tot,n,m;
    int fa[N][35],dep[N],tlca[N],dfn[N],cnt,l[N],r[N];
    bool vis[N];
    int t[N],pt[N],ppt[N],maxdeep;
    typedef std::pair<int,int> PII;
    #define x first
    #define y second
    PII ask[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs1(int x){
        l[x] = ++cnt;
        dfn[cnt] = x;
        for (int i = 1; 1 << i <= n; i++)
            fa[x][i] = fa[fa[x][i-1]][i-1];
        for (int i = head[x];i;i = fail[i]){
            int v = edge[i];
            if (dep[v] != -1) continue;
            fa[v][0] = x;
            dep[v] = dep[x] + 1;
            dfs1(v);
        }
        r[x] = cnt;
    }
    inline int lca(int x,int y){
        if (dep[x] < dep[y]) std::swap(x,y);
        int d = dep[x] - dep[y];
        for (int i = 0; i < 20; i++)
            if (d >> i & 1) x = fa[x][i];
        if (x == y) return x;
        for (int i = 19; i >= 0; i--){
            if (fa[x][i] != fa[y][i]){
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }
    inline int get(int x,int y){
        return dep[x] + dep[y] - 2 * dep[lca(x,y)];
    }
    inline void case1(){
        for (int i = 1; i <= m; i++) 
            if (w[ask[i].x] == 0)ans[ask[i].x]++;
    }
    inline void case2(){
        for (int i = 1; i <= m; i++) ans[ask[i].x]++;
    }
    inline void case3(){
        for (int i = 1; i <= m; i++){
            memset(t,0,sizeof t);
            int a = ask[i].x,b = ask[i].y;
            t[a]++;t[b]++;t[tlca[i]]--;
            t[fa[tlca[i]][0]] -= 2;
            for (int j = n; j >= 1; j--) 
                t[fa[dfn[j]][0]] += t[dfn[j]];
            for (int j = 1; j <= n; j++){
                if (t[j] >= 1 && get(j,a) == w[j]){
                    ans[j]++;
                } 
            }
        }
    }
    inline void case4(){
        std::vector<int> pos[N];
        for (int i = 1; i <= n; i++){
            pos[i].push_back(0);
            pos[i].push_back(inf);
        }
        for (int i = 1; i <= m; i++)
            pos[ask[i].x].push_back(ask[i].y);
        for (int i = 1; i <= n; i++)
            std::sort(pos[i].begin(),pos[i].end());
        for (int i = 1; i <= n; i++){
            if (i - w[i] > 0){
                int loc = i - w[i];
                int count = lower_bound(pos[loc].begin(),pos[loc].end(),i) - pos[loc].begin();
                if (pos[loc][count] < inf) ans[i] += pos[loc].size() - count - 1;
            }
            if (i + w[i] <= n){
                int loc = i + w[i];
                int count = lower_bound(pos[loc].begin(),pos[loc].end(),i) - pos[loc].begin();
                if (pos[loc][count] > i) count--;
                ans[i] += count;
            }
        }
    }
    inline void case5(){
        for (int i = 1; i <= m; i++)
            pt[ask[i].y]++;
        for (int j = n; j >= 1; j--) 
            pt[fa[dfn[j]][0]] += pt[dfn[j]];
        for (int i = 1; i <= n; i++)
            if (dep[i] == w[i]) ans[i] = pt[i];
    }
    std::vector<int> dfnn[N];
    std::vector<int> ttp[N];
    inline void case6(){
        maxdeep = 0;
        for (int i = 1; i <= n; i++) 
            maxdeep = std::max(maxdeep,dep[i]);
        for (int i = 1; i <= n; i++){
            dfnn[dep[dfn[i]]].push_back(i);
            ttp[dep[dfn[i]]].push_back(0);
        }
        for (int i = 1; i <= m; i++){
            int p = ask[i].x;
            int pos = lower_bound(dfnn[dep[p]].begin(),dfnn[dep[p]].end(),l[p]) - dfnn[dep[p]].begin();
            ttp[dep[p]][pos]++;
        }
        for (int i = 0; i <= maxdeep; i++){
            dfnn[i].push_back(inf);
        }
        for (int i = 0; i <= maxdeep; i++){
            for (int j = 0; j < ttp[i].size(); j++){
                if (j > 0)ttp[i][j] = ttp[i][j - 1] + ttp[i][j];
            }
        }
        for (int i = 1; i <= n; i++){
            if (dep[i] + w[i] > maxdeep) continue;
            int deep = dep[i] + w[i];
            int left = lower_bound(dfnn[deep].begin(),dfnn[deep].end(),l[i]) - dfnn[deep].begin();
            int right = lower_bound(dfnn[deep].begin(),dfnn[deep].end(),r[i]) - dfnn[deep].begin();
            if (dfnn[deep][left] == inf) continue;
            if (dfnn[deep][right] == inf || dfnn[deep][right] > r[i]) right--;
            if (dfnn[deep][left] > r[i] || dfnn[deep][right] < l[i]) continue;
            if (left == 0) ans[i] += ttp[deep][right];
            else ans[i] += ttp[deep][right] - ttp[deep][left - 1];
        }
    }
    void main(){
        cnt = tot = 0;
        std::cin >> n >> m;
        for (int i = 1; i < n; i++){
            int a,b;
            std::cin >> a >> b;
            add(a,b);
            add(b,a);
        }
        memset(dep,-1,sizeof dep);
        dep[1] = 0;
        dfs1(1);
        for (int i = 1; i <= n; i++) std::cin >> w[i];
        for (int i = 1; i <= m; i++){
            std::cin >> ask[i].x >> ask[i].y;
            tlca[i] = lca(ask[i].x,ask[i].y);
        } 
       if (n == 991) case1();
       if (n == 992) case2();
       if (n == 993) case3();
       if (n == 99994) case4();
       if (n == 99995) case5();
       if (n == 99996) case6();
       for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
13天前

Case 1

暴力枚举每条边边权为$0$,每次查询询问中的最长路径取$\min$。

复杂度$O(nm\log\ n)$

Case 2

令最长链最小,其显然具有单调性,考虑二分。

转化为判定问题:

是否存在一种方案,满足所有询问中的链长均不超过$x$。

考虑如何判定:

如果在原树中有若条所询问的链长大于$x$,那么显然我们要令边权为$0$的边一定在这些链的公共边上。

那么我们贪心地令这些链的公共边中边权最大的边边权(记作$w$)为$0$后判一下是否满足所有的链长均小于等于$x$。

显然,原来链长小于等于$x$的依然小于等于$x$,而对于原来链长大于$x$的链而言,如果原来的链长为$L$,那么修改后的链长即$L-w$。

那么,如果$x\ge \max(L-w)$即$x$合法。

复杂度$O((n+m)\log L)$

在处理询问时预处理出所有的$lca$以及$dfn$重编号直接从$n$向前递推子树和减少常数(。

#include <iostream>
#include <cstring>
#include <cstdio>

namespace wxy{
    const int N = 3e5 + 5;
    int head[N],fail[N << 1],edge[N << 1],w[N << 1],tot;
    int dep[N],dis[N],fa[N][35],ds[N],dfn[N],wi[N],tlca[N],p;
    typedef std::pair<int,int> PII;
    #define x first
    #define y second
    PII ask[N];
    int t[N],n,m,cnt;
    inline void add(int x,int y,int we){
        edge[++tot] = y;
        w[tot] = we;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs(int x){
        dfn[++cnt] = x;
        for (int i = 1;i < 20; i++)
            fa[x][i] = fa[fa[x][i-1]][i-1];
        for (int i = head[x];i;i = fail[i]){
            int v = edge[i];
            if (v == fa[x][0]) continue;
            dep[v] = dep[x] + 1;
            dis[v] = dis[x] + w[i];
            wi[v] = w[i];
            fa[v][0] = x;
            dfs(v);
        }
    }
    inline int lca(int x,int y){
        if (dep[x] < dep[y]) std::swap(x,y);
        int d = dep[x] - dep[y];
        for (int j = 0; j < 20; j++)
            if (d >> j & 1) x = fa[x][j];
        if (x == y) return x;
        for (int j = 19; j >= 0; j--){
            if (fa[x][j] != fa[y][j]){
                x = fa[x][j];y = fa[y][j];
            }
        }
        return fa[x][0];
    }
    inline bool check(int x){
        memset(t,0,sizeof t);
        int maxd = 0;
        cnt = 0;
        for (int i = 1; i <= m; i++){
            int a = ask[i].x;
            int b = ask[i].y;
            int lc = tlca[i];
            int dist = dis[a] + dis[b] - (dis[lc] << 1);
            if (dist > x){
                cnt++;t[a]++;t[b]++;
                t[lc] -= 2;
                maxd = std::max(maxd,dist);
            }
        }
        if (cnt == 0) return true;
        for (int i = n; i >= 1; i--)
            t[fa[dfn[i]][0]] += t[dfn[i]];
        for (int i = 1; i <= n; i++)
            if (t[i] == cnt && maxd - wi[i] <= x) return true;
        return false;
    }
    void main(){
        cnt = tot = 0;
        scanf("%d%d",&n,&m);
        for (int i = 1; i < n; i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        memset(dep,-1,sizeof dep);
        dep[1] = 0;
        dfs(1);
        for (int i = 1; i <= m; i++){
            scanf("%d%d",&ask[i].x,&ask[i].y);
            tlca[i] = lca(ask[i].x,ask[i].y);
        } 
        int l = 0,r = 1e9;
        while (l < r){
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d",l);
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
14天前
#include <iostream>

namespace wxy{
    const int N = 5e5 + 5;
    struct node{
        int l,r;
        long long s,add;
    }t[N << 2];
    int a[N],n,m;
    inline void pushup(int u){t[u].s = t[u << 1].s + t[u << 1 | 1].s;}
    inline void pushdown(int u){
        if (t[u].add){
            long long ad = t[u].add;
            t[u << 1].s += ad * (t[u << 1].r - t[u << 1].l + 1);
            t[u << 1 | 1].s += ad * (t[u << 1 | 1].r - t[u << 1 | 1].l + 1);
            t[u << 1].add += ad;
            t[u << 1 | 1].add += ad;
            t[u].add = 0;
        }
    }
    inline void build(int u,int l,int r){
        t[u].l = l;t[u].r = r;t[u].add = 0;
        if (l == r){
            t[u].s = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
    inline void cge(int u,int l,int r,long long x){
        if (t[u].l >= l && t[u].r <= r){
            t[u].s += x * (t[u].r - t[u].l + 1);
            t[u].add += x;
        }else{
            pushdown(u);
            int mid = t[u].l + t[u].r >> 1;
            if (l <= mid) cge(u << 1,l,r,x);
            if (r > mid) cge(u << 1 | 1,l,r,x);
            pushup(u);
        }
    }
    inline long long ask(int u,int l,int r){
        if (t[u].l >= l && t[u].r <= r)return t[u].s;
        pushdown(u);
        int mid = t[u].l + t[u].r >> 1;
        long long res = 0;
        if (l <= mid) res += ask(u << 1,l,r);
        if (r > mid) res += ask(u << 1 | 1,l,r);
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        build(1,1,n);
        while(m--){
            char op[1];
            std::cin >> op[0];
            int a,b;
            long long c;
            std::cin >> a >> b;
            if (op[0] == 'Q') std::cout << ask(1,a,b) << std::endl;
            else{
                std::cin >> c;
                cge(1,a,b,c);
            }
        }
    }
}signed main(){wxy::main();return 0;}



wxy_
15天前
#include <iostream>

namespace wxy{
    const int N = 5e5;
    int n,m,a[N];
    struct node{
        int l,r,v,lv,rv,s;
    }t[N << 2];
    inline void push_up(int u){
        int p = std::max(t[u << 1].v,t[u << 1 | 1].v);
        t[u].v = std::max(p,t[u << 1].rv + t[u << 1 | 1].lv);
        t[u].s = t[u << 1].s + t[u << 1 | 1].s;
        t[u].rv = std::max(t[u << 1 | 1].rv,t[u << 1 | 1].s + t[u << 1].rv);
        t[u].lv = std::max(t[u << 1].lv,t[u << 1].s + t[u << 1 | 1].lv);
    }
    inline void build(int u,int l,int r){
        t[u].l = l;t[u].r = r;
        if (l == r){
            t[u].s = t[u].v = t[u].lv = t[u].rv = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        push_up(u);
    }
    inline void cge(int u,int x,int v){
        if (t[u].l == t[u].r && t[u].l == x){
            t[u].s = t[u].v = t[u].lv = t[u].rv = v;
            return;
        }
        int mid = t[u].l + t[u].r >> 1;
        if (x <= mid) cge(u << 1,x,v);
        if (x > mid) cge(u << 1 | 1,x,v);
        push_up(u);
    }
    inline node ask(int u,int l,int r){
        if (t[u].l >= l && t[u].r <= r) return t[u];
        int mid = t[u].l + t[u].r >> 1;
        node r1,r2,res;
        r1 = {0,0,-11451419,-11451419,-11451419,-11451419};
        r2 = {0,0,-11451419,-11451419,-11451419,-11451419};
        if (l <= mid) r1 = ask(u << 1,l,r);
        if (r > mid) r2 = ask(u << 1 | 1,l,r);
        int p = std::max(r1.v,r2.v);
        res.v = std::max(p,r1.rv + r2.lv);
        res.s = r1.s + r2.s;
        res.rv = std::max(r2.rv,r2.s + r1.rv);
        res.lv = std::max(r1.lv,r1.s + r2.lv);
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        build(1,1,n);
        while (m--){
            int a,b,c;
            std::cin >> a >> b >> c;
            if (a == 1 && b > c) std::swap(b,c);
            if (a == 1) std::cout << ask(1,b,c).v << std::endl;
            else cge(1,b,c);
        }
    }
}signed main(){wxy::main();return 0;}



wxy_
15天前
#include <iostream>

namespace wxy{
    const int N = 5e5;
    int n,m,a[N];
    struct node{
        int l,r,v,lv,rv,s;
    }t[N << 2];
    inline void push_up(int u){
        int p = std::max(t[u << 1].v,t[u << 1 | 1].v);
        t[u].v = std::max(p,t[u << 1].rv + t[u << 1 | 1].lv);
        t[u].s = t[u << 1].s + t[u << 1 | 1].s;
        t[u].rv = std::max(t[u << 1 | 1].rv,t[u << 1 | 1].s + t[u << 1].rv);
        t[u].lv = std::max(t[u << 1].lv,t[u << 1].s + t[u << 1 | 1].lv);
    }
    inline void build(int u,int l,int r){
        t[u].l = l;t[u].r = r;
        if (l == r){
            t[u].s = t[u].v = t[u].lv = t[u].rv = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        push_up(u);
    }
    inline void cge(int u,int x,int v){
        if (t[u].l == t[u].r && t[u].l == x){
            t[u].s = t[u].v = t[u].lv = t[u].rv = v;
            return;
        }
        int mid = t[u].l + t[u].r >> 1;
        if (x <= mid) cge(u << 1,x,v);
        if (x > mid) cge(u << 1 | 1,x,v);
        push_up(u);
    }
    inline node ask(int u,int l,int r){
        if (t[u].l >= l && t[u].r <= r) return t[u];
        int mid = t[u].l + t[u].r >> 1;
        node r1,r2,res;
        r1 = {0,0,-11451419,-11451419,-11451419,-11451419};
        r2 = {0,0,-11451419,-11451419,-11451419,-11451419};
        if (l <= mid) r1 = ask(u << 1,l,r);
        if (r > mid) r2 = ask(u << 1 | 1,l,r);
        int p = std::max(r1.v,r2.v);
        res.v = std::max(p,r1.rv + r2.lv);
        res.s = r1.s + r2.s;
        res.rv = std::max(r2.rv,r2.s + r1.rv);
        res.lv = std::max(r1.lv,r1.s + r2.lv);
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        build(1,1,n);
        while (m--){
            int a,b,c;
            std::cin >> a >> b >> c;
            if (a == 1 && b > c) std::swap(b,c);
            if (a == 1) std::cout << ask(1,b,c).v << std::endl;
            else cge(1,b,c);
        }
    }
}signed main(){wxy::main();return 0;}


活动打卡代码 AcWing 1275. 最大数

wxy_
16天前
#include <iostream>

namespace wxy{
    const int N = 2e5 + 5;
    struct node{
        int l,r,v;
    }t[N << 2];
    int n,m,p,a;
    inline void push_up(int u){
        t[u].v = std::max(t[u << 1].v,t[u << 1 | 1].v);
    }
    inline void build(int u,int l,int r){
        t[u].l = l;t[u].r = r;
        t[u].v = 0;
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
    }
    inline void cge(int u,int x,int v){
        if (t[u].l == t[u].r && t[u].l == x){
            t[u].v = v;
            return;
        }
        int mid = t[u].l + t[u].r >> 1;
        if (x <= mid) cge(u << 1,x,v);
        if (x > mid) cge(u << 1 | 1,x,v);
        push_up(u);
    }
    inline int ask(int u,int l,int r){
        if (t[u].l >= l && t[u].r <= r) return t[u].v;
        int mid = t[u].l + t[u].r >> 1;
        int v = 0;
        if (l <= mid) v = ask(u << 1,l,r);
        if (r > mid) v = std::max(v,ask(u << 1 | 1,l,r));
        return v;
    }
    void main(){
        std::cin >> m >> p;
        n = a = 0;
        build(1,1,m);
        while (m--){
            char op[1];
            int d;
            std::cin >> op;
            std::cin >> d;
            if (op[0] == 'Q'){
                a = ask(1,n - d + 1,n);
                std::cout << a << std::endl;
            }else{
                cge(1,++n,(a + d) % p);
            }
        }
    }
}signed main(){wxy::main();return 0;}



wxy_
16天前

分析

设$f[u][j][0/1][0/1]$为在以$u$为根的子树放置恰好$j$个监听器,且除了点$u$其他点均被覆盖,点$u$是否被覆盖,点$u$是否放监听器的方案数。

首先考虑点$u$未被覆盖

如果点$u$未被覆盖,那么其子节点上一定是不能放监听器的。

接下来按点$u$是否放监听器做分类讨论:

如果节点$u$不放监听器,那么子节点在以其为根的子树内是一定被覆盖的。

那么有转移方程:
$$
f[u][j][0][0]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j}\ \prod_{p\in son(u),a_k=P_{i,k}}f[p][a_k][1][0]
$$

如果点$u$放监听器,那么子节点在以其为根点子树内既可以被覆盖,也可以未被覆盖。

那么有转移方程:
$$
f[u][j][0][1]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j-1}\ \prod_{p\in son(u),a_k=P_{i,k}}f[p][a_k][1][0]+f[p][a_k][0][0]
$$

如果点$u$被覆盖的话,那么对于$u$的子节点而言则需要至少有一个子节点放置监听器。

如果点$u$不放置监听器,那么子节点在以其为根的子树内一定被覆盖过。

对于每个子节点而言,都有放监听器与不放监听器两种决策,在统计完之后减掉所有子节点不放监听器的方案即我们要统计的方案。

那么有转移方程:
$$
\begin{aligned}
f[u][j][1][0]&=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j}\ \prod_{p\in son(u),a_k=P_{i,k}}f[p][a_k][1][0]+f[p][a_k][1][1]-\sum_{P,\forall P_i,\sum_{P_{i,k}}=j}\ \prod_{p\in son(u),a_k=P_{i,k}}f[p][a_k][1][0]\
&
\end{aligned}
$$

$$
f[u][j][1][0]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j}\ \prod_{p\in son(u),a_k=P_{i,k}}(f[p][a_k][1][0]+f[p][a_k][1][1])-f[u][j][0][0]
$$
接下来考虑点$u$放监听器的情况,我们发现其子节点的任一一种状态都可以满足与我们的需求,同理在最后减去所有子节点不放监听器点状态即可。

那么有转移方程:

$$
f[u][j][1][1]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j-1}\ \prod_{p\in son(u),a_k=P_{i,k}}(f[p][a_k][1][0]+f[p][a_k][1][1]+f[p][a_k][0][0]+f[p][a_k][0][1])-f[u][j][0][1]
$$
整理得:
$$
\begin{aligned}
&f[u][j][0][0]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j}\ \prod_{p\in son(u),a_k=P_{i,k}}f[p][a_k][1][0]\
&f[u][j][0][1]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j-1}\ \prod_{p\in son(u),a_k=P_{i,k}}f[p][a_k][1][0]+f[p][a_k][0][0]\
&f[u][j][1][0]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j}\ \prod_{p\in son(u),a_k=P_{i,k}}(f[p][a_k][1][0]+f[p][a_k][1][1])-f[u][j][0][0]\
&f[u][j][1][1]=\sum_{P,\forall P_i,\sum_{P_{i,k}}=j-1}\ \prod_{p\in son(u),a_k=P_{i,k}}(f[p][a_k][1][0]+f[p][a_k][1][1]+f[p][a_k][0][0]+f[p][a_k][0][1])-f[u][j][0][1]
\end{aligned}
$$

代码实现

但是有了上面四个转移方程,我们目前并不能在程序中实现,考虑对上述转移方程做一些变型。

我们考虑一个更一般性的式子
$$
f[t]=\sum_{\sum c_i=t}{\prod_{p\in S}w[p,c_i]}
$$
其唯一的约束为$\sum c_i = t$

类似于分组背包,每次只考虑前$i$组:
$$
f[i][j]=\sum_k f[i-1][j-k]\times w[i][k]
$$

那么这样做的复杂度是多少呢?

显然,其复杂度是$O(nm^2)$的,这样是不足以过掉此题的。

而对于树上背包问题,我们可以通过优化上下限排除无用状态的方式优化到$O(nm)$。(具体证明)

令$cntsize$为当遍历到的子树大小的和(不包括子树$v$),$size[v]$为子树$v$的大小,$size[u]$为子树$u$的大小。

那么$j$的取值范围显然为$0\le j\le \min(cntsize+size[v])$

$k$的取值范围为$\max(j-cntsize,0)\le k\le \min(j,size[v])$

优化后的代码实现(全):

#include <iostream>

namespace wxy{
    typedef long long ll;
    const int N = 1e5 + 5,mod = 1e9 + 7;
    int head[N],fail[N << 1],edge[N << 1],tot;
    unsigned int f[N][105][2][2];
    bool vis[N];
    int n,m,size[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs(int x){
        vis[x] = true;
        size[x] = 1;
        f[x][0][0][0] = f[x][0][0][1] = f[x][0][1][0] = f[x][0][1][1] = 1;
        for (int i = head[x];i;i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            dfs(v);
            int presize = size[x];
            size[x] += size[v];
            for (int j = std::min(size[x],m); j >= 0; j--){
                int p = std::max(0,j - presize - 1);
                if (p == 0){
                    f[x][j][0][0] = (1ll * f[x][j][0][0] * f[v][0][1][0]) % mod;
                    f[x][j][0][1] = (1ll * f[x][j][0][1] * (f[v][0][0][0] + f[v][0][1][0]) % mod) % mod;
                    f[x][j][1][0] = (1ll * f[x][j][1][0] * (f[v][0][1][0] + f[v][0][1][1]) % mod) % mod;
                    f[x][j][1][1] = (1ll * f[x][j][1][1] * (f[v][0][0][0] + f[v][0][0][1] + f[v][0][1][0] + f[v][0][1][1]) % mod) % mod;
                    p++;
                }else{
                    f[x][j][0][0] = f[x][j][0][1] = f[x][j][1][0] = f[x][j][1][1] = 0;
                }
                for (int k = p; k <= std::min(size[v],j); k++){
                    f[x][j][0][0] = (f[x][j][0][0] + (1ll * f[x][j - k][0][0] * (f[v][k][1][0])) % mod) % mod;
                    f[x][j][0][1] = (f[x][j][0][1] + (1ll * f[x][j - k][0][1] * (f[v][k][0][0] + f[v][k][1][0]) % mod) % mod) % mod;
                    f[x][j][1][0] = (f[x][j][1][0] + (1ll * f[x][j - k][1][0] * (f[v][k][1][0] + f[v][k][1][1]) % mod) % mod) % mod;
                    f[x][j][1][1] = (f[x][j][1][1] + (1ll * f[x][j - k][1][1] * (f[v][k][0][0] + f[v][k][0][1] + f[v][k][1][0] + f[v][k][1][1]) % mod) % mod) % mod;
                }
            }
        }
        for (int t = std::min(size[x],m); t > 0; t--){
            f[x][t][0][1] = f[x][t - 1][0][1];
            f[x][t][1][1] = f[x][t - 1][1][1];
        }
        f[x][0][0][1] = f[x][0][1][1] = 0;
        for (int t = 0; t <= std::min(size[x],m); t++){
            f[x][t][1][0] = (f[x][t][1][0] - f[x][t][0][0] + mod) % mod;
            f[x][t][1][1] = (f[x][t][1][1] - f[x][t][0][1] + mod) % mod;
        }
    }
    void main(){
        tot = 0;
        std::cin >> n >> m;
        for (int i = 1; i < n; i++){
            int a,b;
            std::cin >> a >> b;
            add(a,b);
            add(b,a);
        }
        dfs(1);
        std::cout << (f[1][m][1][0] + f[1][m][1][1]) % mod;
    }
}signed main(){wxy::main();return 0;}



wxy_
26天前

题意

给出一个$n$个数构成的序列,$a[1],a[2],a[3]…a[n]$。

给出$m$个需求,对于第$1\le i\le m$个需求$p_i,q_i$,表示如果在序列$a$中,如果存在$a[j],1\le j\le n$在二进制表示下的第$p_i$位为$1$,则需要在集合$S$中添加元素$q_i$。

给定一个$k$,求出从$0-2^k-1$中,除了序列$a$中的数最多可以选多少个数放入序列$a$保证集合$S$内的元素不变。

分析

考虑转化为补集:合法方案 = 总方案 - 不合法方案

考虑如何计算出不合法的方案。

令$f[i]$为二进制构成不超过$i$位的数中,不满足要求的数的个数。

考虑如何划分状态以便转移。

以第$i$是$0$还是$1$分类讨论:

如果第$i$位是$0$,其方案数显然为$f[i-1]$

考虑第$i$位是$1$的情况:

如果第$i$位为$1$要选的元素已经在集合内,那么方案数为$f[i-1]$

如果第$i$位为$1$要选的元素不在集合内,则方案数为$2^i$。

因此可以得到状态转移方程

$$
f[i]=f[i-1]+(f[i-1]/2^i)
$$

此步的复杂度为$O(c)$($c$为$q$的种数)

最后的方案数即$2^k-f[k-1]-n$。

预处理出集合$S$之后跑一遍$DP$即可$AC$本题

代码:

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>

namespace wxy{
        __int128 f[65];
        unsigned long long b[1000005];
        bool vis[100000005];
        bool vs[65];
        std::vector<int> a[65];
        int n,m,c,k;
        typedef std::pair<int,int> PII;
        PII q[1000005];
        void print(__int128 x){
            if(x<0)putchar('-'),x=-x;
            if(x>9)print(x/10);
            putchar(x%10+'0');
        }
        __int128 ppp;
        void init(){
            ppp = 1;
            for (int i = 1; i <= 64; i++) ppp *= 2;
        }
        void main(){
            memset(vis,false,sizeof vis);
            memset(vis,false,sizeof vs);
            memset(f,0,sizeof f);
            std::cin >> n >> m >> c >> k;
            init();
            for (int i = 1; i <= n; i++) scanf("%lu",&b[i]);
            for (int i = 1; i <= m; i++){
                    std::cin >> q[i].first >> q[i].second;
                    a[q[i].first].push_back(q[i].second);
            }
            for (int i = 1; i <= n; i++){
                for (int j = k; j >= 0; j--)
                    if (b[i] >> j & 1) vs[j] = true;
            }
            bool pop[1000005];
            for (int i = 1; i <= m; i++){
                if (vs[q[i].first] && !pop[q[i].first]){
                    for (int j = 0; j < a[q[i].first].size(); j++) vis[a[q[i].first][j]] = true;
                }
                pop[q[i].first] = true;
            }
            for (int i = 0; i <= k; i++){
                if (i != 0) f[i] = f[i - 1];
                bool ck = false;
                for (int j = 0; j < a[i].size(); j++){
                    if (!vis[a[i][j]]){
                        __int128 www;
                        if (i < 64)www = 1ull * 1 << i;
                        else www = ppp;
                        f[i] = f[i] + www;
                        ck = true;
                        break; 
                    }
                } 
                if (!ck && i != 0) f[i] = f[i] + f[i - 1];
            }   
            __int128 a;
            if (k < 64) a = 1ull * 1 << k;
            else a = ppp;
            __int128 pppp = n;
            print(a - f[k - 1] - pppp);
        }
}signed main(){wxy::main();return 0;}