首页 > > 程序设计 > C/C++ >

Codeforces Round #617 (Div. 3)

2020-02-10 16:00:47来源：博客园阅读 ()

Codeforces Round #617 (Div. 3)

A	B	C	D	E1	E2	F
\(\checkmark\)	\(\checkmark\)	\(O\)	\(O\)	\(O\)	\(O\)	\(\times\)

\(\checkmark\)：代表比赛时通过。

\(O\)：代表赛后补题通过。

\(\times\)：代表目前还未通过。

A. Array with Odd Sum

题目链接

题目大意

给你一个大小为\(n\)的数组\(a\)，每次操作可以选择两个下标\(i,j\)(\(1\le i,j \le n\)，\(i\ne j\))，使得\(a[i]=a[j]\)，问进行有限次数的操作是否能使数组的和为奇数。

解题思路

分别计数数组当中奇数和偶数的个数，会有以下几种情况：

只有偶数，那么这种情况下一定是不可以的。
只有奇数，如果数组的大小为偶数，那么和不可能为奇数；反之，则可以。
既有奇数，也有偶数，这种情况一定是可以的。

AC代码1

#include<bits/stdc++.h>
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int a[maxn];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        bool flag1=false,flag2=false;
        for(int i=0;i<n;i++){
            if(a[i]%2==1){
                flag1=true;
            }else if(a[i]%2==0){
                flag2=true;
            }
        }
        if(!flag1){
            cout<<"NO"<<endl;
        }else {
            if(flag2){
                cout<<"YES"<<endl;
            }else{
                if(n%2==0){
                    cout<<"NO"<<endl;
                }else{
                    cout<<"YES"<<endl;
                }
            }
        }
    }
    return 0;
}

AC代码2

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int sum = 0;
        bool odd = false, even = false;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            sum += x;
            odd |= x % 2 != 0;
            even |= x % 2 == 0;
        }
        if (sum % 2 != 0 || (odd && even)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    
    return 0;
}

总结

这道题就是一道思维题，没有什么可说的，思维角度不一定相同，但一定尽可能的考虑全面。

B. Food Buying

题目链接

题目大意

手里总共有\(s\)元，去超市买价格为\(x\)(\(1\le x \le s\))的商品，会优惠\(\lfloor \frac x{10} \rfloor\)元，其中\(\lfloor \frac x {10} \rfloor\)为向下取整，问最多消费多少元。

解题思路

贪心思想，因为优惠是向下取整的，那么个位数会丢掉，所有\(x\)为\(10\)的倍数时，能够消费最多。

AC1代码

#include<bits/stdc++.h>
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int s;
        cin>>s;
        ll res=0;
        while(s>=10){
            res+=s/10*10;
            s=s-s/10*10+s/10;
        }
        cout<<res+s<<endl;
    }
    return 0
}

AC代码2

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        int s;
        cin >> s;
        int ans = 0;
        int pw = 1000 * 1000 * 1000;
        while (s > 0) {
            while (s < pw) pw /= 10;
            ans += pw;
            s -= pw - pw / 10;
        }
        cout << ans << endl;
    }
    
    return 0;
}

总结

简单的贪心思维题。

C. Yet Another Walking Robot

题目链接

题目大意

给你一个只包含“\(L,R,U,D\)”的字符串机器指令，其中\(L\)代表向左移动，\(R\)代表向右移动，\(U\)代表向上移动，\(D\)代表向下移动，其中在二维坐标原点\((0,0)\)开始执行机器指令，求字符串能删除的最短子串的下标以达到机器最终到达的二维坐标点不变。

解题思路

暴力。遍历一遍，\(pair\)存下每次到达的二维坐标点，\(map\)存下对应二维坐标的数组下标并担当查询是否出现过的功能。

AC代码1

/*
    C题补题
*/
#include<bits/stdc++.h>
#define p pair<int,int>
#define fre(x) freopen(x,"r",stdin)
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main()
{
    int t;
    // fre("data.txt");
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string str;
        cin>>str;
        map<p,int>mp;
        //初始化位置
        mp[make_pair(0,0)]=0;
        int x=0,y=0;
        p ans=make_pair(1,1e9);
        for(int i=0;i<str.size();i++){
            if(str[i]=='L')x--;
            else if(str[i]=='R')x++;
            else if(str[i]=='U')y++;
            else if(str[i]=='D')y--;
            if(mp.find(make_pair(x,y))!=mp.end()){
                int l=mp[make_pair(x,y)],r=i+1;
                if(r-l<ans.second-ans.first){
                    ans=make_pair(l,r);
                }
            }
            mp[make_pair(x,y)]=i+1;
        }
        if(ans.second!=1e9){
            cout<<ans.first+1<<" "<<ans.second<<endl;
        }else cout<<"-1"<<endl;
    }
}

AC代码2

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        int l = -1, r = n;
        map<pair<int, int>, int> vis;
        pair<int, int> cur = {0, 0};
        vis[cur] = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'L') --cur.first;
            if (s[i] == 'R') ++cur.first;
            if (s[i] == 'U') ++cur.second;
            if (s[i] == 'D') --cur.second;
            if (vis.count(cur)) {
                if (i - vis[cur] + 1 < r - l + 1) {
                    l = vis[cur];
                    r = i;
                }
            }
            vis[cur] = i + 1;
        }
        if (l == -1) {
            cout << -1 << endl;
        } else {
            cout << l + 1 << " " << r + 1 << endl;
        }
    }
    
    return 0;
}

总结

比赛的时候没能想到这道题的解法，尤其是如何去找已经出现过的点。

D. Fight with Monsters

题目链接

题目大意

有\(n\)只怪兽，每个怪兽\(i\)都有一个生命值\(h_i\)，你的攻击值是\(a\),对手的攻击值是\(b\)，对于每一只怪兽，自己先发起攻击，然后对手攻击，若当前怪兽被自己打死，那么加\(1\)分，移动到下一个怪兽。自己有\(k\)次特权，每次特权都可以让对手当前的攻击对怪兽无效，问自己最多可以得多少分。

解题思路

如果当前怪兽的值对两个攻击者的攻击值取余：

若余数小于\(a\)且不为\(0\)，那么不用特权都可以得分，移动到下一个怪兽。
若余数为\(0\)，则当怪兽剩余生命值为\(b\)时，将其值扔到一个数组当中。
若余数不为\(0\)且大于\(a\)，将余数扔到数组当中。

对数组进行排序，贪心策略使用特权\(k\)已达到得分最多。

AC代码1

#include<bits/stdc++.h>
#define p pair<int,int>
#define fre(x) freopen(x,"r",stdin)
const int mod = 1e9+7;
const int maxn=2e5+10;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll num[maxn];
vector<ll>mid;
int main(){
    // fre("data.txt");
    ll n,a,b,k;
    cin>>n>>a>>b>>k;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    ll cnt=0;
    ll sum=a+b;
    for(int i=0;i<n;i++){
        if(num[i]%sum!=0&&num[i]%sum<=a){
            cnt++;
        }else{
            mid.push_back(num[i]%sum==0?b:num[i]%sum-a);
        }
    }
    sort(mid.begin(),mid.end());
    for(int i=0;i<mid.size();i++){
        if(k*a>=mid[i]){
            cnt++;
            k-=(mid[i]/a+(mid[i]%a==0?0:1));
        }else break;
    }
    cout<<cnt<<endl;
}

AC代码2

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
        h[i] %= a + b;
        if (h[i] == 0) h[i] += a + b;
        h[i] = ((h[i] + a - 1) / a) - 1;
    }
    sort(h.begin(), h.end());
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (k - h[i] < 0) break;
        ++ans;
        k -= h[i];
    }
    
    cout << ans << endl;
    
    return 0;
}

总结

取模+贪心。

E1. String Coloring (easy version)

题目链接

题目大意

给你一个只包含小写字母的字符串，给每一个字符图上黑色或者白色，相邻字符串如果颜色不同则可以交换位置，经过有限次数的交换，问是否有可能使得字符串变为有序。

解题思路

题目告诉相邻颜色不同的字符才能交换，换句话说就是颜色相同的字符顺序是不会发生改变的，要达到最后字符串为有序且颜色相同字符的顺序不改变，那么只有颜色相同的字符本身就是有序的，那么问题就转变为字符串是否能够转变为两个非递减的子序列。用两个字符分别标记两个子序列的最后一个字符，如果大于两个字符当中的任意一个，则可添加其到相应子序列的尾部。

AC代码

/*
    E1题补题
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string str;
    cin>>str;
    char l1='a',l2='a';
    string res;
    for(int i=0;i<str.size();i++){
        if(str[i]>=l1){
            res+="0";
            l1=str[i];
        }else if(str[i]>=l2){
            res+="1";
            l2=str[i];
        }else{
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    cout<<res<<endl;
    return 0;
}

总结

在理解到题意之后，不要仅局限于题目给的方向，要换角度思考问题。

E2. String Coloring (hard version)

题目链接

题目大意

题目意思和\(E1\)类似，给你一个长度为\(n\)的字符串，给每个字符涂上一种颜色，相邻不同颜色的字符可以交换位置，问最少需要多少种颜色使得经过有限次数的交换可以让字符串变得有序。

解题思路

思路和\(E1\)类似，去找覆盖字符串所有字符所需要非递减子序列的最少数量，解决方案有两种：

将字符串倒序一下，就是找覆盖所有字符所需要非递增子序列的个数。把每一个子序列尾部的字符插入到\(set\)中，此时可以用二分查找函数找第一个大于等于\(str[i]\)字符的字符。
根据\(Dilworth\)定理可以得知，覆盖整个序列所需的非递减序列的最小数量等于最长递减子序列的长度，那么用动态规划找到达每个字符的最长递减子序列的长度，其中\(dp[i]\)表示到第\(i\)个字符\(c\)的最长递减子序列的长度，其等于所有以大于字符\(c\)的字符结尾的最长递减子序列长度加\(1\)，最后数组\(dp\)存的就是答案。

AC代码1

#include<bits/stdc++.h>
using namespace std;
int c[30];
vector<char>G[300];
int main()
{
    // freopen("data.txt","r",stdin);
    int n;
    cin>>n;
    string str;
    cin>>str;
    set<char>se;
    int cnt=1;
    vector<string>res;
    reverse(str.begin(),str.end());
    se.insert(str[0]);
    c[str[0]-'a']=1;
    for(int i=0;i<str.size();i++){
        auto it=se.lower_bound(str[i]);
        if(it!=se.end()){
            res.push_back(to_string(c[(*it)-'a']));
            c[str[i]-'a']=c[(*it)-'a'];
            se.erase(it);
            se.insert(str[i]);
        }else {
            se.insert(str[i]);
            cnt++;
            c[str[i]-'a']=cnt;
            res.push_back(to_string(cnt));
        }
    }
    reverse(res.begin(),res.end());
    set<string>sp;
    for(int i=0;i<res.size();i++){
        sp.insert(res[i]);
    }
    cout<<sp.size()<<endl;
    for(int i=0;i<res.size();i++){
        if(i)cout<<" ";
        cout<<res[i];
    }
    return 0;
}

AC代码2

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("data.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n;
    string s;
    cin >> n >> s;
    
    vector<int> maxdp(26);
    vector<int> dp(n, 1);
    for (int i = 0; i < n; ++i) {
        for (int c = 25; c > s[i] - 'a'; --c) {
            dp[i] = max(dp[i], maxdp[c] + 1);
        }
        maxdp[s[i] - 'a'] =  max(maxdp[s[i] - 'a'], dp[i]);
    }
    
    cout << *max_element(maxdp.begin(), maxdp.end()) << endl;
    for (int i = 0; i < n; ++i) cout << dp[i] << " ";
    cout << endl;
    
    return 0;
}