Codeforces Round 556 (Div. 1)

发表于 更新于 分类于

https://codeforces.com/contest/1149/problem/C

C. Tree Generator™

考虑$\rm LCA$的一种求法，即如果要求$x,y$的$\rm LCA$，我们把括号序列写下来，左括号为$1$右括号为$-1$统计一遍前缀和，$x,y$之间最小的那个就是$\rm LCA$的深度。

那么两点距离就是$x,y$的深度和减去两倍$\rm LCA$的深度。

所以直径就是所有点对中最大的那个。

那么用线段树维护这个前缀和就好了，每次修改就在树上区间修改，询问就多记录几个信息。

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
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
struct data {int ab,bc,mx,mn,res;}t[maxn];
int tag[maxn],a[maxn],n,q;
char s[maxn];
 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
 
void update(int p) {
    t[p].mx=max(t[ls].mx,t[rs].mx);
    t[p].mn=min(t[ls].mn,t[rs].mn);
    t[p].ab=max(max(t[ls].ab,t[rs].ab),t[ls].mx-t[rs].mn*2);
    t[p].bc=max(max(t[ls].bc,t[rs].bc),t[rs].mx-t[ls].mn*2);
    t[p].res=max(max(t[ls].res,t[rs].res),max(t[ls].mx+t[rs].bc,t[ls].ab+t[rs].mx));
}
 
void push(int p,int x) {
    t[p].mx+=x,t[p].mn+=x;
    t[p].ab-=x,t[p].bc-=x;tag[p]+=x;
}
 
void pushdown(int p) {
    if(tag[p]) push(ls,tag[p]),push(rs,tag[p]),tag[p]=0;
}
 
void modify(int p,int l,int r,int x,int y,int v) {
    if(x<=l&&r<=y) return push(p,v),void();
    pushdown(p);
    if(x<=mid) modify(ls,l,mid,x,y,v);
    if(y>mid) modify(rs,mid+1,r,x,y,v);
    update(p);
}
 
void build(int p,int l,int r) {
    if(l==r) return t[p].mn=t[p].mx=a[l],t[p].ab=t[p].bc=-a[l],void();
    build(ls,l,mid),build(rs,mid+1,r);update(p);
}
 
void debug(int p,int l,int r) {
    if(l==r) {
        printf("%d ",t[p].mn);
    }else pushdown(p),debug(ls,l,mid),debug(rs,mid+1,r);
}
 
int main() {
    read(n),read(q);n=(n-1)*2;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) a[i]=a[i-1]+(s[i]=='('?1:-1);
    build(1,1,n);write(t[1].res);
    for(int i=1;i<=q;i++) {
        int a,b;read(a),read(b);
        if(s[a]!=s[b]) {
            modify(1,1,n,a,n,s[a]=='('?-2:2);
            modify(1,1,n,b,n,s[b]=='('?-2:2);swap(s[a],s[b]);
        }write(t[1].res);
        // debug(1,1,n);puts("");
    }
    return 0;
}

D. Abandoning Roads

神题。。我又是看了题解才会的。。。

注意到只有两种边权，先把所有$a$的边缩起来，然后在拿剩下的$b$边连出一棵树就是最小生成树。

那么一条路径在最小生成树上一定会满足只经过每个$a$的连通块一次。

所以如果直接状压，设$a$的连通块个数为$x$，设$f_{s,x}$表示当前经过了$s$这个状态的块，当前在$x$的最小距离，状态数就是$O(2^x\cdot n)$。

然后转移的时候使用最短路就好了，注意我们要忽略掉所有两个端点在同一个块内的$b$边，因为这种边不会出现在最小生成树内，同理不能通过$b$边走到一个走过的连通块。

显然这个东西会被卡成$2^n$，我们需要一些优化。

注意到如果一个连通块的大小$\leqslant 3$，那么我们其实不需要这个块的状态，因为我们跑最短路的时候至少通过两条$b$边才能从这个块的一个点到另一个点，但这样显然不优，因为这个块两两之间至多两条$a$边就能到达。

所以最短路的过程会保证这种块只走一次。

那么状态数就是$O(2^{n/4}\cdot n)$，复杂度是$O(2^{n/4}\cdot m\log (2^{n/4}\cdot n))$，其实后面那个$\log$能优化掉，但是不优化也只要跑$\rm 400ms$就算了（

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
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 80;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int f[(1<<17)+10][75];
int fa[maxn],head[maxn],tot,n,m,a,b,cnt[maxn],bel[maxn],id[maxn],re[maxn],c,ans[maxn];
struct edge{int to,nxt,w;}e[1000];
struct data {
    int v,s;short x;
    bool operator < (const data &r) const {return v<r.v;}
};
priority_queue<data > q;
 
void ins(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
 
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
 
int main() {
    read(n),read(m),read(a),read(b);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1,x,y,z;i<=m;i++) {
        read(x),read(y),read(z),ins(x,y,z),ins(y,x,z);
        if(z==a) if(find(x)!=find(y)) fa[find(x)]=find(y);
    }
    for(int i=1;i<=n;i++) cnt[find(i)]++,bel[i]=find(i);
    for(int i=1;i<=n;i++) {
        if(cnt[i]<=3) continue;
        id[i]=++c;
    }memset(f,63,sizeof f);
    memset(ans,63,sizeof ans);
    int _=1<<(id[bel[1]]-1);if(!id[bel[1]]) _=0;
    f[_][1]=0;q.push((data){0,_,1});
    while(!q.empty()) {
        data x=q.top();q.pop();ans[x.x]=min(ans[x.x],f[x.s][x.x]);
        if(x.v>f[x.s][x.x]) continue;
        for(int v,i=head[x.x];i;i=e[i].nxt) {
            v=e[i].to;
            if(e[i].w==b&&bel[x.x]==bel[v]) continue;
            if(id[bel[v]]&&e[i].w==b&&(x.s&(1<<(id[bel[v]]-1)))) continue;
            int t;if(!id[bel[v]]) t=x.s;else t=x.s|(1<<(id[bel[v]]-1));
            if(f[t][v]<=f[x.s][x.x]+e[i].w) continue;
            f[t][v]=f[x.s][x.x]+e[i].w,q.push((data){-f[t][v],t,v});
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
    return 0;
}

E. Election Promises

去瞄了一眼题解好像是什么$\rm SG$。。。完全不会，咕咕咕。