Codeforces Round #582 (Div. 3)

A. Chip Moving

题目链接：http://codeforces.com/contest/1213/problem/A

题意：给你一些数字，然后你拥有两个操作

①：把每个数+2 或者 -2 需要的花费为0

②：把每个数+1 或者 -1 需要的花费为1 money

问将所有数字都变为同一数字最少需要花费多少money

分析:

任何奇数经过N次 +2 或者 -2 之后都可以使它的值变为1

任何偶数经过N次 +2 或者 -2之后都可以使它的值变为0

所以我们把所有数都 % 2，然后统计奇数的个数和偶数的个数

如果奇数>偶数我们只要再把所有偶数+1变成奇数即可，如果偶数>奇数，同理

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define inf 0x3f3f3f
 5 template<class T> void read(T &x) {
 6 x=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
 7 while(isdigit(ch))x=x*10+ch-'0',ch=getchar();}
 8 const int N = 1e3+10;
 9 ll a[N];
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     int n;
14     while(cin>>n)
15     {
16         int ou = 0;
17         int ji = 0;
18         for(int i=1;i<=n;i++)
19         {
20             cin>>a[i];
21             if(a[i]%2==0)
22             ou++;
23             else ji++;
24         }
25         if(ou>ji)
26         cout<<ji<<endl;
27         else cout<<ou<<endl;
28     } 
29     return 0;
30 }
31  
32

View Code

B. Bad Price

题目链接：http://codeforces.com/contest/1213/problem/B

题意：给你一个无序数组，对于数组中的每一个元素，如果它的右边存在比它小的数，则它对答案的贡献为1

如果不存在，则它对答案的贡献为0 。然后输出所有数的贡献和即可

分析：

使用单调栈（O(n)）寻找第一个小于它的数，将找到的数对应存到一个vector里如果不存在那个数，则在vector里存入-1

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define inf 0x3f3f3f
 5 template<class T> void read(T &x)
 6 {
 7     x=0;
 8     char ch=getchar();
 9     while(!isdigit(ch))ch=getchar();
10     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
11 }
12 const ll N = 1e3+10;
13 vector<ll> get2(vector<ll> a, ll len)
14 {
15     vector<ll> res(len, -1);
16     stack<ll> sta;
17     sta.push(0);
18     for (ll i = 1; i < len; i++)
19     {
20         while (!sta.empty() && a[i]<a[(sta.top())])
21         {
22             res[(sta.top())] = a[i];
23             sta.pop();
24         }
25         sta.push(i);
26     }
27     return res;
28 }
29 vector<ll>a;
30 int main()
31 {
32     ios::sync_with_stdio(false);
33     ll t,n,x;
34     read(t);
35     while(t--)
36     {
37         a.clear();
38         read(n);
39         for(ll i=1; i<=n; i++)
40         {
41             read(x);
42             a.push_back(x);
43         }
44         ll ans = 0;
45         vector<ll> b = get2(a, n);
46         for(ll i=0; i<b.size(); i++)
47         {
48             if(b[i]!=-1)
49                 ans++;
50             //    cout<<b[i]<<"     ";
51         }
52         cout<<ans<<endl;
53     }
54     return 0;
55 }

View Code

C. Book Reading

题目链接：http://codeforces.com/contest/1213/problem/C

题意：给你一个N 和 M，输出从 1 到 N 所有能被 M 整除的数的个位和

分析：

仔细观察这道题我们是能发现规律的：

如果 M 的个位数是奇数，那么它的循环节长度为10 总和为45

如果M 的个位数是偶数，那么它的循环节长度为5 总和为20

但是为了方便写代码我们将偶数的循环节设为10 总和为40

定义length表示循环节的总和，定义cot表示n包含的循环节的个数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define inf 0x3f3f3f
 5 template<class T> void read(T &x)
 6 {
 7     x=0;
 8     char ch=getchar();
 9     while(!isdigit(ch))ch=getchar();
10     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
11 }
12 const int N = 1e3+10;
13 int main()
14 {
15     ios::sync_with_stdio(false);
16     int t;
17     cin>>t;
18     while(t--)
19     {
20         ll n,m;
21         cin>>n>>m;
22         ll cot = n/m;
23         ll sum = 0;
24         ll length = 0;
25         for(int i=1; i<=10; i++)
26             length += i*m%10;
27         sum += length*(cot/10);
28         for(int i=1; i<=cot%10; i++)
29             sum += i*m%10;
30         cout<<sum<<endl;
31     }
32     return 0;
33 }

View Code

D. Equalizing by Division

题目链接：http://codeforces.com/contest/1213/problem/D1

题意：给你一个长度为 n 的数组，和一个 k ，对于数组中的每一个数你可以将它除2任意次，问

最少需要操作多少次使得数组中至少有 k 个数相同

分析：

题目给的 n 的范围是 1 <= n <= 40 ，然后数组中的每个数 ai 范围也是在2e5之下的，所以完全可以暴力解决的

先把每个数不断除2直到0，将每个数除2达到的新的状态（除2后的值）打入对应二维vector里，然后对二维vector从0-2e5排序，最后挨个取minn值就可以了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define inf 0x3f3f3f
 5 template<class T> void read(T &x)
 6 {
 7     x=0;
 8     char ch=getchar();
 9     while(!isdigit(ch))ch=getchar();
10     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
11 }
12 const int N = 2e5+10;
13 ll a[N];
14 ll num[N];
15 ll d[N];
16 ll len[N];
17 vector<int>v[N];
18 bool cmp(ll a,ll b)
19 {
20     return a>b;
21 }
22 int main()
23 {
24     ios::sync_with_stdio(false);
25     int n ,k;
26 cin>>n>>k;
27     {
28     
29         for(int i=1; i<=n; i++)
30         {
31             cin>>a[i];
32             num[a[i]]++;
33         }
34         for(int i=0; i<2e5; i++)
35             if(num[i]>=k) return cout<<0<<endl,0;
36         int ans = 2e9;
37         for(int i =1; i<=n; i++)
38         {
39             d[i] = a[i];
40             int cnt = 1;
41  
42             while(d[i])
43             {
44                 d[i]/=2;
45                 v[d[i]].push_back(cnt);
46                 cnt++;
47             }
48             v[0].push_back(cnt);
49             len [i] = cnt;
50         }
51         for(int i=0;i<=2e5;i++) sort(v[i].begin(),v[i].end());
52         for(int i=0;i<2e5;i++)
53         {
54             int numm = num[i];
55             int cha = k-numm;
56             int Max = 0;
57             int j = 0;
58             while(j<v[i].size()&&cha>0)
59             {
60                 Max += v[i][j++];
61                 cha --;
62             }
63             if(cha<=0)
64             ans = min(ans,Max);
65         }
66         cout<<ans<<endl;
67     }
68     return 0;
69 }

View Code