Codeforces Round 582 (Div. 3)

比赛链接： Codeforces Round #582 (Div. 3)

比赛时候就写出来两道题，还有一道是py的，赛后又补了三题。剩下的也要补，一定要补！！！

A Chips Moving

description:
You are given n chips on a number line. The i-th chip is placed at the integer coordinate xi. Some chips can have equal coordinates.

You can perform each of the two following types of moves any (possibly, zero) number of times on any chip:

Move the chip i by 2 to the left or 2 to the right for free (i.e. replace the current coordinate xi with xi−2 or with xi+2);
move the chip i by 1 to the left or 1 to the right and pay one coin for this move (i.e. replace the current coordinate xi with xi−1 or with xi+1).
Note that it's allowed to move chips to any integer coordinate, including negative and zero.

Your task is to find the minimum total number of coins required to move all n chips to the same coordinate (i.e. all xi should be equal after some sequence of moves).

Input
The first line of the input contains one integer n (1≤n≤100) — the number of chips.

The second line of the input contains n integers x1,x2,…,xn (1≤xi≤1e9), where xi is the coordinate of the i-th chip.

Output
Print one integer — the minimum total number of coins required to move all n chips to the same coordinate.

Examples
input
3
1 2 3
output
1
input
5
2 2 2 3 3
output
2
Note
In the first example you need to move the first chip by 2 to the right and the second chip by 1 to the right or move the third chip by 2 to the left and the second chip by 1 to the left so the answer is 1.

In the second example you need to move two chips with coordinate 3 by 1 to the left so the answer is 2.

Problem solving:
这道题的意思就是给你一组数，然后给了你两种变换方式，一种是当前数加二或者减二，这种变换方式是免费的。一种是当前数加一或者减一，这种变换方式需要支付一个货币。问你这组数全部变换成一样的数最少需要多少货币。

我们注意到加二减二是免费的，所以只要这个用的是能用的最多的，那就一定能得到最少需要的货币。不管是奇数还是偶数，加二减二之后奇偶性不变。所以我们可以记录一下奇数和偶数的个数，让比较多的一类数通过加减二来变换，然后另一类通过加减一变成另一种类型的数。（奇数变偶数，偶数变奇数），所以我们只要取奇数数量和偶数数量的最小值，就是答案。

code:

#include<bits/stdc++.h>
using namespace std;
const long long maxn = 105;
long long a[maxn];
int main()
{
    long long n,ans=0,os=0,x;
    cin>>n;
    for(long long i=0;i<n;i++)
    {
        cin>>x;
        if(x%2==0)    ans++;
        else    os++;
    }
    cout<<min(ans,os)<<endl;
}

B Bad Prices

description:
Polycarp analyzes the prices of the new berPhone. At his disposal are the prices for n last days: a1,a2,…,an, where ai is the price of berPhone on the day i.

Polycarp considers the price on the day i to be bad if later (that is, a day with a greater number) berPhone was sold at a lower price. For example, if n=6 and a=[3,9,4,6,7,5], then the number of days with a bad price is 3 — these are days 2 (a2=9), 4 (a4=6) and 5 (a5=7).

Print the number of days with a bad price.

You have to answer t independent data sets.

Input
The first line contains an integer t (1≤t≤10000) — the number of sets of input data in the test. Input data sets must be processed independently, one after another.

Each input data set consists of two lines. The first line contains an integer n (1≤n≤150000) — the number of days. The second line contains n integers a1,a2,…,an (1≤ai≤1e6), where ai is the price on the i-th day.

It is guaranteed that the sum of n over all data sets in the test does not exceed 150000.

Output
Print t integers, the j-th of which should be equal to the number of days with a bad price in the j-th input data set.
Example
input
5
6
3 9 4 6 7 5
1
1000000
2
2 1
10
31 41 59 26 53 58 97 93 23 84
7
3 2 1 2 3 4 5
output
3
0
1
8
2

Problem solving:
(这道题我一开始没看懂意思，后来懂了，我太难了
题意就是给你一组数，如果当前的数比它后面的每一个数都要小，那么这个数就不是bad price。反之就是。问你bad price的个数。

所以我们只需要判断如果当前数不是从它开始到最后的数中的最小值，那么它就是bad price，答案加一。
这里需要构建一个后缀最小值数组。注意要从后往前构造。

code:

#include<bits/stdc++.h>
using namespace std;
const long long maxn = 150005;
long long a[maxn],b[maxn];
int main()
{
    long long n,m;
    cin>>n;
    while(n--)
    {
        long long ans=0;
        cin>>m;
        for(long long i=0;i<m;i++)
        {
            cin>>a[i];
        }
        for(long long i=m-1;i>=0;i--)
        {
            if(i==m-1)    b[i]=a[i];
            else    b[i]=min(b[i+1],a[i]);
        }
        for(long long i=0;i<m;i++)
        {
            if(a[i]!=b[i])    ans++;
        }
        cout<<ans<<endl;
    }
}

C Book Reading

description:
Polycarp is reading a book consisting of n pages numbered from 1 to n. Every time he finishes the page with the number divisible by m, he writes down the last digit of this page number. For example, if n=15 and m=5, pages divisible by m are 5,10,15. Their last digits are 5,0,5 correspondingly, their sum is 10.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer q independent queries.

Input
The first line of the input contains one integer q (1≤q≤1000) — the number of queries.

The following q lines contain queries, one per line. Each query is given as two integers n and m (1≤n,m≤1016) — the number of pages in the book and required divisor, respectively.

Output
For each query print the answer for it — the sum of digits written down by Polycarp.

Example
input
7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13
output
1
45
153
294
3359835
0
427262129093995

Problem solving:
这道题的意思就是给你两个数n,m,让你求在1~n内的m的倍数的个位上的数字的和。
先说一下我的思路吧。因为我们只需要考虑个位，所以无论m是多少，只考虑它的个位就行，因为个位上的数也就从0-9有十种情况。并且每一个数加几次之后就会从头开始，这是个循环。所以可以先把0~9的情况列出来，然后你会发现只需要分四种情况讨论

0   0
1   1 2 3 4 5 6 7 8 9 0 1
2   2 4 6 8 0 2
3   3 6 9 2 5 8 1 4 7 0 3
4   4 8 2 6 0 4
5   5 0 5
6   6 2 8 4 0 6
7   7 4 1 8 5 2 9 6 3 0 7
8   8 6 4 2 0 8
9   9 8 7 6 5 4 3 2 1 0 9

四种情况也就是

1. m的个位是0，此时答案就是0
2. m的个位是5，此时循环长度是2，并且每一个循环的总和是5
3. m的个位是除了上面几种情况的偶数，此时循环长度是5，并且每一个循环的总和是20
4. m的个位是除了上面几种情况的奇数，此时循环长度是10，并且每一个循环的总和是45

然后就是代码

code:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll ans=0;
        ll n,m;
        cin>>n>>m;
        if(m%10==0)    ans=0;
        else if(m%10==5)
        {
            n/=m;
            ans+=(n/2)*5;
            n%=2;
            ll mid=m%10;
            for(ll i=0;i<n;i++)
            {
                ans+=mid;
                mid=(mid+m%10)%10;
            }
        }
        else if(m%10%2==0)
        {
            n/=m;
            ans+=(n/5)*20;
            n%=5;
            ll mid=m%10;
            for(ll i=0;i<n;i++)
            {
                ans+=mid;
                mid=(mid+m%10)%10;
            }
        }
        else if(m%10%2==1)
        {
            n/=m;
            ans+=(n/10)*45;
            n%=10;
            ll mid=m%10;
            for(ll i=0;i<n;i++)
            {
                ans+=mid;
                mid=(mid+m%10)%10;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

然后说一下川巨的办法，顺便说一下。川巨是真的强。
因为是个位，所以只要这个数加10次，个位就一定会出现至少一次循环。所以以10为循环节的长度。先算出来m个位的10次循环每次的值，并且求出来总和。然后算出n里面有几个m，也就是总个数。然后再除以10就是循环节的个数，乘以循环的总和。然后再算n/m%10之后的多余的那一部分的值，因为上面计算的时候也一起存了下来所以直接用就行。
再说一下，川巨是真的强。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100];
int main()
{
    ios::sync_with_stdio(false);
    int t;
    ll n,m;
    cin>>t;
    while (t --)
    {
        cin>>n>>m;
        ll ans = 0,cnt = 0;
        for (int i = 1;i <= 10;i ++)
            a[i] = m*i%10,cnt += a[i];
        n /= m;
        ans = n/10*cnt;
        for (int i = 1;i <= n%10;i ++) ans += a[i];
            cout<<ans<<'\n';
    }
    return 0;
}

D Equalizing by Division

description:
The only difference between easy and hard versions is the number of elements in the array.

You are given an array a consisting of n integers. In one move you can choose any ai and divide it by 2 rounding down (in other words, in one move you can set ai:=⌊ai2⌋).

You can perform such an operation any (possibly, zero) number of times with any ai.

Your task is to calculate the minimum possible number of operations required to obtain at least k equal numbers in the array.

Don't forget that it is possible to have ai=0 after some operations, thus the answer always exists.

Input
The first line of the input contains two integers n and k (1≤k≤n≤2⋅1e5) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤2⋅1e5), where ai is the i-th element of a.

Output
Print one integer — the minimum possible number of operations required to obtain at least k equal numbers in the array.

Examples
input
5 3
1 2 2 4 5
output
1
input
5 3
1 2 3 4 5
output
2
input
5 3
1 2 3 3 3
output
0

我懒得写公式，题意不太对的地方可以看截图

Problem solving:
这道题的意思就是给你两个数n和k，n是数组的长度，问你能不能在这n个数中经过变换让里面出现k个相等的数，变化的方式是每次除以2.问你最小的变换次数。

这道题我是没什么思路的。然后看了下Codancer的代码。Orz。Codancer太强了。

首先要思考一下，每个数除以2，比如说16，8都能变成2，但是16需要3次，而8只需要2次。所以我们要先按照升序排个序。
然后遍历数组中的元素，模拟当前数除以2知道除到0的时候，并且累计每次出现的数的出现次数，以及出现这个数需要的变换次数。因为我们已经按照大小排了序，所以当前得到的一定是当前的最小值。如果一个数的出现次数大于等于k，那么答案就需要更新一个成最小值，用min即可。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int a[maxn];
int main()
{
    int n,k,ans=0x3f3f3f3f;
    cin>>n>>k;
    for(int i=0;i<n;i++)    cin>>a[i];
    map<int,int> ma;//用来标记每个数的出现次数
    map<int,int> maa;//用来标记转换到当前数需要的次数（局部的
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        int cnt=0;//cnt记录的就是转换次数
        int mid=a[i];
        while(mid)
        {
            ma[mid]++;maa[mid]+=cnt;
            if(ma[mid]>=k)  ans=min(ans,maa[mid]);//如果出现了出现次数大于等于k的数，更新答案
            mid/=2;
            cnt++;
        }
    }
    cout<<ans<<endl;
}