2016 North American Invitational Programming Contest 补题记录（9 / 11）

发表于 更新于 分类于 本文字数： 22k 阅读时长 ≈ 20 分钟

2016 NAIPC 补题记录

B. Alternative Bracket Notation

tag

  • 思维

题意

有点难懂，略。

思路

每对括号对应值的位数不会变化太多，直接暴力循环，遇到需要修改的地方就直接修改，不需要修改了就退出。
复杂度 O(n2)O(n^2) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 21:19:46
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    const int N=1e5+5;
    vector<int> w(N,0);
    for(int i=0;i<=9;i++) w[i]=1;
    for(int i=10;i<N;i++) w[i]=w[i/10]+1;

    string s;
    cin>>s;

    int n=s.size();

    vector<array<int,2>> vec(n+5,{0,0});
    vector<int> sta,lenl(n+5,1),lenr(n+5,1);
    int now=0;
    for(int _=0;_<=4000;_++){
        sta.clear();
        int now=0;
        for(int i=0;i<n;i++){
            if(s[i]=='('){
                now+=lenl[i]+lenr[i]+2;
                vec[i][0]=now;
                sta.push_back(i);
            }
            else{
                int pos=sta.back();
                vec[pos][1]=now;
                sta.pop_back();
            }
        }

        auto check=[&](){
            int now=0;
            int flag=1;
            for(int i=0;i<n;i++) if(s[i]=='('){
                if(w[vec[i][0]]!=lenl[i]||w[vec[i][1]]!=lenr[i]) flag=0;
                lenl[i]=w[vec[i][0]];
                lenr[i]=w[vec[i][1]];
            }
            return flag;
        };

        if(check()) break;
    }

    for(int i=0;i<n;i++) if(s[i]=='(') cout<<vec[i][0]<<","<<vec[i][1]<<":";

    return true&&false;
}

C. Greetings!

tag

  • 状压DP

题意

有 nn 种不同的照片，最多可以使用 kk 种信封来封装，要求使得最后所有信封浪费的总空间最小。
其中 1≤n,k≤151 \leq n, k \leq 15 。

思路

记录 dpk,maskdp_{k,mask} 为用了k种信封，装了种类集合为 maskmask 的照片的最小浪费空间。计算之前先预处理用一个信封装每个集合的花费。
总复杂度 O(k⋅3n)O(k \cdot 3^n) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 19:30:58
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const i64 INF=0x3f3f3f3f3f3f3f3f;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,K;
    cin>>n>>K;

    vector<array<int,3>> a(n,{0,0,0});
    for(auto &[w,h,q]:a) cin>>w>>h>>q;

    vector<i64> sum(1<<n,0);
    for(int mask=1;mask<(1<<n);mask++){
        int maxw=0,maxh=0;
        i64 tot=0,totarea=0;
        for(int i=0;i<n;i++) if((mask>>i)&1){
            auto [w,h,q]=a[i];
            maxw=max(maxw,w);
            maxh=max(maxh,h);
            tot+=q;
            totarea+=1ll*w*h*q;
        }
        sum[mask]=1ll*tot*maxw*maxh-totarea;
    };

    vector<vector<i64>> dp(K+5,vector<i64>(1<<n,INF));
    dp[0][0]=0;
    for(int k=1;k<=K;k++)
        for(int mask=1;mask<(1<<n);mask++)
            for(int s=mask;s;s=(s-1)&mask) dp[k][mask]=min(dp[k][mask],dp[k-1][mask^s]+sum[s]);
    
    i64 ans=INF;
    for(int k=1;k<=K;k++) ans=min(ans,dp[k][(1<<n)-1]);

    cout<<ans;

    return true&&false;
}

D. Programming Team

tag

  • 二分
  • 树DP

题意

给定 n+1n + 1 的节点的树，节点编号为 0−n0 - n ，点带点权 ss 和 pp ，节点 ii 只有当父节点 faifa_i 被选择后才能被选，除 00 节点外选择 kk 个点，最后总价值为 ∑p∑s\frac{\sum p}{\sum s} ，最大化总价值。
其中 1≤k,n≤2500,1≤s,p≤10000,fai<i1 \leq k, n \leq 2500, 1 \leq s, p \leq 10000, fa_i < i 。

思路

经典 0101 分数规划。
二分总价值后转换为树背包，由于 fai<ifa_i < i ，做树 DPDP 可以直接从大到小 forfor 一遍，不用连边 dfsdfs 。
总复杂度 O(n2⋅logn)O(n^2 \cdot logn) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 19:56:52
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const double INF=1e20;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int k,n;
    cin>>k>>n;

    vector<array<int,3>> a(n+5,{0,0,0});
    for(int i=1;i<=n;i++){
        auto &[s,p,fa]=a[i];
        cin>>s>>p>>fa;
    }

    double l=0,r=25000000,ans=0;
    vector<vector<double>> dp(n+5,vector<double>(n+5,-INF));
    for(int i=1;i<=50;i++){
        double mid=(l+r)/2;

        auto check=[&](double mid){
            vector<int> sz(n+5,1);
            for(int i=0;i<=n;i++) dp[i].clear();
            for(int i=0;i<=n;i++){
                dp[i].resize(2);
                auto [s,p,fa]=a[i];
                dp[i][0]=0;
                dp[i][1]=p-mid*s;
            }
            for(int x=n;x>=1;x--){
                auto [s,p,fa]=a[x];
                vector<double> g(sz[fa]+sz[x]+1,-INF);
                g[0]=0;
                for(int i=1;i<=sz[fa];i++)
                    for(int j=0;j<=sz[x];j++)
                        g[i+j]=max(g[i+j],dp[fa][i]+dp[x][j]);
                dp[fa].swap(g);
                sz[fa]+=sz[x];
            }
            return dp[0][k+1]>=0;
        };

        if(check(mid)){
            ans=mid;
            l=mid;
        }
        else r=mid;
    }

    cout<<fixed<<setprecision(3)<<ans;

    return true&&false;
}

E. K-Inversions

tag

  • NTT

题意

给定串 ss ，对 k∈[1,n−1]k \in [1, n - 1] ，求 si=B,sj=A,i−j=ks_i = B, s_j = A, i - j = k 的数对 (i,j)(i, j) 个数。
其中 1≤∣s∣≤1061 \leq |s| \leq 10^6 。

思路

直接 NTTNTT 即可。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 19:13:55
*/
#include<bits/stdc++.h>
using namespace std;

using i64=int;

const int mod=998244353;
const int N=1e6+5;

namespace NTT{
    const int g=3;
    const int p=::mod;
    int wn[35];
    int inv[N];
    int power(int a,int b=p-2){
        int res=1;
        while(b){
            if(b&1) res=1ll*res*a%p;
            a=1ll*a*a%p;
            b>>=1;
        }
        return res;
    }
    int _=[]{
        for(int i=0;i<35;i++) wn[i]=power(g,(p-1)/(1ll<<i));
        inv[0]=inv[1]=1;
        for(int i=2;i<N;i++) inv[i]=(1ll*(p-p/i)*inv[p%i])%p;
        return 0;
    }();
    void ntt(int *a,int len,int flag){
        int i,j=0,t,k,w,id;
        for(i=1;i<len-1;i++){
            for(t=len;j^=t>>=1,~j&t;);
            if(i<j) swap(a[i],a[j]);
        }
        for(i=1,id=1;i<len;i<<=1,id++){
            t=i<<1;
            for(j=0;j<len;j+=t){
                for(k=0,w=1;k<i;k++,w=1ll*w*wn[id]%p){
                    int x=a[j+k],y=1ll*w*a[j+k+i]%p;
                    a[j+k]=(x+y)%p;
                    a[j+k+i]=(x-y+p)%p;
                }
            }
        }
        if(!flag){
            for(i=1,j=len-1;i<j;i++,j--) swap(a[i],a[j]);
            int in=power(len);
            for(i=0;i<len;i++) a[i]=1ll*a[i]*in%p;
        }
    }
    void mul(vector<int> &a,vector<int> &b){
        int l1=a.size(),l2=b.size();
        int len,i;
        for(len=1;len<=l1+l2;len<<=1);
        static int A[N<<3],B[N<<3];
        a.resize(len,0);
        b.resize(len,0);
        for(i=0;i<len;i++) A[i]=a[i];
        for(i=0;i<len;i++) B[i]=b[i];
        ntt(A,len,1);ntt(B,len,1);
        for(i=0;i<len;i++) A[i]=1ll*A[i]*B[i]%p;
        ntt(A,len,0);
        for(i=0;i<len;i++) a[i]=A[i];
        a.resize(l1+l2);
        b.resize(l2,0);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    string s;
    cin>>s;
    
    int n=s.size();

    vector<int> f(n,0),g(n,0);
    for(int i=0;i<n;i++){
        if(s[i]=='A') f[i]=1;
        else g[n-i-1]=1;
    }

    NTT::mul(f,g);

    for(int i=1;i<n;i++) cout<<f[n+i-1]<<"\n";

    return true&&false;
}

F. Mountain Scenes

tag

  • DP

题意

略。

思路

DPDP 后减掉不合法的部分即可。
复杂度 O(n⋅w⋅h)O(n \cdot w \cdot h) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 18:33:43
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int mod=1e9+7;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,w,h;
    cin>>n>>w>>h;

    int ans=0,cnt=0;
    for(int i=0;i<=min(n,h);i++) if(i*w<=n) cnt++;

    vector<vector<int>> dp(w+5,vector<int>(n+5,0));
    dp[0][0]=1;
    for(int i=1;i<=w;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=min(j,h);k++) dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;
    for(int i=0;i<=n;i++) ans=(ans+dp[w][i])%mod;

    cout<<(ans+mod-cnt)%mod;

    return true&&false;
}

G. Symmetry

tag

  • 计算几何

题意

平面上 nn 个点，问最少再加入多少个点能使得平面上的点构成一个轴对称 / 中心对称的样式。
其中 1≤n≤10001 \leq n \leq 1000 。

思路

正解应该是枚举点对找出现次数最多的对称轴 / 对称中心，一个轴 / 中心一定可以对应恰好两个点，所以结果就是总点数减去两倍的出现次数最多的对称轴 / 中心个数。
复杂度 O(n2)O(n^2) 。
场上写的时候胡了一个随机化的写法，不会证正确性，复杂度大概 O(k⋅n2)O(k \cdot n^2) 。

代码

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
/*
    Author: Cupids_Bow
    Time: 2022-10-07 21:55:35
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const double eps=1e-8;
const double inf=1e20;
const double pi=acos(-1.0);
const int maxp=1e3+5;

int sgn(double x){
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}

inline double sqr(double x){return x*x;}

struct Point{
    double x,y;
    Point(double _x=0,double _y=0){
        x=_x;
        y=_y;
    }
    void input(){
        cin>>x>>y;
    }
    void output(){
        cout<<x<<" "<<y<<"\n";
    }
    bool operator == (Point b)const{
        return sgn(x-b.x)==0&&sgn(y-b.y)==0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
    }
    Point operator - (const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator ^ (const Point &b)const{
        return x*b.y-y*b.x;
    }
    double operator * (const Point &b)const{
        return x*b.x+y*b.y;
    }
    double len(){
        return hypot(x,y);
    }
    double len2(){
        return x*x+y*y;
    }
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
    Point operator + (const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator * (const double &k)const{
        return Point(x*k,y*k);
    }
    Point operator / (const double &k)const{
        return Point(x/k,y/k);
    }
    double rad(Point a,Point b){
        Point p=*this;
        return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
    }
    Point trunc(double r){
        double l=len();
        if(!sgn(l)) return *this;
        r/=l;
        return Point(x*r,y*r);
    }
    Point rotleft(){
        return Point(-y,x);
    }
    Point rotright(){
        return Point(y,-x);
    }
    Point rotate(Point p,double angle){
        Point v=(*this)-p;
        double c=cos(angle),s=sin(angle);
        return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }
};
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s=_s;
        e=_e;
    }
    bool operator == (Line v){
        return (s==v.s)&&(e==v.e);
    }
    Line(Point p,double angle){
        s=p;
        if(sgn(angle-pi/2)==0) e=(s+Point(0,1));
        else e=(s+Point(1,tan(angle)));
    }
    Line(double a,double b,double c){
        if(sgn(a)==0){
            s=Point(0,-c/b);
            e=Point(1,-c/b);
        }
        else if(sgn(b)==0){
            s=Point(-c/a,0);
            e=Point(-c/a,1);
        }
        else{
            s=Point(0,-c/b);
            e=Point(1,(-c-a)/b);
        }
    }
    void input(){
        s.input();
        e.input();
    }
    void adjust(){
        if(e<s) swap(s,e);
    }
    double length(){
        return s.distance(e);
    }
    double angle(){
        double k=atan2(e.y-s.y,e.x-s.x);
        if(sgn(k)<0) k+=pi;
        if(sgn(k-pi)==0) k-=pi;
        return k;
    }
    int relation(Point p){
        int c=sgn((p-s)^(e-s));
        if(c<0) return 1;
        else if(c>0) return 2;
        else return 3;
    }
    bool pointonseg(Point p){
        return sgn((p-s)^(e-s))==0&&sgn((p-s)*(p-e))<=0;
    }
    bool parallel(Line v){
        return sgn((e-s)^(v.e-v.s))==0;
    }
    int segcrossseg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2&&(d3^d4)==-2) return 2;
        return (d1==0&&sgn((v.s-s)*(v.s-e))<=0)||
                (d2==0&&sgn((v.e-s)*(v.e-e))<=0)||
                (d3==0&&sgn((s-v.s)*(s-v.e))<=0)||
                (d4==0&&sgn((e-v.s)*(e-v.e))<=0);
    }
    int linecrossseg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        if((d1^d2)==-2) return 2;
        return (d1==0||d2==0);
    }
    int linecrossline(Line v){
        if((*this).parallel(v))
        return v.relation(s)==3;
        return 2;
    }
    Point crosspoint(Line v){
        double a1=(v.e-v.s)^(s-v.s);
        double a2=(v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }
    double dispointtoline(Point p){
        return fabs((p-s)^(e-s))/length();
    }
    double dispointtoseg(Point p){
        if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0)
        return min(p.distance(s),p.distance(e));
        return dispointtoline(p);
    }
    double dissegtoseg(Line v){
        return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
    }
    Point lineprog(Point p){
        return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
    }
    Point symmetrypoint(Point p){
        Point q=lineprog(p);
        return Point(2*q.x-p.x,2*q.y-p.y);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    if(n==1){
        cout<<"0";
        return true&&false;
    }
    
    vector<Point> a(n+5,Point(0,0));
    vector<unordered_map<int,int>> mp(400000+5);
    for(int i=1;i<=n;i++) a[i].input(),mp[a[i].x+200000][a[i].y]++;

    vector<int> p(n,0);
    iota(p.begin(),p.end(),1);

    int ans=n;
    for(int k=1;k<=60;k++){
        random_shuffle(p.begin(),p.end());
        
        auto check=[&](int id1,int id2){
            int res1=0,res2=0,res3=0;
            Point midp=(a[id1]+a[id2])/2;
            Line midl1(midp,a[id2]),midl2(a[id1],a[id2]);
            midl1.e=midl1.e.rotate(midl1.s,pi/2);
            for(int i=1;i<=n;i++){
                Point resp=midl1.symmetrypoint(a[i]);
                if(resp.x!=(int)resp.x||!mp[resp.x+200000].count(resp.y)) res1++;
                resp=midl2.symmetrypoint(a[i]);
                if(resp.x!=(int)resp.x||!mp[resp.x+200000].count(resp.y)) res2++;
                resp=midp*2-a[i];
                if(resp.x!=(int)resp.x||!mp[resp.x+200000].count(resp.y)) res3++;
            }
            return min({res1,res2,res3});
        };

        for(int i=1;i<n;i++) ans=min(ans,check(p[0],p[i]));
    }

    cout<<ans;

    return true&&false;
}

H. Jewel Thief

tag

  • dp
  • 决策单调性优化
  • 分治

题意

nn 个物品，每个物品有有价格 ww 和价值 vv ，分别求背包容量为 i(i∈[1,k])i(i \in [1, k]) 的情况下的最大价值。
其中 1≤n≤106,1≤k≤105,1≤w≤300,1≤v≤1091 \leq n \leq 10^6, 1 \leq k \leq 10^5, 1 \leq w \leq 300, 1 \leq v \leq 10^9 。

思路

注意到价格很小，可以先对每个价格单独做，排序后做前缀和即可。
记录 dpi,jdp_{i,j} 表示用了价格小于等于 ii 的物品，总花费为 jj 的最大价值，可以发现 dpi,jdp_{i,j} 中模 ii 相同的 jj 具有决策单调性，分治 dpdp 即可。
复杂度 O(n+w⋅k⋅logk)O(n + w \cdot k \cdot logk) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-10 10:41:56
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const i64 INF=0x3f3f3f3f3f3f3f3f;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,k;
    cin>>n>>k;

    vector<vector<i64>> g(300+5,vector<i64>(0));
    for(int i=1,w,v;i<=n;i++){
        cin>>w>>v;
        g[w].push_back(v);
    }

    for(int w=1;w<=300;w++){
        sort(g[w].begin(),g[w].end(),greater<i64>());
        for(int i=1;i<g[w].size();i++) g[w][i]+=g[w][i-1];
    }

    vector<vector<i64>> dp(300+5,vector<i64>(k+5,0));
    function<void(int,int,int,int,int,int)> solve=[&](int l,int r,int ql,int qr,int x,int w){
        if(ql>qr) return;
        int mid=ql+qr>>1;
        int pos=mid;
        for(int i=min(mid-1,r);i>=l;i--){
            if(mid-i-1>=g[w].size()) break;
            if(dp[w-1][i*w+x]+g[w][mid-i-1]>dp[w][mid*w+x]){
                dp[w][mid*w+x]=dp[w-1][i*w+x]+g[w][mid-i-1];
                pos=i;
            }
        }
        solve(l,pos,ql,mid-1,x,w);
        solve(pos,r,mid+1,qr,x,w);
    };

    for(int i=1;i<=300;i++){
        for(int j=0;j<i;j++) solve(0,(k-j)/i,0,(k-j)/i,j,i);
        for(int j=0;j<=k;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
    }

    for(int i=1;i<=k;i++) cout<<dp[300][i]<<" ";

    return true&&false;
}

I. Tourists

tag

  • DFS
  • LCA

题意

给定 nn 个节点的树，点编号为 1−n1 - n ，边权均为 11 ，求 ∑x=1n∑x∣ydis(x,y)\sum\limits_{x = 1}^{n} \sum\limits_{x | y} dis(x, y) 。
其中 2≤n≤2⋅1052 \leq n \leq 2 \cdot 10^5 。

思路

枚举 x,yx, y ，需要预处理后 O(1)O(1) 求 lcalca 计算 dis(x,y)dis(x, y) ， stst 表预处理 lcalca 即可。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 18:48:19
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int N=2e5+5;

struct ST{
    int minn[19][N*5];
    int pos[19][N*5];
    int lg[N*5];
    void init(int n,vector<int> &idfn,vector<int> &dep){
        for(int i=1;i<=n;i++){
            minn[0][i]=dep[idfn[i]];
            pos[0][i]=idfn[i];
        }
        for(int j=1;j<19;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                minn[j][i]=min(minn[j-1][i],minn[j-1][i+(1<<(j-1))]);
                if(minn[j][i]==minn[j-1][i]) pos[j][i]=pos[j-1][i];
                else pos[j][i]=pos[j-1][i+(1<<(j-1))];
            }
        }
        lg[0]=-1;
        for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    }
    int get(int l,int r){
        int k=lg[r-l+1];
        int ma=min(minn[k][l],minn[k][r-(1<<k)+1]);
        return (ma==minn[k][l]?pos[k][l]:pos[k][r-(1<<k)+1]);
    }
}st;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    
    vector<vector<int>> e(n+5,vector<int>(0));
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    int dfn0=0;
    vector<int> dep(n+5,0),idfn(n*5+5,0),fi(n+5,0);
    function<void(int,int)> dfs=[&](int x,int fa){
        idfn[++dfn0]=x;
        fi[x]=dfn0;
        for(auto v:e[x]){
            if(v==fa) continue;
            dep[v]=dep[x]+1;
            dfs(v,x);
            idfn[++dfn0]=x;
        }
    };

    dfs(1,1);
    st.init(dfn0,idfn,dep);

    auto get_lca=[&](int x,int y){
        x=fi[x];
        y=fi[y];
        if(x>y) swap(x,y);
        return st.get(x,y);
    };

    auto get_dis=[&](int x,int y){
        int lca=get_lca(x,y);
        return dep[x]+dep[y]-2*dep[lca]+1;
    };

    i64 ans=0;
    for(int x=1;x<=n;x++)
        for(int y=x*2;y<=n;y+=x) ans+=get_dis(x,y);
    
    cout<<ans;

    return true&&false;
}

K. YATP

tag

  • 分治
  • 李超树

题意

给定 nn 个节点的树，点有点权 aa ，边有边权 ww 。
定义一条路径的权值为路径中包含的边的边权和加上路径两个端点的点权乘积，路径可以只包含一个点，权值为对应点权的平方。
对每个点 i∈[1,n]i \in [1, n] ，求其中一端点为 ii 的路径中，权值最小的路径对应的权值。求每个点对应路径权值的和。
其中 1≤n≤2⋅105,1≤ai,wi≤1061 \leq n \leq 2 \cdot 10^5, 1 \leq a_i, w_i \leq 10^6 。

思路

对于点 x,yx, y ，端点为 x,yx, y 的路径的权值为 ax⋅ay+∑i∈Path(x,y)wia_x \cdot a_y + \sum\limits_{i \in Path(x,y)} w_i ，若只考虑以 x 为一端的答案，则权值等价于直线 f(z)=ay⋅z+∑wif(z) = a_y \cdot z + \sum w_i 在 z=axz = a_x 处的取值。则以 xx 为一端的答案即为所有其他点对应直线在 axa_x 处取到的最小值。点对之间贡献可以点 / 边分治处理，计算最小值套李超树。
总复杂度 O(n⋅logn2)O(n \cdot log_n^2) 。

代码

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
/*
    Author: Cupids_Bow
    Time: 2022-12-22 08:13:51
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;
using pii=pair<int,int>;

const i64 INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+5;

vector<int> e[N];
vector<array<int,3>> ed;
int n,edge,m;
int sz[N],mx[N];
i64 dep[N];
int vis[N];
int u[N],v[N],w[N];
int a[N];
i64 ans[N];
struct Line{
    i64 k;
    i64 b;
    Line(){}
    Line(i64 _k,i64 _b){
        k=_k;
        b=_b;
    }
    i64 val(int x){
        return k*x+b;
    }
};
struct Seg_Tree{
    int tot;
    int rt;
    int lc[N<<5];
    int rc[N<<5];
    Line line[N<<5];
    void clear(){
        rt=tot=0;
        lc[0]=rc[0]=0;
        line[0]=Line(0,INF);
    }
    Seg_Tree(){
        clear();
    }
    int addnode(){
        tot++;
        lc[tot]=rc[tot]=0;
        line[tot]=Line(0,INF);
        return tot;
    }
    void insert(int &x,int l,int r,int ql,int qr,Line li){
        if(!x) x=addnode();
        int mid=l+r>>1;
        if(l>=ql&&r<=qr){
            if(li.val(l)<=line[x].val(l)&&li.val(r)<=line[x].val(r)){
                line[x]=li;
                return;
            }
            else if(li.val(l)>line[x].val(l)&&li.val(r)>line[x].val(r)) return;
            else{
                insert(lc[x],l,mid,ql,qr,li);
                insert(rc[x],mid+1,r,ql,qr,li);
            }
            return;
        }
        if(mid>=ql) insert(lc[x],l,mid,ql,qr,li);
        if(mid+1<=qr) insert(rc[x],mid+1,r,ql,qr,li);
    }
    void search(int x,int l,int r,int pos,i64 &res){
        if(!x) return;
        res=min(res,line[x].val(pos));
        if(l==r) return;
        int mid=l+r>>1;
        if(pos<=mid) search(lc[x],l,mid,pos,res);
        else search(rc[x],mid+1,r,pos,res);
    }
}tr;

void get_edge(int x,int tot){
    sz[x]=1;
    mx[x]=0;
    for(auto id:e[x]){
        if(vis[id]) continue;
        vis[id]=1;
        int y=0;
        if(x!=v[id]) y=v[id];
        else y=u[id];
        get_edge(y,tot);
        sz[x]+=sz[y];
        mx[id]=max(tot-sz[y],sz[y]);
        if(edge==0||mx[id]<mx[edge]) edge=id;
        vis[id]=0;
    }
}

void dfs(int x,i64 dis,vector<int> &vec){
    if(x<=m) vec.push_back(x);
    dep[x]=dis;
    for(auto id:e[x]){
        if(vis[id]==1) continue;
        vis[id]=1;
        int y=0;
        if(x!=v[id]) y=v[id];
        else y=u[id];
        dfs(y,dis+w[id],vec);
        vis[id]=0;
    }
}

void solve(int id){
    vector<int> vecu,vecv;
    dfs(u[id],0,vecu);
    dfs(v[id],0,vecv);
    tr.clear();
    for(auto x:vecu) tr.insert(tr.rt,1,N,1,N,Line(a[x],dep[x]));
    for(auto x:vecv){
        i64 res=INF;
        tr.search(tr.rt,1,N,a[x],res);
        ans[x]=min(ans[x],res+dep[x]+w[id]);
    }
    tr.clear();
    for(auto x:vecv) tr.insert(tr.rt,1,N,1,N,Line(a[x],dep[x]));
    for(auto x:vecu){
        i64 res=INF;
        tr.search(tr.rt,1,N,a[x],res);
        ans[x]=min(ans[x],res+dep[x]+w[id]);
    }
}

void divide(int x,int tot){
    if(tot<=1) return;
    edge=0;
    get_edge(x,tot);
    vis[edge]=1;
    solve(edge);
    int nx=u[edge],
        ny=v[edge],
        szx=(sz[u[edge]]>sz[v[edge]]?tot-sz[v[edge]]:sz[u[edge]]),
        szy=(sz[u[edge]]>sz[v[edge]]?sz[v[edge]]:tot-sz[u[edge]]);
    divide(nx,szx);
    divide(ny,szy);
    return;
}

void link(int x,vector<array<int,2>> &vec){
    if(vec.size()==0) return;
    if(vec.size()==1){
        ed.push_back({x,vec[0][0],vec[0][1]});
        return;
    }
    vector<array<int,2>> vec1,vec2;
    for(int i=0;i<vec.size()/2;i++) vec1.push_back(vec[i]);
    for(int i=vec.size()/2;i<vec.size();i++) vec2.push_back(vec[i]);
    m++;
    ed.push_back({x,m,0});
    link(m,vec1);
    m++;
    ed.push_back({x,m,0});
    link(m,vec2);
}

void init(int x,int fa){
    vector<array<int,2>> vec;
    for(auto id:e[x]){
        int y=0;
        if(x!=v[id]) y=v[id];
        else y=u[id];
        if(y==fa) continue;
        init(y,x);
        vec.push_back({y,w[id]});
    }
    link(x,vec);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        cin>>u[i]>>v[i]>>w[i];
        e[u[i]].push_back(i);
        e[v[i]].push_back(i);
    }

    m=n;
    init(1,1);
    for(int i=1;i<=n;i++) e[i].clear();
    swap(n,m);
    for(int i=1;i<=ed.size();i++){
        auto [x,y,z]=ed[i-1];
        u[i]=x;
        v[i]=y;
        w[i]=z;
        e[x].push_back(i);
        e[y].push_back(i);
    }

    for(int i=1;i<=m;i++) ans[i]=1ll*a[i]*a[i];
    divide(1,n);

    i64 sum=0;
    for(int i=1;i<=m;i++) sum+=ans[i];

    cout<<sum;

    return true&&false;
}