2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest 补题记录（10 / 11）

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

2015-2016 ptz Moscow 补题记录

懒得写了就随便记一下

A. ABBA

tag

  • 高斯消元

题意

太复杂了，略。

思路

本质上是求秩的大小，高斯消元即可。
复杂度 O(n3)O(n^3) 。

代码

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

using i64=long long;

const int mod=998244353;
const int N=2e2+5;

i64 power(i64 a,i64 b=mod-2){
    i64 res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int n,m;
struct Matrix{
    i64 val[N][N];
    int gauss_jordan(){
        for(int i=1;i<=n;++i){
            int r=i;
            for(int j=i+1;j<=n;++j) if(abs(val[r][i])<abs(val[j][i])) r=j;
            if(r!=i) for(int j=1;j<=m;++j) swap(val[i][j],val[r][j]);
            if(!val[i][i]) return i-1;
            for(int j=1;j<=n;++j) if(j!=i){
                i64 tmp=val[j][i]*power(val[i][i])%mod;
                for(int k=i+1;k<=m;++k){
                    val[j][k]+=(mod-val[i][k]*tmp%mod)%mod;
                    val[j][k]%=mod;
                }
            }
        }
        for(int i=1;i<=n;i++){
            i64 in=power(val[i][i]);
            for(int j=n+1;j<=m;j++) val[i][j]=val[i][j]*in%mod;
        }
        return n;
    }
}mat;

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

    cin>>n>>m;

    if(n<=m){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) cin>>mat.val[i][j];
    }
    else{
        swap(n,m);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++) cin>>mat.val[j][i];
    }

    cout<<mat.gauss_jordan();

    return true&&false;
}

C. Mr. Credo

tag

  • 计算几何
  • 差分

题意

给定 nn 个光源的坐标 x,yx, y 与照射角度范围，保证所有角度加起来小于 2⋅π2 \cdot \pi ，找一个半径为 11 的圆使得不被照到。
其中 1≤n≤2⋅105,−50≤xi,yi≤501 \leq n \leq 2 \cdot 10^5, -50 \leq x_i, y_i \leq 50 。

思路

构造的圆心坐标范围可以达到 [−109,109][-10^9, 10^9] ，光源的坐标范围为 [−50,50][-50, 50] 相差很大，可以认为所有光源均在原点，找一个没有被照射的角度将圆取在尽可能远的位置即可。
复杂度 O(n)O(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
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
/*
    Author: Cupids_Bow
    Time: 2022-10-03 14:16:15
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const long double pi=acos(-1.0);

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

    int n;
    cin>>n;
    
    vector<int> f(1296000,0);
    for(int i=1,x,y,l,r;i<=n;i++){
        cin>>x>>y>>r>>l;
        r+=l-1;
        r%=1296000;
        if(l<=r){
            f[l]++;
            if(r+1<1296000) f[r+1]--;
        }
        else{
            f[l]++;
            f[0]++;
            if(r+1<1296000) f[r+1]--;
        }
    }
    for(int i=1;i<1296000;i++) f[i]+=f[i-1];

    vector<array<int,2>> vec;
    for(int i=0;i<1296000;){
        if(f[i]==0){
            int j=i;
            while(j+1<1296000&&f[j+1]==0) j++;
            vec.push_back({i,j});
            i=j+1;
        }
        else i++;
    }
    if(f[0]==0&&f[1269000-1]==0){
        vec[0][0]=vec.back()[0];
        vec.pop_back();
    }

    int len=-1;
    long double ang=0;
    for(auto [l,r]:vec){
        int newlen=0;
        if(l<=r) newlen=r-l+1;
        else{
            l-=1296000;
            newlen=r-l+1;
            l+=1296000;
        }
        if(newlen>len){
            len=newlen;
            if(l<=r) ang=pi*2.0*((1.0*l+r+1)/2.0)/1296000.0;
            else{
                l-=1296000;
                ang=pi*2.0*((1.0*l+r+1)/2.0)/1296000.0;
            }
        }
    }

    cout<<"YES\n"<<(int)(cos(ang)*1e9)<<" "<<(int)(sin(ang)*1e9);

    return true&&false;
}

D. Deep Purple

tag

  • 后缀自动机
  • 树链剖分
  • 线段树

题意

给定长为 nn 的小写字母串 ss ， qq 次询问，每次询问区间 [l,r][l, r] 的最长 borderborder 。
其中 1≤n,q≤2⋅105,1≤li,ri≤n1 \leq n, q \leq 2 \cdot 10^5, 1 \leq l_i, r_i \leq n 。

思路

考虑单次询问，即求最大的 ii 满足 lcs(i,r)>i−llcs(i, r) > i - l ，对 ss 建出 SAMSAM ，记 posxpos_x 为 endpos=xendpos = x 的节点在后缀树上的编号， ii 的条件即为存在节点 xx 满足：

  • xx 为 posrpos_r 的祖先节点
  • xx 的子树中存在节点 ii 使得 len(x)+l>endposilen(x) + l > endpos_i

求出满足条件的最大的 ii ，若 i≥li \geq l ，询问答案即为 i−l+1i - l + 1 。
对于单次询问，可以先将后缀树上 posrpos_r 到根的路径上每个节点加上权值 len(x)+llen(x) + l ，再从大到小枚举 ii ，找到第一个 ii 满足： ii 到根的路径上存在节点的标记值大于 ii 。用 ii 更新答案即可。
对于多次询问，可以将询问离线下来处理，从大到小枚举 ii ，遇到询问右端点 rr 就将 posrpos_r 到根这段路径打上权值 len(x)+llen(x) + l ，再查询 ii 能更新的询问，更新完成或者不能再被更新后就把对应询问打上的标记删去。感觉这部分将询问一起处理有点类似整体二分的过程。
现在需要能够加 / 删标记与查询标记最大值，可以树剖 + 线段树维护。
对于 posrpos_r 到根的这段路径，将它拆成 loglog 条重链，分两颗线段树 tr0,tr1tr0, tr1 来维护， tr0tr0 维护加上的 ll 的最大值， tr1tr1 维护 len(x)+llen(x) + l 的最大值，加 / 删标记时对于每条重链只将 ll 加 / 删在链尾并在线段树上修改对应节点的值（树上每个节点维护一个 setset 记录加 / 删在当前节点的权值，线段树只负责维护一个区间 maxmax ）。
查询时对每条重链分为两部分，一部分为 tr1tr1 直接查询的区间的值，另一部分为最深的节点的 lenlen 加上 tr0tr0 查询的整条链的值，因为 len(x)len(x) 随着 xx 的深度增加而单调增，所以查询结果一定在其中一个中。
复杂度 O(n⋅log2n)O(n \cdot log^2n) 。

代码

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

using i64=long long;

const int N=2e5+5;
const int M=26;

struct Seg_Tree{
    int l[N<<3];
    int r[N<<3];
    array<int,2> maxn[N<<3];
    void pushup(int x){
        maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
    }
    void build(int x,int L,int R){
        l[x]=L;
        r[x]=R;
        maxn[x]={0,0};
        if(L==R) return;
        int mid=L+R>>1;
        build(x<<1,L,mid);
        build(x<<1|1,mid+1,R);
        return;
    }
    void change(int x,int pos,array<int,2> val){
        if(l[x]==r[x]){
            maxn[x]=val;
            return;
        }
        if(pos<=r[x<<1]) change(x<<1,pos,val);
        else change(x<<1|1,pos,val);
        pushup(x);
        return;
    }
    array<int,2> search(int x,int ql,int qr){
        if(l[x]>=ql&&r[x]<=qr) return maxn[x];
        array<int,2> res={0,0};
        if(r[x<<1]>=ql) res=max(res,search(x<<1,ql,qr));
        if(l[x<<1|1]<=qr) res=max(res,search(x<<1|1,ql,qr));
        return res;
    }
}tr0,tr1;
struct SAM{
    int tot;
    int nex[N*2][M];
    int len[N*2];
    int link[N*2];
    int pos[N];
    int lst;
    void clear(){
        tot=0;
        len[0]=lst=0;
        link[0]=-1;
        memset(nex[0],0,sizeof(nex[0]));
    }
    SAM(){
        clear();
    }
    int addnode(){
        tot++;
        len[tot]=0;
        link[tot]=-1;
        memset(nex[tot],0,sizeof(nex[tot]));
        return tot;
    }
    void cpy(int x,int y){
        for(int i=0;i<M;i++) nex[x][i]=nex[y][i];
        len[x]=len[y];
        link[x]=link[y];
    }
    void extend(char c,int ind){
        int w=c-'a';
        int u=addnode();
        len[u]=len[lst]+1;
        int p=lst;
        while(p!=-1&&!nex[p][w]){
            nex[p][w]=u;
            p=link[p];
        }
        if(p==-1) link[u]=0;
        else{
            int q=nex[p][w];
            if(len[p]+1==len[q]) link[u]=q;
            else{
                int clone=addnode();
                cpy(clone,q);
                len[clone]=len[p]+1;
                while(p!=-1&&nex[p][w]==q){
                    nex[p][w]=clone;
                    p=link[p];
                }
                link[q]=link[u]=clone;
            }
        }
        lst=u;
        pos[ind]=lst;
    }
}sam;
namespace TCD{
    const int N=::N;
    vector<int> e[N*2];
    int rt,dfn0;
    int sz[N*2],fa[N*2];
    int dfn[N*2],son[N*2],top[N*2],tail[N*2];
    set<array<int,2>> st[N*2];
    void init(int n,int _rt){
        rt=_rt;
        dfn0=0;
        for(int i=0;i<=n;i++){
            sz[i]=1;
            fa[i]=dfn[i]=top[i]=tail[i]=0;
            son[i]=-1;
            e[i].clear();
        }
    }
    void add(int x,int y){
        e[x].push_back(y);
    }
    void getson(int x,int f){
        fa[x]=f;
        for(auto v:e[x]){
            if(v==f) continue;
            getson(v,x);
            sz[x]+=sz[v];
            if(son[x]==-1||sz[v]>sz[son[x]]) son[x]=v;
        }
    }
    void dfs(int x,int f,int tp){
        dfn[x]=++dfn0;
        top[x]=tp;
        tail[tp]=max(tail[tp],dfn[x]);
        if(son[x]!=-1) dfs(son[x],x,tp);
        for(auto v:e[x]){
            if(v==f||v==son[x]) continue;
            dfs(v,x,v);
        }
    }
    void divide(){
        getson(rt,-1);
        dfs(rt,-1,rt);
        tr0.build(1,1,dfn0);
        tr1.build(1,1,dfn0);
    }
    void insert(int x,array<int,2> arr){
        while(x!=-1){
            st[x].insert(arr);
            if(st[x].size()){
                auto val=(*st[x].rbegin());
                tr0.change(1,dfn[x],val);
                tr1.change(1,dfn[x],{val[0]+sam.len[x],val[1]});
            }
            else{
                tr0.change(1,dfn[x],{0,0});
                tr1.change(1,dfn[x],{0,0});
            }
            x=fa[top[x]];
        }
    }
    void erase(int x,array<int,2> arr){
        while(x!=-1){
            st[x].erase(arr);
            if(st[x].size()){
                auto val=(*st[x].rbegin());
                tr0.change(1,dfn[x],val);
                tr1.change(1,dfn[x],{val[0]+sam.len[x],val[1]});
            }
            else{
                tr0.change(1,dfn[x],{0,0});
                tr1.change(1,dfn[x],{0,0});
            }
            x=fa[top[x]];
        }
    }
    array<int,2> search(int x){
        array<int,2> res={0,0};
        while(x!=-1){
            res=max(res,tr1.search(1,dfn[top[x]],dfn[x]));
            array<int,2> tmp=tr0.search(1,dfn[x],tail[top[x]]);
            res=max(res,{tmp[0]+sam.len[x],tmp[1]});
            x=fa[top[x]];
        }
        return res;
    }
}

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

    int n,q;
    cin>>n>>q;

    string s;
    cin>>s;

    for(int i=1;i<=n;i++) sam.extend(s[i-1],i);
    TCD::init(sam.tot,0);
    for(int i=1;i<=sam.tot;i++) TCD::add(sam.link[i],i);
    TCD::divide();

    vector<int> ans(q+5,0);
    vector<array<int,2>> qry(q+5,{0,0});
    vector<vector<int>> add(n+5,vector<int>(0));
    for(int i=1,ql,qr;i<=q;i++){
        cin>>ql>>qr;
        qry[i]={ql,qr};
        add[qr].push_back(i);
    }

    for(int i=n;i>=1;i--){
        while(1){
            array<int,2> res=TCD::search(sam.pos[i]);
            if(res[1]==0) break;
            if(res[0]>i){
                int id=res[1];
                if(i>=qry[id][0]) ans[id]=i-qry[id][0]+1;
                TCD::erase(sam.pos[qry[id][1]],{qry[id][0],id});
            }
            else break;
        }
        for(auto id:add[i]){
            auto [ql,qr]=qry[id];
            TCD::insert(sam.pos[qr],{ql,id});
        }
    }

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

    return true&&false;
}

E. Elvis Presley

tag

  • 模拟

题意

阅读理解题，略。

思路

略。

代码

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

using i64=long long;

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

    int x,y;
    cin>>x>>y;

    auto get=[&](int x,int y){
        while(x){
            if(x==y) return 1;
            x>>=1;
        }
        return 0;
    };

    if(get(x,y)||get(y,x)){
        cout<<"-1";
        return true&&false;
    }

    set<int> st,ans;
    x>>=1;
    y>>=1;
    while(x){
        st.insert(x);
        x>>=1;
    }
    while(y){
        st.insert(y);
        y>>=1;
    }
    for(auto val:st){
        if(st.find(val<<1)==st.end()) ans.insert(val<<1);
        if(st.find(val<<1|1)==st.end()) ans.insert(val<<1|1);
    }

    for(auto val:ans) cout<<val<<" ";

    return true&&false;
}

F. Frank Sinatra

tag

  • 莫队
  • bitset

题意

给定 nn 个节点的树，边有边权 xx ，每次查询一条链上边权的 mexmex 。
其中 2≤n,q≤105,0≤x≤1092 \leq n, q \leq 10^5, 0 \leq x \leq 10^9 。

思路

询问离线下来树上莫队 + bitset 维护即可，大于 nn 的边权可以直接忽略，不用离散化。
复杂度 O(n⋅n+n2w)O(n \cdot \sqrt{n} + \frac{n^2}{w}) 。

代码

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

using i64=long long;

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

    int n,q;
    cin>>n>>q;
    int blo=sqrt(n);

    vector<int> bl(2*n+5,0);
    for(int i=1;i<=2*n;i++) bl[i]=(i-1)/blo+1;

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

    int dfn0=0;
    vector<int> st(n+5,0),en(n+5,0),dep(n+5,0),a(n+5,0);
    vector<int> dfn(n*2+5,0);
    vector<array<int,18>> f(n+5);
    auto get_lca=[&](int x,int y){
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=17;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        for(int i=17;i>=0;i--) if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
        while(x!=y){
            x=f[x][0];
            y=f[y][0];
        }
        return x;
    };

    function<void(int,int)> dfs=[&](int x,int fa){
        f[x][0]=fa;
        for(int i=1;i<18;i++) f[x][i]=f[f[x][i-1]][i-1];
        dfn[++dfn0]=x;
        st[x]=dfn0;
        for(auto [v,w]:e[x]){
            if(v==fa) continue;
            dep[v]=dep[x]+1;
            a[v]=w;
            dfs(v,x);
        }
        dfn[++dfn0]=x;
        en[x]=dfn0;
    };

    dfs(1,1);

    vector<array<int,3>> qry(0);
    for(int i=1,x,y,lca;i<=q;i++){
        cin>>x>>y;
        if(st[x]>st[y]) swap(x,y);
        lca=get_lca(x,y);
        if(lca==x) qry.push_back({st[x]+1,st[y],i});
        else qry.push_back({en[x],st[y],i});
    }

    sort(qry.begin(),qry.end(),[&](array<int,3> &a,array<int,3> &b){
        if(bl[a[0]]!=bl[b[0]]) return bl[a[0]]<bl[b[0]];
        else{
            if(bl[a[0]]&1) return a[1]<b[1];
            else a[1]>b[1];
        }
    });

    int l=1,r=0;
    vector<int> cnt(n+5,0),vis(n+5,0),ans(q+5,0);
    bitset<100005> bit;
    bit.set();
    auto add=[&](int ind){
        if(a[ind]>n) return;
        cnt[a[ind]]++;
        if(cnt[a[ind]]==1) bit.flip(a[ind]);
    };

    auto del=[&](int ind){
        if(a[ind]>n) return;
        cnt[a[ind]]--;
        if(cnt[a[ind]]==0) bit.flip(a[ind]);
    };

    for(auto [ql,qr,id]:qry){
        while(l<ql){
            vis[dfn[l]]^=1;
            if(vis[dfn[l]]) add(dfn[l]);
            else del(dfn[l]);
            l++;
        }
        while(l>ql){
            l--;
            vis[dfn[l]]^=1;
            if(vis[dfn[l]]) add(dfn[l]);
            else del(dfn[l]);
        }
        while(r<qr){
            r++;
            vis[dfn[r]]^=1;
            if(vis[dfn[r]]) add(dfn[r]);
            else del(dfn[r]);
        }
        while(r>qr){
            vis[dfn[r]]^=1;
            if(vis[dfn[r]]) add(dfn[r]);
            else del(dfn[r]);
            r--;
        }
        ans[id]=bit._Find_first();
    }

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

    return true&&false;
}

G. Green Day

tag

  • 构造

题意

构造一张图，边总共有k种颜色，要求每种颜色的边均构成一棵生成树且任意两点在任意两棵生成树上的路径的交集只含有路径端点。
其中 1≤k≤1001 \leq k \leq 100 。

思路

选定点数 n=2⋅kn = 2 \cdot k ，结果为一个完全图。
对于 i∈[1,k]i \in [1, k] ，使 ii 向 i+j(i+1≤j≤i+k)i + j(i + 1 \leq j \leq i+k) 连边， i+ki + k 向 i+k+j(1≤j≤n−1−k)i + k + j(1 \leq j \leq n-1-k) 连边即可。
复杂度 O(k)O(k) 。

代码

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

using i64=long long;

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

    int k,n;
    cin>>k;

    n=k*2;
    cout<<n<<"\n";
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=i+k;j++) cout<<i<<" "<<j<<"\n";
        for(int j=1;j<=n-1-k;j++) cout<<i+k<<" "<<(i+k+j-1)%n+1<<"\n";
    }

    return true&&false;
}

H. Hans Zimmer

tag

  • 数学
  • 期望

题意

给定 w∗hw * h 的矩形，随机横着或者竖着切 nn 次，求最后面积最小的矩形的期望面积。
其中 1≤w,h≤103,1≤n≤1061 \leq w, h \leq 10^3, 1 \leq n \leq 10^6 。

思路

结论：

  • 长度为 11 的线段切成 nn 段，其中最小段的期望长度为 1n2\frac{1}{n^2}

枚举横着切了 ii 刀，结果为：

  • ∑i=0n(in)2n⋅(i+1)2⋅(n−i+1)2\sum\limits_{i = 0}^{n} \frac{\binom{i}{n}}{2^n \cdot (i + 1)^2 \cdot (n - i + 1)^2}

但交上去之后发现精度寄了， nn 比较大的时候算 2n2^n 直接算裂了。
考虑取对数后再 expexp 回去即可。
复杂度 O(n)O(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
/*
    Author: Cupids_Bow
    Time: 2022-10-07 12:18:01
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

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

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

    double ans=0,binom=0;
    for(int i=0;i<=n;i++){
        ans+=exp(binom-n*log(2)-2*log(i+1)-2*log(n-i+1));
        binom+=log(n-i)-log(i+1);
    }

    cout<<fixed<<setprecision(100)<<ans*w*h;

    return true&&false;
}

I. Ivan Dorn

tag

  • 单调栈
  • 线段树

题意

给定长为 nn 的序列 aa ，定义一个区间 [l,r][l, r] 为 NBNB 区间当且仅当 al=ar,max[l,r]=ala_l = a_r, max[l, r] = a_l 。
qq 次询问，每次询问 [l,r][l, r] 内最长的 NBNB 区间的长度。
其中 1≤n,q≤5⋅105,1≤l,r≤n1 \leq n, q \leq 5 \cdot 10^5, 1 \leq l, r \leq n 。

思路

对于一个询问 [l,r][l, r] ，找出 [l,r][l, r] 的区间 maxmax 最左边和最右边的位置 posl,posrposl, posr ，则 [l,r][l, r] 被 posl,posrposl, posr 分割为 2/32 / 3 部分，显然中间部分是没有用的，剩下来只要求出左边部分最长能往右延申的长度 lenllenl 和右边部分最长能往左延申的长度 lenrlenr ，再和 posr−poslposr - posl 取 maxmax 即可，由于左右部分被区间 maxmax 分隔开，延伸长度一定不会跨过询问区间外，直接取 maxmax 是正确的。
每个位置的延申长度可以单调栈预处理，区间 maxmax 套线段树即可。
复杂度 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
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
/*
    Author: Cupids_Bow
    Time: 2022-10-06 08:44:07
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int N=5e5+5;

vector<int> a,val0,val1;

struct tree{
    int l[N<<2];
    int r[N<<2];
    int maxn0[N<<2];
    int maxn1[N<<2];
    int maxn2[N<<2];
    int posl[N<<2];
    int posr[N<<2];
    void pushup(int x){
        maxn0[x]=max(maxn0[x<<1],maxn0[x<<1|1]);
        maxn1[x]=max(maxn1[x<<1],maxn1[x<<1|1]);
        maxn2[x]=max(maxn2[x<<1],maxn2[x<<1|1]);
        if(maxn2[x]==maxn2[x<<1]) posl[x]=posl[x<<1];
        else posl[x]=posl[x<<1|1];
        if(maxn2[x]==maxn2[x<<1|1]) posr[x]=posr[x<<1|1];
        else posr[x]=posr[x<<1];
    }
    void build(int x,int L,int R){
        l[x]=L;
        r[x]=R;
        if(L==R){
            maxn0[x]=val0[L];
            maxn1[x]=val1[L];
            maxn2[x]=a[L];
            posl[x]=posr[x]=L;
            return;
        }
        int mid=L+R>>1;
        build(x<<1,L,mid);
        build(x<<1|1,mid+1,R);
        pushup(x);
        return;
    }
    array<int,3> merge(array<int,3> a,array<int,3> b){
        array<int,3> c;
        c[0]=max(a[0],b[0]);
        if(c[0]==a[0]) c[1]=a[1];
        else c[1]=b[1];
        if(c[0]==b[0]) c[2]=b[2];
        else c[2]=a[2];
        return c;
    }
    array<int,3> searchmaxn(int x,int ql,int qr){
        if(l[x]>=ql&&r[x]<=qr) return {maxn2[x],posl[x],posr[x]};
        if(r[x<<1]>=ql&&l[x<<1|1]<=qr) return merge(searchmaxn(x<<1,ql,qr),searchmaxn(x<<1|1,ql,qr));
        else if(r[x<<1]>=ql) return searchmaxn(x<<1,ql,qr);
        else return searchmaxn(x<<1|1,ql,qr);
    }
    int search0(int x,int ql,int qr){
        if(l[x]>=ql&&r[x]<=qr) return maxn0[x];
        if(r[x<<1]>=ql&&l[x<<1|1]<=qr) return max(search0(x<<1,ql,qr),search0(x<<1|1,ql,qr));
        else if(r[x<<1]>=ql) return search0(x<<1,ql,qr);
        else return search0(x<<1|1,ql,qr);
    }
    int search1(int x,int ql,int qr){
        if(l[x]>=ql&&r[x]<=qr) return maxn1[x];
        if(r[x<<1]>=ql&&l[x<<1|1]<=qr) return max(search1(x<<1,ql,qr),search1(x<<1|1,ql,qr));
        else if(r[x<<1]>=ql) return search1(x<<1,ql,qr);
        else return search1(x<<1|1,ql,qr);
    }
}tr;

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

    int n,q;
    cin>>n>>q;

    a.resize(n+5,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    
    map<int,vector<int>> pos;
    for(int i=1;i<=n;i++) pos[a[i]].push_back(i);

    vector<int> st;
    val0.resize(n+5,0);
    val1.resize(n+5,0);
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[st.back()]<=a[i]) st.pop_back();
        if(st.empty()) val0[i]=i-pos[a[i]].front();
        else val0[i]=i-(*upper_bound(pos[a[i]].begin(),pos[a[i]].end(),st.back()));
        st.push_back(i);
    }
    st.clear();
    for(int i=n;i>=1;i--){
        while(!st.empty()&&a[st.back()]<=a[i]) st.pop_back();
        if(st.empty()) val1[i]=pos[a[i]].back()-i;
        else val1[i]=(*(upper_bound(pos[a[i]].begin(),pos[a[i]].end(),st.back())-1))-i;
        st.push_back(i);
    }

    tr.build(1,1,n);

    while(q--){
        int ql,qr;
        cin>>ql>>qr;

        int ans=0;
        array<int,3> res=tr.searchmaxn(1,ql,qr);
        ans=max(ans,res[2]-res[1]);
        if(ql<=res[1]-1) ans=max(ans,tr.search1(1,ql,res[1]-1));
        if(res[2]+1<=qr) ans=max(ans,tr.search0(1,res[2]+1,qr));

        cout<<ans<<"\n";
    }

    return true&&false;
}

J. Jimi Hendrix

tag

  • 树DP

题意

给定 nn 个节点的树，边有边权为小写字母，问树上是否存在一条链使得链组成的小写字母串包含给定串 ss 作为一个子序列。
其中 1≤n≤5⋅105,1≤∣s∣≤n−11 \leq n \leq 5 \cdot 10^5, 1 \leq |s| \leq n - 1 。

思路

树 DPDP 即可。记一下每个节点的子树中正 / 倒着匹配 ss 能匹配到的最长长度和起 / 终点。
复杂度 O(n)O(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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
    Author: Cupids_Bow
    Time: 2022-10-03 13:24:20
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;
using pic=pair<int,char>;

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

    int n,m;
    cin>>n>>m;

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

    string s;
    cin>>s;

    array<int,2> ans={-1,-1};
    vector<array<int,2>> pre(n+5,{0,0}),suf(n+5,{0,0});
    function<void(int,int)> dfs=[&](int x,int fa){
        array<int,2> maxpre={0,0},maxsuf={0,0};
        for(auto [v,c]:e[x]){
            if(v==fa) continue;
            dfs(v,x);
            maxpre={0,0};
            maxsuf={0,0};
            if(pre[v][0]<m&&s[pre[v][0]]==c){
                maxpre={pre[v][0]+1,pre[v][1]};
                if(maxpre[0]==1) maxpre[1]=v;
            }
            else maxpre=pre[v];
            if(m-suf[v][0]-1>=0&&s[m-suf[v][0]-1]==c){
                maxsuf={suf[v][0]+1,suf[v][1]};
                if(maxsuf[0]==1) maxsuf[1]=v;
            }
            else maxsuf=suf[v];
            if(pre[x][0]+maxsuf[0]>=m) ans={pre[x][1],maxsuf[1]};
            if(maxpre[0]+suf[x][0]>=m) ans={maxpre[1],suf[x][1]};
            pre[x]=max(pre[x],maxpre);
            suf[x]=max(suf[x],maxsuf);
        }
        if(pre[x][0]>=m) ans={pre[x][1],x};
        if(suf[x][0]>=m) ans={x,suf[x][1]};
    };

    dfs(1,1);

    cout<<ans[0]<<" "<<ans[1];

    return true&&false;
}

K. Korn

tag

  • 图论
  • DFS树

题意

给定 nn 和点 mm 条边的无向连通图，求 NBNB 点的个数。
一个点为 NBNB 点当且仅当从这个点开始走的所有回路均为原图的一条欧拉回路。
其中 3≤n≤2⋅105,n−1≤m≤5⋅1053 \leq n \leq 2 \cdot 10^5, n - 1 \leq m \leq 5 \cdot 10^5 。

思路

首先将存在奇数度数点的情况特判掉。
剩下来的情况中一个点为 NBNB 点当且仅当所有环均经过它，跑出原图的 dfsdfs 树判一下即可。
复杂度 O(n)O(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
49
50
51
52
53
54
55
56
57
/*
    Author: Cupids_Bow
    Time: 2022-10-03 22:57:14
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

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

    int n,m;
    cin>>n>>m;

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

    for(int i=1;i<=n;i++) if(e[i].size()&1){
        cout<<"0";
        return true&&false;
    }

    int dfn0=0;
    vector<int> dfn(n+5,0),low(n+5,0);
    vector<int> ans;
    function<void(int,int)> dfs=[&](int x,int fa){
        int cnt=0;
        dfn[x]=low[x]=++dfn0;
        for(auto v:e[x]){
            if(v==fa) continue;
            if(dfn[v]){
                cnt++;
                low[x]=min(low[x],dfn[v]);
            }
            else{
                dfs(v,x);
                cnt+=(low[v]<dfn[x]);
                low[x]=min(low[x],low[v]);
            }
        }
        if(m-(n-1)==cnt) ans.push_back(x);
    };

    dfs(1,0);
    sort(ans.begin(),ans.end());

    cout<<ans.size()<<"\n";
    for(auto x:ans) cout<<x<<" ";

    return true&&false;
}