Codeforces Round #767 (Div. 2) ABCD

Codeforces Round #767 (Div. 2) ABCD

日常卡C

A - Download More RAM 题目大意

(换了个世界观)给定 n n n个道具，体积为 a [ i ] a[i] a[i]，效果为 b [ i ] b[i] b[i]，当前容量为 k k k。每次可以选择一个体积小于等于当前容量的物品，选择后容量扩大为 k + b [ i ] k + b[i] k+b[i]。问容量最大可以扩大到多大。

思路

直接排序优先选择体积小&&效果大的物品，然后贪心选择直到无法再选为止。复杂度取决于排序 O ( n log ⁡ n ) O(n log n) O(nlogn)。

Accepted Code

#include 
using namespace std;

const int N = 110;

struct node{
    int a, b;
    const bool operator< (const node &x) const {
        if(a == x.a) return b > x.b;
        return a < x.a;
    }
}p[N];

inline void solve(){
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> p[i].a;
    for(int i = 1; i <= n; i++) cin >> p[i].b;
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; i++){
        if(k < p[i].a) break;
        k += p[i].b;
    }
    cout << k << endl;
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

B - GCD Arrays 题目大意

给定一个区间 [ l , r ] [l,r] [l,r]，每次 *** 作可以选择两个数字删除，并将他们的乘积加入原序列。问能否通过 k k k次以内的 *** 作，使得整个序列 G C D GCD GCD大于 1 1 1.

思路

直接统计区间奇数个数，最少 *** 作次数为所有奇数合并再乘一个偶数的 *** 作次数，即为奇数的个数$-1 + 1 = $奇数个数

Accepted Code

#include 
using namespace std;

inline void solve(){
    int l, r, k; cin >> l >> r >> k;
    if(l == r){
        if(l > 1) cout << "YES" << endl;
        else cout << "NO" << endl;
        return;
    }
    int res = 0;
    int det = r - l;
    res += (det >> 1);
    if(((l & 1) == 1) || ((r & 1) == 1)) res++;
    if(res > k) cout << "NO" << endl;
    else cout << "YES" << endl;
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

C - Meximum Array 题目大意

当 a a a不为空时有一下 *** 作：

选择一个整数 k ( 1 ≤ K ≤ ∣ a ∣ ） k(1≤K≤|a |） k(1≤K≤∣a∣）。

将数组 a a a的前 k k k个数字的 M E X MEX MEX附加到数组 b b b的末尾，并从数组 a a a中删除它们，从而移动 a a a中其余数字的位置。

要求输出字典序最大的 b b b串。

思路

单独记录每个数字的出现次数，然后暴力查找MEX，模拟删除即可。

怎么会卡这题

Accepted Code

#include 
using namespace std;

const int N = 2e5 + 10;
int vis[N], a[N], ans[N], tag[N];

inline void solve(){
    int n = 0, cnt = 0; cin >> n;
    memset(tag, 0, (n + 5) * sizeof(int));
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        tag[a[i]]++;
    }
    for(int id = 0; id < n;){
        int pos = 0;
        while(tag[pos]) ++pos;
        if(!pos){
            ans[++cnt] = 0, id++;
            continue;
        }
        else ans[++cnt] = pos;
        memset(vis, 0, (n + 5) * sizeof(int));
        for(int i = pos; i;){
            id++;
            if(!vis[a[id]] && a[id] < pos) i--, vis[a[id]] = true;
            tag[a[id]]--;
        }
    }
    cout << cnt << endl;
    for(int i = 1; i <= cnt; i++) cout << ans[i] << (i == cnt ? 'n' : ' ');

}


signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
}

D - Peculiar Movie Preferences 题目大意

给定 n n n个字符串，每个串长度不超过 3 3 3，问能否通过删除某些字符串，使剩余的串按顺序连接后为回文串。

思路

每个串的长度 ≤ 3 leq 3 ≤3，那么就可以进行分类讨论了：

如果某个串长度为 1 1 1，YES，它自己就能构成回文串如果某个串长度为 2 2 2:

AA型：本身可构成回文串，YESAB型：可以对前后提供贡献，先查找之前有无BA，再插入集合维护即可 如果某个串长度为 3 3 3：

ABA型：本身可构成回文串，YESABC型：

为前后提供ABC贡献，先查找之前有无CBA，再插入集合维护为前面提供BC贡献，查找之前有无CB为后面提供AB贡献，查找之后有无BA(这里无法按顺序处理，需要反序扫描一遍) Accepted Code

#include 
using namespace std;

const int N = 1e5 + 10;
string a[N];
set st;


inline void solve(){
    int n = 0; cin >> n;
    bool flag = false;
    st.clear();
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(flag) continue;
        if(a[i].length() == 1) flag = true;
        if(a[i].length() == 2 && a[i][0] == a[i][1]) flag = true;
        if(a[i].length() == 3 && a[i][0] == a[i][2]) flag = true;
        if(a[i].size() == 2){
            string rev = "";
            rev += a[i][1], rev += a[i][0];
            if(st.count(rev)) flag = true;
        }
        else if(a[i].size() == 3){
            string rev1 = "", rev3 = "";
            rev1 += a[i][2], rev1 +=  a[i][1], rev1 += a[i][0];
            rev3 += a[i][2], rev3 += a[i][1];
            if(st.count(rev1) || st.count(rev3)) flag = true;
        }
        st.insert(a[i]);
    }
    if(!flag){
        st.clear();
        for(int i = n; i >= 1; --i){
            if(a[i].size() == 3){
                string rev = "";
                rev += a[i][1], rev += a[i][0];
                if(st.count(rev)){ flag = true; break; }
            }
            st.insert(a[i]);
        }
    }
    if(flag){ cout << "YES" << endl; return; }
    else cout << "NO" << endl;
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}