A - Download More RAM

题目大意

给定n个内存条, 每个内存条可以增加\(b_i\)的内存, 但前提是你有足够的内存\(a_i\)去使用, 初始内存为k

思路

只要内存大于所要求的\(a_i\), 就可以使内存增加\(b_i\), 那么按照a排序贪心就好

代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 110;
 
int n, k;
struct Node {
    int a, b;
}a[N];
 
int main() {
    int T;
    cin >> T;
    while (T --) {
        cin >> n >> k;
        for (int i = 1; i <= n; i ++ ) cin >> a[i].a ;
        for (int i = 1; i <= n; i ++) cin >> a[i].b;
        sort(a + 1, a + n + 1, [](Node a, Node b) {
            return a.a < b.a;
        });
 
        for (int i = 1; i <= n; i ++)
            if (a[i].a <= k) {
                k += a[i].b;
            }
        cout << k << endl;
    }
    return  0;
}

B - GCD Arrays

题目大意

给定一个去区间[l, r], 问经过k次操作之后, 能不能使所有数的最大公约数不为1
每次操作为删除两个数, 并将这两个数的乘积加入数组

思路

区间[l, r], 一串相连的数字, 那么他们的最大公约数除了1, 只能是2了, 又或者所有数合成了一个

• 合成一个, 需要至少r - l + 1次, 这里有个特例就是左右端点相等, 那这两个端点就不能为1了
• 最大公约数为2, 必须得相邻两个相互配对, 而且如果右端点为奇数的化, 那么右端点就必须和左边的那一组配对

代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 110;
 
int n, k;
struct Node {
    int a, b;
}a[N];
 
int main() {
    int T;
    cin >> T;
    while (T --) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == b && a > 1) puts("YES");
        else if ((b - a + 1 + (b % 2)) / 2 <= c) puts("YES");
        else puts("NO");
    }
    return  0;
}

C - Meximum Array

题目大意

每次可以从头开始, 选取任意长度的原数组, 然后将这段序列的MEX加入新数组中, 问最后形成的新数组最大是多少

思路

首先原数组是一定要被遍历完的

• 新数组最大, 一定是先将所有数可以凑出的最大的MEX加入
• 然后从0到n, 一旦遇到断点, 就将断点加入答案
• 如果是0缺失的化, 应该是加入剩下原数组长度的0加入答案
  然后是怎么样遍历
  我们可以枚举当前的MEX, 如果后面存在这个数, 那么MEX++, 如果不存在, 那么这个MEX就是断点
  预处理每个数的位置, 利用数组下标i来判断是否是否枚举完毕

代码

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
 
using namespace std;
 
const int N = 2e5 + 10;
 
int n;
int a[N], b[N];
vector<int> idx[N];
vector<int> ans;
 
int main() {
    int T;
    cin >> T;
    while (T --) {
        cin >> n;
        ans.clear();
        for (int i = 0; i <= n; i ++) {
            idx[i].clear();
            b[i] = 0;
        }
 
        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
            idx[a[i]].push_back(i);
        }
 
            int cnt = 0, i = 1;
            while (i <= n) {                                                         // 当没有枚举到数组末尾的时候
                //cout << ans.size() << ' ' << cnt << ' ' << i << endl;
                if (b[cnt] < idx[cnt].size()) {                                      // 如果当前的MEX在数组后面还有
                    i = max(i, idx[cnt][b[cnt]]);                                    // 将数组下标后移
                    b[cnt ++] ++;
                    if (cnt > n) {
                        for (int j = 0; j < cnt; j ++)                                // 所有数组下标之前的数, 都不能再进行访问
                            while (b[j] < idx[j].size() && idx[j][b[j]] <= i) b[j] ++;
                        ans.push_back(cnt);
                        cnt = 0;
                    }
                }
                else {
                    if (cnt == 0) {                                                    // 如果缺失的是0
                        while (i <= n) {
                            ans.push_back(0);
                            i ++;
                        }
                        break;
                    }
                    else {                                                              // 不是0, 缺失一个断点, 重新进行遍历
                        ans.push_back(cnt);
                        for (int j = 0; j < cnt; j ++)
                            while (b[j] < idx[j].size() && idx[j][b[j]] <= i) b[j] ++;
                        cnt = 0;
                        if (i == n) break;                                              // 数组已经到末尾就退出, 没有到就++, 继续进行下一轮的遍历
                        else i ++;
                    }
                }
            }
 
            cout << ans.size() << endl;
            for (auto j : ans) cout << j << ' '; cout << endl;
 
    }
    return  0;
}

D - Peculiar Movie Preferences

题目大意

给定n个长度不超过3的字符串, 问是否可以选取任意多个字符串来构成一个回文字符串

思路

主要是有长度不超过3这个限制, 这样我们就可以进行暴力的枚举, 回文串的长度无非是1, 2, 3, 4, 5, 6, 如果有更长的回文串的话, 我们一定可以删去其中的一部分

• 长度为1的字符串, 一定就是回文串了
• 长度为2的字符串, 要么本身是回文, 要么是存在一个字符串正好相反
• 长度为3的字符串, 第一种还是本身是回文, 第二种是存在一个相反的字符串, 第三种是存在一个长度为2的字符串, 可以拼接到后面或者前面形成一个回文

代码

#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
 
#define x first
#define y second
 
using namespace std;
 
int n;
map<string, vector<int> > mp;
 
bool solve() {
    mp.clear();
 
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        string x;
        cin >> x;
        mp[x].push_back(i);
    }
 
    for (auto i : mp) {
        if (i.first.size() == 1) {
            return true;
        }
        else if (i.first.size() == 2) {
            string x = i.first;
            reverse(x.begin(), x.end());
            if (mp.count(x)) return true;
        }
        else {
            string x = i.first.substr(0, 2); // 拼接到这个后面
            string y = i.first.substr(1, 2); // 拼接到这个前面
            string z = i.first;
            reverse(x.begin(), x.end());
            reverse(y.begin(), y.end());
            reverse(z.begin(), z.end());
 
            if (mp.count(x) && mp[x].back() > i.second.front()) return true;
            if (mp.count(y) && mp[y].front() < i.second.back()) return true;
            if (mp.count(z)) return true;
        }
    }
    return false;
}
 
int main() {
    int T;
    cin >> T;
    while (T --) {
        if (solve()) puts("YES");
        else puts("NO");
    }
}