牛客练习赛121补题

C.

思路

由于水滴会影响一个区间里的水滴，所以只需要为何区间[l, r]即可

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 1e18;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int a[N];
int n, p, l, r;

void dfs(int x) {//dfs(x)表示在x的位置上加1水滴
    a[x] ++;
    if (x == 0 || x == n + 1) return;
    if (a[x] == 10) {
        if (x == l) l --;
        if (x == r) r ++;
        dfs(r);
        dfs(l);
    }
}

void solve() {
    cin >> n >> p;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[0] = a[n + 1] = 0;
    l = p - 1;
    r = p + 1;
    dfs(p);
    
    cout << a[0] << ' ' << a[n + 1] << endl;
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

D.

思路

构造。先用操作1构造出两个gcd(x, y), 然后用倍增是思路把逼近lcm(x, y)的规模，在达到lcm(x, y)的规模时用位运算的方式逼近正确答案

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 1e18;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

void solve() {
    i64 x, y;
    cin >> x >> y;
    if (x < y) swap(x, y);
    i64 d = __gcd(x, y);
    i64 lcm = x / d * y;
    
    if (x == lcm || y == lcm) {
        cout << "0\n";
        return;
    }
    
    vector<i64> t;
    vector<pair<i64, i64>> op;
    op.push_back({x, y});
    op.push_back({x, y});
    t.push_back(d);
    
    while (1) {
        if (lcm - t.back() < t.back()) break;
        i64 tmp = t.back();
        op.push_back({tmp, tmp});
        t.push_back(tmp + tmp);
        if (lcm - t.back() < t.back()) break;
        op.push_back({tmp, tmp});
    }
    
    if (t.back() != lcm) {
        i64 cnt = 1;
        i64 b = (lcm - t.back()) / d;
        while (b) {
            if (b & 1) {
                i64 tt = cnt * d;
                op.push_back({t.back(), tt});
                i64 z = t.back() + tt;
                t.push_back(z);
            }
            b >>= 1;
            cnt *= 2;
        }
    }
    
    cout << op.size() << endl;
    for (int i = 0; i < op.size(); i++) {
        if (i < 2) cout << 1 << ' ';
        else cout << 2 << ' ';
        cout << op[i].first << ' ' << op[i].second << endl;
    }
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

E.

思路

折扣券和立减券要用在大价格的物品上，dp[i][j]表示前i个物品都使用了券且用了j张折扣券

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 1e18;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

void solve() {
    int n, a, b;
    cin >> n;
    vector<i64> p(n);
    for (auto &i : p) cin >> i;
    cin >> a;
    vector<i64> x(a);
    for (auto &i : x) cin >> i;
    cin >> b;
    vector<i64> y(b);
    for (auto &i : y) cin >> i;
    sort(p.begin(), p.end(), greater<i64>());
    sort(x.begin(), x.end());
    sort(y.begin(), y.end(), greater<i64>());
    
    double ans = 0;
    for (int i = a + b; i < n; i++)
        ans += 1.0 * p[i];
    
    double dp[5010][5010];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = 1e9;
    dp[0][0] = 0;
    
    n = min(n, a + b);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= min(i, a); j++) {
            if (i - j > b) continue;
            if (j > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 0.01 * p[i - 1] * x[j - 1]);
            if (i - j > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + max(0.0, 1.0 * p[i - 1] - 1.0 * y[i - j - 1]));
        }
    }

    double mn = 1e9;
    for (int j = 0; j <= a; j++) mn = min(mn, dp[n][j]);
    ans += mn;
    printf("%.10lf\n", ans);

}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //cout.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}