Codeforces Round 526 (Div. 1)

发表于 更新于 分类于

https://codeforces.com/contest/1083

A. The Fair Nut and the Best Path

$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
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
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 = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,head[maxn],tot,val[maxn],mx[maxn],mx2[maxn],c[maxn],ans;
struct edge{int to,nxt,w;}e[maxn<<1];
 
void ins(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
 
void dfs(int x,int fa) {
    mx[x]=mx2[x]=-1;
    for(int v,i=head[x];i;i=e[i].nxt) {
        if((v=e[i].to)==fa) continue;c[v]=e[i].w;
        dfs(v,x);int t=mx[v]-e[i].w;if(t<0) continue;t+=val[x];
        if(mx[x]<=t) mx2[x]=mx[x],mx[x]=t;
        else mx2[x]=max(mx2[x],t);
    }int t=val[x];
    if(mx[x]<=t) mx2[x]=mx[x],mx[x]=t;
    else mx2[x]=max(mx2[x],t);
    ans=max(ans,mx[x]);
}
 
void dfs2(int x,int fa,int p) {
    if(p-c[x]>=0) p=p-c[x]+val[x];
    else p=val[x];ans=max(ans,p);
    for(int v,t,i=head[x];i;i=e[i].nxt) {
        if((v=e[i].to)==fa) continue;
        if(mx[x]==mx[v]-e[i].w+val[x]) t=mx2[x];else t=mx[x];
        dfs2(v,x,max(p,t));
    }
}
 
signed main() {
    read(n);
    for(int i=1;i<=n;i++) read(val[i]);
    for(int i=1,x,y,z;i<n;i++) read(x),read(y),read(z),ins(x,y,z),ins(y,x,z);
    dfs(1,0);dfs2(1,0,0);write(ans);
    return 0;
}

B. The Fair Nut and Strings

首先考虑把所有串拉出来建一棵$\rm trie$树，设$f_i$表示每一层的点数。

那么显然如果我们找到了一个$x$满足$f_x\leqslant k<f_{x+1}$，那么$1\sim x$的点全会被占满，然后还会延伸出$k$条长度为$n-x$的链，这样显然是最优的。

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
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
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 = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
char s[maxn],t[maxn];
int n,k,f[maxn],ss[maxn];
 
signed main() {
    read(n),read(k);scanf("%s%s",s+1,t+1);int bo=0;
    for(int i=1;i<=n;i++) {
        f[i]=max(0ll,f[i-1]-2)*2+2+bo*((s[i]=='a')+(t[i]=='b'));
        if(s[i]!=t[i]) bo=1;if(!bo) f[i]--;
        ss[i]=f[i]+ss[i-1];//write(f[i]);
        if(f[i]>k) {
            write(ss[i-1]+(n-i+1)*k);
            return 0;
        }
    }write(ss[n]);
    return 0;
}

C. Max Mex

很巧妙的题。

首先因为他是个排列，每个权值都只会出现一次，我们可以开一颗线段树，区间$[l,r]$记录有没有一条链经过$l\sim r$的所有值。

那么区间合并就直接合并两条链就好了，查询就线段树上二分。

如果我们用$\rm rmq$来$O(1)$求$\rm LCA$，复杂度就是$O(n\log 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
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
#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 = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int p[maxn],n;
 
struct tree {
    int head[maxn],tot,in[maxn],out[maxn],dep[maxn],cnt,rev[maxn],lg[maxn];
    struct edge{int to,nxt;}e[maxn<<1];
    pii f[maxn][20];
 
    void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
 
    void dfs(int x,int fa) {
        in[x]=++cnt;dep[x]=dep[fa]+1;rev[cnt]=x;
        for(int i=head[x];i;i=e[i].nxt)
            if(e[i].to!=fa) dfs(e[i].to,x),rev[++cnt]=x;
        out[x]=++cnt;rev[cnt]=x;
    }
    
    void prepare() {
        for(int i=1;i<=cnt;i++) f[i][0]=mp(dep[rev[i]],i);
        for(int j=1;j<20;j++) 
            for(int i=1;i<=cnt;i++)
                f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        for(int i=2;i<=cnt;i++) lg[i]=lg[i>>1]+1;
        // for(int i=1;i<=cnt;i++) printf("%d ",rev[i]);puts("");
    }
 
    int lca(int x,int y) {
        x=out[x],y=in[y];if(x>y) swap(x,y);
        int p=lg[y-x+1];pii t=min(f[x][p],f[y-(1<<p)+1][p]);
        return rev[t.sc];
    }
 
    int dis(int x,int y) {return dep[x]+dep[y]-2*dep[lca(x,y)];}
}T;
 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
 
struct segment_tree {
    pii t[maxn];
 
    pii merge(int x,int y,int z) {
        int xy=T.dis(x,y),yz=T.dis(y,z),zx=T.dis(z,x);
        if(xy+yz==zx) return mp(z,x);
        if(zx+xy==yz) return mp(y,z);
        if(yz+zx==xy) return mp(x,y);
        return mp(-1,-1);
    }
 
    pii unite(pii x,pii y) {
        if(!x.fr) return y;
        if(~x.fr&&~y.fr) {
            x=merge(x.fr,x.sc,y.fr);
            if(~x.fr) x=merge(x.fr,x.sc,y.sc);
            return x;
        }return mp(-1,-1);
    }
 
    void modify(int p,int l,int r,int x,int v) {
        if(l==r) return t[p]=mp(v,v),void();
        if(x<=mid) modify(ls,l,mid,x,v);
        else modify(rs,mid+1,r,x,v);
        t[p]=unite(t[ls],t[rs]);
    }
 
    pii query(int p,int l,int r,pii v) {
        if(l==0&&r==n-1&&~t[p].fr) return mp(-1,n-1);
        if(l==r) {
            pii x=merge(v.fr,v.sc,t[p].fr);
            // printf("query :: %d %d %d %d %d\n",l,x.fr,v.fr,v.sc,t[p].fr);
            if(~x.fr) return mp(-1,l);
            else return mp(-1,l-1);
        }
        pii x=unite(v,t[p]);
        if(~x.fr) return x;
        x=query(ls,l,mid,v);
        if(~x.fr) return query(rs,mid+1,r,x);
        return x;
    }
 
    void debug(int p,int l,int r) {
        printf("debug :: %d %d %d %d\n",l,r,t[p].fr,t[p].sc);
        if(l==r) return ;debug(ls,l,mid),debug(rs,mid+1,r);
    }
}st;
 
int main() {
    read(n);
    for(int i=1;i<=n;i++) read(p[i]);
    for(int i=2,x;i<=n;i++) read(x),T.ins(x,i),T.ins(i,x);
    T.dfs(1,0);T.prepare();
    // write(T.lca(4,6));
    for(int i=1;i<=n;i++) st.modify(1,0,n-1,p[i],i);
    int q;read(q);
    for(int i=1;i<=q;i++) {
        int op;read(op);
        if(op==2) write(st.query(1,0,n-1,mp(0,0)).sc+1);
        else {
            int x,y;read(x),read(y);
            st.modify(1,0,n-1,p[x],y),st.modify(1,0,n-1,p[y],x);
            swap(p[x],p[y]);
        }
        // st.debug(1,0,n-1);puts("");
    }
    return 0;
}

D. The Fair Nut’s getting crazy

好毒瘤啊先咕咕咕，话说为什么D题有3400分啊。。

E. The Fair Nut and Rectangles

这可能是本场最水的题了。。为什么E题比AB都水啊。。

首先按$x$排序，那么$y$一定是递减的。

设$f_i$表示选了$i$，前面的可选可不选的最大值，那么：

这显然可以斜率优化，拿单调队列搞一搞就行了。

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;
 
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 = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
struct pps {int x,y;ll a;}a[maxn];
int n,q[maxn],ql,qr;ll f[maxn];
 
int cmp(pps a,pps b) {return a.x<b.x;}
 
lf slope(int l,int r) {return 1.0*(f[l]-f[r])/(a[l].x-a[r].x);}
 
signed main() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i].x),read(a[i].y),scanf("%lld",&a[i].a);
    sort(a+1,a+n+1,cmp);ql=qr=1;
    for(int i=1;i<=n;i++) {
        while(qr>ql&&slope(q[ql],q[ql+1])>=a[i].y) ql++;
        f[i]=max(f[i-1],f[q[ql]]+1ll*a[i].y*(a[i].x-a[q[ql]].x)-a[i].a);
        while(qr>ql&&slope(q[qr],q[qr-1])<=slope(q[qr],i)) qr--;
        q[++qr]=i;
    }printf("%lld\n",f[n]);
    return 0;
}

F. The Fair Nut and Amusing Xor

神题。

首先令$c_i=a_i\oplus b_i$，$r_i=c_i\oplus c_{i-1}$，那么这样差分之后每次修改就变成了了$r_i$和$r_{i+k}$异或上$x$。

那么我们把$r$按下标$\bmod k$同余分组，每次就是相邻的修改。

考虑任意一组，将其记为$w_i$，那么我们每次就要异或$w_1,w_1\oplus w_2,w_1\oplus w_2 \oplus w_3 \cdots$，这之中等于$0$的就是我们省掉的操作，那么我们能全消成$0$当且仅当全部异或起来等于$0$。

那么暴力就很好写了，只需要每次修改的时候遍历这一组，然后统计一下哪些前缀异或和是$0$就可以了。

这样复杂度是$O(\frac{n}{k}\cdot q)$的，如果$k\geqslant \sqrt n$，那么复杂度就是$O(q\sqrt n)$。

现在考虑$k<\sqrt n$怎么做，其实做法也很显然了，我们现在要进行的操作是区间异或还有统计有多少值为$0$，因为这里区间异或其实是在前缀和数组上进行。

那么我们分块，打区间异或标记，块内暴力修改，因为权值不是很大，对于每个块记个桶表示当前值有多少个，统计答案就很简单了。

时间复杂度$O(q\sqrt n)$，空间复杂度$O(wk\cdot \sqrt{\frac{n}{k}}) =O(w\sqrt{nk})$，调整一下块大小就能过了。

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
#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 = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
const int B = 400;
 
int a[maxn],b[maxn],n,k,q;
int c[maxn],s[maxn],ans,res;
 
namespace pps {
    void modify(int p,int x) {
        c[p]=x;
        for(int i=p;i<=n;i+=k) {
            ans-=!(!s[i]);
            if(i+k>n) res-=!s[i];
            s[i]=c[i]^(i>=k?s[i-k]:0);
            if(i+k>n) res+=!s[i];
            ans+=!(!s[i]);
        }
    }
    
    void solve() {
        ans=n-ans;
        while(q--) {
            char op;int p,v;scanf("%c",&op),read(p),read(v);
            if(op=='a') a[p]=v;else b[p]=v;
            modify(p,(a[p]^b[p])^(a[p-1]^b[p-1]));p++;
            modify(p,(a[p]^b[p])^(a[p-1]^b[p-1]));
            write(res==k?ans:-1);
        }
    }
}
 
namespace modpps {
    struct block {
        vector<int > r,bel,val,w;
        vector<vector<int > > t;
        int tag[600],m;
 
        void init(int x) {
            if(!x) x=k;m=0;
            for(int i=x;i<=n;i+=k) m++;
            r.resize(m+2),bel.resize(m+2);
            val.resize(m+2),w.resize(m+2);
            for(int i=1;i<=m;i++) bel[i]=(i-1)/B+1;
            // printf("init :: %d %d\n",x,m);
            for(int i=m;i;i--) r[i]=bel[i]==bel[i+1]?r[i+1]:i;
            for(int i=1;i<=m;i++) {
                w[i]=s[(i-1)*k+x];val[i]=c[(i-1)*k+x];
                // printf("%d ",val[i]);
            }
            // puts("");
            vector<int > et(1<<14,0);
            for(int i=0;i<=bel[m];i++) t.pb(et);
            for(int i=1;i<=m;i++) t[bel[i]][w[i]]++;
        }
 
        void modify(int x,int v) {
            // printf("mdf %d %d %d %d\n",x,v,v^val[x],res);
            x=x/k+(x%k!=0);int _=v^val[x];val[x]=v;v=_;
            res-=tag[bel[m]]==w[m];
            for(int i=x;i<=r[x];i++) {
                t[bel[i]][w[i]]--;if(w[i]==tag[bel[i]]) ans--;
                w[i]^=v;
                t[bel[i]][w[i]]++;if(w[i]==tag[bel[i]]) ans++;
            }
            for(int i=bel[x]+1;i<=bel[m];i++) {
                ans-=t[i][tag[i]];tag[i]^=v;
                ans+=t[i][tag[i]];
            }
            res+=tag[bel[m]]==w[m];//write(res);
        }
    }s[402];
    
    void solve() {
        for(int i=0;i<k;i++) s[i].init(i);cerr<<"OK"<<endl;
        while(q--) {
            char op;int p,v;scanf("%c",&op),read(p),read(v);
            if(op=='a') a[p]=v;else b[p]=v;
            s[p%k].modify(p,(a[p]^b[p])^(a[p-1]^b[p-1]));p++;
            s[p%k].modify(p,(a[p]^b[p])^(a[p-1]^b[p-1]));
            write(res==k?n-ans:-1);if(q%10000==0) cerr<<q<<endl;
        }
    }
}
 
int main() {
    int st=clock();
    read(n),read(k),read(q);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);n++;
    for(int i=1;i<=n;i++) c[i]=(a[i]^b[i])^(a[i-1]^b[i-1]);
    for(int i=1;i<=n;i++)  s[i]=c[i]^(i>=k?s[i-k]:0),ans+=!s[i];
    for(int i=n-k+1;i<=n;i++) res+=!s[i];
    write(res==k?n-ans:-1);
    
    if(k>B) pps :: solve();
    else modpps :: solve();
    cerr<<(lf)(clock()-st)/1e3<<endl;
    return 0;
}