Codeforces补题2020.2.28（Round624 Div 3)

A.Add Odd or Subtract Even

签到题~

#include<bits/stdc++.h>

using namespace std;

int T;

int a,b;

int main () {

    scanf("%d",&T);

    while (T--) {

        scanf("%d%d",&a,&b);

        if (a==b) {

            printf ("0\n");continue;

        }

        if (a>b&&(a-b)%==) {

            printf ("1\n");continue;

        }

        if (a>b&&(a-b)%==) {

            printf ("2\n");continue;

        }

        if (a<b&&(b-a)%==) {

            printf ("2\n");continue;

        }

        if (a<b&&(b-a)%==) {

            printf ("1\n");continue;

        }

    }

    return ;

}

B.Weired Sort

题意：

给你一个长度为n的数组a。

你还得到一组不同的位置p1，p2，…，pm，其中1≤pi<n。位置pi意味着你可以交换元素a[pi]和a[pi+1]。您可以对每个给定位置应用此操作任意次数。

您的任务是确定是否可以仅使用允许的交换按非递减顺序（a1≤a2≤⋯≤an）对初始数组进行排序。

例如，如果a=[3,2,1]和p=[1,2]，那么我们可以首先交换元素a[2]和a[3]（因为位置2包含在给定的集合p中）。我们得到数组a=[3,1,2]。然后我们交换a[1]和a[2]（位置1也包含在p中）。我们得到数组a=[1,3,2]。最后，我们再次交换a[2]和a[3]，得到数组a=[1,2,3]，按非递减顺序排序。

可以看到，如果a=[4,1,2,3]和p=[3,2]，则无法对数组进行排序。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int a[maxn];

int b[maxn];

int T;

int N,M,K;

int main () {

    scanf("%d",&T);

    while (T--) {

        scanf("%d%d",&M,&N);

        for (int i=;i<=M;i++) scanf("%d",&a[i]);

        for (int i=;i<=N;i++) scanf("%d",&b[i]);

        for (int i=;i<=M;i++) {

            for (int j=;j<=N;j++) {

                if (a[b[j]]>a[b[j]+]) {

                    swap(a[b[j]+],a[b[j]]);

                }

            }

        }

        if (is_sorted(a+,a+M+)) printf ("YES\n");

        else printf ("NO\n");

    }

    return ;

}

C.Perform the Combo

题意：

你想在一个流行的格斗游戏中对你的对手进行连击。组合是由n个小写拉丁字母组成的字符串s。要执行组合，您必须按所有按钮在s中的显示顺序按它们。即，如果s=“abca”，则必须再次按“a”，然后按“b”、“c”和“a”。

你知道你将花费m个错误的尝试来执行组合，在第i次尝试中，你将在第i个按钮之后（1≤pi<n）犯一个错误（即，你将按第一个pi按钮，从一开始就开始执行组合）。可以保证在m+1次尝试中，您正确地按下所有按钮，最后执行组合。

一、 e.如果s=“abca”、m=2和p=[1,3]，则按下的按钮顺序将是“a”（这里您犯了错误，从一开始就开始执行组合）、“a”、“b”、“c”（这里您犯了错误，从一开始就开始执行组合）、“a”（注意，此时您不会因为错误而执行组合），“b”、“c”、“a”。

你的任务是为每个按钮（字母）计算你按下它的次数。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int p[maxn];

char s[maxn];

int pos[maxn][];

int cnt[];

int T;

int N,M;

int main () {

    scanf("%d",&T);

    while (T--) {

        memset(cnt,,sizeof(cnt));

        scanf("%d%d",&N,&M);

        scanf("%s",s);

        for (int i=;i<=M;i++)

            scanf("%d",&p[i]);

        p[++M]=N;

        for (int i=;i<=;i++)

            pos[][i]=;

        pos[][s[]-'a'+]++;

        for (int i=;i<N;i++) {

            for (int j=;j<=;j++)

                pos[i][j]=pos[i-][j];

            pos[i][s[i]-'a'+]++;

        }

        for (int i=;i<=M;i++) {

            for (int j=;j<=;j++) {

                cnt[j]+=pos[p[i]-][j];

            }

        }

        for (int i=;i<=;i++)

            printf ("%d ",cnt[i]);

        printf ("\n");

    }

    return ;

}

D.Three Integers

题意：

给你三个整数a≤b≤c。

在一次移动中，您可以将+1或-1添加到这些整数中的任何一个（即，将任意数字增加或减少一个）。您可以执行这样的操作任意（可能为零）次，甚至可以使用一个数字执行此操作多次。注意，使用这种操作不能生成非正数。

为了得到三个整数A≤B≤C，使B可被A整除，C可被B整除，必须执行这样的操作的最小数目。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

const int inf=1e9;

int N;

int main () {

    int T;

    int a,b,c;

    scanf("%d",&T);

    while (T--) {

        scanf("%d%d%d",&a,&b,&c);

        int mmin=inf;

        int A,B,C;

        for (int i=;i<=;i++)

            for (int j=i;j<=;j+=i)

                for (int k=j;k<=;k+=j) {

                    int tmp=abs(a-i)+abs(b-j)+abs(c-k);

                    if (tmp<mmin) {

                        mmin=tmp;

                        A=i;

                        B=j;

                        C=k;

                    }

                }

        printf ("%d\n",mmin);

        printf ("%d %d %d\n",A,B,C);

    }

    return ;

}

E.Construct the Binary Tree

题意：

给定两个整数n和d，需要构造一个由n个顶点组成的有根二叉树，顶点1有根，所有顶点的深度之和等于d。

树是没有圈的连通图。有根树有一个特殊的顶点叫做根。顶点v的父顶点是从根到顶点v的路径上最后一个不同于v顶点的顶点。顶点v的深度是从根到顶点v的路径的长度。顶点v的子顶点是所有v为父顶点的顶点。二叉树是这样一棵树，没有一个顶点有超过2个子节点。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int T;

int N;

int d;

int father[maxn];

int dep[maxn];

int a[maxn];

int ans;

int visit[maxn];

int main () {

    scanf("%d",&T);

    while (T--) {

        scanf("%d%d",&N,&d);

        int mmax=;

        a[]=;

        for (int i=;i<=N;i++) {

            father[i]=i/;

            dep[i]=dep[father[i]]+;

            d-=dep[i];

            mmax=max(mmax,dep[i]);

        }

        if (d<) {

            printf ("NO\n");

            continue;

        }

        for (int i=;i<=N;i++) visit[i]=;

        int tn=N;

        while (tn) {

            a[dep[tn]]=tn;

            visit[tn]=;

            tn=father[tn];

        }

        for (int i=N;i>=;i--) {

            if (visit[i]) continue;

            int pre=mmax;

            while (dep[father[i]]<pre&&d) {

                father[i]=a[dep[father[i]]+];

                dep[i]=dep[father[i]]+;

                if (dep[i]>mmax) {

                    mmax++;

                    a[mmax]=i;

                    visit[i]=;

                }

                d--;

            }

        }

        if (d) {

            printf ("NO\n");

            continue;

        }

        printf ("YES\n");

        for (int i=;i<=N;i++) printf ("%d ",father[i]);

        printf ("\n");

    }

    return ;

}

F.Moving Points

题意：

坐标轴上有N个点，第i个点位于整数点席，具有速度VI。保证两个点不占用同一个坐标。所有n个点以恒定速度移动，第i个点在时刻t（t可以是非整数）的坐标计算为xi+t⋅vi。

考虑两点i和j。设d（i，j）为这两点在任何可能的时间矩（甚至非整数）上的最小可能距离。这意味着，如果两个点i和j在某个时刻重合，则值d（i，j）将为0。

你的任务是计算∑1≤i<j≤n d（i，j）（所有点对上的最小距离之和）。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

typedef long long ll;

int lowbit (int x) {

    return x&-x;

}

int N;

ll c1[maxn];

ll c2[maxn];

int v1[maxn];

int v2[maxn];

int x1[maxn];

int x2[maxn];

int sa[maxn];

bool cmp1 (int a,int b) {

    return x1[a]<x1[b];

}

bool cmp2 (int a,int b) {

    return v2[a]<v2[b]||(v2[a]==v2[b]&&x2[a]<x2[b]);

}

void add (int p,ll v) {

    for (;p<=N;p+=lowbit(p)) {

        c1[p]++;

        c2[p]+=v;

    }

}

pair<ll,ll> getSum (int p) {

    ll ans1=;

    ll ans2=;

    for (;p;p-=lowbit(p)) {

        ans1+=c1[p];

        ans2+=c2[p];

    }

    return make_pair(ans1,ans2);

}

int main () {

    scanf("%d",&N);

    for (int i=;i<=N;i++) {

        scanf("%d",&x1[i]);

        sa[i]=i;

    }

    for (int i=;i<=N;i++) scanf("%d",&v1[i]);

    sort (sa+,sa+N+,cmp1);

    for (int i=;i<=N;i++) {

        v2[i]=v1[sa[i]];

        x2[i]=x1[sa[i]];

        sa[i]=i;

    }

    sort (sa+,sa+N+,cmp2);

    ll ans=;

    for (int i=;i<=N;i++) {

        pair<ll,ll> res=getSum(sa[i]-);

        ans+=res.first*x2[sa[i]]-res.second;

        add(sa[i],x2[sa[i]]);

    }

    printf ("%lld\n",ans);

    return ;

}

巴特西

Codeforces补题2020.2.28（Round624 Div 3)

最新文章

热门文章