Codeforces Global Round 1

发表于 更新于 分类于

比赛链接： https://codeforces.com/contest/1110 。

D. Jongmah

注意到如果操作$(x-2,x-1,x)$使用了三次，那么可以转换成三个形如$(x,x,x)$的操作，那么$x$这个操作最多只被使用了两次。

那么暴力$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
#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 t[maxn],n,m,f[maxn][3][3];
 
void chmax(int &x,int y) {if(y>x) x=y;}
 
int main() {
    read(n),read(m);
    for(int i=1,x;i<=n;i++) read(x),t[x]++;
    memset(f,-63,sizeof f);
    f[2][0][0]=0;
    for(int i=3;i<=m;i++) 
        for(int x=0;x<=2&&x<=t[i];x++)
            for(int p=0;p<=2;p++)
                for(int q=0;q<=2;q++) {
                    if(f[i-1][p][q]<0) continue;
                    if(t[i-1]<p+x) continue;
                    if(t[i-2]<q+x+p) continue;
                    chmax(f[i][x][p],f[i-1][p][q]+x+(t[i-2]-q-x-p)/3);
                }
    int ans=0;
    for(int i=0;i<=2;i++)
        for(int j=0;j<=2;j++)
            chmax(ans,f[m][i][j]+(t[m]-i)/3+(t[m-1]-j-i)/3);
    write(ans);
    return 0;
}

E. Magic Stones

考虑差分数组$b_i=a_i-a_{i-1}$，那么如果对$a_i$进行操作，仔细分析下这次操作等价于${\rm swap}(b_i,b_{i+1})$。

那么只需要判断一下两个序列的差分数组排序之后相不相同就行了。

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
#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 n,a[maxn],b[maxn];
 
int main() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    if(a[1]!=b[1]||a[n]!=b[n]) return puts("No"),0;
    for(int i=n;i;i--) a[i]-=a[i-1],b[i]-=b[i-1];
    sort(a+2,a+n+1),sort(b+2,b+n+1);
    for(int i=2;i<=n;i++) if(a[i]!=b[i]) return puts("No"),0;
    puts("Yes");
    return 0;
}

F. Nearest Leaf

把询问离线下来，对于$1$号点的询问，直接建一棵线段树就好了。

然后利用换根$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
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
#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 = 5e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,q,head[maxn],tot,ans[maxn],sz[maxn];
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;}
 
struct info {int l,r,id;};
 
vector<info > a[maxn];
 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
 
struct segment_tree {
    int t[maxn<<2],tag[maxn<<2];
 
    void push(int p,int v) {tag[p]+=v,t[p]+=v;}
    void pushdown(int p) {push(ls,tag[p]),push(rs,tag[p]),tag[p]=0;}
 
    void cov(int p,int l,int r,int x,int v) {
        if(l==r) return t[p]=v,void();
        if(x<=mid) cov(ls,l,mid,x,v);
        else cov(rs,mid+1,r,x,v);
        t[p]=min(t[ls],t[rs]);
    }
 
    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);
        t[p]=min(t[ls],t[rs]);
    }
 
    int query(int p,int l,int r,int x,int y) {
        if(x<=l&&r<=y) return t[p];
        int ans=1e18;pushdown(p);
        if(x<=mid) ans=min(ans,query(ls,l,mid,x,y));
        if(y>mid) ans=min(ans,query(rs,mid+1,r,x,y));
        return ans;
    }
}T;
 
void get(int x,int fa,int d) {
    int bo=1;sz[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa) get(e[i].to,x,d+e[i].w),bo=0,sz[x]+=sz[e[i].to];
    if(bo) T.cov(1,1,n,x,d);
}
 
void solve(int x,int fa) {
    for(auto t:a[x]) ans[t.id]=T.query(1,1,n,t.l,t.r);
    for(int v,i=head[x];i;i=e[i].nxt) {
        if((v=e[i].to)==fa) continue;
        T.modify(1,1,n,1,n,e[i].w);
        T.modify(1,1,n,v,v+sz[v]-1,-2*e[i].w);
        solve(v,x);
        T.modify(1,1,n,1,n,-e[i].w);
        T.modify(1,1,n,v,v+sz[v]-1,2*e[i].w);
    }
}
 
signed main() {
    read(n),read(q);
    for(int i=2,p,x;i<=n;i++) read(p),read(x),ins(i,p,x),ins(p,i,x);
    for(int i=1,l,r,v;i<=q;i++) read(v),read(l),read(r),a[v].pb((info){l,r,i});
    memset(T.t,63,sizeof T.t);
    get(1,0,0),solve(1,0);
    for(int i=1;i<=q;i++) write(ans[i]);
    return 0;
}

G. Tree-Tac-Toe

神仙题。。图源自$\rm CF$官方题解。

首先我们可以把白色的点换成这样：

那么如果白色一开始就放了$A$点，黑色一定只能放$B$点，这样的开局一定不比什么都不干劣。

那么考虑这棵新的树：

  • 如果有一个点点度$\geqslant 4$显然白色赢。
  • 如果有一个点点度$\geqslant 3$并且有$\geqslant 2$个儿子点度不为$1$，那么白色先放点度$3$的那个点，显然白色赢。
  • 根据上面那一条可以推出最多只有两个点点度为$3$，其他的都为$1,2$。

如果有两个点度为$3$，那么除开上面的情况，这个图一定长这样：

把左边那个点度为$3$的点标号为$1$，然后一路往右标号直到$k$，即水平的那条链。

那么如果$k$为奇数则白色必胜，因为白色可以先放$2$，那么黑色一定放$1$，然后白色$4$，黑色$3\cdots$，最后白色会把$k-1,k$都放了，此时显然白色必胜。

容易知道其他的情况就只有链和类似于上面那张图从中间切开只要一边的情况，显然会和局。

复杂度$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
#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;
 
char s[maxn];
int d[maxn],n,c,cnt;
vector<int > e[maxn];
 
void solve() {
    read(n);cnt=n,c=0;
    for(int i=1;i<=n;i++) e[i].clear(),d[i]=0;
    for(int i=1,x,y;i<n;i++) read(x),read(y),d[x]++,d[y]++,e[x].pb(y),e[y].pb(x);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) if(s[i]=='W') d[i]++,c++,cnt+=3,e[i].pb(cnt),d[cnt]=3;
    for(int i=1;i<=n;i++)
        if(d[i]>=4) return puts("White"),void();
        else if(d[i]==3) c++;
    if(c>=3) return puts("White"),void();
    for(int i=1;i<=n;i++)
        if(d[i]==3) {
            int b=0;
            for(auto x:e[i]) if(d[x]>=2) b++;
            if(b>=2) return puts("White"),void();
        }
    if(c==2&&(cnt&1)) return puts("White"),void();
    puts("Draw");
    
}
 
int main() {
    int t;read(t);while(t--) solve();
    return 0;
}