专栏文章

模拟赛题目复盘

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio7uain
此快照首次捕获于
2025/12/02 14:47
3 个月前
此快照最后确认于
2025/12/02 14:47
3 个月前
查看原文
难度: CSPS - NOIP

Day11

估分 100+15+26+0=141100 + 15 + 26 + 0 = 141，结果 CC 挂没了。

T1.P11989 弱化

Description
有 nn 个任务，所有任务有总限时 TT。
每个任务有完成限时 sis_i，重量 hih_i，分数 pip_i。
每一时刻，你可以选择一个任务 ii 使得 hi=max(hi−1,0)h_i = max(h_i - 1, 0)
最小化 ∑hi⋅pi\sum h_i\cdot p_i。
n≤2×105n \le 2\times 10 ^ 5, T≤1018T \le 10 ^ {18}.
按照 ss 从大到小排序，增量构造。每次加入新任务时，若时间不够，则进行反悔贪心，换掉 pp 更大的任务以最小化分数。
代码CPP
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

#define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

/*
I had an idea of greedy with backtracking, seems to be 100pts
hope it can pass the problem
*/

const int maxn = 2e5 + 10;

int n, m;
struct node {
	int s, h, p;
	bool operator < (const node &o) const {
		return s < o.s;
	}
} a[maxn];

struct edge {
	int h, p;
	bool operator < (const edge &o) const {
		return p > o.p;
	}
};

priority_queue<edge> q;

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("eata6.in", "r", stdin); 
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> a[i].s >> a[i].h >> a[i].p;
	sort(a + 1, a + n + 1);
	int tot = 0, ans = 0;
	for (int i = 1; i <= n; ++i) {
		int c = tot + a[i].h - a[i].s;
		if (c <= 0) {
			tot += a[i].h;
			q.push({a[i].h, a[i].p});
		} else {
			if (q.size() && a[i].p > q.top().p) {
				while (q.size() && a[i].p > q.top().p && c > 0) {
					int hh = q.top().h, pp = q.top().p;
					q.pop();
					if (hh > 0) {
						if (c <= hh) {
							hh -= c;
							ans += c * pp;
							c = 0;
						} else {
							c -= hh;
							ans += hh * pp;
							hh = 0;
						}
					}
					if (hh == 0) 
						continue;
					q.push({hh, pp});
				}
				ans += c * a[i].p;
			} else {
				ans += c * a[i].p;
			}
			tot = a[i].s;
			q.push({a[i].h - c, a[i].p});
		}
	}
	cout << (ans == 0 ? 1 : 0) << ' ' << ans << '\n';
	cout << flush;
	return 0;
}
T2 P11770
长为 nn 的序列，第一个数为 11。
对于第 ii 个数，当前只为 vv, 给所有编号 ii 的整数倍（不含 ii ）的数从大到小更新取最大值 v+1,v+2,...v + 1, v + 2, ...
求序列的总和。
solution
首先一个数字最终的值一定是由它的因数推出来的。
设 pip_i 是 ii 的一个因子，容易得到 xx 要小，则 pip_i 为 ii 的最大质因子最合适。
x=ipix=\dfrac{i}{p_i}
fi=fx+1−pi+nxf_i=f_x+1-p_i+\dfrac{n}{x}
用 ii 枚举 xx，以保证时间复杂度。
找到 fi×jf_{i\times j} 被统计当且仅当 i×ji\times j 可以推（除）几次最大质因子得到 ii，也就是满足 ii 的最大质因子小于等于 jj 的最小质因子，这样每次推的都是 jj 的质因子。
所以我们计算 nx\dfrac{n}{x} , 对 xx 调和级数。
代码CPP
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

#define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

const int maxn = 2e6 + 10;

int n, tot;
int p[maxn], mx[maxn], mn[maxn], ans[maxn];
bool vis[maxn];

void init() {
	mx[1] = mn[1] = vis[1] = 1;
	for (int i = 1; i < maxn; ++i) 
		ans[i] = 1;
		
	for (int i = 2; i < maxn; ++i) {
		if (!vis[i]) 
			p[++tot] = mx[i] = mn[i] = i;
		for (int j = 1; j <= tot && i * p[j] < maxn; ++j) {
			vis[i * p[j]] = 1, mx[i * p[j]] = mx[i], mn[i * p[j]] = p[j];
			if (i % p[j] == 0)
				break;
		}
	}
	for (int i = 2; i < maxn; ++i) {
		ans[i] += 1 - mx[i];
		for (int j = 2; i * j < maxn; ++j)
			if (mx[i] <= mn[j])
				ans[i * j] += 1 - mx[i];
	}
	for (int i = 1, o = 0; i < maxn; ++i, o = 0) {
		for (int j = 2; i * j < maxn; ++j) {
			ans[i * j] += o;
			if (mx[i] <= mn[j])
				ans[i * j] += j, o++;
		}
	}
	
	for (int i = 1; i < maxn; ++i)
		ans[i] += ans[i - 1];
}

void solve() {
	cin >> n;
	cout << ans[n] << '\n';
}


signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while (t--)
    	solve();
    cout << flush;
    return 0;
}

Day10

Score
估 100 20 0 20
实 100 20 0 0
T1 abc166f 弱化
初始时 ABC 都有初值。
nn 次操作，每次操作给出个字符串，为 AB / AC / BC。
对一个字符串，可以选择给其中一个字符 +1+ 1，给另一个 −1-1。
求能否保证，每次操作完一个字符串后，ABC 的值都不能为负数。
solution
简单题，直接 dfsdfs，复杂度保证在 O(n)O(n)。
当然也可以思考神秘结论。
代码CPP
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

// #define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

const int maxn = 1e5 + 10; 

int n, g[maxn];
char f[maxn];
int A, B, C;

void dfs(int a, int b, int c, int s) {
	if (s == n + 1) {
		cout << "Yes\n";
		exit(0);
	}
	if (g[s] == 1) {
		if (a > 0) {
			f[s] = 'B';
			dfs(a - 1, b + 1, c, s + 1);
		}
		if (b > 0) {
			f[s] = 'A';
			dfs(a + 1, b - 1, c, s + 1);
		}
	} else if (g[s] == 2) {
		if (a > 0) {
			f[s] = 'C';
			dfs(a - 1, b, c + 1, s + 1);
		}
		if (c > 0) {
			f[s] = 'A';
			dfs(a + 1, b, c - 1, s + 1);
		}
	} else {
		if (b > 0) {
			f[s] = 'C';
			dfs(a, b - 1, c + 1, s + 1);
		}
		if (c > 0) {
			f[s] = 'B';
			dfs(a, b + 1, c - 1, s + 1);
		}
	}
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    freopen("D1.in", "r", stdin);
//    freopen("D1.ans", "w", stdout);
    cin >> n >> A >> B >> C;
    string t;
    for (int i = 1; i <= n; ++i)
    	cin >> t,
    	g[i] = (t == "AB" ? 1 : (t == "AC" ? 2 : 3));
    dfs(A, B, C, 1);
    cout << "No\n";
    cout << flush;
    return 0;
}

Day9

Score
估 100 10 0 20 实 100 10 0 0
T1 cf1967b2
给定 n,mn,m，求满足 a+b∣b×gcd⁡(a,b)a+b|b\times \gcd(a,b) 的 1≤a≤n,1≤b≤m1\le a \le n,1 \le b \le m 的整数对 (a,b)(a,b) 的个数。
solution
let d=gcd⁡(a,b)\text{let}~d = \gcd(a,b)
letx=ad\text{let}x = \dfrac{a}{d}
lety=bd\text{let}y = \dfrac{b}{d}
则式字变为 x+y∣y×dx+y|y\times d
gcd⁡(x+y,y)=gcd⁡(x,y)=1\gcd(x+y,y)=\gcd(x,y)=1
式子变为 x+y∣dx+y|d
设 d=k(x+y)d=k(x+y)
则 a=d×x=k(x2+y)a=d\times x=k(x^2+y)
b=d×y=k(x+y2)b=d\times y=k(x+y^2)
推出 x≤nx\le \sqrt n
y≤my\le \sqrt m
直接枚举 x,yx,y 时间复杂度 O(nm)O(\sqrt {nm})
代码CPP
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

// #define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

int n, m, ans, sn, sm, a, b;

void solve() {
	cin >> n >> m;
	ans = 0;
	sn = sqrt(n), sm = sqrt(m);
	for (int i = 1; i <= sn; ++i) {
		for (int j = 1; j <= sm; ++j) {
			if (__gcd(i, j) != 1) 
				continue; 
			a = (i + j) * i, b = (i + j) * j;
			if (a > n || b > m) 
				continue;
			ans += min(n / a, m / b); 
		}
	}
	cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
	cin >> t;
	while (t--)
		solve(); 
    cout << flush;
    return 0;
}
T2 arc104c
nn 个线段，两端点为 aia_i 和 bib_i。
满足
1.ai<bia_i<b_i
2.所有 aa 和 bb 组成 2n2n 的排列
3.若两线段有交集，则它们长度一样。
先给出所有 aia_i 和 bib_i，有些端点遗漏为 −1-1（可自行填数），有些可能有误。判断能否存在构造满足条件。
solution
首先特判，ababa..
考虑合法方案的形态，线段必然没有包含关系，考虑每个独立的段，发现必定形如:
前半部分是左端点，后半部分是右端点。
我们需要知道是否有合法方案，考虑可行性 dp。
设 fif_i 表示 fif_i 是否可行，转移时容易的:fi←fj且chk(j+1,i)f_i←f_j 且 chk(j+1,i)，其中 chk(l,r)chk(l,r) 表示 [l,r][l,r] 是否能成为合法段。 考虑怎么计算 chk(l,r)chk(l,r)，维护每个线段的起点和终点，判断是否有矛盾即可。
代码CPP
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

// #define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

const int maxn = 5e2 + 10;

int n;
int A[maxn], B[maxn], f[maxn], c[maxn], d[maxn];

bool cc() {
	for (int i = 1; i <= n; ++i)
		if (c[i] > 1) 
			return 0;
	return 1;
}

bool ck(int l, int r) {
	for (int i = l + 1; i <= r; ++i) {
		if (f[i] < 0 && A[-f[i]] != -1 && A[-f[i]] < l) 
			return 0;
		if (f[i] > 0 && B[f[i]] != -1 && B[f[i]] > r)
			return 0;
	}
	int len = (r - l + 1) >> 1;
	for (int i = l, j = l + len; i <= l + len - 1; ++i, ++j) {
		if (f[i] < 0 && f[j] > 0) 
			return 0;
		if (f[i] && B[f[i]] != -1 && B[f[i]] != j) 
			return 0;
		if (f[i] && f[j] && f[i] + f[j])
			return 0;
	}
	return 1;
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n * 2; ++i)
		c[i] = d[i] = f[i] = 0;
	for (int i = 1; i <= n; ++i) 
		cin >> A[i] >> B[i];
	for (int i = 1, a, b; i <= n; ++i) {
		a = A[i], b = B[i];
		if (b > 0 && a > b) {
			cout << "0\n";
			return;
		}
		if (a > 0) 
			c[a]++, f[a] = i;
		if (b > 0)
			c[b]++, f[b] = -i;
	}
	n <<= 1;
	if (!cc()) {
		cout << "0\n";
		return;
	}
	d[0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = (i & 1); j < i; j += 2) 
			d[i] = (d[i] | (d[j] && ck(j + 1, i)));
	}
	cout << d[n] << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) 
    	solve();
    cout << flush;
    return 0;
}

评论

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

正在加载评论...