Codeforces Round #582 (Div. 3)

港控/mmm° 2023-06-01 11:14 33阅读 0赞

链接：[http://codeforces.com/contest/1213][http_codeforces.com_contest_1213]

A. Chips Moving

思路：+2免费代表奇偶性一样的免费，那么只要求奇变成偶的少还是偶变成奇的少就行。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn = 105;
     4 int num[2];
     5 int main()
     6 {
     7     std::ios::sync_with_stdio(false);
     8     int n;
     9     cin >> n;
    10     int a;
    11     for(int i = 0;i < n;i++)
    12     {
    13         cin >> a;
    14         num[a%2]++;
    15     }
    16     cout << min(num[1], num[0]) << endl;
    17     return 0;
    18 }

--------------------

B. Bad Prices

思路：倒过来维护最小值，大于最小值的都是bad。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn = 2e5;
     4 int a[maxn];
     5 int main()
     6 {
     7     std::ios::sync_with_stdio(false);
     8     int t;
     9     cin >> t;
    10     while(t--)
    11     {
    12         int n;
    13         cin >> n;
    14         for(int i = 0; i < n;i++) cin >> a[i];
    15         int ans =  0;
    16         int mi = a[n - 1];
    17         for(int i = n - 1;i >= 0;i--){
    18                 if(a[i] > mi) ans++;
    19                 else mi = a[i];
    20         }
    21         cout << ans << endl;
    22     }
    23     return 0;
    24 }

--------------------

C. Book Reading

思路：m的个位数是奇数的10个一循环，循环的总和是10，偶数5个一循环，循环和为20，特判0和5即可。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn = 2e5;
     5 int main()
     6 {
     7     std::ios::sync_with_stdio(false);
     8     int t;
     9     cin >> t;
    10     while(t--)
    11     {
    12         ll n, m;
    13         cin >> n >> m;
    14         ll id = m%10;
    15         ll sum = n / m;
    16         if(id  % 2 == 0)
    17         {
    18             if(id == 0) {cout << 0 << endl;continue;}
    19             ll ans = sum / 5LL * 20LL;
    20             for(ll i = 1;i <= sum%5LL;i++){
    21                 ans += (id * i)%10;
    22             }
    23             cout << ans << endl;
    24         }
    25         else {
    26             if(id == 5){
    27                 cout << (sum / 2 + sum%2) * 5LL << endl;
    28                 continue;
    29             }
    30             ll ans = sum / 10LL * 45LL;
    31             for(ll i = 1;i <= sum%10LL;i++){
    32                 ans += (id * i)%10;
    33             }
    34             cout << ans << endl;
    35         }
    36     }
    37     return 0;
    38 }

--------------------

D. Equalizing by Division

思路：贪心 ，从小到大遍历把每个数算出到0的步数（不断除以2），每到一个数给那个数字的个数加一，然后如果那个数字的个数等于K了就更新最小值

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn = 2e5 + 50;
     5 const int INF = 0x3f3f3f3f;
     6 int a[maxn];
     7 int num[maxn];
     8 int ans[maxn];
     9 int main()
    10 {
    11     std::ios::sync_with_stdio(false);
    12     int n, k;
    13     cin >> n >> k;
    14     for(int i = 0;i < n;i++) {
    15         cin >> a[i];
    16     }
    17     sort(a, a + n);
    18     int sum = INF;
    19     for(int i = 0;i < n;i++){
    20         int t = a[i];
    21         int cnt = 1;
    22         while(t){
    23             num[t]++;
    24             if(num[t] == k){
    25                 sum = min(ans[t],sum);
    26             }
    27             t /= 2;
    28             ans[t] += cnt++;
    29         }
    30     }
    31     cout << sum << endl;
    32     return 0;
    33 }

--------------------

E. Two Small Strings

思路：全排列abc的所有组合，易知排列需满足abcabcabc...abc这样的或者是a...ab...bc...c,这样的（抱歉没看出来..），在所有组合中搜索不存在S和T的字符串即可。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int main()
     5 {
     6     std::ios::sync_with_stdio(false);
     7     int n;
     8     string s, t;
     9     cin >> n >> s >> t;
    10     string sum = "abc";
    11     vector<string> v;
    12     do{
    13         string ans;
    14         for(int i = 0;i < n;i++) ans += sum;
    15         v.push_back(ans);
    16         v.push_back(string(n,ans[0]) + string(n,ans[1]) + string(n,ans[2]));
    17     }
    18     while(next_permutation(sum.begin(),sum.end()));
    19     for(auto i : v)
    20     {
    21         if(i.find(s) == string::npos && i.find(t) == string::npos){
    22             cout<< "YES" << endl;
    23             cout << i << endl;
    24             return 0;
    25         }
    26     }
    27     cout << "NO" << endl;
    28     return 0;
    29 }

转载于:https://www.cnblogs.com/Carered/p/11437778.html

[http_codeforces.com_contest_1213]: http://codeforces.com/contest/1213
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/b595d14a19e64e59a9ccb153682f6fef.png