2024夏令营提高1模考0721模拟赛（提高1）补题报告
\[07121模拟赛(提高1) \\ \ 补题报告\ \\ \ 2024年7月21日 \ \\ by \ \ \ 唐一潇 \]一、做题情况
- 第一题比赛 \(100 / 100\) ，赛后通过
- 第二题比赛 \(0 / 100\) ，赛后通过
- 第三题比赛 \(0 / 100\) ，赛后通过
- 第四题比赛 \(0/ 100\) ，赛后通过
- 比赛得分 \(100 / 400\) ，赛后补题 \(400\) / \(400\)
二、比赛概况
T1AC用前缀和+哈希，时间复杂度 \(O(n)\) ，同学 前缀和+排序 \(O(n \log(n))\) 都过了。
T2CE，再交上去AC，本质是贪心+DFS。
T3 分组背包。
T4 在有理数取模时，要乘逆元。
三、题解报告
T1：数列
题面：
给你一个长度为N的正整数序列，如果一个连续的子序列，子序列的和能够被K整
除，那么就视此子序列合法，求原序列包括多少个合法的连续子序列？
对于一个长度为8的序列,K=4的情况：2, 1, 2, 1, 1, 2, 1, 2 。它的答案为6，子序列
是位置1->位置8,2->4,2->7,3->5,4->6,5->7。
做法：
考虑有 \(T\) 组样例，暴力枚举时间复杂度为 \(O(T*n^2)\)。
可以取模 \(k\) 后哈希做。
记 \(s_i=\sum_{i=1}^{a_i}\mod k\)
如果对于 \(i,j\)，满足 \(s_i=s_j\) ,那么子序列 \(i+1...j\) 是合法的。
从左往右求解即可。
附：AC代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#define int long long
using namespace std;
namespace fast_read_write {
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { //! isdigit(ch)
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') // isdigit(ch)
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x * f;
}
inline void write(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
} // namespace fast_read_write
using namespace fast_read_write;
const int N = 5e4 + 5;
int T, n, k, a[N], sum[N], cnt;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
while (T--) {
cin >> k >> n;
unordered_map<int, int> mod_count;
mod_count[0] = 1;
cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] %= k;
sum[i] = (sum[i - 1] + a[i]) % k;
cnt += mod_count[sum[i]];
mod_count[sum[i]]++;
}
cout << cnt << '\n';
}
return 0;
}
T2 小信爬树
Fake Plastic Trees - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题面：
树的根是顶点 \(1\)，顶点 \(v\) 的父节点是 \(p_v\)。调整每个顶点上的数字，使得每个顶点的数字都在其指定的范围内 \((l_v \le a_v \le r_v)\)。
在单次调整中，我们执行以下操作：
- 选择某个顶点 \(v\)。
- 令 \(b_1,b_2,...,b_k\) 是从顶点 \(1\) 到顶点 \(v\) 的路径上的顶点（即 \(b_1=1\)，\(b_k=v\)，并且 \(b_i\) 是 \(p_{b_{i+1}}\)。
- 选择一个长度为 \(k\) 的非递减数组 \(c\) ，其中 \(c_1 \le c_2 \le ... \le c_k\) 数组元素都是非负整数。
- 对于每个 \(i\ (1 \le i \le k)\)，给 \(a_{b_i}\) 加上 \(c_i\)。
求至少需要多少次操作才能完成这个调整。
思路解析
考虑DFS。
我们从根节点开始进行深度优先搜索，计算每个节点的值。
对于每个节点 \(u\)，我们计算其子节点的值之和 \(tag\)。
- 如果 \(tag > {r_u}\)，则 \(u\) 的值为 \(r_u\)。
- 如果 \(tag < l_u\)，则需要进行一次操作，将 \(u\) 的值增加到 \(r_u\)，并将操作次数加 \(1\)。
- 否则 \(u\) 的值为 \(tag\)。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, fa[N], l[N], r[N], ans, T;
vector<int> edge[N];
int dfs(int u) {
int tag = 0;
for (int v : edge[u])
tag += dfs(v);
if (tag > r[u])
return r[u];
if (tag < l[u]) {
ans++;
return r[u];
}
return tag;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
while (T--) {
ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
edge[i].clear();
}
for (int i = 2; i <= n; ++i) {
cin >> fa[i];
edge[fa[i]].push_back(i);
}
for (int i = 1; i <= n; ++i)
cin >> l[i] >> r[i];
dfs(1);
cout << ans << '\n';
}
return 0;
}
T3 无力的小丑
题面
做法
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 5;
int n, m, C, lim[N], sum[N], dp[N][N], f[N][N];
struct obj {
int v, w, c;
obj() {}
obj(int _v, int _w, int _c) {
v = _v;
w = _w;
c = _c;
}
};
vector<obj> v[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> C;
for (int i = 1; i <= n; ++i) {
int v, w, c;
cin >> v >> w >> c;
::v[c].push_back(obj(v, w, c));
sum[c] += w;
}
for (int i = 1; i <= C; ++i) {
cin >> lim[i];
lim[i] = min(lim[i], m);
}
for (int i = 1; i <= C; ++i) {
f[i][0] = 0;
for (int j = 1; j <= m; ++j) {
f[i][j] = -0x3f3f3f3f;
}
for (int j = 0; j < v[i].size(); ++j) {
for (int k = lim[i]; k >= v[i][j].w; --k) {
f[i][k] = max(f[i][k], f[i][k - v[i][j].w] + v[i][j].v);
}
}
}
memset(dp, -0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= C; ++i) {
for (int j = 0; j <= m; ++j) {
dp[i][j] = dp[i - 1][j];
}
for (int j = 0; j <= min(lim[i], sum[i]); ++j) {
for (int k = j; k <= m; ++k) {
dp[i][k] = max(dp[i][k], dp[i - 1][k - j] + f[i][j]);
}
}
}
int ans = 0;
for (int i = 0; i <= m; ++i)
ans = max(ans, dp[C][i]);
cout << ans << endl;
return 0;
}
T4 quq
题面
做法
说句闲话，有理数取模要乘逆元。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 10000005, mod = 19260817;
int n, a[N], iv[N], ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
iv[1] = 1;
for (int i = 2; i <= a[n]; i++) {
int j = mod / i + 1;
iv[i] = 1ll * j * iv[i * j - mod] % mod;
}
for (int i = n; i; i--){
for (int j = a[i]; j > a[i - 1]; j--){
ans = (ans + 1ll * a[i] * iv[a[n] - j + 1]) % mod;
}
}
cout << ans << '\n';
return 0;
}
四、赛后总结
省流：我们要多学多练DP方面的知识，掌握好时间分配和心态整理。
引言
在信息学奥林匹克的赛场上，每一位选手都是勇敢的水手，在代码的海洋中航行，寻找解决问题的灯塔。正如爱因斯坦所说：“解决问题的最佳方法是在更高层次上思考。”在刚刚结束的一场OI比赛中，我深刻体会到了这一点。
一、比赛前的准备
比赛前的准备是成功的关键。我回顾了自己在算法理论、编程实践、心理调适等方面的准备情况。虽然我已经掌握了一些基本的算法和数据结构，但在深入理解和应用上还有所欠缺。我意识到，”实践出真知”。理论学习与实践应用之间，我显然还有很长的路要走。
二、比赛中的体验
比赛当天，我如同往常一样，带着紧张而又期待的心情走进考场。然而，当题目展现在眼前时，我发现自己对某些算法的理解并不深刻，导致解题时犹豫不决。这让我想起了达芬奇的名言：“理论是灰色的，生命之树常青。”在理论学习与实践应用之间，我显然还有很长的路要走。
三、题目分析与解题策略
在解决一道道题目的过程中，我发现自己在题目分析和解题策略上存在不足。我花费了大量时间去推敲状态转移方程，却忽略了边界条件的重要性，导致算法在测试数据上频频出错。这让我意识到，细节决定成败，正如老子所言：“天下难事，必作于易；天下大事，必作于细。”
四、心态调整与情绪管理
比赛中的心态波动对我的表现产生了不小的影响。面对难题时，我曾一度陷入焦虑，这直接影响了我的判断力和决策速度。我需要学会像罗斯福那样：“最大的恐惧是恐惧本身。”在未来的比赛中，我必须学会控制情绪，保持冷静，以更加稳定的心态面对挑战。
五、知识与技能的反思
回顾比赛，我发现自己在算法和数据结构的掌握上还有所欠缺。特别是在图论和动态规划方面，我需要更加深入地学习和理解。正如高尔基所说：“人的天才只是火花，要想使它成为熊熊烈火，那就只有学习！学习！”我将把这句话作为学习的动力，不断充实自己的知识库。
六、错误与调试
在比赛中，我遇到了一些错误和调试的问题。我发现自己在调试过程中缺乏系统的方法和策略，这导致我在解决一些看似简单但实际复杂的问题时花费了过多的时间。我需要学习更有效的调试技巧，以提高解决问题的效率。
七、未来规划
针对比赛中暴露出的问题，我制定了以下未来计划：
- 加强基础：重新审视并巩固数据结构与算法的基础知识。
- 深入学习：针对图论和动态规划等难点，进行专项学习和训练。
- 实践应用：通过大量练习，将理论知识转化为解题能力。
- 心态培养：学习心理调适技巧，提高比赛中的心态稳定性。
- 经验总结：每次比赛后，及时总结经验教训，不断优化策略。
八、结语
每一场比赛都是一次学习和成长的机会。正如爱迪生所说：“我没有失败，我只是发现了一万种行不通的方法。”我将这些失败视为通往成功的垫脚石，不断前进。在未来的OI旅程中，我将以更加坚定的步伐，迎接每一个挑战，寻找属于自己的灯塔。
\(\Huge 傻孩子们，快跑啊！！——MWL\_wma\)
标签：0721,模考,ch,比赛,int,sum,cin,tag,补题 From： https://www.cnblogs.com/TangyixiaoQAQ/p/18314656