洛谷P1291 [SHOI2002]百事世界杯之旅

题目链接：

题目分析：

收集邮票的弱弱弱弱化版，因为是期望，考虑倒推

设\(f[i]\)表示现在已经买齐了\(i\)种，距离买完它的剩余期望次数

那么下一次抽有\(\frac{i}{n}\)的概率抽到已经有的，有\(\frac{n - i}{n}\)的概率抽到还没有的

那这两种情况的期望分别是\(\frac{i}{n} * f[i]\)和\(\frac{n - i}{n} * f[i + 1]\)，再加上它自己的期望\(1\)

有\(f[i] = f[i] * \frac{i}{n} + \frac{n - i}{n} * f[i + 1] + 1\)

化简一下得到\(f[i] = f[i + 1] + \frac{n}{n - i}\)

倒回来\(dp\)即可

输出比较恶心，开两个数组分别记录状态的分子和分母，然后手写一下约分之类的函数

代码：

#include <bits/stdc++.h>

#define N (1000 + 10)

#define int long long

using namespace std;

inline int read() {

	int cnt = 0, f = 1; char c = getchar();

	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}

	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}

	return cnt * f;

}

int n;

int f1[N], f2[N];

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

int lcm(int a, int b) {return a * b / gcd(a, b);}

int calc1(int x, int y, int x_, int y_) {

	int LCM = lcm(y, y_);

	int d1 = LCM / y, d2 = LCM / y_;

	int ans = x * d1 + x_ * d2;

	return ans;

}

int calc2(int x, int y, int x_, int y_) {

	int LCM = lcm(y, y_);

	return LCM;

}

void solve(int &x, int &y) {

	int GCD = gcd(x, y);

	x /= GCD, y /= GCD;

}

int get_digit(int x) {

	int cnt = 0;

	while(x) {

		++cnt;

		x /= 10;

	}

	return cnt;

}

int ans1, ans2, ans3;

signed main(){

	n = read();

	f1[n] = 0, f2[n] = 0;

	f1[n - 1] = n, f2[n - 1] = 1;

	for (register int i = n - 2; ~i; --i) {

		f1[i] = calc1(f1[i + 1], f2[i + 1], n, n - i);

		f2[i] = calc2(f1[i + 1], f2[i + 1], n, n - i);

		solve(f1[i], f2[i]);

	}

	ans1 = f1[0] / f2[0];

	if (f1[0] % f2[0] == 0) return printf("%lld", ans1), 0;

	f1[0] = f1[0] % f2[0];

	int c1 = get_digit(ans1);

	int c2 = get_digit(f2[0]);

	for (register int i = 1; i <= c1; i++) printf(" ");

	printf("%lld\n%lld", f1[0], ans1);

	for (register int i = 1; i <= c2; i++) printf("-");

	printf("\n");

	for (register int i = 1; i <= c1; i++) printf(" ");

	printf("%lld", f2[0]);

	return 0;

}

巴特西

洛谷P1291 [SHOI2002]百事世界杯之旅

题目链接：

题目分析：

代码：

最新文章

热门文章