ABC243
E
题目大意
给出一个无向连通图，在保证任两点最短路 \(d(u,v)\) 不变的情况下，最多能删多少边。
解题思路
考虑一条边满足什么条件可以删。
给出结论：当 \(d(u,v) \le w\) 且 \(d(u,v)\) 所代表的路径不经过 \((u,v)\) 时，可以删去边 \((u,v)\)。
证明：当 \(d(u,v) \le w\) 时，如果有两点之间的最短路要从 \(u\) 到 \(v\)，那么走 \(d(u,v)\) 所代表的路径一定不劣，因此任意两点最短路一定可以不走 \((u,v)\)，此边可以删去。
现在考虑如何实现算法，观察到数据范围： \(n\le 300\)，考虑使用 Floyd 算法。
- 当 \(d(u,v) < w\) 时，只需用 Floyd 计算两点间最短路再判断大小即可。
- 当 \(d(u,v) = w\) 且 \(d(u,v)\) 所代表的路径不经过 \((u,v)\) 时，由于此时 \(d(u,v) = w\) ，在 Floyd 松弛时如果发现松弛后与当前最短路相等（且 \(k\) 与 \(i\)、\(j\) 不相等），用一个布尔数组记录这两点间最短路不唯一即可。
代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
const int N = 310, M = 1e5 + 10;
struct edge
{
int u, v;
ll w;
} e[M];
int n, m, ans;
ll dis[N][N];
bool b[N][N];
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(dis, 0x3f, sizeof dis);
for (int i = 1; i <= m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
dis[e[i].u][e[i].v] = dis[e[i].v][e[i].u] = e[i].w;
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (dis[i][j] == dis[i][k] + dis[k][j] && i != k && j != k)
{
b[i][j] = 1;
}
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
for (int i = 1; i <= m; i++)
{
if (b[e[i].u][e[i].v] == 1 || dis[e[i].u][e[i].v] < e[i].w)
{
ans++;
}
}
cout << ans << endl;
return 0;
}
F
题目大意
有 \(n\) 个元素，给出每个元素被抽到的概率 \(w\)，抽 \(k\) 次，求恰好抽到 \(m\) 种元素的概率。
解题思路
观察数据范围，暴力判断抽到哪些元素会超时，考虑概率 dp。
- 状态表示：\(dp[i][j][k]\) 表示考虑到第 \(i\) 个元素，抽了 \(k\) 次，有 \(j\) 种不同元素的概率。
- 初始化：显然不抽一定会有 \(0\) 种不同，所以 \(dp[i][0][0]=1\)。
- 状态转移：类似于多重背包，我们分两种情况讨论。
- 不抽第 \(i\) 个元素：那么就是前 \(i-1\) 个元素，抽了 \(k\) 次，有 \(j\) 种不同元素的概率，有转移方程：\[dp[i][j][k]=dp[i-1][j][k] \]
- 抽第 \(i\) 个元素：设抽了 \(x\) 个，那么抽中其他元素的概率就是 \(dp[i-1][k-x][j-1]\)，抽中 \(x\) 个 \(i\) 元素的概率就是 \((\frac{w_i}{\sum w})^x\)，另外我们不考虑抽中元素的顺序，因此需要再乘上 \(C_k^x\)，于是有转移方程：\[dp[i][j][k]=dp[i-1][k-x][j-1]\cdot(\frac{w_i}{\sum w})^x\cdot C_k^x \]
- 答案：\(dp[n][m][k]\)。
代码实现上，可以预处理阶乘来 \(O(1)\) 计算组合数，总时间复杂度 \(O(n^4\log P)\)，\(O(\log P)\)是逆元的复杂度。
代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
const ll N = 60, P = 998244353;
int n, m, t;
ll w[N], jc[N], sum;
ll dp[N][N][N];
inline ll qkpow(ll x, ll y)
{
ll res = 1;
while (y)
{
if (y & 1)
{
(res *= x) %= P;
}
(x *= x) %= P;
y >>= 1;
}
return res;
}
inline ll c(ll x, ll y)
{
return jc[y] * qkpow(jc[x] * jc[y - x] % P, P - 2) % P;
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> t;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
sum += w[i];
dp[i][0][0] = 1;
}
jc[0] = 1;
for (int i = 1; i <= t; i++)
{
jc[i] = (jc[i - 1] * i) % P;
}
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
for (int k = 1; k <= t; k++)
{
dp[i][j][k] = dp[i - 1][j][k];
for (int x = 1; x <= k; x++)
{
(dp[i][j][k] += dp[i - 1][j - 1][k - x] * c(x, k) % P * qkpow(w[i], x) % P * qkpow(qkpow(sum, x), P - 2) % P) %= P;
}
}
}
}
cout << dp[n][m][t];
return 0;
}
G
题目大意
给出一个序列，一开始只有 \(X\) 这一元素，设序列末尾数为 \(Y\)，可以往序列末尾加小于 \(\sqrt Y\) 的数，求进行 \(10^{100}\) 次操作后有多少可能的序列。
解题思路
算法 1
发现当末尾的数为 \(1\) 时，后面的数只能为 \(1\)，因此可以将多余的 \(1\) 剔除以此大大减小序列长度。
考虑线性 dp。
队首元素为 \(X\)，很大，难以处理，队末为 \(1\)，较好处理，并且序列长度不定，不好描述。
于是便可以如此设计动态规划：
- 状态表示：\(dp[i]\) 表示以 \(i\) 为队首的序列个数。
- 初始化：\(dp[1]=1\)。
- 状态转移：\(i\) 后加的数范围为 \(1\le j<\sqrt{i}\)，所以有：\[dp[i]=\sum_{j=1}^{\lfloor\sqrt i\rfloor}dp[j] \]考虑用前缀和优化，记 \(s[i]\) 为 \(\sum_{j=1}^{i}dp[j]\)，所以有：\[dp[i]=s[\lfloor\sqrt{i}\rfloor] \]
- 答案：因为\(dp[X]=s[\lfloor\sqrt{X}\rfloor]\)，所以只要遍历到 \(\lfloor\sqrt{X}\rfloor\) 即可，答案为 \(s[\lfloor\sqrt{X}\rfloor]\)
时间复杂度 \(O(\sqrt X)\)，50 分。
算法 2
考虑优化算法 1，用同样的套路，变形状态转移方程：
\[\begin{aligned} dp[i]&=\sum_{j=1}^{\lfloor\sqrt i\rfloor}dp[j]\\ &=\sum_{j=1}^{\lfloor\sqrt i\rfloor}s[\lfloor\sqrt j\rfloor] \end{aligned} \]发现 \(dp[X]\) 只由 \(\sqrt[4]{x}\) 种不同的 \(s[i]\) 组成，所以只需遍历到 \(\sqrt[4]{x}\) 即可。
考虑具体的数量关系，不难发现开根号向下取整为 \(x\) 的整数有 \(2x+1\) 个，特别地，最后一项可能凑不齐，为 \(\lfloor\sqrt X\rfloor-(\lfloor\sqrt[4] X\rfloor)^2+1\)。
所以有：
\[dp[X]=\sum_{i=1}^{\lfloor\sqrt[4] X\rfloor-1}(2i+1) \cdot s[i]+(\lfloor\sqrt X\rfloor-(\lfloor\sqrt[4] X\rfloor)^2+1)\cdot s[\lfloor\sqrt[4] X\rfloor] \]时间复杂度 \(O(\sqrt[4] X)\)，可以通过本题。
代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define ld long double
using namespace std;
const int N = 1e5;
ll t, x, n, ans;
ll dp[N], s[N];
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
dp[1] = s[1] = 1;
for (int i = 2; i < N; i++)
{
dp[i] = s[(ll)sqrtl((ld)i)];
s[i] = s[i - 1] + dp[i];
}
cin >> t;
while (t--)
{
ans = 0;
cin >> x;
n = sqrtl(sqrtl((ld)x));
for (int i = 1; i <= n - 1; i++)
{
ans += (2 * i + 1) * s[i];
}
ans += s[n] * ((ll)sqrtl((ld)x) - n * n + 1);
cout << ans << endl;
}
return 0;
}