专栏文章

20250814 LiveDream 模拟赛总结

___JCY__
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miobkg4e
此快照首次捕获于
2025/12/02 16:31
3 个月前
此快照最后确认于
2025/12/02 16:31
3 个月前
查看原文

总结

期望 100+100+0+0=200100 + 100 + 0 + 0 = 200
实际 100+100+0+0=200100 + 100 + 0 + 0 = 200
排名 5/40
少考了30分钟，感觉还行

T1

签到，fi,jf_{i,j} 表示第 ii 选 jj 的方案数，前缀和优化暴力枚举倍数
CPP
#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

也挺简单的其实，状态很好想, fi,jf_{i,j} 在第 ii 个位置放置第 jj 个超级城市的最小代价。由于不能确定 ii 之后的代价，所以在下次转移的时候再加上
CPP
#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

fi,jf_{i,j} 表示第 ii 秒前，干扰 jj 次的最小钱数。收集不好写，考虑扩散，用一个堆维护在区间内的红包，如果没有红包直接继承，有红包开率干扰或抢
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

套路题，发现这是一个无向环图。取值为 22 证明可以存在二元环。
fif_i 表示 ii 个数的组合方案。考虑添加一个树时怎么变化。
发现二元组明显特别，单独考虑二元组。方案为 fi−1×(i−1)f_{i-1} \times (i - 1)。
放入三元组，发现不好考虑，那么把一个 ii 与另一个点绑起来，这样加进去至少是三元组，方案为 fi−2×(i−2)f_{i-2} \times (i - 2)。
发现肯定有重复，考虑 在aa，bb中间加边，加左边连起来跟右边连起来显然是一样的，答案会重复算，减去答案 fi−3×(i−1)×(i−2)2\frac{f_{i-3} \times (i - 1) \times (i - 2)}{2}
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...