目录
Contest InfoSolutions A. Fifty-FiftyB. Ordinary NumberC. Divide the ProblemsD. Blue and Red BallsE. Hopscotch AddictF. Small ProductsPractice Link
SolvedABCDEF6/6OOOOØO O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试题意： 有\(K\)个蓝球，\(N - K\)个红球，询问将蓝球分成\(i(1 \leq i \leq k)\)堆，中间用红球隔开的方案数分别是多少?
思路： 考虑先将\(k\)个蓝球分成\(i\)堆，然后每堆后面跟着一个红球，然后就有\(i + 1\)个空隙，剩下的红球相当于要放入\(i + 1\)个空箱中，允许空箱的经典问题。
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 2010 const int p = 1e9 + 7; int n, k; ll fac[N], inv[N]; ll qmod(ll base, ll n) { ll res = 1; while (n) { if (n & 1) { res = res * base % p; } base = base * base % p; n >>= 1; } return res; } ll C(int n, int m) { if (n < m) return 0; return fac[n] * inv[m] % p * inv[n - m] % p; } ll f(int n, int i, int k) { ll remind = n - k; if (n - k < i - 1) { return 0; } remind -= i - 1; return C(k - 1, i - 1) * C(i + remind, i) % p; } int main() { fac[0] = 1; for (int i = 1; i <= 2000; ++i) { fac[i] = fac[i - 1] * i % p; } inv[2000] = qmod(fac[2000], p - 2); for (int i = 2000; i >= 0; --i) { inv[i - 1] = inv[i] * i % p; } while (scanf("%d%d", &n, &k) != EOF) { for (int i = 1; i <= k; ++i) { printf("%lld\n", f(n, i, k)); } } return 0; }题意： 求\(S\)到\(T\)的最短路，并且要满足其长度是\(3\)的倍数。
思路：\(dis[i][j]\)表示到第\(i\)个点，长度模\(3\)的值为\(j\)的最短路是多少，然后跑Dijkstra即可。
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 100010 int n, m, s, t; vector <vector<int>> G; struct node { int u, w; node() {} node (int u, int w) : u(u), w(w) {} bool operator < (const node &other) const { return w > other.w; } }; int dis[N][3], used[N][3]; void BFS() { for (int i = 1; i <= n; ++i) { for (int j = 0; j < 3; ++j) { dis[i][j] = INF; used[i][j] = 0; } } dis[s][0] = 0; priority_queue <node> pq; pq.push(node(s, 0)); while (!pq.empty()) { int u = pq.top().u, w = pq.top().w; pq.pop(); if (used[u][w % 3]) continue; used[u][w % 3] = 1; for (auto v : G[u]) { if (dis[v][(w + 1) % 3] > w + 1) { dis[v][(w + 1) % 3] = w + 1; pq.push(node(v, w + 1)); } } } } int main() { while (scanf("%d%d", &n, &m) != EOF) { G.clear(); G.resize(n + 1); for (int i = 1, u, v; i <= m; ++i) { scanf("%d%d", &u, &v); G[u].push_back(v); } scanf("%d%d", &s, &t); BFS(); if (dis[t][0] == INF) puts("-1"); else { printf("%d\n", dis[t][0] / 3); } } return 0; }题意： 构造一个长度为\(k\)的，并且相邻两数之积不超过\(N\)的序列的方案数是多少？
思路：\(f[i][j]\)表示到第\(i\)位，当前位为\(j\)的方案数是多少。 暴力\(DP\)显然不行。 但是我们考虑我们每次对于\(j\)转移的都是\(\sum\limits_{j = 1}^{N / j} f[i - 1][j]\)，考虑到\(N / j\)的取值只有\(2\sqrt{N}\)种，所以只需要存\(k \cdot 2\sqrt{N}\)种状态。转移即可。
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 110 #define M 100010 #define pii pair <int, int> #define fi first #define se second const ll p = 1e9 + 7; int n, k; ll f[N][M]; pii g[M]; map <int, int> mp; int main() { while (scanf("%d%d", &k, &n) != EOF) { memset(f, 0, sizeof f); mp.clear(); int m = 0; for (int i = 1, j; i <= k; i = j + 1) { j = k / (k / i); g[++m] = pii(j, j - i + 1); mp[j] = m; } for (int i = 1; i <= m; ++i) { f[1][i] = (f[1][i - 1] + g[i].se) % p; } for (int i = 2; i <= n; ++i) { for (int j = 1; j <= m; ++j) { f[i][j] = (f[i][j - 1] + 1ll * g[j].se * f[i - 1][mp[k / g[j].fi]] % p) % p; } } printf("%lld\n", f[n][m]); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11148059.html
