2024.10.23

First Post:

Last Update:

Word Count:
3.3k

Read Time:
17 min

Day -3

最近都不知道写什么题···

啥也不会啥也不想写···

请注意，以下有大量口胡内容。

总结一下最近写的杂题

[湖南集训] Clever Rabbit

首先手玩样例，可以发现答案非常少。

然后打了一个小表，发现答案确实非常少。

因为 ，所以考虑打表。

这里有一个性质：如果两个数字构成的可重集相同，则 值一样。

所以可以直接枚举集合，一共有 个。

然后高精算一下答案，把表打出来即可。

分数统计

无聊题。

询问一前缀和，询问二离线下来回滚莫队，询问三 ST 表。

没删 define int long long 被卡空间，导致没一遍过，气。

[HEOI2014] 大工程

看到保证关键点总数想到虚树。

建完虚树以后就是个简单树形 dp。

询问一就是经典的 。

做法是把贡献拆成每条边的贡献，统计每条边的经过次数。

询问二三就是树上最短路径长和树的直径。

注意虚树上边的边权是什么。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10,inf=1e18;
int n,m,cnt,tim,num,ans,mn,mx,len;
int head[maxn];
int key[maxn],a[maxn<<1];
int f[maxn][3];
bitset<maxn> vis;
vector<int> g[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
struct node{
    int fa,siz,dep,top,hson,dfn;
}t[maxn];
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void dfs1(int u,int fa){
    t[u].fa=fa,t[u].dep=t[fa].dep+1,t[u].siz=1;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v;
    }
}
inline void dfs2(int u,int top){
    t[u].top=top,t[u].dfn=++tim;
    if(!t[u].hson) return;
    dfs2(t[u].hson,top);
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==t[u].fa||v==t[u].hson) continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v){
    while(t[u].top!=t[v].top){
        if(t[t[u].top].dep<t[t[v].top].dep) swap(u,v);
        u=t[t[u].top].fa;
    }
    return t[u].dep<t[v].dep?u:v;
}
inline bool cmp(int x,int y){return t[x].dfn<t[y].dfn;}
inline void build(){
    sort(key+1,key+num+1,cmp);
    len=0;
    for(re int i=1;i<num;++i){
        a[++len]=key[i];
        a[++len]=lca(key[i],key[i+1]);
    }
    a[++len]=key[num];
    a[++len]=1;
    sort(a+1,a+len+1,cmp);
    len=unique(a+1,a+len+1)-(a+1);
    for(re int i=1;i<len;++i){
        int lc=lca(a[i],a[i+1]);
        g[lc].push_back(a[i+1]),g[a[i+1]].push_back(lc);
    }
}
inline void dfs(int u,int fa){
    t[u].siz=vis[u];
    if(vis[u]) f[u][1]=f[u][2]=0;
    else f[u][1]=inf,f[u][2]=-inf;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        int w=t[v].dep-t[u].dep;
        t[u].siz+=t[v].siz;
        ans+=w*t[v].siz*(num-t[v].siz);
        mn=min(mn,f[u][1]+f[v][1]+w),mx=max(mx,f[u][2]+f[v][2]+w);
        f[u][1]=min(f[u][1],f[v][1]+w),f[u][2]=max(f[u][2],f[v][2]+w);
    }
    g[u].clear();
}
inline void solve(){
    build();
    ans=0,mn=inf,mx=-inf;
    dfs(1,0);
    cout<<ans<<" "<<mn<<" "<<mx<<'\n';
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1,u,v;i<n;++i) cin>>u>>v,add(u,v),add(v,u);
    dfs1(1,0),dfs2(1,1);
    cin>>m;
    while(m--){
        cin>>num;
        for(re int i=1;i<=num;++i) cin>>key[i],vis[key[i]]=1;
        solve();
        for(re int i=1;i<=num;++i) vis[key[i]]=0;
    }
    return 0;
}

[SCOI2016] 美味

异或问题基本就三个方向：按位考虑，01trie，线性基。

如果没有这个加 ，那这是可持久化trie模板。

upd：可持久化trie好像也能做？不太会，还是按位考虑好想。

但现在有 ，所以只能按位考虑。

我们从高位到低位贪心。

设前面位累计的答案为 ，然后考虑当前位情况。

设当前考虑到第 位。

若当前位 位为 1，则我们希望 当前位为 0。

那么 。

若当前位 位为 0，则我们希望 当前位为 1。

那么 。

如果这一位能找到合法的 ，那么 就加上 。

但这为什么是对的？为什么不会在低位的区间里找一个合法的 ，但它从未出现在高位的区间里过？

如果你仔细想，你会发现如果高位有一位选到了合法值，那么低位的区间会变小。

也就是说，区间大小是单调不增的。

那么如果你在低位的区间里找到了一个合法值，那么它一定也出现在高位的区间里过。

那么现在问题变为了序列上在 内，值域在 内的信息。

因为要求在线，所以需要主席树上区间二分。

当然树套树也行，但复杂度两个 ，太劣了。

如果题目能离线，那么莫队+值域分块一般也能做。

复杂度 

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10,lgn=30,V=1e5;
int n,m,segcnt;
int rt[maxn];
struct tree{
    int ls,rs,sum;
}tr[maxn*lgn];
inline void up(int p){tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum;}
inline void update(int l,int r,int pos,int &p1,int p2){
    p1=++segcnt;
    tr[p1]=tr[p2];
    if(l==r){++tr[p1].sum;return;}
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,pos,tr[p1].ls,tr[p2].ls);
    else update(mid+1,r,pos,tr[p1].rs,tr[p2].rs);
    up(p1);
}
inline bool query(int l,int r,int L,int R,int p1,int p2){
    if(tr[p1].sum==tr[p2].sum) return 0;
    int mid=(l+r)>>1;
    if(l>=L&&r<=R){
        if(l==r) return 1;
        bool res=query(l,mid,L,R,tr[p1].ls,tr[p2].ls);
        if(res) return 1;
        else return query(mid+1,r,L,R,tr[p1].rs,tr[p2].rs);
    }
    else{
        if(L<=mid){
            bool res=query(l,mid,L,R,tr[p1].ls,tr[p2].ls);
            if(res) return 1;	
        }
        if(R>mid){
            bool res=query(mid+1,r,L,R,tr[p1].rs,tr[p2].rs);
            if(res) return 1;
        }
        return 0;
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif	
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,x;i<=n;++i){
        cin>>x;
        update(0,V,x,rt[i],rt[i-1]);
    }
    for(re int i=1,ans,b,x,l,r;i<=m;++i){
        cin>>b>>x>>l>>r;
        ans=0;
        for(re int j=17,L,R,op;j>=0;--j){
            if((b>>j)&1) L=ans-x,R=ans+(1<<j)-1-x,op=0;
            else L=ans+(1<<j)-x,R=ans+(1<<(j+1))-1-x,op=1;
            if(!query(0,V,max(0ll,L),min(R,V),rt[l-1],rt[r])) op^=1;
            ans+=(op<<j);
        }
        cout<<(ans^b)<<'\n';
    }
    return 0;
}

[SDOI2013] 森林

看到链上 kth 想到主席树，看到动态加边想到 LCT。

但这俩没法同时维护。

所以考虑每个点维护一颗主席树，然后合并时启发式合并。

然后把链上 kth 做一下树上差分，同时查四颗主席树然后合并答案即可。

但有个问题，怎么动态求 lca？

维护 LCT 即可。

当然也可以倍增，在启发式合并时重构倍增数组即可。

动态 lca 模板：DYNALCA - Dynamic LCA

不会写 LCT 了，悲。

[HNOI2015] 接水果

树套树和整体二分我都不会啊？只能写无脑莫队了。

查 kth 直接值域分块。

注意：在一条链的两个点都被加进来时，这条链的权值才能算进来。

没了。

upd1：补题的时候 20 分钟写完，真的很好写啊，吊打同学写的整体二分了，还得调半天。

upd2：唐，这个莫队的复杂度错完了，竟然能让我草过去，大家还是写正解整体二分吧。

upd3：莫队真了。

刚才那个莫队假的原因是一个点上会挂一堆路径，你这一个点遍历多次就死掉了，复杂度变成 。

所以我们把一个点展开成多个点（每挂一条路径就多一个点），这样新序列长度是 的。

然后把询问的区间对应到这个新序列上，再进行莫队，复杂度就真了。

代码以后补。

upd4：莫队又死了。

因为树上莫队需要考虑 ，所以可以构造 被拆成一堆点，那么你每次还是得跑这一堆点，就死了。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=4e4+10,maxm=210;
int n,p,m,cnt,tim,siz,tot;
int a[maxn];
int head[maxn],seq[maxn<<1],ans[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxn],cnt2[maxm];
vector<pii> g[maxn];
bool vis[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
struct node{
    int l,r;
    int fa,siz,top,hson,dep;
}t[maxn];
struct Query{
    int l,r,k,id,lca;
}q[maxn];
inline bool cmp(Query a,Query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void dfs1(int u,int fa){
    t[u].l=++tim;seq[tim]=u;
    t[u].fa=fa,t[u].siz=1,t[u].dep=t[fa].dep+1;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v;
    }
    t[u].r=++tim;seq[tim]=u;
}
inline void dfs2(int u,int top){
    t[u].top=top;
    if(!t[u].hson) return;
    dfs2(t[u].hson,top);
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==t[u].fa||v==t[u].hson) continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v){
    while(t[u].top!=t[v].top){
        if(t[t[u].top].dep<t[t[v].top].dep) swap(u,v);
        u=t[t[u].top].fa;
    }
    return t[u].dep<t[v].dep?u:v;
}
inline void init(){
    siz=sqrt(p);
    tot=p/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=p;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void add(int x){++cnt1[x],++cnt2[bel[x]];}
inline void del(int x){--cnt1[x],--cnt2[bel[x]];}
inline int query(int k){
    for(re int i=1;i<=tot;++i){
        if(k-cnt2[i]<=0){
            for(re int j=st[i];j<=ed[i];++j){
                if(k-cnt1[j]<=0) return a[j];
                k-=cnt1[j];
            }
        }
        k-=cnt2[i];
    }
    return -1;
}
inline void work(int u){
    if(vis[u]){for(auto x:g[u]) if(vis[x.fi]) del(x.se);}
    else{for(auto x:g[u]) if(vis[x.fi]) add(x.se);}
    vis[u]^=1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>p>>m;
    for(re int i=1,u,v;i<n;++i) cin>>u>>v,add(u,v),add(v,u);
    dfs1(1,0),dfs2(1,1);
    for(re int i=1,u,v,w;i<=p;++i) cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w}),a[i]=w;
    sort(a+1,a+p+1);
    p=unique(a+1,a+p+1)-(a+1);
    for(re int u=1;u<=n;++u) for(auto &x:g[u]) x.se=lower_bound(a+1,a+p+1,x.se)-a;
    for(re int i=1,u,v,k,lc;i<=m;++i){
        cin>>u>>v>>k;
        if(t[u].l>t[v].l) swap(u,v);
        lc=lca(u,v);
        if(lc==u) q[i]={t[u].l,t[v].l,k,i,0};
        else q[i]={t[u].r,t[v].l,k,i,lc};
    }
    siz=sqrt(n<<1);
    sort(q+1,q+m+1,cmp);
    init();
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        while(r<q[i].r) work(seq[++r]);
        while(l>q[i].l) work(seq[--l]);
        while(r>q[i].r) work(seq[r--]);
        while(l<q[i].l) work(seq[l++]);
        if(q[i].lca) work(q[i].lca);
        ans[q[i].id]=query(q[i].k);
        if(q[i].lca) work(q[i].lca);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

[SHUPC 2024] 原神，启动！

设 表示第 个被攻击的次数，那么列出方程应该长这样

然后高斯消元解就完事了。

注意是在模意义下解高斯消元，所以除法要注意。

≡