Codeforces Round 582

这次比赛看着是Div.3就打了，没想到还是被虐了，并再次orz各位AK的大神……

A. Chips Moving

签到题。（然而签到题我还调了20min……）
因为数据小，所以像我一样打模拟也可以，但其实只要统计一下奇数偶数的个数并输出较小的一个即可。

#include<bits/stdc++.h>

using namespace std;

int n;
long long ans=0x3f3f3f3f;
int a[110];

void Read() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    return;
}

int main()
{
    Read();
    for(int i=1;i<=n;i++) {
        long long tmp=0;
        for(int j=1;j<=n;j++) {
            if(abs(a[j]-i)%2==1) {
                tmp++;
            }
        }
        ans=min(ans,tmp);
    }
    printf("%lld",ans);
    return 0;
}

B. Bad Prices

（题目中的Polycarp真是太有经济头脑了，自己作为买家还希望卖家不要亏本……）
这道题本来也想来个暴力模拟，结果第一次提交成功在第三个点上T掉；后来优化了一下数组，第二次提交还是第三个点T掉。后来想到只要维护一个后缀最小值数组，即从最后一天到第\(n\)天中价格的最小值。若第\(n\)天的价格大于第\(n\)天的后缀最小值，那就是一个"Bad Price"。

#include<bits/stdc++.h>

using namespace std;

int t,n,ans;
int a[150010],pre[150010];

void Init() {
    n=0;
    ans=0;
    memset(a,0,sizeof(a));
    memset(pre,0x7f,sizeof(pre));
    return;
}

void Read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    return;
}

void findMin() {
    for(int i=n;i>=1;i--) {
        pre[i]=min(pre[i+1],a[i]);
    }
    return;
}

void Solve() {
    for(int i=1;i<=n;i++) {
        if(a[i]>pre[i]) {
            ans++;
        }
    }
    printf("%d\n",ans);
    return;
}

int main()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++) {
        Init();
        Read();
        findMin();
        Solve();
    }
    return 0;
}

C. Book Reading

这题只用统计\(m\)倍数的个位数字之和，继续打模拟，结果连样例都跑不出来……
一看样例：

1234312817382646 13

顿时醒悟……当\(n\)远大于\(m\)时，\(n\div m\)的值会很大，以至于1s根本跑不完。
于是我就在这卡了将近1h……（在此期间尝试调了下D1，结果发现根本没思路）
在临近比赛结束前15min，忽然灵光一闪，既然只统计个位数字，取值就只有\(0\)-\(9\)共十种，那为什么不……打表呢？
于是经过一番简单的运算，这道题就……A了。

#include<bits/stdc++.h>

using namespace std;

int q,lownum;
long long n,m,ans;

int main()
{
    scanf("%d",&q);
    for(int i=1;i<=q;i++) {
        ans=0;
        long long div=0,mod=0;
        scanf("%lld%lld",&n,&m);
        div=n/m;
        mod=div%10;
        div-=mod;
        div/=10;
        switch(m%10) {
            case 0:
                ans=0;
                break;
            case 1:
                ans=div*45;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*1)%10;
                }
                break;
            case 2:
                ans=div*40;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*2)%10;
                }
                break;
            case 3:
                ans=div*45;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*3)%10;
                }
                break;
            case 4:
                ans=div*40;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*4)%10;
                }
                break;
            case 5:
                ans=div*25;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*5)%10;
                }
                break;
            case 6:
                ans=div*40;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*6)%10;
                }
                break;
            case 7:
                ans=div*45;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*7)%10;
                }
                break;
            case 8:
                ans=div*40;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*8)%10;
                }
                break;
            case 9:
                ans=div*45;
                for(int j=1;j<=mod;j++) {
                    ans+=(j*9)%10;
                }
                break;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

当然还是要提一下正解的思路的。
令\(k=[\frac nm]\)是从\(1\)到\(n\)的整数个数，可被\(m\)整除。我们可以注意到，因为我们只记下每个可被\(m\)整除的数字的最后一位数字，所以数字“周期”的长度不超过\(10\)。事实上，我们总是可以假设它是\(10\)，因为对于从0到9的所有\(i\)，都有\(i\times m\equiv(10+i)\times m\ (mod\ 10)\)。所以对于从\(0\)到\(9\)的所有\(i\)，使\(cycle_i=m\times (i+1)\ mod\ 10\)，然后答案是\([\frac k{10}]\sum_{i=0}^9cycle_i+\sum_{i=0}^{k\ mod\ 10}cycle_i\).

D. Equalizing by Division

这题就是分为两个难度，我调了一下easy的，但发现思路基本是错的，然后就放弃了……
至于Hard的……就以后再说吧。

E. Two Small Strings

F. Unstable String Sort

G. Path Queries

总之，以后还是要多刷题，多打比赛，多多听从老师教诲……

Codeforces Round 582

原文：https://www.cnblogs.com/luoshui-tianyi/p/11437770.html