当前位置：首页 > article >正文

Atcoder ABC382

article 2025/1/12 8:05:45

C

在回转寿司店里面有n个标为 $A_i$ 人和m个标为 $B_j$ 寿司。
每个寿司依次从1 2 3 … n人面前经过，当 $B_j \geq A_i$ 时i人就拿走寿司。
问：每个寿司被谁吃了？

对寿司进行排序，依次从1 2 3 … n人来看每个人怎么拿。
排序之后会发现，每个人一定会把最前面的那些满足条件的寿司拿走。然后下一个人接着拿。因此可以用一个指针指向当前拿到的寿司位置。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int n, m;
const int N = 200020;
struct Item {
	int x, i;
} b[N];
int a[N];
int ans[N];


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; ++ i) {
		int t;
		cin >> t;
		b[i] = {t, i};
	}
	sort(b + 1, b + m + 1, [&](Item x, Item y){
		return x.x > y.x;
	});
	memset(ans, -1, sizeof(ans));
	int j = 0;
	for(int i = 1; i <= n; ++ i) {
		while(j + 1 <= m && b[j + 1].x >= a[i]) {
			ans[b[j + 1].i] = i;
			++ j;
		}
	}
	for (int i = 1; i <= m; ++ i) {
		printf("%d\n", ans[i]);
	}
    return 0;
}

D

搜索数列。写的时候注意剪枝。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


vector<vi> ans;
int n, m;
int path[12];


void go(int pos, int cur) {
    if (cur > m)
        return;
    path[pos] = cur;
    if (pos == n - 1) {
        vi temp(path, path + n);
        ans.push_back(temp);
        return;
    }
    int lmt = cur + (n - pos - 1) * 10;
    if (lmt > m)
        return;
    
    for (int i = 10; i <= 20; ++i) {
        go(pos + 1, cur + i);
    }
}


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for (int a0 = 1; a0 <= min(m, 20); ++a0) {
        go(0, a0);
    }
    printf("%d\n", ans.size());
    for (auto vi : ans) {
        for (int x : vi) {
            printf("%d ", x);
        }
        printf("\n");
    }
    return 0;
}

E

有无数个包，每个包里面都有N张卡片，每张卡片是稀有卡的概率是 $p_i$
一次只能打开一个包，然后拿出所有卡片抽卡。
问：抽到S张稀有卡片或以上，需要打开包的数量的数学期望。

经典数学期望模型。
这个题有两个子问题。第一个子问题是每次打开一个包，在单独一个包内抽到 $t$ 张稀有卡的分布。
第二个子问题是已知离散分布 $t$ ，求 $\sum^k_{i=1} t_i \geq S$ 时次数k的期望。

第一问可以用经典dp来做：设 $g (i, j)$ 为抽到第i张卡片时有j张稀有卡的概率
$g(i,j)=g(i-1,j)*q_i+g(i-1,j)*p_i$ 其中 $q_i$ 是非稀有的概率 $1-p_i)$
最后的分布概率 $p (t) = g (n, t)$
第二问是数学期望求法中常见的技巧：
设 $E (X)$ 代表总和能拿到 $X$ 或以上的数量稀有卡片需要的期望次数。这里不是exactly X次，而用了 $\geq X$
$E (x) = (E (0) p (x) + E (1) p (x - 1) + .. + E (x) p (0)) + 1$
注意：这里将每一项期望都拆开成和式就会发现公式成立
移项可得
$(1-p(0))E(x)=1+\sum_{i=0}^{x-1} E(i)p(x-i)$
依次递推即可求得

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

double f[5005][5005];
double g[5005];
double p[5005];
int n, X;


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> X;
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;
        p[i] = double(t) / 100;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = f[i - 1][0] * (1 - p[i]);
        for (int j = 1; j <= X; ++j) {
            f[i][j] = f[i - 1][j - 1] * p[i] + f[i - 1][j] * (1 - p[i]);
        }
    }
    double r = 1 - f[n][0];
    g[0] = 0;
    for (int i = 1; i <= X; ++i) {
        double s = 0;
        for (int j = 1; j < i; ++j) {
            s += g[i - j] * f[n][j];
        }
        g[i] = (1 + s) / r;
    }
    printf("%.12f\n", g[X]);
    return 0;
}

F

线段树
从下往上排序，落下来的线段要检查[l,r]上最大值，然后落在最大值+1的行上。
然后这条线段对[l,r]区间更新最大值+1

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int h, w, n;
const int N = 200020;
struct Item {
    int r, c, l, i;
} a[N];
int ans[N];

#define lu (u * 2) 
#define ru (u * 2 + 1)
struct SegTree {
    struct Node {
        int l, r, mx, mark;
    } tr[N << 2];

    void up(int u) {
        tr[u].mx = max(tr[lu].mx, tr[ru].mx);
    }

    void down(int u) {
        if (tr[u].mark) {
            tr[lu].mark = tr[ru].mark = tr[u].mark;
            tr[lu].mx = tr[ru].mx = tr[u].mx;
            tr[u].mark = 0;
        }
    }

    void build(int l, int r, int u) {
        tr[u].l = l, tr[u].r = r;
        if(l == r) {
            tr[u].mx = 0;
            return;
        }
        int mi = (l + r) / 2;
        build(l, mi, lu);
        build(mi + 1, r, ru);
    }

    void update(int l, int r, int u, int val) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].mark = 1;
            tr[u].mx = val;
            return;
        }
        down(u);
        int mi = (tr[u].l + tr[u].r) / 2;
        if (l <= mi) {
            update(l, r, lu, val);
        } 
        if (r > mi) {
            update(l, r, ru, val);
        }
        up(u);
    }

    int query(int l, int r, int u) {
        if (l <= tr[u].l && tr[u].r <= r) {
            return tr[u].mx;
        }
        down(u);
        int rt = 0;
        int mi = (tr[u].l + tr[u].r) / 2;
        if (l <= mi) {
            rt = max(rt, query(l, r, lu));
        } if (r > mi) {
            rt = max(rt, query(l, r, ru));
        }
        return rt;
    }
} st;


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> h >> w >> n;
    for (int i = 1; i <= n; ++i) {
        int r, c, l;
        cin >> r >> c >> l;
        a[i] = { r, c, l, i };
    }
    sort(a + 1, a + n + 1, [](Item x, Item y) {
        return x.r > y.r;
        }
    );
    st.build(1, w, 1);
    for (int i = 1; i <= n; ++i) {
        int l = a[i].c, r = a[i].c + a[i].l - 1;
        int max_h = st.query(l, r, 1);
        int cur_h = max_h + 1;
        ans[a[i].i] = cur_h;
        st.update(l, r, 1, cur_h);
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", h + 1 - ans[i]);
    }
    return 0;
}