20241012总结

bryce蒟蒻的小窝 / 2024-10-19 / 原文

126 带权平均数之和

枚举区间长度然后拆贡献简单计算。

#include<iostream>
#define int long long

using namespace std;

inline int read(){
    register int x = 0, f = 1;
    register char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

const int N = 3e5 + 10, mod = 1e9 + 7;
int n, ans;
int a[N], w[N], s[N];

signed main(){
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read() % mod, s[i] = (s[i - 1] + a[i]) % mod;
    for (int i = 1; i <= n; i++) w[i] = read() % mod;
    int sum = 0, len = 1;
    for (len = 1; len <= (n % 2 == 0 ? n / 2 : n / 2 + 1); len++){
        ans = (ans + (w[len] * ((s[n - len + 1] - s[len - 1] + mod) % mod * len % mod + sum) % mod) % mod) % mod;
        if (len != n - len + 1) sum = (sum + (a[len] + a[n - len + 1]) % mod * len % mod) % mod;
    }
    sum = 0;
    for (int i = n; i >= len; i--){
        sum = (sum + (s[i] - s[n - i] + mod) % mod) % mod;
        ans = (ans + w[i] * sum % mod) % mod;
    }
    cout << ans;
    return 0;
}

129 Climb

很明显，这是一个带悔贪心，开两个优先队列，一个维护当前一次性能跳上去的最大值，即 $a$，记为 $qmax$，另一个维护当前这一天能跳多少的最大值，记为 $qdis$。首先，如果当前高度 $now$ 加上 $qmax$ 大于 $L$，那么直接输出天数，如果当前高度 $now$ 加上最大的 $qdis$ 也无法到达水位线，那么直接输出 $-1$。接下来考虑怎么带悔，假设当前有两个药丸，功能如下，$a_1 = 13, b_1 = 6$，$a_2 = 5, b_2 = 0$，那么我们先选第一个，因为它的 $qdis$ 最大，但是要考虑也许以后第一个药丸可以直接跳 $13$ 格到顶，于是在 $qmax$ 中插入 $5 - 6 + 13$，即选了第二个药丸完成正常跳跃后使用第一个药丸可以一次性比当前先选 $1$ 号药丸跳跃到的位置多 $12$ 格，于是，带悔完成，对于每一个小于 $qdis_max$ 且能够跳跃到水位线以上的 $qdis$ 做一次带悔，但是这样做常数太大，于是玄学优化，由于数据太水，一次性带悔次数一定不会超过 $100$ 所以每一次带悔只进行 $100$ 次，本人亲测，不带悔能过脚造数据，只带悔 $1$ 次就能过全部生成的 $hack$ 数据。

#include<iostream>
#include<queue>

using namespace std;

inline int read(){
    register int x = 0, f = 1;
    register char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

const int N = 1e6 + 10;
int n, l, h, now;
int a[N], b[N], c[N];
struct node{
    int id, val;
    bool operator < (const node &b) const{
        if (val != b.val) return val < b.val;
        return a[id] > a[b.id];
    }
};
priority_queue<node> qmax;
priority_queue<node> qdis;
node stk[N];
int tot;
bool vis[N];

int main(){
    freopen("129.in", "r", stdin);
    freopen("129.out", "w", stdout);
    n = read(), l = read();
    for (int i = 1; i <= n; i++){
        a[i] = read(), b[i] = read();
        qdis.push((node){i, a[i] - b[i]});
        qmax.push((node){i, a[i]});
    }
    for (int i = 1; i <= n; i++) c[i] = read();
    for (int i = 1; i <= n; i++){
        while (!qmax.empty() && vis[qmax.top().id]) qmax.pop();
        if (!qmax.empty() && now + qmax.top().val >= l){
            cout << i;
            return 0;
        }
        h += c[i];
        if (now + qdis.top().val <= h){
            cout << -1;
            return 0;
        }
        int x = qdis.top().val, id = qdis.top().id;
        qdis.pop();
        vis[id] = 1;
        int cnt = 0;
        while (!qdis.empty() && qdis.top().val + now > h && cnt <= 100){
            qmax.push((node){qdis.top().id, qdis.top().val - x + a[id]});
            stk[++tot] = qdis.top();
            qdis.pop();
            cnt++;
        }
        now += x;
        while (tot) qdis.push(stk[tot--]);
    }
    cout << -1;
    return 0;
}

106 石头剪刀布

暴力搜索加 $dp$ 过 $10 pts$。

#include<iostream>
#include<cstring>

using namespace std;

inline int read(){
    register int x = 0, f = 1;
    register char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

const int N = 2e3 + 10, mod = 998244353;
int n, ans[N];
char c[N][5];
int a[N][5], d[N], dp[N];
void dfs(int x){
    if (x == n + 1){
        for (int i = 1; i <= n; i++) dp[i] = 1;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j < i; j++){
                if (d[j] == 0 && d[i] == 1 || d[j] == 1 && d[i] == 2 || d[j] == 2 && d[i] == 0) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) res = max(res, dp[i]);
        ans[res] = (ans[res] + 1) % mod;
        return;
    }
    for (int i = 1; i <= a[x][0]; i++){
        d[x] = a[x][i];
        dfs(x + 1);
    }
}

int main(){
    freopen("106.in", "r", stdin);
    freopen("106.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++){
        cin >> c[i];
        for (int j = 0; j < strlen(c[i]); j++) a[i][j + 1] = c[i][j] - '0';
        a[i][0] = strlen(c[i]);
    }
    dfs(1);
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    return 0;
}