B. 硬币问题
题目描述
有 \(N\) 种硬币，每种都有无限个。求 \([1,m]\) 中有多少种面额是不能被凑出来的。
思路
我们可以先求出不使用 \(w_1\) 凑出来的数，由于之后可以再添加若干个 \(w_1\)。所以对于 \(\bmod w_1\) 同余的数只需看较小的数。这明显就是一个最短路。对于每种余数求出有多少种即可。
空间复杂度 \(O(N+\min\{w_i\})\)，时间复杂度 \(O(N\min \{w_i\})\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const int MAXN = 101, MAXV = 1000001;
const ll INF = (ll)(1e18);
int n, a[MAXN];
ll m, ans, dist[MAXV];
bool vis[MAXV];
void dij() {
priority_queue<pii, vector<pii>, greater<pii>> pq;
fill(dist, dist + a[1], INF);
dist[0] = 0;
pq.push({0, 0});
for(; !pq.empty(); ) {
ll dis = pq.top().first, u = pq.top().second;
pq.pop();
if(vis[u]) {
continue;
}
vis[u] = 1;
for(int i = 2; i <= n; ++i) {
if(dis + a[i] < dist[(u + a[i]) % a[1]] && dis + a[i] <= m) {
dist[(u + a[i]) % a[1]] = dis + a[i];
pq.push({dis + a[i], (u + a[i]) % a[1]});
}
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
dij();
for(int i = 0; i < a[1]; ++i) {
ans += (dist[i] == INF ? 0ll : (m - dist[i]) / a[1] + 1);
}
cout << ans - 1;
return 0;
}
D. 期望长度
题目描述
有 \(N\) 个数 \(A_1,A_2,\dots,A_N\)。你要从中选出一个区间 \([l,r]\)，使得其最大值为 \(x\)。
对于 \(\forall 1\le x\le N\)，求出你选出区间的期望长度。
思路
看到这种题目，首先想到枚举最大值。并用单调栈求出每个数左/右边第一个大于当前数的下标 \(l_i,r_i\)。很显然最大值 \(=A_i\) 的方案数为 \((i-l_i)\cdot (r_i-i)\)。接着我们来推一下长度之和，这里我们令 \(a=i-l_i,b=r_i-l_i-1\)：
\[\begin{array}{l} &(a+\dots+b)+((a-1)+\dots+(b-1))+\dots+(1+\dots+(b-a+1))\\ =&\frac{(a+b)\cdot (b-a+1)}{2}+\frac{(a+b-2)\cdot (b-a+1)}{2}+\dots+\frac{(b-a+2)\cdot (b-a+1)}{2}\\ =&\frac{b-a+1}{2}\cdot ((a+b)+(a+b-2)+\dots(b-a+2))\\ =&\frac{b-a+1}{2}\cdot \frac{(2b+2)\cdot a}{2}\\ =&\frac{(b-a+1)\cdot (b+1)\cdot a}{2} \end{array} \]时空复杂度均为 \(O(N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100001, MOD = int(1e9) + 7, inv2 = 500000004;
int n, a[MAXN], stk[MAXN], top, l[MAXN], r[MAXN], sum[MAXN], cnt[MAXN];
int Pow(int a, int b) {
int ret = 1;
for(; b; a = 1ll * a * a % MOD, b >>= 1) {
if(b & 1) {
ret = 1ll * ret * a % MOD;
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
r[i] = n + 1;
}
for(int i = 1; i <= n; ++i) {
for(; top && a[stk[top]] < a[i]; r[stk[top--]] = i) {
}
l[i] = stk[top];
stk[++top] = i;
}
for(int i = 1; i <= n; ++i) {
cnt[a[i]] = (cnt[a[i]] + 1ll * (i - l[i]) * (r[i] - i) % MOD) % MOD;
int L = i - (l[i] + 1) + 1, R = (r[i] - 1) - (l[i] + 1) + 1;
sum[a[i]] = (sum[a[i]] + 1ll * (R - L + 1) * (R + 1) % MOD * L % MOD * inv2 % MOD) % MOD;
}
for(int i = 1; i <= n; ++i) {
cout << 1ll * sum[i] * Pow(cnt[i], MOD - 2) % MOD << "\n";
}
return 0;
}