刷题之Codeforces Round #767 (Div. 2)

刷题之Codeforces Round #767 (Div. 2)

A. Download More RAMB. GCD ArraysC. Meximum ArrayD. Peculiar Movie Preferences

题目链接：Download More RAM

类型：贪心

思路：按照花费的内存排序，先用花费少的

#include
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector
#define PII pair
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e2 + 5;
const db eps = 1e-10;
int cas, n, k;
struct AC{
    int a, b;
}ram[N];
bool cmp(AC x, AC y){
    return x.a < y.a;
}
int main(){
    cin >> cas;
    while(cas--){
        cin >> n >> k;
        rep(i, 1, n) cin >> ram[i].a;
        rep(i, 1, n) cin >> ram[i].b;
        sort(ram + 1, ram + 1 + n, cmp);
        rep(i, 1, n){
            if(k >= ram[i].a) k += ram[i].b;
            else break;
        }
        cout << k << endl;
    }
}

题目链接：GCD Arrays

思路：要让 gcd ⁡ > 1 gcd>1 gcd>1，只需要两两都不互质即可。由于是连续数字，则所有 [ l , r ] [l,r] [l,r] 中数字有约一半是 2 2 2 的倍数，于是只需要将所有奇数与偶数相乘便可用最少的步骤（约总数字的一半）两两不互质的数字（ gcd ⁡ = 2 gcd=2 gcd=2）。

判断数组中奇数个数是否比要求操作数 k k k 大即可特判 k = 0 k=0 k=0 时的情况

#include
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector
#define PII pair
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const db eps = 1e-10;
int cas, ok;
int l, r, k, n, add;
int main(){
    cin >> cas;
    while(cas--){
        cin >> l >> r >> k;
        if(!k){
            if(l == r) puts(l > 1 ? "YES" : "NO");
            else puts("NO");
            continue;
        }
        n = r - l + 1, ok = 0;
        add = (n % 2 && l % 2) ? 1 : 0;
        if(k >= (n + add) / 2) ok = 1;
        puts(ok ? "YES" : "NO");
    }
}

复杂度算错，比赛时没敢写

题目链接：Meximum Array

类型：贪心

思路：这道题复杂度 < O ( n 2 )

对于一个数字的 MEX，有个性质：单调不减要求 b b b 数组字典序最大，则每次肯定要取 a a a 数组可以得到的最大 MEX（根据性质，也就是数组全体的 MEX）。在 a a a 数组前部分找到满足 MEX 的子段，即找到最小的 nownum，使得前 nownum 个数的 MEX = 整个数组的 MEX删掉这 nownum 个数后剩下的序列重复上面步骤

#include
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector
#define PII pair
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 2e5 + 5;
const db eps = 1e-10;
int cas, n, a[N], flg[N], subflg[N];
int mex, nownum;
VI ans;
void init(){
    nownum = 0;
    memset(subflg, 0, sizeof(subflg));
}
int main(){
    cin >> cas;
    while(cas--){
        cin >> n;
        memset(flg, 0, sizeof(flg));
        rep(i, 1, n){
            cin >> a[i];
            flg[a[i]]++;
        }
        //统计数组全部的mex
        mex = 0;
        while(flg[mex]) mex++;
        ans.clear();
        init();
        rep(i, 1, n){
            //统计可凑够mex的最小数字nownum
            if(a[i] <= mex - 1){
                if(!subflg[a[i]]) nownum++;
                subflg[a[i]]++;
            }
            if(nownum == mex){
                ans.push_back(mex);
                //删去前面部分
                rep(j, 0, mex) flg[j] -= subflg[j];
                //重新计算剩余数组的mex
                mex = 0;
                while(flg[mex]) mex++;
                init();
            }
        }
        cout << ans.size() << endl;
        for(auto i : ans) cout << i << " "; 
        cout << endl;
    }
}

题目链接：Peculiar Movie Preferences

题目：用 n n n 个长度不超过 3 3 3 的字符串拼接组成回文串

类型：构造

思路：

结论：若能组成，则最多需要两个字符串

首先，若一个字符串自己就是回文串，成立

其次，若两个字符串可组成（即一个字符串组不成，那么一定没有长度为 1 1 1 的字符串了），那一定是 2 + 2 , 3 + 3 , 3 + 2 , 2 + 3 2+2,3+3,3+2,2+3 2+2,3+3,3+2,2+3 这四种情况中的一种。可用 m a p map map 记录，便于对应查找

注意： 2 + 3 2+3 2+3 时要根据当前长度为 3 3 3 的字符串找到前半部分 before 内满足要求的字符串。其他时候只需要在后半部分 last 内找满足要求的字符串

由于 “subsequence” 是有顺序的

其他情况均可以通过减少中间的字符串个数来使总拼接个数降为两个

#include
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector
#define PII pair
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const db eps = 1e-10;
int cas, n, ok;
string s[N], tmp;
map last, before;
bool self(string s){
    if(s.size() == 1) return 1;
    else if(s.size() == 2) return (s[0] == s[1]);
    else return (s[0] == s[2]);
}
bool check(string s, int flg){  //flg == 1表示检查last中,flg == 0表示检查before中
    string tmp = s;
    reverse(tmp.begin(), tmp.end());
    if(flg) return last[tmp] > 0;
    else return before[tmp] > 0;
}
int main(){
    cin >> cas;
    while(cas--){
        cin >> n;
        ok = 0;
        last.clear(), before.clear();
        rep(i, 1, n){
            cin >> s[i];
            if(self(s[i])) ok = 1;
            last[s[i]]++;
            // st.insert(s[i]);
        }
        //考虑拼接情况：注意要求子序列，即只能使后面的字符串拼接在当前字符串末尾，用map
        rep(i, 1, n){  //不考虑所有s[i].size() == 1的情况
            if(s[i].size() == 2){
                //2 + 2
                if(check(s[i], 1)) ok = 1;
            }
            if(s[i].size() == 3){
                //3 + 3
                if(check(s[i], 1)) ok = 1;
                //2 + 3
                if(check(s[i].substr(1, 2), 0)) ok = 1;
                //3 + 2
                if(check(s[i].substr(0, 2), 1)) ok = 1;
            }
            before[s[i]]++;
            last[s[i]]--;
        }
        puts(ok ? "YES" : "NO");
    }
}