C、星际解码计划

有两个解法 一种dp 一种考虑贡献

dp dp[0],用于记录字符串中字符 't'出现的累计次数.在遍历字符串的过程中,每当遇到字符 't',就将 dp[0] 的值加 1. dp[1] ：表示字符 'q' 前面出现 't' 的累计数量之和.当遍历到字符 'q' 时,将当前 dp[0] 的值累加到 dp[1] 上.这是因为每出现一个 'q',它前面的每个 't' 都可以和它组成一种特定的组合(这里可以理解为一种计数关系). dp[2] ：记录字符 'w' 前面出现符合特定组合('t' 和 'q' 按顺序出现)的累计数量之和。当遍历到字符 'w' 时，将当前 dp[1] 的值累加到 dp[2] 上。

贡献法 枚举中间的字母看这个字母q左边有多少个t右边有多少个w 相乘就是答案

// 贡献法
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    string s; cin >> s;
    int cntw = 0, cntt = 0, ans = 0; // cntw 记录w的个数，cntt记录t的个数
    for(int i = 0; i < s.size(); i++) cntw += (s[i] == 'w');
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'q') ans += cntw * cntt;
        else if(s[i] == 't') cntt++; 
        else if(s[i] == 'w') cntw--; 
    }
    cout << ans << endl;
    return 0;
}

// dp法
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    string s; cin >> s;
    vector<int> dp(3);
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 't') dp[0]++;
        else if(s[i] == 'q') dp[1] += dp[0];
        else if(s[i] == 'w') dp[2] += dp[1];
    }
    cout << dp[2] << endl;
    return 0;
}

F、模 230

题意： 给定一个序列，找出是否存在两个不同的子序列，子序列的总和对 230 同余。

解题思路： 一个直接的想法就是将所有可能的情况都遍历一边，如果我们使用最暴力的方法，枚举每个元素所在组的情况，时间复杂度将会非常高，因此我们需要另外的解法。考虑到子序列求和后需要对 230 求余，也就是说我们得到的余数结果的范围 [0,230) 之间。题目要求出一对子序列，也就是说总和求余后是一样的。

这里我们可以根据抽屉原理，知道如果我们计算过 230 个子序列后，就必定存在两个子序列的总和是同余的 举个例子：把六个苹果放进五个抽屉，一定存在一个抽屉的苹果数量是>= 2 的,

本题对子序列和对 230 取模最多只有230种情况，只需要枚举到第231个子序列， 就一定会存在对 230 取模结果相同的两个不同的序列

综上，我们只需要 min ( n , 8 )个元素，再利用二进制枚举子序列，最后找到相同余数的子序列就得到结果，如果不存在就输出No;

#include <bits/stdc++.h>
using namespace std;
#define int long long

void print(int x) {
    vector<int> ans;
    for(int i = 0; x >> i; i++) {
        if((x >> i) & 1) ans.push_back(i + 1);
    }
    cout << ans.size() << ' ';
    for(auto x : ans) cout << x << ' ';
    cout << endl;
}

signed main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int x = min<int>(n, 8);
    map<int, int> mp;
    for(int i = 1; i < (1 << x); i++) {
        int t = 0;
        for(int j = 0; i >> j; j++) {
            if((i >> j) & 1) t = (t + a[j]) % 230;
        }
        if(mp.count(t)) {
            cout << "YES" << endl;
            print(mp[t]);
            print(i);
            return 0;
        }
        mp[t] = i;
    }
    cout << "NO" << endl;
    return 0;
}

O、魔法大师

解题思路： 这是一道二分板子题， 首先对数组a进行排序， 如果b[i] > a.[n - 1] 输出 -1， 否则二分寻找在数组a中第一个大于等于b[i]的数， 看代码吧

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    sort(a.begin(), a.end());
    for(int i = 0; i < m; i++) {
        if(b[i] > a.back()) cout << "-1 ";
        else cout << *lower_bound(a.begin(), a.end(), b[i]) << ' ';
    }
    return 0;
}