南外集训 Day 3

The third day of intensive training at Nanjing Foreign Language School.
今天打比赛，第一题水题
第二题思路没错，但打的时候代码有问题

#include <bits/stdc++.h>
using namespace std;
int T, l, r;
void work() {
    int res = INT_MAX, tot = 0;
    cin >> l >> r;
    int d = 1;
    for (int i = l; i <= r; i = i + d) {
        int k = i, dis = 1, ans = 0;
        while (k % 10 == 0) {
            k = k / 10;
            dis *= 10;
        }
        int h = k % 10, c = 0;
        while (k) {
            c++;
            k = k / 10;
        }
        if (h == 5) {
            ans = c * 2 - 1;
        } else {
            ans = c * 2;
        }
        if (res > ans) {
            tot = i;
            res = ans;
        }
        d = dis;
    }
    cout << tot << endl;
}
int main() {
    cin >> T;
    while (T) {
        work();
        T--;
    }
    return 0;
}

第三题手写队列，但是有个部分的思路错误

#include <bits/stdc++.h>
using namespace std;
int m, k, p, head, tail, all, a[52000];
string s;
int main() {
    cin >> m >> k >> p;
    cin >> s;
    int len = s.size();
    tail = k - 1;
    while (tail < len) {
        int q = 0;
        for (int i = head; i <= tail; i++) {
            if (s[i] == &#039;Q&#039;) {
                q++;
            }
        }
        if (q >= p) {
            for (int i = head; i <= tail; i++) {
                a[i]++;
            }
            all++;
        }
        head++;
        tail++;
    }
    int x = all - m + 1;
    for (int i = 0; i < len; i++) {
        if (a[i] == 0) {
            cout << "-";
        } else if (a[i] >= x) {
            cout << "+";
        } else {
            cout << "?";
        }
    }
    return 0;
}

第四题用背包，改良后却还是错，打题的思路有问题

#include <bits/stdc++.h>
using namespace std;
struct EEE {
    int w, v;
} a[10000];
int dp[10050][5];
int n, l;
int main() {
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].v >> a[i].w;
    }
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        int c;
        ans = max(ans, a[i].w);
        if (a[i].v % 2 == 0)
            c = a[i].v / 2;
        else
            c = a[i].v / 2 + 1;
        for (int j = l; j >= c; j--) {
            for (int t = 2; t >= 0; t--) {
                if (t >= 1) {
                    dp[j][t] = max(dp[j][t], dp[j - c][t - 1] + a[i].w);
                }
                if (j >= a[i].v) {
                    dp[j][t] = max(dp[j][t], dp[j - a[i].v][t] + a[i].w);
                }
            }
        }
    }
    for (int i = 1; i <= l; i++) {
        for (int j = 0; j <= 2; j++) {
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;
    return 0;
}