目录

A. Plus or Minus

B. 抓糖果

C. 查找并替换

D. 奇数查询

E. 面试

F. 弹跳球

G2. 子序列加法（困难版）

A. Plus or Minus

直接模拟

void solve() {
    int a, b, c; cin >> a >> b >> c;
    a + b == c ? puts("+") : puts("-");
}

B. 抓糖果

先处理偶数再处理奇数，只需检查总数

void solve() {
    int n; cin >> n;
    long long s1 = 0, s2 = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (x % 2) s2 += x;
        else s1 += x;
    }
    s1 > s2 ? puts("YES") : puts("NO");
}

C. 查找并替换

将第一个字符变为0或1均可，后续会相应变化。如果出现相等的情况则不行。

void solve() {
    int n; cin >> n;
    string a; cin >> a;
    int f = 0;
    unordered_map<char, int> q;
    q[a[0]] = 1;
    for (int i = 1; i < n; i++) {
        if (!q.count(a[i])) q[a[i]] = q[a[i - 1]] ^ 1;
        if (q[a[i]] == q[a[i - 1]]) {
            f = 1;
            break;
        }
    }
    q.clear();
    if (f) puts("NO");
    else puts("YES");
}

D. 奇数查询

简单区间查询，使用前缀和维护即可

void solve() {
    int n, m; cin >> n >> m;
    long long sum = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        a[i] += a[i - 1];
    }
    while (m--) {
        int l, r, k; cin >> l >> r >> k;
        long long ans = a[l - 1] - a[r];
        long long res = sum + ans + k * (r - l + 1);
        res & 1 ? puts("YES") : puts("NO");
    }
}

E. 面试

简单的交互题通常使用二分。这里使用前缀和维护，然后通过二分查询判断是否满足，调整中间值 mid 即可。

void solve() {
    int n; cin >> n;
    vector<long long> a(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = a[i];
    for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        cout << "? " << mid - l + 1 << " ";
        for (int i = l; i <= mid; i++) cout << i << " ";
        cout << endl;
        long long res; cin >> res;
        if (res != sum[mid] - sum[l - 1]) r = mid;
        else l = mid + 1;
    }
    cout << "! " << l << endl;
}

F. 弹跳球

直接模拟弹跳的过程。根据题目提示，数据范围为 nm，最多会有 nm 个点，根据鸽巢原理，必然会重复。因此可以推断出结果。

void solve() {
    int n, m, sx, sy, ex, ey; cin >> n >> m >> sx >> sy >> ex >> ey;
    char s[2]; cin >> s;
    int x = s[0] == 'D' ? 1 : -1, y = s[1] == 'R' ? 1 : -1;
    int ans = 0, flag = false, res = 0;
    while (sx != ex || sy != ey) {
        int f = 0;
        res++;
        if (sx + x > n || sx + x <= 0) x = -x, f++, ans++;
        if (sy + y > m || sy + y <= 0) y = -y, f++, ans++;
        if (f == 2) ans--;
        sx += x, sy += y;
        if (ans > n * m) {
            flag = true;
            break;
        }
    }
    !flag ? cout << ans << endl : cout << -1 << endl;
}

G2. 子序列加法（困难版）

后面的数一定由前面的数构成。如果某个数比前面的总和还大，则无法构造。使用前缀和维护即可。

void solve() {
int n; cin >> n;
vector a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.begin() + n + 1);
if (a[1] != 1) {
cout << "NO" << endl;
return;
}
vector b(n + 1);
b[0] = 0;
for (int i = 1; i <= n; i++) b[i] = b[i - 1] + a[i];
b[0] = 1;
for (int i = 1; i <= n; i++) {
if (a[i] > b[i - 1]) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}