WFYZ 暑期 CSP-S 模拟训练 2 —— 解题报告

本卷共 4 题，均以 C++14 为标程标准（g++ -std=c++14 -O2 编译，已本机实测通过）。 覆盖 背包 DP（多维/计数）、贪心排序 + DP、数位计数/分段多项式求和 等高阶题型。 难度梯度为 普及+/提高- 到 提高+/省选-，适合 CSP-S 暑期冲刺。

题目总览

各题要点与易错提醒

A. 运输金子（背包 DP + 端点外挂）

• 转化：每根金条重心必须在容器内，因此除最左、最右各一根可有一半露在外，其余必须完全在容器内。长度乘 2 后容量变 2L：完整放入占 2aᵢ，端点外挂只占 aᵢ 且最多 2 根。
• 做法：dp[t][j] = 已外挂 t 根、占用长度 j 的最大价值，0-1 背包转移。
• 易错：单根金条重心放容器正中、两侧都能外挂，任何长度都放得下，答案初值要取 max(vᵢ)；价值用 long long。

B. 土豆先生（背包 DP + 凸性）

• 转化：P₁·P₂ = C₁(C−C₁) / (A₁(A−A₁))，固定 A₁ 时分子关于 C₁ 开口向下，最小值在 C₁ 极值处。
• 做法：背包 DP 同时求「恰好 L 袋、土豆总数 w」时总价的最小值和最大值，两个极值各试一次。
• 易错：输出保留 3 位小数，建议用整数运算精确舍入（scaled = floor(2000·C₁·C₂ + w(A−w)) / (2w(A−w))），避免浮点误差。

C. 四方配额（计数 + 分段多项式求和）

• 转化：a+c>b+d 且 a+d≥b+c ⟺ a>b 且 −(a−b) < c−d ≤ a−b。
• 做法：答案 = Σ f(k)·h(k)，f(k)=min(B,A−k)+1，h(k)=G(k)−G(−k)，G(t)=#{c−d≤t} 可用闭式 O(1) 求。f、G 都是分段低次多项式，在 O(1) 个区间上做多项式求和。
• 易错：G(k) 含半整系数（/2），求和时需用模逆 inv2；断点要取全（A−B+1、C、C−D+1、D+1、D−C+1），答案取模 10⁹+7。

D. 项目经验（贪心排序 + 背包 DP）

• 转化：同段内按 a/b 从大到小执行；总收入 = Σ bᵢ·(前缀 a 和 + [训练营后]·X)。
• 做法：按 a/b 从小到大处理项目，枚举 targetB（训练营后项目 b 之和），DP dp[j][k] 表示已放训练营后 j 个、b 之和为 k 的最大贡献。
• 易错：转移两分支（训练营前 / 后）的贡献公式要区分「已处理同段项目」；bᵢ≤10、Σb≤500 是 DP 状态可行的关键；本题为文件输入输出（money.in / money.out）。

训练建议

• A、B 是背包 DP 的变形，属于 CSP-S 必会考点，应优先吃透；尤其注意「端点外挂」「凸性取极值」这类建模转化。
• C 题重在把不等式约束转化为两个差值的区域，再用闭式 + 分段求和，是省选常见计数套路；做不出来属正常，重点是理解 G(t) 的闭式与分段求和思想。
• D 题的「同段排序 + 枚举划分 + 背包」是经典的排序 + DP 组合，建议结合 a/b 排序结论与贡献拆解反复理解。

数据与标程说明

• 每题提供 16~20 组测试数据 data1.in / data1.ans …，按子任务梯度分布（详见各题 README 子任务表）。
• 标程统一 C++14，g++ -std=c++14 -O2 编译，已本机实测：全部 68 组数据与官方/修正样例均通过。
• data/ 目录下 data_maker.py 为数据生成器，solver_ref.py 为 Python 参考求解器（与 C++ 标程交叉验证一致）。
• D 题样例修正说明：原题提供的 3 组样例中 X 值存在笔误（样例 1 的 18 应为 10、样例 2 的 108 应为 100、样例 3 输出 22696 应为 22288），本卷 README 已修正为与题解算法一致的自洽样例。

有啥问题请前往评论区

#include <bits/stdc++.h>


using namespace std;

int main() {
    freopen("problem.conf", "w", stdout);

    bool G;
    cout << "use_builtin_judger on" << endl;
    cerr << "has special judge?" << endl; cin >> G;
    if (!G)
        cout << "use_builtin_checker wcmp\n";

    cout << "n_ex_tests 0\n\
n_sample_tests 0" << endl;
    cerr << "tests count:" << endl;
    int x; cin >> x;
    cout << "n_tests " << x << endl;
    cerr << "subtask count:" << endl;
    int y; cin >> y;
    if (y) {
        cout << "n_subtask " << y << endl;
        for (int i = 1; i <= y; ++i) {
            cerr << "subtask " << i << " end:" << endl;
            int x; cin >> x;

            cout << "subtask_end_" << i << ' ' << x << endl;   

            cerr << "subtask " << i << " score:" << endl;
            cin >> x;

            cout << "subtask_score_" << i << ' ' << x << endl;
        }
    }

    int a;
    cerr << "Time limit(s):" << endl; cin >> a;
    cout << "time_limit " << a << endl;
    cerr << "Memory limit(mb):" << endl; cin >> a;
    cout << "memory_limit " << a << endl;

    string s; bool t;
    cerr << "has same pre?" << endl; cin >> t;
    if (t) { 
        cerr << "input_pre:" << endl; cin >> s;
        cout << "input_pre " << s << endl;
        cerr << "output_pre:" << endl; cin >> s;
        cout << "output_pre " << s << endl;   
    } else {
        cout << "has_input_pre false" << endl;
        cout << "has_output_pre false" << endl;
    }
    cerr << "input_suf:" << endl; cin >> s;
    cout << "input_suf " << s << endl;
    cerr << "output_suf:" << endl; cin >> s;
    cout << "output_suf " << s << endl;

    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-05 09:41:59

Day -1

在家休息，让 Chatgpt 找了几道分类讨论的题写了写。

Day 0

上午啥也没干，摆摆摆。

中午出发，发现手机没电了，于是乎蜘蛛纸牌接接接。

下午到了酒店，感觉打板子没用，于是复习编译选项以及常见tricks，一车人在我房间耍。途中尝试跟 S08577 联机 MC，发现 S08577 的菜鸡电脑啥都带不动，遂放弃。

发现酒店的饭不如 wfyz 一根，随便吃了点就找 quyuan 点了外卖。

然后去试机，感觉机器特别好用啊，敲个线段树试试。欸怎么重启了，我们的系统跟考试不一样说是。重启之后文件都没了，就懒得再写一遍了，只是把所有按键都试了一遍没问题就离场了。

Day 1

上午爽睡到 7:30，吃完饭回来就稍微复习了一下，然后被 S08577 通知去 tianruihan 的房间，于是随便收拾了一下，然后去玩了会。

吃完午饭也不想睡觉，发了会呆就到点了，然后下去集合，尝试预言必考线段树。

进考场开题，看了眼第一题，欸怎么这么难，先想想没限制不就是全选最大的，那就至多只有一个是 $> \frac n2$ 的，那直接把最大减次大放三个 set 就做完了，于是马上开写，写完很快就过了大样例，此时我同桌还在问压缩包密码是啥。

然后看第二题，怎么题面这么混乱，怎么城市跟乡镇混着用，他本来不就是城市，怎么还要城市化改造。先去看看第三题，看第三题发现只有可能是 $i$ 不相同，不可能是 $x,z$ 不相同，然后就是直接把两个串最长公共前后缀找出来，然后匹配一下，发现暴力有很多分，于是回去看 T2。

先按照乡镇就是前 $k$ 个城市来理解吧，那就是直接 $2^k$ 枚举改不改造，然后把新的边和原图最小生成树上的边混一块再做一遍最小生成树，那就开写。

欸小样例怎么没过，欸他怎么 $1$ 向 $1$ 连边，哦原来乡镇是独立的，那直接把编号改成 $n + i$ 就行，一遍过了大样例，但是我并没有用归并，因为相信 CCF 神机。

吃个士力架，嗯嚎吃。

然后看了看第四题，设了好几个状态都假了，然后发现只会状压，便回去想第三题。

想想，欸我之前怎么会的是 $O(L^2)$，$L^2$ 怎么分这么少，想想还能怎么做，哦那我只把公共后缀取出来，然后枚举前缀的长度，那左端点就固定了，然后只需要使得公共后缀相同就行，然后总共只有 $n$ 个，所以就是 $O(nq + L)$，写写吧。欸不对，样例二怎么有个长度不相同的，这是啥阴，长度不同不是一定不行吗，让我想想，哦对啊，这不是直接输出 $0$ 就行了，为啥放这种没用的数据啊。

吃个士力架，嗯嚎吃。

写写写，要用哈希懒得双了，就用单哈希吧不会卡的，写写写怎么还要用 map<pair<int, int>, int> 要不要离散化一下然后少一维，算了反正是暴力，写写写，好前两个样例过了，欸第三个怎么寄了，这怎么调，自己写一个比较程序吧。

然后找到是第 101 个询问不对，输出了一下，发现很多串都有这个子串，这我怎么找，欸我怎么输出 $0$，哦我后缀怎么求得是询问串的后缀，应该从前缀往后延伸的，改完对了，欸怎么跑这么快，不管了应该过不去。

吃个士力架，嗯嚎吃。

现在还剩 1.5h，想想还是先写特殊性质吧，第三题只有特殊性质 B 没写，发现这个只需要满足前缀且后缀长度比询问的串小就行，那我直接提前排好序然后二分就是喽，写写写，怎么挂了，再次使用比较程序。

哦原来是没有元素的时候会一直 continue，不会触发 break 导致寄了，那就先 break，好过了，怎么跑的没暴力快，不管了。

吃个士力架，嗯嚎吃。

现在还剩 1h，先写第四题暴力吧，没怎么调就过样例了，此时还剩 40m。

继续尝试思考第三题，发现可以直接把中间不同的那一段删了，然后把相同前后缀拼起来，中间隔开，然后把中间相同的分成若干等价类，然后每个等价类就相当于统计有多少串是询问串的子串，这不就是AC自动机板子。但是感觉写不完了，于是看了眼第四题把 $n=m$ 写了，然后就摆了，开始肉眼调试四道题。

发现第三题特殊性质判错了，改了改，然后到最后也没看出来啥其他的。

出考场没碰到熟人，然后就直接往巴车方向走，也没看到老师，然后看到了 Dtw，他说第二题不归并会被卡，感觉有点可能不过还是相信 CCF 神机，然后又碰到了 xuyunao，他说 xz001 因为运气不好，导致电脑炸缸写不了代码，浪费了几个小时，可能去不了 WC 了，默哀。

然后去到大巴随便吃了点东西就摆了，发现大家有点炸缸，而且好像有人每判第三题长度不相同。

后记

早上起来一看，哟云斗这么速度，发现自己没挂分，很开心。

在其他平台上测了测我的码，发现第二题很可能就是会被卡到 $80$，第三题得分在 $[70, 90]$ 之间。

然后跟 S08577 聊了聊发现他第一题挂成了 $5$ 分，感觉非常神秘，仔细一看发现他第一题判特殊性质判的是只要有非 $0$ 的就执行特殊性质，全是 $0$ 才是 $n^3$ 的暴力，然后挂飞了，只有 $n \le 200$ 并且 $b_i, c_i$ 全等于 $0$ 的这一个点有分。

发现很多人第二题读错题之后数组开小了忘改了。

NOIP 加油吧

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-21 13:28:33

考虑两种操作，左端点要么是变成一个数，要么是变成一个数剪掉长度。

所以考虑设左端点都为 $a + b \cdot len$，其中 $len$ 为线段长度。

然后我们把 $a, b$ 相同的分为一类，然后每一类对应一个区间。

那么每次修改就把在 $1 \sim v$ 中的区间和 $v + 1 \sim n$ 的区间分裂开，然后将在 $1 \sim v$ 的区间都删除，并修改成对应的 $a + b \cdot len$。

然后显然左右端点都有单调性，直接二分即可找出合法区间。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-12 10:06:08

考虑说直接贪心不太能做，所以考虑 DP。

考虑说我们选后缀比前缀容易，所以我们倒着 DP。

考虑说我们如果设 $f_{i,j}$ 表示分了后 $i$ 个 $j$ 段是否可行，我们发现 $i,j$ 从 $f_{k,j - 1}$ 转移，但我们需要枚举 $i,j,k$ 还有 $k$ 最后一段的长度，感觉不太好优化。

考虑到原来的 DP 主要关心最后一段多长，所以我们考虑设 $f_{i, j}$ 表示 $[i, n]$ 这段后缀，最后一段为 $[i,j]$ 最长的段数是多少。

然后我们枚举 $i, j$，然后考虑用 SA 求出来 $[i, n]$ 和 $[j + 1, n]$ 的最长公共前缀设为 $s$，那么就看如果 $[i,i + \min(lcp, j - i + 1)]$ 这段是否小于 $[j + 1, j + 1 + \min(lcp, j - i + 1)]$，如果是的话，那么 $f_{i,j}$ 就是 $\max_{k=j + 1 + \min(lcp, j - i + 1)} ^ {n} f_{j + 1, k}$，然后发现是后缀 $\max$，于是再开一个数组维护即可。

#include <bits\/stdc++.h>

using namespace std;

const int N = 10010;

int n, m, p;
char s[5010];
pair<int, int> f[5010][5010];
pair<int, int> g[5010][5010];
int st[16][N], log_2[N];
int sa[N], rk[N], ork[N], id[N], cnt[N];

int queryM(int l, int r) {
	int L = log_2[r - l + 1];
	return min(st[L][l], st[L][r - (1 << L) + 1]);
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);

	m = 255;
	for (int i = 1; i <= n; ++i) cnt[rk[i] = s[i]]++;
	for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
	for (int i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

	for (int w = 1; ; w <<= 1, m = p) {
		int cc = 0;
		for (int i = n - w + 1; i <= n; ++i) id[++cc] = i;
		for (int i = 1; i <= n; ++i)
			if (sa[i] > w) id[++cc] = sa[i] - w;

		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; ++i) cnt[rk[i]]++;
		for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
		for (int i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i];

		memcpy(ork, rk, sizeof(ork));
		p = 0;
		for (int i = 1; i <= n; ++i)
			if (ork[sa[i]] == ork[sa[i - 1]] && ork[sa[i] + w] == ork[sa[i - 1] + w])
				rk[sa[i]] = p;
			else
				rk[sa[i]] = ++p;

		if (p == n) break;
	}
	
	for (int i = 1, k = 1; i <= n; ++i) {
		if (!rk[i]) continue;
		if (k) --k;
		\/\/ cout << sa[rk[i] - 1] << ' ' << i << ' ' << rk[i] << ' ' << sa[rk[i]] << ' ' << sa[rk[i] - 1] << ' ' << sa[i] << endl;
		while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;

		st[0][rk[i]] = k;
	}

	for (int i = 1; i <= 15; ++i)
		for (int j = 1; j <= n; ++j)
			st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	log_2[1] = 0;
	for (int i = 2; i <= n; ++i) log_2[i] = log_2[i >> 1] + 1;

	for (int i = n; i >= 1; --i) {
		for (int j = i; j <= n; ++j) {
			if (j == n) {
				f[i][j] = {1, n + 1};
				break;
			}

			int l = rk[i], r = rk[j + 1];
			if (l > r) swap(l, r);
			int lcp = min(queryM(l + 1, r), j - i + 1);

			if (lcp == n - j) continue;

			if (lcp >= j - i + 1) {
				if (g[j + 1][j + j - i + 2].first + 1 > f[i][j].first)
					f[i][j] = {g[j + 1][j + j - i + 2].first + 1, g[j + 1][j + j - i + 2].second};
			} else {
				if (s[i + lcp] < s[j + lcp + 1]) {
					if (g[j + 1][j + lcp + 1].first + 1 > f[i][j].first)
						f[i][j] = {g[j + 1][j + lcp + 1].first + 1, g[j + 1][j + lcp + 1].second};
				}
			}

			\/\/ cout << i << ' ' << j << ' ' << lcp << ' ' << f[i][j].first << "----" << ' ' << j + lcp + 1 << ' ' << g[j + 1][j + lcp + 1].first << endl;
		}

		for (int j = n; j >= i; --j) {
			g[i][j] = max(g[i][j + 1], {f[i][j].first, j});
		}
	}

	int ans = 0, id = 0;
	for (int i = 1; i <= n; ++i) {
		if (f[1][i].first > ans) {
			ans = f[1][i].first;
			id = i;
		}
	}

	printf("%d\n", ans);
	int l = 1;
	while (id <= n) {
		for (int i = l; i <= id; ++i) putchar(s[i]);
		putchar('\n');
		int tid = id;
		id = f[l][id].second;
		l = tid + 1;
	}

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-15 21:30:01

我们发现，这就是给你一个矩阵，第 $i$ 行第 $j$ 列的权值是 $\left | A_i - B_j \right |$，有 $k$ 个询问，每次问你矩阵里 $(1,1)$ 到 $(x,y)$ 的和。

然后我么发现每个矩阵都有一个 $(1, 1)$ 固定，只有 $(x,y)$ 在变，所以就直接类似一维莫队，然后维护两个权值线段树，一个维护当前扫到的所有 $B_j$，另一个维护当前扫到的所有 $A_i$。

然后考虑新加一个 $x + 1$，那么就是说多了 $\sum \left | A_{x + 1} - B_j \right |$，那么就把绝对值拆开，然后就是在维护 $B$ 的权值线段树上，查 $\le A_{x + 1}$ 的 $B_j$ 的和以及数量，以及 $> A_{x + 1}$ 的 $B_j$ 的和以及数量，然后删除和关于 $y$ 的类似，然后就做完了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-06 10:10:06

前置知识：

杨表

看到最长上升/下降子序列长度还有计数，考虑杨表。

然后有一个结论，就是杨表的第一行的长度就是这个序列的最长上升子序列的长度，第一列的长度就是这个序列的最长下降子序列的长度。

由于这道题固定了最长上升子序列和最长下降自序的长度，并且长度为 $AB - 1$，那么最后杨表一定是长这个样子的：

然后由于最后要加上 $n + 0.5$，并且数量不变，所以要把 $n + 0.5$ 扔到 $b_{1,A}$ 上，并且把所以 $b_{i, A} (1 \le i < B)$ 都一一放到 $b_{i, A} (2 \le i \le B)$ 上。

那么我们要满足：

$b_{i + 1, A - 1} < b_{i, A}$，因为这样才能让 $n + 0.5$ 插进去后所有的 $b_{i, A}$ 都到 $b_{i + 1, A}$ 上。

由于数据范围极小，那么我们可以考虑暴力 $DP$。

设 $f_{a_1,a_2, \dots, a_A}$ 表示杨表第 $i$ 列填了 $a_i$ 个数的序列个数。

那么这个直接暴力转移，枚举当前数填到哪里，只要 $a_i < a_{i - 1}$，那么就可以从 $a_1, a_2, \dots, a_i, \dots, a_A$ 转移到 $a_1, a_2, \dots, a_i + 1, \dots, a_A$。

再统计合法的杨表的数量，那么我们设 $f_{a_1, a_2, \dots, a_n}$ 表示满足的杨表个数。

那么我们考虑大部分转移和上一部分是一样的，不过对于 $a_A$，它必须 $< a_{A - 1} - 1$ 才能转移，因为如果是 $< a_{A - 1}$，那么当前这个数填到 $a_A$ 上后，若 $a_A = a_{A - 1}$ 并且 $a_{A - 1}$ 还未填，那么我们就会发现再填上一个数之后就有一个不满足 $b_{i + 1, A - 1} < b_{i, A}$。

然后就做完了。

Code

#include <bits\/stdc++.h>

using namespace std;

int A, B, mod;
map<vector<int>, int> f;

int dp1() {
	f.clear();
	f[vector<int> (A, 0)] = 1;

	for (auto [u, v] : f) {
		vector<int> t = u;
		for (int i = 0; i < A; ++i) {
			int lim = (i == 0) ? (B) : (u[i - 1]);

			if (u[i] < lim) {
				++t[i];

				f[t] += v;
				if (f[t] >= mod) f[t] -= mod;

				--t[i];
			}
		}
	}

	vector<int> t(A, B);
	return f[t];
}

int dp2() {
	f.clear();
	f[vector<int> (A, 0)] = 1;

	for (auto [u, v] : f) {
		vector<int> t = u;
		for (int i = 0; i < A; ++i) {
			int lim = (i == 0) ? B : ((i == A - 1) ? (u[i - 1] - 1) : (u[i - 1]));

			if (t[i] < lim) {
				++t[i];

				f[t] += v;
				if (f[t] >= mod) f[t] -= mod;

				--t[i];
			}
		}
	}

	vector<int> t(A, B);
	t[A - 1] = B - 1;

	return f[t];
}

int main() {
	scanf("%d%d%d", &A, &B, &mod);

	int res1 = dp1();
	cout << res1 << endl;
	int res2 = dp2();

	printf("%d\n", 1ll * res1 * res2 % mod);

	return 0;
}

当然，我们也可以先在第 $A$ 列选一个（也就是 $n + 0.5$ 的位置），然后再填其他的，这样也是可以的。

这里只给出和上一个方法不同的地方。

Code:

int dp2() {
	f.clear();
	vector<int> a(A, 0);
	a.back() = 1;
	f[a] = 1;

	for (auto [u, v] : f) {
		vector<int> t = u;
		for (int i = 0; i < A; ++i) {
			int lim = (i == 0) ? B : (u[i - 1]);

			if (t[i] < lim) {
				++t[i];

				f[t] += v;
				if (f[t] >= mod) f[t] -= mod;

				--t[i];
			}
		}
	}

	vector<int> t(A, B);

	return f[t];
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-04 18:33:02

T3 线段树

我是小丑

build(1, 0, n);
modify(1, 0, Maxn, 0, 0);

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-18 14:08:28

A

直接模拟即可

B

直接暴力预处理出所有在 $1 ... 1000$ 中可以被 $4ab + 3a + 3b$ 表示出的数即可。

C

直接暴力时间复杂度是正确的。

D

套路题，之前做过类似的。

二分之后将所有点与 $mid$ 取 $\min$，此时只要 $\sum a_i$ 是 $\ge mid \cdot k$ 的就合法否则不合法，因为对 $mid$ 取 $\min$ 就相当于限制了每个数选的次数。

E

考虑记搜，枚举所有排列其实可以每次把一个字符扔到前面来实现，而由于我们只关心最后状态是什么不关心中途是怎么换的，那么把某个字符扔到前面实际上只用选最前面的字符即可。

然后把字符串 $S$ 和剩余步数记录一下即可。

#include <bits\/stdc++.h>

using namespace std;

namespace A{
	int n, k, a;
	void main() {
		scanf("%d%d%d", &n, &k, &a);
		for (int i = 1; i < k; ++i) {
			a = a % n + 1;
		}
		
		printf("%d\n", a);
	}
}

namespace B {
	int n, s;
	bool st[10100];
	
	void init() {
		for (int i = 1; i <= 1000; ++i) {
			for (int j = 1; j <= 1000; ++j) {
				if (4 * i * j + 3 * i + 3 * j > 1000) break;
				st[4 * i * j + 3 * i + 3 * j] = true;
			}
		}
	}
	
	void main() {
		init();
		int ans = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			int a;
			scanf("%d", &a);
			ans += !st[a];
		}
		
		printf("%d\n", ans);
	}
}

namespace C {
	typedef long long ll;
	
	ll n;
	
	void main() {
		scanf("%lld", &n);
		ll ans = 0;
		for (ll A = 1; A * A * A <= n; ++A) {
			for (ll B = A; A * B * B <= n; ++B) {
				ll C = n \/ (A * B) - B + 1;
				ans += C;
			}
		}
		
		printf("%lld\n", ans);
	}
}

namespace D {
	typedef long long ll;
	int n, k;
	ll a[200010];
	
	bool check(ll mid) {
		ll sum = 0;
		for (int i = 1; i <= n; ++i) {
			sum += min(a[i], mid);
		}
		
		return sum \/ k >= mid;
	}

	void main() {
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
		
		ll l = 1, r = 200000000000000000;
		while (l < r) {
			ll mid = (l + r + 1) >> 1ll;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		
		printf("%lld\n", l);
	}
}

namespace E {
	typedef long long ll;
	int k;
	string s;
	map<pair<string, int>, ll> ma;
	
	ll dfs(string s, int k) {
		if (k < 0) return 0;
		if (s.size() <= 1) return 1;
		if (ma.count({s, k})) return ma[{s, k}];
		
		ll res = 0;
		for (int i = 0; i < (int)s.size(); ++i) {
			if (s[i] == 'K') {
				string t;
				for (int j = 0; j < i; ++j) t += s[j];
				for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];
				
				res += dfs(t, k - i);

				break;
			}
		}
		for (int i = 0; i < (int)s.size(); ++i) {
			if (s[i] == 'E') {
				string t;
				for (int j = 0; j < i; ++j) t += s[j];
				for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];
				
				res += dfs(t, k - i);

				break;
			}
		}
		for (int i = 0; i < (int)s.size(); ++i) {
			if (s[i] == 'Y') {
				string t;
				for (int j = 0; j < i; ++j) t += s[j];
				for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];
				
				res += dfs(t, k - i);

				break;
			}
		}
		
		return ma[{s, k}] = res;
	}
	
	void main() {
		cin >> s >> k;
		cout << dfs(s, k);
	}
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-18 13:59:42

A

一开始尝试直接输出的时候使用 %.lf 来四舍五入，但是发现 0.5 的时候会输出 0，最后还是用 $\lfloor a+0.5 \rfloor$ 来实现的四舍五入。

B

考虑先按照长度排序，对与长度相同的，把第一个数作为第一关键字，第二个数作为第二关键字以此类推，这样相等的一定是连续一段直接统计即可。

C

显然可以从 $n$ 开始 dfs 一遍，然后若遇到访问过的，那么它以及他后边需要的一定全解锁了，直接返回 $0$，否则继续下去，如果是叶子就是 $t_i$。

D

由于 $1 \le n \le 500$，考虑枚举两个点，那么对与这两个点，设最小满足的为 $(a,b)$，那么其他满足的一定是当前的倍数，所以我们可以求出任意两对点之间最小的 $(a,b)$ 然后扔到 set 里，然后看有多少不同即可。

E

一开始没看到要求每个点恰好一个出边，还以为不可做。

若最后可以使每个点恰好有一个出边，那么整个图就是若干个环，而每个环有两种方案，所以答案就是 $2^{\text{环的个数}}$。

#include <bits\/stdc++.h>

using namespace std;

namespace A {
	long double n;
	void main() {
	    scanf("%Lf", &n);
	    printf("%.0Lf", floor(n + 0.5));
	}
}

namespace B {
	int n;
	vector<vector<int>> v;
	void main() {
		scanf("%d", &n);
		v.push_back({});
		for (int i = 1; i <= n; ++i) {
			int l; scanf("%d", &l);
			v.push_back({});
			for (int j = 1; j <= l; ++j) {
				int a; scanf("%d", &a);
				v[i].push_back(a);
			}
		}
		
		sort(v.begin(), v.end(), [&](vector<int> a, vector<int> b) {
			if (a.size() != b.size()) return a.size() < b.size();
			return a < b;
		});
		
		int ans = n;
		for (int i = 2; i <= n; ++i) {
			if (v[i] == v[i - 1]) --ans;
		}
		
		printf("%d\n", ans);
	}
}

namespace C {
	typedef long long ll;
	int n;
	ll t[200010];
	vector<int> e[200010];
	bool st[200010];
	
	ll dfs(int u) {
		if (st[u]) return 0;
		st[u] = true;
		
		ll res = 0;
		for (auto t : e[u]) {
			res += dfs(t);
		}
		
		return res + t[u];
	}
	
	void main() {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%lld", &t[i]);
			int l; scanf("%d", &l);
			for (int j = 1; j <= l; ++j) {
				int c; scanf("%d", &c);
				e[i].push_back(c);
			}
		}
		
		printf("%lld\n", dfs(n));
	}
}

namespace D {
	int n;
	pair<int, int> a[510];
	
	int gcd(int a, int b) {
		return !b ? a : gcd(b, a % b);
	}
	
	void main() {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%d%d", &a[i].first, &a[i].second);
		}
		
		set<pair<int, int>> cnt;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (i != j) {
					int tx = a[i].first - a[j].first, ty = a[i].second - a[j].second;
					int t = abs(gcd(tx, ty));
					
					cnt.insert({tx \/ t, ty \/ t});
				}
			}
		}
		
		printf("%d\n", cnt.size());
	}
}

namespace E {
	const int mod = 998244353;
	int n, m;
	vector<int> e[200010];
	bool st[200010];
	int cntE, cntV;

	void dfs(int u) {
		st[u] = true;
		++cntV;
		cntE += e[u].size();

		for (auto v : e[u]) {
			if (!st[v]) {
				dfs(v);
			}
		}
	}
	
	void main() {
		int ans = 1;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; ++i) {
			int u, v; scanf("%d%d", &u, &v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		
		for (int i = 1; i <= n; ++i) {
			if (!st[i]) {
				cntE = cntV = 0;
				dfs(i);
				
				if (cntE != cntV * 2) ans = 0;
				else {
					ans *= 2;
					if (ans >= mod) ans -= mod;
				}
			}
		}
		
		printf("%d\n", ans);
	}
}