Codeforces Round 925 Div. 3 题解

发表于 更新于 分类于 ，

题目链接：https://codeforces.com/contest/1931

A. Recovering a Small String

难度：800

将a记为1，b记为2，以此类推。给出一个3-78之间的一个数，求出一个字典序最小的3个字母，使得这3个字母相加等于给定的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int t,x,a,b,c;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI x;
        F(i,1,26)
            F(j,1,26)
                F(k,1,26)
                    if (i+j+k==x)
                    {
                        cout<<(char)(i-1+'a')<<(char)(j-1+'a')<<(char)(k-1+'a')<<endl;
                        goto l;
                    }
        l:
        x++;   
    }
    return 0;
}

B. Make Equal

难度：800

给出一个数组，数组的每个数都可以分一部分给后面的数，问最后是否能够让每个数都相等。

先求出数组的总和并求出平均值，从头遍历数组，同时用一个变量x记录当前数字加x后比均值多出多少，然后将x加上当前数字并减去均值，如果图中出现变量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
int t,a[200005],sum,n,avg,x,f;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        sum=x=0;
        f=1;
        CI n;
        F(i,1,n)
        {
            CI a[i];
            sum+=a[i];
        }
        avg=sum/n;
        F(i,1,n)
        {
            if (a[i]+x>=avg) x=a[i]+x-avg;
            else
            {
                f=0;
                break;
            }
        }
        if (f) CO "YES" L;
        else CO "NO" L;
    }
    return 0;
}

C. Make Equal Again

难度：1000

给出一个数组，修改这些数组中的连续的一串数，使得数组中每个数都相等，求出最小的修改数量。

为了得到最小的修改数量，可以分别求出这组数中开头和结尾相同值有多少，如果开头和结尾相等，则用总长度减去开头和结尾相等值的长度；否则用总长度减去开头和结尾中较长的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int t,n,a[200005];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n;
        F(i,1,n)
            CI a[i];
        int l1=a[1],l2=1,r1=a[n],r2=1;
        F(i,2,n)
            if (a[i]==l1) l2++;
            else break;
        FD(i,n-1,1)
            if (a[i]==r1) r2++;
            else break;
        if (l1==r1) CO max(0,n-l2-r2) L;
        else CO min(n-l2,n-r2) L;
    }
    return 0;
}

D. Divisible Pairs

难度：1300

找到题目中要求的数组，需要找出在前面中是否存在一个数满足(x-a%x)%x，a%y。

用一个字典，键为pair，存储的是(a%x,a%y），值为当前pair出现的次数。如果能找到((x-a%x)%x,a%y)，则将ans加上该键对应的值。然后将当前数(a%x,a%y)加入到字典中，如果已存在，则将值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LL t,n,x,y,a,ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        ans=0;
        map<pair<LL,LL>,int> s;
        CI n>>x>>y;
        F(i,1,n)
        {
            CI a;
            if (s.find(make_pair((x-a%x)%x,a%y))!=s.end()) ans+=s.find(make_pair((x-a%x)%x,a%y))->second;
            if (s.find(make_pair(a%x,a%y))!=s.end()) s[make_pair(a%x,a%y)]++;
            else s.insert(make_pair(make_pair(a%x,a%y),1));
        }
        CO ans L;
    }
    return 0;
}