20250814 LiveDream 模拟赛总结

· · 个人记录

总结

期望 100 + 100 + 0 + 0 = 200

实际 100 + 100 + 0 + 0 = 200

排名 5/40

少考了30分钟，感觉还行

T1

签到，f_{i,j} 表示第 i 选 j 的方案数，前缀和优化暴力枚举倍数

#include <bits/stdc++.h>
#define i64 long long

using namespace std;

const i64 kMaxN = 15, kMaxM = 1e5 + 5, Mod = 99824353;

i64 f[kMaxN][kMaxM], n, k, sm, sm1, ans;

signed main() {

//  freopen("T1.in", "r", stdin);
//  freopen("T1.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= k; i++) f[1][i] = 1, sm++;
    for (int i = 2; i <= n; i++) {
        sm1 = 0;
        for (int j = 1; j <= k; j++) {
            f[i][j] = sm;
            for (int kk = 2; kk * j <= k; kk++) {
                f[i][j] = (f[i][j] - f[i - 1][kk * j] + Mod) % Mod;
            } 
            sm1 = (sm1 + f[i][j]) % Mod;
        }
        sm = sm1;
    } 
    cout << sm; 
    return 0;
}

T2

也挺简单的其实，状态很好想, f_{i,j} 在第 i 个位置放置第 j 个超级城市的最小代价。由于不能确定 i 之后的代价，所以在下次转移的时候再加上

#include <bits/stdc++.h>
#define i64 long long
#define Pii pair<i64, i64>

using namespace std;

const i64 kMaxN = 300, INF = 1e18;

i64 f[kMaxN][kMaxN], s[kMaxN][kMaxN], x[kMaxN], c[kMaxN], l[kMaxN], n, k, ans = INF;
Pii e[kMaxN];

signed main() {
//  freopen("T2.in", "r", stdin);
//  freopen("T2.out", "w", stdout);
    fill(f[0], f[0] + kMaxN * kMaxN, INF);
    for (int i = 1; i <= 256; i++) f[i][0] = 0; 
    cin >> n >> k;
    for (i64 i = 1; i <= n; i++) {
        cin >> e[i].first >> e[i].second, e[i].first++;
    }
    sort(e + 1, e + n + 1);
    for (i64 i = 1; i <= n; i++) {
        x[i] = e[i].first, c[i] = e[i].second, l[x[i]] += c[i];
    }
    for (i64 i = 1; i <= 256; i++) {
        for (i64 j = 1; j <= 256; j++) {
            s[i][j] = s[i][j - 1] + (j - i) * (j - i) * l[j];
        }
    }
    for (i64 i = 1; i <= 256; i++) {
        for (i64 j = 1; j <= k; j++) {
            if (j == 1) {
                f[i][j] = s[i][i]; continue;
            }
            for (i64 p = 1; p <= i - 1; p++) {
                i64 mid = i + p >> 1;
                f[i][j] = min(f[i][j], f[p][j - 1] + s[p][mid] - s[p][p - 1] + s[i][i] - s[i][mid]);
            }
        }
    }
    for (int i = 1; i <= 256; i++) {
        ans = min(ans, f[i][k] + s[i][256] - s[i][i]);  
    }
    cout << ans << '\n'; 
    return 0;
}

T3

```cpp #include <bits/stdc++.h> #define i64 long long using namespace std; const i64 kMaxN = 1e5 + 5, kMaxM = 205, INF = 1e18; i64 f[kMaxN][kMaxM], n, m, k; struct E { i64 s, t, d, w; friend bool operator<(const E A, const E B) { if (A.w == B.w) return A.d < B.d; return A.w < B.w; } } a[kMaxN]; bool cmp(E A, E B) { return A.s < B.s; } priority_queue<E> q; signed main() { cin >> n >> m >> k; for (i64 i = 1; i <= k; i++) cin >> a[i].s >> a[i].t >> a[i].d >> a[i].w; sort(a + 1, a + k + 1, cmp); fill(f[2], f[kMaxN], INF); for (i64 i = 1, j = 1; i <= n; i++) { for (; j <= k && a[j].s == i; q.push(a[j]), j++); for (; q.size() && q.top().t < i; q.pop()); if (!q.size()) { for (i64 p = 0; p <= m; p++) f[i + 1][p] = min(f[i + 1][p], f[i][p]); } else { for (i64 p = 0; p <= m; p++) f[q.top().d + 1][p] = min(f[q.top().d + 1][p], f[i][p] + q.top().w); for (i64 p = 0; p < m; p++) f[i + 1][p + 1] = min(f[i + 1][p + 1], f[i][p]); } } i64 ans = INF; for (i64 i = 0; i <= m; i++) ans = min(ans, f[n + 1][i]); cout << ans; return 0; } ``` # [T4](https://www.luogu.com.cn/problem/U551228?contestId=268963) 套路题，发现这是一个无向环图。取值为 $2$ 证明可以存在二元环。 $f_i$ 表示 $i$ 个数的组合方案。考虑添加一个树时怎么变化。 发现二元组明显特别，单独考虑二元组。方案为 $f_{i-1} \times (i - 1)$。 放入三元组，发现不好考虑，那么把一个 $i$ 与另一个点绑起来，这样加进去至少是三元组，方案为 $f_{i-2} \times (i - 2)$。 发现肯定有重复，考虑 在$a$，$b$中间加边，加左边连起来跟右边连起来显然是一样的，答案会重复算，减去答案 $\frac{f_{i-3} \times (i - 1) \times (i - 2)}{2} 
#include <bits/stdc++.h>
#define i64 long long

using namespace std;

const i64 kMaxN = 1e5 + 5, kMaxM = 205, INF = 1e18, Mod = 99824353;

i64 f[kMaxN];

signed main() {
    f[1] = 0, f[2] = 1, f[3] = 1;
    for (i64 i = 4; i <= 100000; i++) {
        f[i] = (((i - 1) * f[i - 1] % Mod + (i - 1) * f[i - 2] % Mod - (i - 2) * (i - 1) * f[i - 3] / 2 % Mod) % Mod + Mod) % Mod;
    }
    i64 T;
    for (cin >> T; T; T--) {
        i64 x; cin >> x; cout << f[x] << '\n';
    }
    return 0;
}