Codeforces Round #624 (Div. 3)补题

发表于 更新于 分类于 阅读次数：

上场恰好掉到了1600，只能打星，血亏……
这场签到手太慢了，C题数组开小了RE了一发，D题范围小了fst了……

本场关键字

分类讨论、并查集、前缀和、暴力、逆序数、树状数组

A. Add Odd or Subtract Even(700)

分类讨论，手慢了

代码

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;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll t,a,b;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        if(a<b)
        {
            if((b-a)&1)
                cout<<1<<endl;
            else
                cout<<2<<endl;//拆成两个
        }
        else if(a>b)
        {
            if((a-b)&1)//奇数且
                cout<<2<<endl;
            else
                cout<<1<<endl;
        }
        else
            cout<<0<<endl;
    }
    return 0;
}

B. WeirdSort(1200)

思路

并查集+$multiset$
因为下标在同一组的元素可以任意交换，所以很容易想到并查集。
再因为排序要把小的元素尽量往前排，所以选用$multiset$，每次贪心地取出集合中的第一个元素。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=105,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
int a[maxn],p[maxn],fa[maxn];
int findfa(int x)
{
    if(x!=fa[x])
        fa[x]=findfa(fa[x]);
    return fa[x];
}
bool Merge(int x,int y)
{
    int a=findfa(x),b=findfa(y);
    if(a==b)
        return 0;
    if(a<b)
    {
        fa[b]=a;
    }
    else{
        fa[a]=b;
    }
    return 1;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        vector<int>res;
        multiset<int>st[maxn];
        multiset<int>::iterator it;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)//合并可交换的位置
        {
            cin>>p[i];
            Merge(p[i],p[i]+1);
        }
        for(int i=1;i<=n;i++)//插入对应集合
        {
            st[findfa(i)].insert(a[i]);
        }
        for(int i=1;i<=n;i++)//取出所属集合中的最小值
        {
            it=st[findfa(i)].begin();
            res.push_back(*it);//res为排序后数组
            st[findfa(i)].erase(it);
        }
        int pre=0,flag=1;
        for(auto &i:res)
        {
            if(i<pre)
            {
                flag=0;
                break;
            }
            pre=i;
        }
        cout<<(flag?"YES":"NO")<<endl;
    }
    return 0;
}

C. Perform the Combo(1300)

题目很长

题意

没玩过格斗游戏的童鞋最好去看洛谷的翻译。
一个萌新在练习格斗游戏的连续技，必须要不间断输入指令集$s$才能成功完成。
这个萌新练习失败了$m$次，第$i$次在$p_i$个指令上断连。
并且他最终成功打出了这套连续技。
请输出这个萌新对于每个指令输入了多少次。

思路

前缀和
对每个指令$p_i$都求一个前缀和，将$m$次断连和一次成功的操作通过前缀和$O(m)$求出，注意不要在循环内写$memset$
很神奇，我也不知道为什么1e4会fst，要开2e4

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
char s[maxn];
int st[30],sum[maxn][30];
ll ans[30];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n,m,p;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>s+1;
        memset(st,0,sizeof(st));
//        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++)
        {
            int ch=s[i]-'a';
            sum[i][ch]=sum[i-1][ch]+1;
            for(int j=0;j<26;j++)
                if(j!=ch)
                    sum[i][j]=sum[i-1][j];
        }
        for(int i=0;i<26;i++)
            ans[i]=sum[n][i];
        while(m--)
        {
            cin>>p;
            for(int i=0;i<26;i++)
                ans[i]+=sum[p][i];
        }
        for(int i=0;i<26;i++)
            cout<<ans[i]<<' ';
        cout<<endl;
    }
    return 0;
}

D. Three Integers(1900)

题意

给你$a,b,c$三个数，你可以将他们加$1$或减$1$操作任意次，操作一次花费$1$，求最终$a$整除$b$，$b$整除$c$的最小花费，并输出$a,b,c$

思路

emm，一言难尽，赛中正确做法秒得😣，但是因为复杂度估计错误自我怀疑演了一个小时，直觉以为是$O(n^3)$，其实只有$O(n^{\frac{7}{4}})$的复杂度。
这个想法真的很暴力……在[1,2e4]范围内枚举出$a$，然后用$a$枚举出$a$的倍数$b$，再枚举$b$的倍数$c$，计算当前$a,b,c$的代价，记录代价最小的一组。
AC之后心态崩了……

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e4+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll t,a,b,c,ans[3],rec;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c;
        rec=LLONG_MAX;
        for(int x=1;x<maxn;x++)//枚举a
        {
            for(int i=1;x*i<maxn;i++)
            {
                ll y=x*i;//
                for(ll j=1;y*j<maxn;j++)
                {
                    ll z=y*j;
                    ll now=abs(x-a)+abs(y-b)+abs(z-c);
                    if(now<rec)
                    {
                        rec=now;
                        ans[0]=x;
                        ans[1]=y;
                        ans[2]=z;
                    }
                }
            }
        }
        cout<<rec<<endl;
        for(int i=0;i<3;i++)
            cout<<ans[i]<<' ';
        cout<<endl;
    }
    return 0;
}

E. Construct the Binary Tree(2400)

图论构造题，判定有思路，实现不会，看了题解也不会

题意

给出$n$与$d$，要求构造一个$n$个节点的二叉树，节点1为根，要使所有节点到根的距离之和为d。

思路

先判定是否有解，显然当$n$为一条链时深度之和最大；当$n$个点构成完全二叉树时深度和最小。
在这个范围区间即有解，先将$n$个节点组成一条链，逐步将深度最浅的叶子节点向上移，若遇见此节点上方为满二叉树，则将此节点打上$bad$标记，继续调整，复杂度$O(nd)$。
详见代码QwQ……

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
int fa[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll t,n,d;
    cin>>t;
    while(t--)
    {//最大:链,最小:完全二叉树
        cin>>n>>d;
        ll mi=0;
        for(ll i=1,now=n-1;now>0;i++)
        {//now为剩余节点数量
            if(now>=(1<<i))
            {
                mi+=i*(1<<i);
                now-=(1<<i);
            }
            else{
                mi+=now*i;
                break;
            }
        }
        if(d>n*(n-1)/2||d<mi)
            cout<<"NO"<<endl;
        else{
            cout<<"YES"<<endl;
            vector<int>fa(n),dep(n);//构造出一条链,下标[0,n-1]
            iota(fa.begin(),fa.end(),-1);//递增赋值
            iota(dep.begin(),dep.end(),0);
            int tot=n*(n-1)/2;//链的深度和
            vector<int>cnt(n,1),bad(n);
            cnt[n-1]=0;//cnt[i]表示i节点的儿子数量
            while(tot>d)
            {//尽力在上部构造完全二叉树
                int v=-1,p=-1;
                for(int i=0;i<n;i++)//找深度最浅的叶子节点v
                    if(!bad[i]&&cnt[i]==0&&(v==-1||dep[v]>dep[i]))
                        v=i;
                for(int i=0;i<n;i++)//找一个深度比v浅的,但与v最近的节点作为父节点
                    if(cnt[i]<2&&dep[i]<dep[v]-1&&(p==-1||dep[i]>dep[p]))
                        p=i;
                if(p==-1)
                {//上部为满二叉树,这个节点不能再向上蹿了
                    bad[v]=1;
                    continue;
                }
                cnt[fa[v]]--;
                dep[v]--;//v上移一个单位
                cnt[p]++;
                fa[v]=p;
                tot--;//深度之和--
            }
            for(int i=1;i<n;i++)
                cout<<fa[i]+1<<' ';
            cout<<endl;
        }
    }
    return 0;
}

F. Moving Points(2100)

非常好的一道数据结构题，但是我不会……

题意

点上面的链接去洛谷看……很清晰……

思路

因为所有点的初始位置$x$都不同，很明显对于任意两点$i$与$j$，设初始位置$x_i<x_j$，若$v_i>v_j$，则$d(i,j)=0$，否则$d(i,j)=x_j-x_i$。
所以先按照$x$排序，这样在第$i$个点之前的点初始位置一定小于$x_i$，此时查询在点$i$之前的点有多少个点的速度大于$v_i$，记个数为$m$，这些点的初始位置之和为$sum$，则插入点$i$时产生的贡献为$m*x_i-sum$。
对所有的速度$v$进行离散化，用两个树状数组，一个按照求逆序数的方式维护小于$v_i$的点的个数，另一个维护目前小于$v_i$的点的初始位置$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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
struct BinaryIndexedsTree
{
    int n;
    ll c[maxn];
    inline int lowbit(int x)
    {
        return x & (-x);
    }
    void build(int *a,int n)//a是原数组,n是元素个数
    {
        this->n=n;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
            add(i,a[i]-a[i-1]);//构建差分c数组
    }
    void add(int k,ll val)//修改:a[k]加上val,直接在c数组上操作
    {
        while(k<=n)
        {
            this->c[k]+=val;
            k+=lowbit(k);
        }
    }
    void range_update(int l, int r, ll val)//区间更新
    {
        add(l,val);//把l之后所有的点都更新一遍
        add(r+1,-val);//因为r之后的点是不用更新的，但是多更新了，所以要每个点都-val；
    }
    ll query(int k)//查询:1~k的区间和
    {
        ll sum=0;
        while(k)
        {
            sum+=this->c[k];
            k-=lowbit(k);
        }
        return sum;
    }
} bit1,bit2;
struct point
{
    ll x,v;
} a[maxn];
vector<ll> mp;
void disc(int n)//对速度进行离散化
{
    for(int i=1;i<=n;i++)
        mp.push_back(a[i].v);
    sort(mp.begin(),mp.end());
    mp.erase(unique(mp.begin(),mp.end()),mp.end());
}
ll id(ll x)
{
    return lower_bound(mp.begin(),mp.end(),x)-mp.begin()+1;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x;
    for(int i=1;i<=n;i++)
        cin>>a[i].v;
    sort(a+1,a+n+1,[](const point &a,const point &b){
            return a.x<b.x;//按x排序
        });//返回小于vi的数量,以及符合的点的x和
    disc(n);//对速度进行离散化
    ll ans=0;
    bit1.n=bit2.n=n;
    for(int i=1;i<=n;i++)
    {
        int now=id(a[i].v);
        ans+=a[i].x*bit1.query(now)-bit2.query(now);
        bit1.add(now,1);//逆序数的求法
        bit2.add(now,a[i].x);//按v的大小次序求一个x前缀和...
    }
    cout<<ans<<endl;
    return 0;
}