牛客寒假算法基础集训营3

思路：
  1. f[i][j] 表示前i个瓜，重量为j的方案数
    f[i][j] = (f[i - 1][j] + f[i - 1][j - w[i]] + f[i - 1][j - w[i] / 2]) % mod
  2. 压缩一维，滚动数组。
    f[j] += f[j - w[i]];
    f[j] += f[j - w[i] / 2];

void solve() {
    cin >> n >> m;
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        for (int j = m; j >= 1; j--) {
            if(j - x >= 0) f[j] = (f[j] + f[j - x]) % mod;
            if(j - x / 2 >= 0) f[j] = (f[j] + f[j - x / 2]) % mod;
        }
    }
    for (int i = 1; i <= m; i++) cout << f[i] << ' ';
}

n = int(input())
s = input()
print(s[n - 1:] + s[:n - 1])

思路：
  1. 因为k<10，所以本题数据范围不大，直接暴力排序。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010, mod = 1e9 + 7;
int n, m, k;
int a[N];
bool st[N];
bool cmp(char x, char y) { return x > y; }
signed main() {
    cin >> n >> m >> k;
    string s; cin >> s;
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans1 = 0;
    for (int i = 0; i < n; i++) {
        if(st[i]) continue;
        st[i] = true;
        int l = i - 1, r = i + 1;
        while(l >= 0 && a[l] == a[i]) st[l] = true, l--;
        while(r < n && a[r] == a[i]) st[r] = true, r++;
        sort(s.begin() + l + 1, s.begin() + r, cmp);
    }
    for (int i = 0; i < s.size(); i++) 
        ans1 = (s[i] - '0' + ans1 * 10 % mod) % mod;
    cout << ans1 << endl;
    while(k--) {
        int x, y; cin >> x >> y;
        memset(st, 0, sizeof st);
        for (int i = 0; i < n; i++)
            if(a[i] == x) a[i] = y;
        for (int i = 0; i < n; i++) {
            if(st[i]) continue;
            st[i] = true;
            int l = i - 1, r = i + 1;
            while(l >= 0 && a[l] == a[i]) st[l] = true, l--;
            while(r < n && a[r] == a[i]) st[r] = true, r++;
            sort(s.begin() + l + 1, s.begin() + r, cmp);
        }
        int ans2 = 0;
        for (int i = 0; i < s.size(); i++) 
        ans2 = (s[i] - '0' + ans2 * 10 % mod) % mod;
        cout << ans2 << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int A, B, C, D;
int n, L, R;
string s;
bool judge()
{
    return (A > 0) + (B > 0) + (C > 0) + (D > 0) >= 3;
}
void add(char c)
{
    if (c >= 'A' && c <= 'Z')
        A++;
    else if (c >= 'a' && c <= 'z')
        B++;
    else if (c >= '0' && c <= '9')
        C++;
    else
        D++;
}
void des(char c)
{
    if (c >= 'A' && c <= 'Z')
        A--;
    else if (c >= 'a' && c <= 'z')
        B--;
    else if (c >= '0' && c <= '9')
        C--;
    else
        D--;
}
int main()
{
    cin >> n >> L >> R;
    cin >> s;
    int       l = 0, r = -1;
    long long ans = 0;
    while (l < n - L + 1 && r < n) {
        while (!judge() && r < n) add(s[++r]);
        if (r <= l + L - 1)
            ans += min(R + l - 1, n - 1) - l - L + 2;
        else if (r <= l + R - 1)
            ans += min(R + l - 1, n - 1) - r + 1;
        des(s[l++]);
    }
    cout << ans << endl;;
    return 0;
}