C、H、I 题解_牛客博客

若若跟我说要出三个前期/中期题，于是就有了这三个题。

C 挖矿

有个显然的想法：对于黑心资本家的检查，你被抓住的概率只和你的下矿天数有关，和你的具体下矿日期无关。

因此就变成了两个部分：对于某一个下矿天数 $x$ ，求 $x$ 天下矿的最大期望收益和 $x$ 天下矿不被监工发现的概率，相乘就是下矿 $x$ 天的最大期望收益。然后从 $0 \cdots n$ 枚举下矿天数，可得最大期望收益。

对于前者，可以设 $f_{x, y}$ 表示对于前 $x$ 天，下矿 $y$ 次的期望最大收益，一般地，有：

f_{x,y} = \max \{f_{x-1,y},(f_{x-1,y-1}+a_x)(1-p_x)\}

注意一下边界，dp 一下就能求出来。

对于后者，考虑使用古典概型求，设 $pp_n[k][m]$ 表示下矿 $m$ 天监工 $k$ 天不被发现的概率，有 $pp_n[k][m] = \frac{\binom{m}{k}}{\binom{n}{k}}$ 。

其中 $k \leq m \leq n$ 。

展开之后发现这个东西可以递推： pp[k][m] = (m-k+1)/(n-k+1) * pp[k-1][m]

边界：

$pp_n[0][m] = 1$ 。
$pp_n[k'][m'] = 0, k' > m'$ 。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;

const int N = 5e3 + 10;
int a[N];
double p[N], f[N][N], pp[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, C, x;
    cin >> n >> C;
    cout << n << endl;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n) cin >> x, p[i] = x / 1000.0;
    f[0][0] = 0;
    rep(i,1,n) {
		f[i][0] = 0;
		rep(k,1,i-1)
	 	  	f[i][k] = max(f[i - 1][k], (f[i - 1][k - 1] + a[i]) * (1 - p[i]));
			f[i][i] = (f[i - 1][i - 1] + a[i]) * (1 - p[i]);
    }
    pp[0][0] = 1;
    rep(m,1,n) {
		pp[0][m] = 1;
		rep(k,1,min(m,n)) pp[k][m] = pp[k - 1][m] * (m - k + 1) / (n - k + 1);
    }

    cout.setf(ios::fixed);
    cout.precision(12);
    rep(k,0,n) {
		double ans = 0;
		rep(j,0,n) ans = max(ans, (C + f[n][j] / 5) * pp[k][j]);
		cout << ans << ' ';
    }
    cout << endl;
    return 0;
}

H 数学

对于分解为 $1$ 的数，可以用 $\mathcal{O}(\sqrt n)$ 的时间枚举平方根，共 $\mathcal{O}(\sqrt n)$ 。

对于分解为 $2$ 的数，可以分别枚举组成它的两个平方数（取值集大小 $\mathcal{O}(\sqrt n)$ ，由上一步求出）是什么，时间复杂度 $\mathcal{O}(n)$ ，然后剔除掉只分解为 $1$ 的数。

分解为 $3$ 的数同样可以参照上面的方法在 $\mathcal{O}(n \sqrt n)$ 求出。

根据拉格朗日四数平方和定理，剩下的数分解数为 $4$ 。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define pb push_back

using namespace std;

const int N = 1e5 + 10, mod = 998244353;

int f[N];
inline bool sq(int x) {
    int p = sqrt(x);
    return p * p == x;
}

signed main() {
    int n;
    cin >> n;
    vector<int> v, w;
    for(int i = 1; i * i <= n; ++ i) {
	f[i * i] = 1;
	v.pb(i * i);
    }
    for(int x : v)
	for(int y : v) {
	    if(x + y > n) break;
	    if(!f[x + y]) {
		f[x + y] = 2;
		w.pb(x + y);
	    }
	}
    for(int y : w)
	for(int x : v) {
	    if(x + y > n) break;
	    if(!f[x + y]) f[x + y] = 3;
	}

    int ans = 1;
    rep(i,1,n) {
	if(!f[i]) f[i] = 4;
	ans = 1ll * ans * f[i] % mod;
    }
    cout << ans << endl;
    return 0;
}

I 电梯

对不起，题面写了依托答辩。

只需要维护一下电梯运行的状态，仔细判断何时上下客即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define pb push_back

using namespace std;

const int N = 1e5 + 10;
int t[N], a[N], b[N], ans[N];
queue<int> up[N], down[N];
struct node {
    int id;
    node() {}
    node(int x) : id(x) {}
    bool operator < (const node &o) const { return b[id] < b[o.id]; }
    bool operator > (const node &o) const { return b[id] > b[o.id]; }
};
priority_queue<node> inn;
priority_queue<node,vector<node>,greater<node>> in;
int cnt;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int q, K, C = 0, task = 0;
    cin >> q >> K;
    rep(i,1,q) {
	cin >> t[i] >> a[i] >> b[i];
	C = max(C, max(a[i], b[i]));
    }
    int p = 1, flr = 1, state = 0;
    for(int tm = 0; ; ++ tm) {
 	if(task == q) break;
	// unload
	if(state == 1)
	    while(!in.empty() && b[in.top().id] == flr) {
		ans[in.top().id] = tm;
		in.pop(); -- cnt; ++ task;
	    }
	if(state == 2)
	    while(!inn.empty() && b[inn.top().id] == flr) {
		ans[inn.top().id] = tm;
		inn.pop(); -- cnt; ++ task;
	    }

	// add item by order
	vector<int> inc;
	while(p <= q && t[p] <= tm) { inc.pb(p); ++ p; }
	stable_sort(inc.begin(), inc.end(), [&](int x, int y) {
	    return t[x] < t[y] || (t[x] == t[y] && abs(a[x] - b[x]) < abs(a[y] - b[y]));
	});
	for(int x : inc) {
	    if(a[x] < b[x]) up[a[x]].push(x);
	    else down[a[x]].push(x);
	}

	// modify state
	bool hasupper = false, haslower = false;
	rep(i,flr+1,C) if(up[i].size() || down[i].size()) { hasupper = true; break; }
	if(cnt < K && up[flr].size()) hasupper = true;
	rep(i,1,flr-1) if(up[i].size() || down[i].size()) { haslower = true; break; }
	if(cnt < K && down[flr].size()) haslower = true;

	if(state == 0) {
	    if((cnt < K && up[flr].size()) || hasupper) state = 1;
	    else if((cnt < K && down[flr].size()) || haslower) state = 2;
	} else if(state == 1) {
	    if(!hasupper && cnt == 0) state = 0;
	} else if(state == 2) {
	    if(!haslower && cnt == 0) state = 0;
	}

	// load users
	if(state == 1) {
	    while(cnt < K && up[flr].size()) {
		in.push(up[flr].front()); up[flr].pop(); ++ cnt;

	    }
	} else if(state == 2) {
	    while(cnt < K && down[flr].size()) {
		inn.push(down[flr].front()); down[flr].pop(); ++ cnt;
	    }
	}

	// modify floor
	if(state == 1) ++ flr;
	else if(state == 2) -- flr;
    }

    rep(i,1,q) cout << ans[i] << ' ';
    cout << endl;
    return 0;
}