Hile_Meow's Blog

20220227周赛

2022-02-28 分类 个人训练 作者 Hile_Meow ~25.72K 字

A 最短路 dp

赛中直接每次询问暴力Dijkstra，$O(qn\log n)$就能过，属于是CF神机太快了。

正解应该是dp，用$f_{c,i,j}$表示经过了$c$条边（$c+1$个点）后，$i$到$j$的最短距离，于是有转移

因此每次可以在$O(nm)$时间内处理出经过$c$个点的最短路，此时再$O(q)$更新所有询问的答案，对于询问$q(u,v,x)$，答案即为$min(f_{c,u,v}+c\times x)$，总复杂度$O(n^2m+nq)$。也就只比暴力快了400ms

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=500+7;
const int Q=1e5+7;
const int MOD=1e9+7;
int qx[Q],qy[Q],qw[Q],ans[Q];
int f[2][N][N];
int main(){
    ios::sync_with_stdio(false);
    int n,m,q,d[N];
    vector<array<int,3>> E;
    cin>>n>>m>>q;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        E.push_back({u,v,w});
    }
    for(int i=1;i<=q;i++){
        cin>>qx[i]>>qy[i]>>qw[i];
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++){
        f[0][i][i]=0;
    }
    memset(ans,0x3f,sizeof ans);
    for(int c=1;c<n;c++){
        memset(f[c&1],0x3f,sizeof f[c&1]);
        for(int i=1;i<=n;i++){
            for(auto e:E){
                f[c&1][i][e[1]]=min(f[c&1][i][e[1]],f[~c&1][i][e[0]]+e[2]);
            }
        }
        for(int i=1;i<=q;i++){
            ans[i]=min(ans[i],f[c&1][qx[i]][qy[i]]+(c+1)*qw[i]);
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[i]>1e9)ans[i]=-1;
        if(qx[i]==qy[i])ans[i]=qw[i];
        cout<<ans[i]<<'\n';
    }
}

B 签到

阅读理解，看懂题目所给公式就会了。

如果要让结果最大，就要选取所有权值为奇数的边，因此答案就是所有奇边权之积，注意没有奇数边权输出$1$。

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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=2e5+7;
const int MOD=1e9+7;
int n,m,a,b,c;
int main(){
    ios::sync_with_stdio(false);
    int T=1;
    // cin>>T;
    while(cin>>n>>m){
        int ans=1;
        for(int i=1;i<=m;i++){
            cin>>a>>b>>c;
            if(a%2){
                ans*=a;
            }
        }
        cout<<ans<<'\n';
    }
}

C kmp

题意即求所有子串的最长公共前后缀长度之和。

由于$length\le5000$，对于所有起始位置跑一遍kmp，得到的next数组（前缀函数）就是最长公共前后缀，求和即可。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=2e5+7;
const int MOD=1e9+7;
string s;
int nx[N];
void getnx(string s){
    for(int i=0;i<s.size();i++)nx[i]=0;
    for(int i=1;i<s.size();i++){
        int j=nx[i-1];
        while(j&&s[i]!=s[j]){
            assert(j!=nx[j-1]);
            j=nx[j-1];
        }
        nx[i]=(s[i]==s[j])?++j:0;
    }
}
void solve(){
    // cin>>s;
    ll ans=0;
    int n=s.size();
    for(int i=0;i<n;i++){
        getnx(s.substr(i));
        for(int j=0;j<n-i;j++){
            ans+=nx[j];
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    int T=1;
    // cin>>T;
    while(cin>>s){
        solve();
    }
}

D 模拟

纯模拟，建议写个函数单独提出x前后的数字，用map记录次数相同的项，求导就是$(ax^b)’=abx^{b-1}$。注意当求导后没有任何项的时候要输出0。

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=2e5+7;
const int MOD=1e9+7;
string s;
int n;
map<ll,ll> mp;//mp[a]=b <=> bx^a
int getPre(int x){
    vector<int> a;
    int sgn=1,val=0;
    for(;x>=0;x--){
        if(isdigit(s[x])){
            a.push_back(s[x]-'0');
        }else if(s[x]=='-'){
            sgn=-1;break;
        }else break;
        s[x]='#';
    }
    if(!a.size())return sgn;
    while(a.size()){
        val=val*10+a.back();
        a.pop_back();
    }
    return val*sgn;
}
int getNxt(int x){
    int sgn=1,cnt=0,val=0;
    if(s[x]=='-')sgn=-1,x++;
    for(;x<n;x++){
        if(isdigit(s[x])){
            val=val*10+s[x]-'0';
        }else break;
        s[x]='#';
    }
    return val*sgn;
}
string out(ll a,ll b){
    string s;
    if(a>0)s+="+";
    else s+="-";
    s+=to_string(abs(a));
    if(b){
        s+="x";
        if(b!=1){
            s+="^";
            s+=to_string(b);
        }
    }
    return s;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++){
        if(s[i]=='x'){
            int a=1,b=1;
            if(i){
                a=getPre(i-1);
            }
            if(i+1<n&&s[i+1]=='^'){
                s[i+1]='#';
                b=getNxt(i+2);
            }
            s[i]='#';
            mp[b]+=a;
            // dbg(a,b);
        }
    }
    // dbg(s);
    map<ll,ll> mp2;
    for(auto i:mp){
        if(i.sc){
            mp2[i.fs-1]+=i.fs*i.sc;
            if(mp2[i.fs-1]==0){
                mp2.erase(i.fs-1);
            }
        }
    }
    mp=mp2;
    // for(auto i:mp){
    //     dbg(i.fs,i.sc);
    // }
    if(!mp.size())cout<<0;
    int f=0;
    for(auto it:mp){
        ll a=it.sc;
        ll b=it.fs;
        string s=out(a,b);
        if(!f&&s[0]=='+'){
            s.erase(s.begin());
        }
        f=1;
        cout<<s;
    }
}

E 构造

原问题等价于给树上的每条边确定一个方向使得有最多的边满足入度=出度（称其为平衡），其拓扑序即为答案。

首先如果一个点的度为奇数显然不可能平衡，那么我们只需要考虑使度数为偶的点平衡。

先只考虑所有度数为偶数的点组成的图$G’$，一个显然的结论是，只要这张图所有点的入/出度都不大于其度数的一半，则所有点一定能被平衡（用度数为奇数的点调整），所以怎么舒服怎么写就可以了。

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=5e5+7;
const int MOD=1e9+7;
int n,l[N],r[N],d[N],c[N],vis[N];
vector<int> G[N],R[N],res;
void dfs(int u){
    vis[u]=1;
    for(auto v:G[u]){
        if(vis[v]||d[v]%2)continue;
        if(l[u]<d[u]/2){
            R[u].push_back(v);
            l[u]++,r[v]++,c[v]++;
        }else{
            R[v].push_back(u);
            r[u]++,l[v]++,c[u]++;
        }
        dfs(v);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;u++,v++;
        G[u].push_back(v);
        G[v].push_back(u);
        d[u]++,d[v]++;
    }
    for(int i=1;i<=n;i++){
        if(d[i]%2)d[i]=MOD;
    }
    for(int i=1;i<=n;i++){
        if(d[i]%2||vis[i])continue;
        dfs(i);
    }
    for(int i=1;i<=n;i++){
        if(d[i]%2){
            for(auto j:G[i]){
                if(d[j]%2==0){
                    if(r[j]<d[j]/2){
                        r[j]++,c[j]++;
                        R[i].push_back(j);
                    }else{
                        l[j]++,c[i]++;
                        R[j].push_back(i);
                    }
                }
            }
        }
    }
    queue<int> q;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!c[i]){
            q.push(i);
        }
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        cnt++;
        cout<<t-1;
        if(cnt<n)cout<<' ';
        for(auto i:R[t]){
            c[i]--;
            if(!c[i]){
                q.push(i);
            }
        }
    }
}

F adhoc

考虑把原来的操作2转化一下。可以发现，操作2等价于把矩阵的最后一列往下，然后整列插到第一列前面。

因此我们可以记录一下哪里是当前矩阵的最后一列，每次操作2不做实质上的移动，只维护最后一列的位置，然后$O(n)$将最后一列往下移动。注意此时操作1也要根据最后一列的位置调整修改的坐标。

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=5000+7;
const int MOD=1e9+7;
int n,q,a[N][N],ans,X[N],Y[N];
void del(int x,int y){
    if(a[x][y]){
        if(X[x]==n)ans--;
        if(Y[y]==n)ans--;
        X[x]--,Y[y]--;
    }
    a[x][y]=0;
}
void add(int x,int y,int b){
    a[x][y]=b;
    if(b){
        X[x]++,Y[y]++;
        if(X[x]==n)ans++;
        if(Y[y]==n)ans++;
    }
}
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=1;j<=n;j++){
            a[i][j]=s[j-1]=='1';
            X[i]+=a[i][j];
            Y[j]+=a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        if(X[i]==n)ans++;
        if(Y[i]==n)ans++;
    }
    int R=n;
    while(q--){
        int op,x,y,b;
        cin>>op;
        if(op==1){
            cin>>x>>y>>b;
            y=R+y;
            if(y>n)y-=n;
            del(x,y);
            add(x,y,b);
        }else{
            cin>>b;
            for(int i=n;i>=2;i--){
                del(i,R);
                add(i,R,a[i-1][R]);
            }
            del(1,R);
            add(1,R,b);
            R--;
            if(!R)R=n;
        }
        cout<<ans<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(false);
    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }
}

G 重链剖分 线段树

一道比较直球的数据结构题，给一棵带点权的树，需要支持：

  1. 询问任意两点路径上的权值和
  2. 对任意子树增加一个关于深度的等差数列

涉及动态子树加+维护树上路径和，显然得套个重链剖分，假设我们能用线段树维护每条链的结果，这样1就解决了。

考虑2操作在一条链上如何维护，即如何在数组上实现区间加等差数列+询问区间和。可以发现等差数列是可以合并的，我们可以将加在$i\in[l,r]$上的等差数列$s+(i-l)\times d$移动一下，转化为$(s-l\times d)+(i\times d)$，如此我们就能把整个数组分成两部分信息维护（设其为$a$和$b$）并且预处理出线段树上每个区间的$\sum i$，每次区间加操作时，对于当前节点就有$a+=(s-l\times d),\ b+=(\sum i)\times d$。

转换到树上，就相当于把上面的$i$全都改成$i$节点的深度。dfs序建线段树然后维护等差数列拆出来的两部分，每次询问$(u,v)$再拆成$query(v)+query(u)-2\times query(lca(u,v))+w_{lca(u,v)}$，$query(u)$表示从$u$到根的路径和，处理时直接暴力往根跳最多$\log$条链到根，每次在线段树上询问一段连续dfs序的和。总复杂度$O(n\log^2 n)$。

会爆ll，要用__int128

写起来真的恶心 都算得上是大模拟了

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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef __int128 ll;
const int N=3e5+7;
const int MOD=1e9+7;
namespace HLD{
    int n,dep[N],fa[N],sz[N],son[N],top[N],id[N],rev[N],tot;
    vector<int> G[N];
    void dfs1(int u){
        sz[u]=1;
        dep[u]=dep[fa[u]]+1;
        for(auto v:G[u]){
            if(v==fa[u])continue;
            fa[v]=u;
            dfs1(v);
            sz[u]+=sz[v];
            if(sz[son[u]]<sz[v])son[u]=v;
        }
    }
    void dfs2(int u,int tp){
        id[u]=++tot;
        rev[tot]=u;
        top[u]=tp;
        if(son[u])dfs2(son[u],tp);
        for(auto v:G[u]){
            if(v==fa[u]||v==son[u])continue;
            dfs2(v,v);
        }
    }
    int LCA(int u,int v){
        int tu=top[u],tv=top[v];
        while(tu!=tv){
            if(dep[tu]<dep[tv])v=fa[tv],tv=top[v];
            else u=fa[tu],tu=top[u];
        }
        if(dep[u]<dep[v])return u;
        return v;
    }
};
using namespace HLD;
struct SegmentTree{
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    ll a[N<<2],b[N<<2],aa[N<<2],bb[N<<2],s[N<<2];
    void pushup(int o){
        a[o]=a[o<<1]+a[o<<1|1];
        b[o]=b[o<<1]+b[o<<1|1];
    }
    void build(int o,int l,int r){
        aa[o]=bb[o]=0;
        if(l==r){
            a[o]=0,b[o]=0,s[o]=dep[rev[l]];
            return;
        }
        int mid=l+r>>1;
        build(lson);
        build(rson);
        s[o]=s[o<<1]+s[o<<1|1];
        pushup(o);
    }
    void pd(int o,int l,int r,ll A,ll B){
        a[o]+=A*(r-l+1);
        b[o]+=B*s[o];
        aa[o]+=A;
        bb[o]+=B;
    }
    void pushdown(int o,int l,int r){
        int mid=l+r>>1;
        pd(lson,aa[o],bb[o]);
        pd(rson,aa[o],bb[o]);
        aa[o]=bb[o]=0;
    }
    void update(int o,int l,int r,int L,int R,ll A,ll B){
        if(L<=l&&r<=R){
            pd(o,l,r,A,B);
            return;
        }
        pushdown(o,l,r);
        int mid=l+r>>1;
        if(L<=mid)update(lson,L,R,A,B);
        if(R>mid)update(rson,L,R,A,B);
        pushup(o);
    }
    ll query(int o,int l,int r,int L,int R,ll res=0){
        if(L<=l&&r<=R)return a[o]+b[o];
        pushdown(o,l,r);
        int mid=l+r>>1;
        if(L<=mid)res+=query(lson,L,R);
        if(R>mid)res+=query(rson,L,R);
        // dbg(l,r,res);
        return res;
    }
}T;
void update(int u,ll v,ll k){
    // dbg(v,k);
    T.update(1,1,n,id[u],id[u]+sz[u]-1,v,k);
}
ll calc(int u){
    ll res=0;
    while(u){
        res+=T.query(1,1,n,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    return res;
}
ll query(int u,int v){
    int lca=LCA(u,v);
    return calc(u)+calc(v)-calc(lca)*2+T.query(1,1,n,id[lca],id[lca]);
}
string prt(ll x){
    string ss;
    do{
        ss.push_back(x%10+'0');
        x/=10;
    }while(x);
    reverse(all(ss));
    return ss;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1);
    dfs2(1,1);
    T.build(1,1,n);
    // for(int i=1;i<=n;i++){
    //     cout<<id[i]<<" \n"[i==n];
    // }
    int q;
    cin>>q;
    while(q--){
        int op,u,v,k;
        cin>>op;
        if(op){
            cin>>u>>v>>k;
            update(u,ll(v)-ll(dep[u])*k,k);
        }else{
            cin>>u>>v;
            cout<<prt(query(u,v))<<"\n";
        }
        // for(int i=1;i<=n;i++){
        //     dbg(i,T.query(1,1,n,i,i));
        // }
    }
}

H 数学

由于数据范围较小，可以直接模拟，从头开始到$t$时刻每次找到$C$和$A,B$相交的时间，注意处理$B$恰好到达$d$而第三个人从$A$前往$B$处的情况（因为这个到结束都没改出来）。本题不卡精度，很良心。

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=2e5+7;
const int MOD=1e9+7;
typedef double ld;
const ld EPS=1e-7;
int sgn(ld x){
    if(x<-EPS)return -1;
    return x>EPS;
}
ld solve(){
    ld d,v1,v2,v3,t;
    scanf("%lf%lf%lf%lf%lf",&d,&v1,&v2,&v3,&t);
    if(sgn(v1*t-d)>=0)return d;
    else{
        ld p1=0,p2=1,p3=0,tt=0;
        int f=0;
        while(sgn(t)>0){
            do{//p1->p2
                ld dlt=(p2-p1)/(v3-v2);
                if(sgn((tt+dlt)*v2+1-d)>=0){
                    p2=d;
                    dlt=(p2-p1)/v3;
                }
                dlt=min(t,dlt);
                t-=dlt;
                tt+=dlt;
                p1+=dlt*v1;
                p2=min(d,p2+dlt*v2);
                p3+=dlt*v3;
            }while(0);
            do{//p2->p1
                ld dlt=(p2-p1)/(v1+v3);
                dlt=min(t,dlt);
                t-=dlt;
                tt+=dlt;
                p1+=dlt*v1;
                p2=min(d,p2+dlt*v2);
                p3-=dlt*v3;
            }while(0);
        }
        return p3;
    }
}
int main(){
    printf("%.10lf",solve());
}

I 网络流

Code
1

J 计算几何

牛逼防AK计算几何，扔了。

K 树状数组

题意就是求对于所有红点求出其到最近的蓝点的曼哈顿距离之和。

考虑两点曼哈顿距离的公式$|x_1-x_2|+|y_1+y_2|$，实际上拆开绝对值符号一共有四种情况，以$x_1-x_2+y_1-y_2$为例：

我们先按照$x$坐标排序，枚举$x_1$同时用树状数组维护下标为$y_2$时的贡献（$-y_2-x_2$），因为是按$x$升序排序，可以保证$x_1\le x_2$，在树状数组上查询所有不大于$y_1$的点中的最小值更新答案即可。对于其他拆绝对值的方式，实际上可以将所有点绕原点旋转90度然后复用上面的方法。

（拆绝对值的四种情况对应到图象上就是$2$相对$1$的四个象限）

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=4e5+7;
const int MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3f;
ll ans[N];
struct node{
    int x,y,id,t;
    void rot(){
        y=-y;
        swap(x,y);
    }
    bool operator < (const node &t){
        if(x==t.x)return y<t.y;
        return x<t.x;
    }
}p[N];
struct BIT{
    ll n,c[N];
    void init(int _){n=_;for(int i=1;i<=n;i++)c[i]=LINF;}
    void add(int x,ll y){for(;x<=n;x+=x&-x)c[x]=min(c[x],y);}
    ll ask(int x,ll res=LINF){for(;x;x-=x&-x)res=min(res,c[x]);return res;}
}T;
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n+m;i++){
        ans[i]=LINF;
        cin>>p[i].x>>p[i].y;
        p[i].id=i;
    }
    for(int c=0;c<4;c++){
        int cnt=0;
        T.init(n+m);
        for(int i=1;i<=n+m;i++){
            swap(p[i].x,p[i].y);
        }
        sort(p+1,p+1+n+m);
        for(int i=1;i<=n+m;i++){
            swap(p[i].x,p[i].y);
            p[i].t=++cnt;
        }
        sort(p+1,p+1+n+m);
        for(int i=1;i<=n+m;i++){
            if(p[i].id>n){
                T.add(p[i].t,-p[i].x-p[i].y);
            }else{
                ans[p[i].id]=min(ans[p[i].id],p[i].x+p[i].y+T.ask(p[i].t));
            }
        }
        for(int i=1;i<=n+m;i++){
            p[i].rot();
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=ans[i];
    }
    cout<<res<<'\n';
}

L dp

注意到我们每次操作选取的点集可以为空，因此只要用最少的代价将这棵树调整为堆即可。

如果每次操作可以加上任意的正值，我们就可以从根dfs，每次如果当前节点小于其子树中的最大值，就要将其调整到这个值，设其差为$\Delta$。

考虑到每次加的值$x_i$是给定的，所以在调整子树的时候要用所给$x_i$组成尽可能小的合法值（即不小于$\Delta$的最小值），这就是经典背包问题了，$f_i=1/0 $表示用所给$x_i$能/否恰好组成$i$，扔到$set$里每次加的时候二分。

由于$\sum x_i\le10^6,q\le10^3$，需要跑$10^9$次，因此考虑经典$bitset$优化01背包，时间复杂度$O(\frac{10^{9}}{\omega}+n)$。

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=1e6+7;
const int MOD=1e9+7;
int n,q,a[N],b[N];
bitset<1000001> f;
vector<int> G[N];
ll ans;
set<int> se;
void dfs(int u,int fa=0){
    b[u]=a[u];
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
        b[u]=max(b[u],b[v]);
    }
    if(*se.rbegin()<b[u]-a[u]){
        cout<<-1;
        exit(0);
    }
    int k=*se.lower_bound(b[u]-a[u]);
    b[u]=a[u]+k;
    ans+=b[u];
}
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    f[0]=1;
    for(int i=1,x;i<=q;i++){
        cin>>x;
        f|=(f<<x);
    }
    for(int i=0;i<=1e6;i++){
        if(f[i]==1){
            se.insert(i);
        }
    }
    dfs(1);
    cout<<ans;
}
int main(){
    ios::sync_with_stdio(false);
    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }
}

M 贪心

问题转化成往图中加边$e(i,b_i)$使得整张图是个长为$n$的环且数组$b$和$a$最接近（要在和$a$的$LCP$尽量大的前提下字典序最小）。

由于要和$a$尽可能相似，我们就从头开始令$b_i=a_i$，同时将$e(i,a_i)$插入原图，用并查集维护连通性。当遇到加入$a_x$时和之前的成小于$n$的环或者$a_x$在以前出现过时，停止插入$a$序列。此时维护图中所有点数大于$1$的链，从小到大遍历$[x,n]$，每次贪心的将$i$连向最小的可以连的链尾（即为$b_i$），同时更新链尾，直到所有数都在一个长为$n$的环上。时间复杂度$O(n\log n)$。

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
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
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define all(x) (x).begin(),x.end()
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}
typedef long long ll;
const int N=5e5+7;
const int MOD=1e9+7;
int fa[N];
void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}
int n,l[N],r[N],a[N];
set<int> ss;
vector<int> ve;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    init(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(ss.count(a[i])||find(a[i])==find(i)&&ve.size()!=n-1){
            set<int> se;
            for(int j=1;j<=n;j++){
                if(!r[j]){
                    se.insert(j);
                }
            }
            for(int j=i;j<=n;j++){
                int x=*se.begin();
                if(se.size()>1&&find(j)==find(x)){
                    x=*++se.begin();
                }
                se.erase(x);
                if(!r[j])se.insert(j);
                ve.push_back(x);
                r[x]=j;
                merge(x,j);
            }
            break;
        }else{
            merge(a[i],i);
            r[a[i]]=i;
            ve.push_back(a[i]);
        }
        ss.insert(a[i]);
    }
    for(auto i:ve){
        cout<<i<<" \n"[i==ve.back()];
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2022-03-08