Educational Codeforces Round 162 Solution

发表于 更新于 分类于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 10 分钟

目前进度：

A B C D E F
solved contest solved contest solved contest solved later solved contest not solved

A. Moving Chips

简要翻译

给定一个 \(\texttt{01}\) 串，每次可以把一个 \(\texttt{1}\) 和左侧最近的一个 \(\texttt{0}\) 交换，求把 \(\texttt{1}\) 连成一块的最小步数。

思路解析

将最左最右的 \(\texttt{1}\) 包围起来的区间称为块。

每次 \(\texttt{1}\) 向左动相当于 \(\texttt{0}\) 向右动，考虑最少步数将块中的 \(\texttt{0}\) 移到块的右侧。

那么每次将块中最右侧的 \(\texttt{0}\) 与块末尾的 \(\texttt{1}\) 交换即可。

\(\Theta(n^2)\) 的复杂度，可以接受。

代码

Code

 
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
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
    const int BuffLen=1<<20;
    char buf[BuffLen|2],*p1=buf,*p2=buf;
    inline char getc(){
        if(p1==p2)
            p1=buf,
            p2=buf+fread(buf,1,BuffLen,stdin);
        return p1==p2?EOF:*p1++;
    }
    inline bool isdgt(const char op){return op>='0'&&op<='9';}
    inline bool ischr(const char op){return op>='a'&&op<='z';}
    long long read(){
        static long long res;static char op,f;
        for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
        for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
        return f?-res:res;
    }
    int readstr(char *s){
        static int len;static char op;
        do op=getc();while(!ischr(op));
        for(len=0;ischr(op);op=getc())s[len++]=op;
        return len;
    }
}
typedef long long ll;
const int N=300010;
int a[N],suma[N],n;
void work(){
    n=Input::read();
    for(int i=1;i<=n;++i)
        a[i]=Input::read(),
        suma[i]=suma[i-1]+a[i];
    ll ans=0;
    for(int i=n;i;--i){
        if(!a[i])continue;
        for(int j=i-1;j;--j)
            if(!a[j]&&suma[j-1]){
                a[j]=1;
                a[i]=0;
                ans++;
                for(int l=j;l<i;++l)
                    suma[l]++;
                break;
            }
    }
    printf("%lld\n",ans);
}
signed main(int argc,char **argv){
    int T=Input::read();
    while(T--)work();
    return 0;
}

B. Monsters Attack!

简要翻译

有 \(n\) 个怪物，初始位置 \(x_i\)，血量 \(a_i\)，每秒向位置 \(0\) 靠近 \(1\)，到达 \(0\) 时你死亡； 同时你每秒造成 \(k\) 点伤害，可以任意分配。求能否击杀所有怪物。

思路解析

贪心地想，应该先击杀早到 \(0\) 的怪物。注意 \(x_i\) 可以为负数，按 \(|x_i|\) 考虑。

按 \(|x_i|\) 将怪物排序，每次判断 \(|x_i| \times k \ge \sum_{j=1}^{i} a_j\) 即可。

代码

Code

 
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
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
    const int BuffLen=1<<20;
    char buf[BuffLen|2],*p1=buf,*p2=buf;
    inline char getc(){
        if(p1==p2)
            p1=buf,
            p2=buf+fread(buf,1,BuffLen,stdin);
        return p1==p2?EOF:*p1++;
    }
    inline bool isdgt(const char op){return op>='0'&&op<='9';}
    inline bool ischr(const char op){return op>='a'&&op<='z';}
    long long read(){
        static long long res;static char op,f;
        for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
        for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
        return f?-res:res;
    }
    int readstr(char *s){
        static int len;static char op;
        do op=getc();while(!ischr(op));
        for(len=0;ischr(op);op=getc())s[len++]=op;
        return len;
    }
}
using Input::read;
typedef long long ll;
const int N=300010;
ll h[N],pos[N],k;
int id[N],n;
void work(){
    n=read();k=read();
    for(int i=1;i<=n;++i)
        h[i]=read();
    for(int i=1;i<=n;++i)
        pos[i]=read(),
        id[i]=i;
    sort(id+1,id+n+1,[&](int x,int y){
        return abs(pos[x])<abs(pos[y]);
    });
    ll sumh=0;
    bool ans=1;
    for(int i=1;ans&&i<=n;++i){
        sumh+=h[id[i]];
        if(k*abs(pos[id[i]])<sumh)
            ans=0;
    }
    puts(ans?"YES":"NO");
}
signed main(int argc,char **argv){
    int T=Input::read();
    while(T--)work();
    return 0;
}

C. Find B

简要翻译

给定正项序列 \(c\)，每次询问一个子区间 \(a = \{c_l, \ldots, c_r\)}，问能否构造满足条件的序列 \(b\)：

  1. \(\sum\limits_{i=1}^{m} a_i = \sum\limits_{i=1}^{m} b_i\);

  2. \(a_i \neq b_i\);

  3. \(b_i > 0\).

思路解析

对于某一项 \(x>1\)，将其变为 \(1\) 可以空出 \(x-1\) 放在其他的项上。

而 \(x=1\) 的项则必须获得这样的值至少 \(1\)。

如果一个子区间不存在 \(x=1\) 的项，则每项 \(-1\) ，多余的值放在最后一项即可。

如果存在 \(x=1\) 的项，设 \(cnt\) 为 \(x=1\) 的项个数，\(sum\) 为区间内 \(x>1\) 的项的 \(x-1\) 之和。

只要 \(sum \ge cnt\) 就能保证所有 \(1\) 都能变为至少 \(2\)，一定有方案；否则，一定有某个 \(b_i = a_i = 1\)。

代码

Code

 
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<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
    const int BuffLen=1<<20;
    char buf[BuffLen|2],*p1=buf,*p2=buf;
    inline char getc(){
        if(p1==p2)
            p1=buf,
            p2=buf+fread(buf,1,BuffLen,stdin);
        return p1==p2?EOF:*p1++;
    }
    inline bool isdgt(const char op){return op>='0'&&op<='9';}
    inline bool ischr(const char op){return op>='a'&&op<='z';}
    long long read(){
        static long long res;static char op,f;
        for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
        for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
        return f?-res:res;
    }
    int readstr(char *s){
        static int len;static char op;
        do op=getc();while(!ischr(op));
        for(len=0;ischr(op);op=getc())s[len++]=op;
        return len;
    }
}
using Input::read;
typedef long long ll;
const int N=300010;
ll a[N],suma[N],sum1[N];
int n,m;
void work(){
    n=read();m=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        suma[i]=suma[i-1];
        sum1[i]=sum1[i-1];
        if(a[i]==1)
            sum1[i]++;
        else
            suma[i]+=a[i];
    }
    int x,y,flag;
    while(m--){
        x=read();y=read();
        flag=1;
        if(x==y)
            flag=0;
        else{
            int otherlen=y-x+1-(sum1[y]-sum1[x-1]);
            if(suma[y]-suma[x-1]-otherlen<sum1[y]-sum1[x-1])
                flag=0;
        }
        puts(flag?"YES":"NO");
    }
}
signed main(int argc,char **argv){
    int T=Input::read();
    while(T--)work();
    return 0;
}

D. Slimes

简要翻译

有 \(n\) 只史莱姆，第 \(i\) 只初始大小为 \(a_i\)。

每秒恰有一只史莱姆吃掉另一只。

设大小为 \(x\) 的史莱姆吃掉大小为 \(y\) 的史莱姆。则需满足 \(x>y\)，吃掉后 \(x\) 变为 \(x+y\)。

问对于每一只史莱姆 \(i\)，最早在第几秒被吃掉。

思路解析

每秒只有一只史莱姆能活动，那么最优方案一定是某只史莱姆吃到 \(i\) 的旁边，再把它吃掉。

因为，如果一个方案是 \(i\) 吃几只史莱姆再被吃掉，\(i\) 吃下的史莱姆留给吃掉 \(i\) 的史莱姆更优。

所以最优方案下 \(i\) 不动。从左侧和右侧分别考虑答案。

容易发现，对于同样一段史莱姆 \([l,r]\)，无论操作顺序如何，

剩一只史莱姆的时候其大小一定为 \(\sum\limits_{i=l}^{r} a_i\)，同时一定经过了 \(r-l\) 秒。

所以变为求左侧/右侧最短的区间，使得区间和大于 \(a_i\)。向两侧二分/倍增即可。

这里有一种特殊情况：区间内所有数均相等时不能合并。

如果有至少两种数字，至少有一个最大值，其左右有比它小的值，合并之后依然如此。

所以合法区间内至少要有两种以上的数字（长度为 \(1\) 的除外）。

赛时就推出来了，苦于二分和特判，最后寄了。

代码

Code

 
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
#include<algorithm>
#include<cstdio>
using namespace std;
namespace Input{
    const int BuffLen=1<<20;
    char buf[BuffLen|2],*p1=buf,*p2=buf;
    inline char getc(){
        if(p1==p2)
            p1=buf,
            p2=buf+fread(buf,1,BuffLen,stdin);
        return p1==p2?EOF:*p1++;
    }
    inline bool isdgt(const char op){return op>='0'&&op<='9';}
    inline bool ischr(const char op){return op>='a'&&op<='z';}
    long long read(){
        static long long res;static char op,f;
        for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
        for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
        return f?-res:res;
    }
    int readstr(char *s){
        static int len;static char op;
        do op=getc();while(!ischr(op));
        for(len=0;ischr(op);op=getc())s[len++]=op;
        return len;
    }
}
using Input::read;
typedef long long ll;
const int N=300010;
ll sum[N],a[N];
int ans[N],pre[N],nxt[N],n;
ll calc(int x,int y){
    if(x<y)swap(x,y);
    if(y<1)return sum[x];
    else return sum[x]-sum[y-1];
}
void work(){
    n=read();
    a[n+1]=0;
    for(int i=1;i<=n;++i){
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
        ans[i]=(n<<1);
        pre[i]=(a[i]==a[i-1])?pre[i-1]:i-1;
    }
    for(int i=n;i;--i)
        nxt[i]=(a[i]==a[i+1])?nxt[i+1]:i+1;
    for(int i=2,l=0;i<=n;++i){
        if(a[i-1]>a[i]){
            ans[i]=1;
            continue;
        }
        int lb=1,rb=pre[i-1],mid;
        while(lb+1<rb){
            mid=(lb+rb)>>1;
            if(calc(i-1,mid)>a[i])
                lb=mid;
            else
                rb=mid;
        }
        if(lb>rb)continue;
        if(calc(i-1,rb)>a[i]){
            ans[i]=min(ans[i],i-rb);
        }
        else if(calc(i-1,lb)>a[i]){
            ans[i]=min(ans[i],i-lb);
        }
    }
    for(int i=n-1;i;--i){
        if(a[i+1]>a[i]){
            ans[i]=1;
            continue;
        }
        int lb=nxt[i+1],rb=n,mid;
        while(lb+1<rb){
            mid=(lb+rb)>>1;
            if(calc(i+1,mid)>a[i])
                rb=mid;
            else
                lb=mid;
        }
        if(lb>rb)continue;
        if(calc(i+1,lb)>a[i]){
            ans[i]=min(ans[i],lb-i);
        }
        else if(calc(i+1,rb)>a[i]){
            ans[i]=min(ans[i],rb-i);
        }
    }
    for(int i=1;i<=n;++i)
        if(ans[i]==(n<<1))ans[i]=-1;
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    putchar('\n');
}
signed main(int argc,char **argv){
    int T=Input::read();
    while(T--)work();
    return 0;
}

E. Count Paths

简要翻译

给定一棵染色的树，求树上两个同颜色点间没有第三个同颜色点的点对数量。

思路分析

回顾此题 Happy Life in University，我们考虑类似的计算方法。

对于合法的点对，要么是父子关系，要么两者到 \(\mathrm{lca}\) 的路径上都没有同颜色的点。

不妨设 \(1\) 为树根。设 \(last_x\) 为 \(x\) 向上遇到的第一个同颜色的点，\(son_x\) 表示 \(\lbrace y | last_y = x \rbrace\)。

对于第一种情况，父子关系的答案为 \(\sum_{x} |son_x|\)。

对于第二种情况，两点到 \(\mathrm{lca}\) 时都不可能更新 \(last\)，所以 \(last\) 必定相同。

答案的大小就为 \(\sum_x \binom{|son_x|}{2}\)。

这时，我们忽略了一个情况：\(y_1, y_2 \in son_x, \mathrm{lca}(y_1, y_2) = x\)。它们也不是合法点对。

这种情况如何计数呢？

可以发现这种情况等价于 \(y_1, y_2\) 分属 \(x\) 的不同子树。

灵光一闪，可以发现，\(dfs\) 搜索某个 \(y\) 时，向 \(son_x\) 添加的新点与 \(son_x\) 中原有的点，它们恰好分属不同子树，应当删去。

最后特判 \(\mathrm{lca}(x,y) = 1\) 的第二种点对，对每种颜色单独计算即可。

时间复杂度 \(\Theta(n)\)。

代码

Code

 
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
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
namespace Input{
    const int BuffLen=1<<20;
    char buf[BuffLen|2],*p1=buf,*p2=buf;
    inline char getc(){
        if(p1==p2)
            p1=buf,
            p2=buf+fread(buf,1,BuffLen,stdin);
        return p1==p2?EOF:*p1++;
    }
    inline bool isdgt(const char op){return op>='0'&&op<='9';}
    long long read(){
        static long long res;static char op,f;
        for(f=0,op=getc();!isdgt(op);op=getc())f|=(op=='-');
        for(res=0;isdgt(op);op=getc())res=res*10+(op^'0');
        return f?-res:res;
    }
}
using Input::read;
typedef long long ll;
const int N=200010;
vector<int> son[N],ver[N],supson[N];
int col[N],fa[N];
int rev[N],lst[N];
int n;
ll ans;
void clear(){
    for(int i=1;i<=n;++i)
        son[i].clear(),
        ver[i].clear(),
        supson[i].clear(),
        fa[i]=0;
    ans=0;
}
void dfs(int x){
    lst[x]=rev[col[x]];
    if(lst[x])
        son[lst[x]].emplace_back(x);
    else
        supson[col[x]].emplace_back(x);
    rev[col[x]]=x;
    ll minus=0,lsts=0;//calculate pairs lca(y1, y2) = x
    for(int y : ver[x]){
        if(y==fa[x])continue;
        fa[y]=x;
        dfs(y);
        minus+=lsts*(son[x].size()-lsts);//old nodes * new nodes
        lsts=son[x].size();
    }
    rev[col[x]]=lst[x];
    ans-=minus;
}
void work(){
    n=read();
    clear();
    for(int i=1;i<=n;++i)
        col[i]=read();
    for(int i=1,x,y;i<n;++i){
        x=read();
        y=read();
        ver[x].emplace_back(y);
        ver[y].emplace_back(x);
    }
    dfs(1);
    for(int i=1;i<=n;++i){//|son(x)| + C(|son(x)|, 2)
        ll t=son[i].size();
        if(!t)continue;
        ans+=t+t*(t-1)/2;
    }
    for(int i=1;i<=n;++i){//lca(x,y) == 1, col[x] == col[y] != col[1]
        ll t=supson[i].size();
        if(!t)continue;
        ans+=t*(t-1)/2;
    }
    printf("%lld\n",ans);
}
signed main(int argc,char **argv){
    int T=Input::read();
    while(T--)work();
    return 0;
}