海亮NOIP集训-每日总结

[总结] xzh 2021暑假每日结

2021年7月12日

内容主题

DP，树型DP（讲解人：王修涵）

考场题目总结

T1: 考场简单想法：

算出两两点间距离，贪心，所用时间 $1.5h$ 左右。

预估分数：$30$ 实际分数：$20$ ；

T2: 考场简单想法：

通过左端点与右端点的关系求解，比较接近正解，但是没DP。

所用时间：$1.5h$，预估分数：20 实际分数：0；

T3: 考场简单想法：

本来想打个暴力的，结果暴力写挂了，样例都没过。

所用时间，$30min$ 预估分数：$0$ 实际分数：$0$ ；

T4: 考场简单想法：

样例看懂了，但计算不来概率，所用时间 $45min$ 左右。

预估分数：0 实际分数： 0 ；

考后总结

收获

DP需要更多的熟练度，这可以通过刷题解决；DP也需要更广的思维，这可以通过独立思考培养。

考试失误

T1去年做过的，竟然没有想起来

今日未解决后期解决问题

T3，T4

其他想记录的

遇到暴力都打不来的题该怎么办？

PYB: 收获里面写的东西是很到位的了，明确了自己要做的和欠缺的，那么接下来做的时候，就向PYB所说的那样方式去训练，肯定会有很大的提升的。

2021年7月13日

内容主题

DP，数位DP（讲解人：王修涵）

考场题目总结

T1: 考场简单想法：

本来想打表找规律的，结果也没发现什么规律，就打了个暴力。

所用时间 $45min$ ，预估分数： $20$ 实际分数：$20$ ；

T2: 考场简单想法：

先将 $0$ 节点赋值为 $0$ ，然后从 $0$ 节点开始BFS，每个节点在向下更新时，先将儿子按标号从小到大排序，在逐一赋值。

所用时间 $1h$，预估分数：$0-100？$ 实际分数： $5$ ；

T3: 考场简单想法：

最后才发现可以打表，但打到结束也没能把 $n=6$ 的点打出来。

所用时间，$30min$ 预估分数： $20$ 实际分数：$20$ ；

T4: 考场简单想法：

先算出每个人能向右或向左到达终点的概率（这个我调了好久），然后从左到右，选 $a$ 个向左的人，从右到左，选 $b$ 个向右的人，将他们的概率乘起来（然后我就没想到边缘的人可以互相抵消掉）。

所用时间 $2h$ ，预估分数： $?$ 实际分数： $0$ ；

考后总结

收获

考试失误

T3应该先把表打起的。

今日未解决后期解决问题

其他想记录的

2021年7月14日

内容主题

DP，DP优化（讲解人：王修涵）

考场题目总结

T1: 考场简单想法：

设 $f_i$ 表示前 $i$ 个数的最大结果。

然后

\[f_i=max_{1\le k \le i-1}
\begin{Bmatrix}
f_k-(2*|a_{k+1}|)+s_i-s_k
\\
f_k+s_i-s_k
\end{Bmatrix}
\]

$s $ 是 $a$ 的前缀和数组。$O(n^2)$ 的，不知道哪里写挂了。

所用时间 $20min$ ，预估分数： $40$ 实际分数：$0$ ；

T2: 考场简单想法：

设 $f_{i,j}$ 表示前 $i$ 个点选 $j$ 个点的最大收益，且第 $i$ 个点必选。

设 $g_{i,j}$ 表示当前选 $j$ 个点形成的环中 $i$ 节点的后继。

\[f_{i,j} =max_{1\le k\le i-1} \{f_{k,j-1}-|p_{g_{k,j-1}}-p_k|+|p_{g_{k,j-1}}-p_i| +|p_i-p_k|+val\};\\
g_{i,j}=g_{k,j-1};
\]

$val$ 是当前额外的 $a_n$ 收益，暴力搜环计算即可。

$O(n^3)$ 的，然后就又挂了（我早有预感）。

所用时间 $75min$ ，预估分数：$30$ 实际分数： $0$ ；

T3: 考场简单想法：

设 $f_i$ 表示前 $i$ 个人分若干组的方案数。

先对 $a$ 按从大到小排序，然后

\[f_i=f_{i-1}+\sum_{t=1}^{min(a_i-1,i-1)}
\dbinom{i-1}{t}
\]

$O(n)$ 的，绝对会挂

所用时间 $35min$，预估分数：$0-10?$ 实际分数： $0 \ !$ ；

T4: 考场简单想法：

想不出来DP，就写暴力网络流搜增广路（在图的重置问题上调了很久）。

所用时间 $2h$，预估分数：$10$ 实际分数： $10$ ；

考后总结

收获

想什么DP都会挂，还不如暴力来得直接。

考试失误

至今不知挂在哪里

今日未解决后期解决问题

其他想记录的

或许就该写个对拍（就是没时间了）。

前两天，天天写贪心，天天挂；今天不写贪心了，还是挂。（还有为什么今天写贪心的能玄学那么多分）

2021年7月15日

内容主题

微积分，线性代数（讲解人：钟子谦）

收获

又学会一点大学内容。

逐步渗入高等数学。

今日未解决后期解决问题

线性代数有点懵，下来在看看。

其他想记录的

FZUOJ #3047. 「BZOJ2178」圆的面积并空间限制有问题！！！

原题 1.5GB，FZUOJ 256MB！！！

望尽快修改（我交了3页才发现）！！！

2021年7月16日

内容主题

贪心（讲解人：闫书弈）

考场题目总结

T1: 考场简单想法

本来想写O(nm)正解的，但想了很久也没想出来，就只写了40分的暴力，结果没特判还挂了10分。

所用时间想得有点久，预估分数： $40$ 实际分数： $30$ ；

T2: 考场简单想法

当时看错题了，判每个点四周是否比它高，然后取最小高度差。

所用时间 $20min$ ，预估分数： $0$ 实际分数： $10$ ；

T3: 考场简单想法

自己造了几组数据手算，发现答案是 $\sum 每个环的大小 -1 $ 到 $ n - 联通块个数 $。

期望时间复杂度：$O(n)$ ，但被一条链卡了，退化成 $O(n^2)$ ，再加上一些不知道的因素，就 T 了

所用时间 $90min$ ，预估分数： $40$ 实际分数： $20$ ；

考后总结

收获

各种玄学的贪心方法：（倒着贪，存着最后贪，可后悔地贪···）。

考试失误

T2 是道比较简单的搜索，竟然挂了。

放在 T1 上的时间太久了。

今日未解决后期解决问题

其他想记录的

PYB(0716):前几天的总结由于你换地址了，一直没看到，感觉还是写的挺认真的，虽然说前面内容难，但应该也是收获不错的吧。

另：题目空间已修改

2021年7月17日

内容主题

构造（讲解人：闫书弈）

考场题目总结

T1: 考场简单想法：

原本写了一个暴力 DP ，但造了个数据把自己hack了，而且时间杂度也不现实，然后我就开始打表找规律了。但最后也并没有找到什么规律，写的暴力还没有分。

所用时间 $106min$，预估分数： $0$ 实际分数： $0$ ；

T2: 考场简单想法：

不会，跳过。

所用时间 $<5min$，预估分数： $0$ 实际分数： $0$ ；

T3: 考场简单想法：

考虑根据深度分层。先遍历一遍整棵树，并在回溯时记录顺序（相当于后序遍历的dfn），并将每一层的点存入该层的 $vector$ 中，将每一层的点按 dfn 的大小排序。我们发现，如果 v 在 u 的子树中，那么 v 的 dfn，应该在 u 的 dfn 和 u 的前驱的 dfn 之间（这里的前驱是指与 u 同层且 dfn 值比 u 小的点中，dfn 最大的一个点）。于是对于每次修改，枚举要修改的每层，并在该层的点中通过二分查找找到 u 的子节点然后区间修改。对于每次查询同理。但害怕 $vector$ 用 $lower\_bound$ 的虚假时间复杂度，我就自己写二分（然后就在下标问题上搞了很久）。对于接下来的区间修改，当时我本想打棵线段树，但我看了一下觉得没时间调了就直接打的暴力修改——结果可以拿90分！（数据也太水了）。

但由于过于仓促，输出答案时就忘了换行。。。

考完后，发现根本不用用 $vector$ 存点，直接记录 bfn 再维护。

但我还是用我考试的方法过了，而且还要快一些（我感觉常数挺大的），就是在用树状数组维护时要卡一下空间，还好 wpc 交了我用 $vector$ 套 $vector$ 动态储存。

所用时间 $105min$ ，预估分数： $30$ 实际分数： $0$ ；

考后总结

收获

vector<vector<vector<vector<.....> > > >。

int ***...a;

等空间优化。

考试失误

已经写在前面了。

今日未解决后期解决问题

T2以后有时间做一下。

巴特西

海亮NOIP集训-每日总结

[总结] xzh 2021暑假每日结

2021年7月12日

内容主题

考场题目总结

考后总结

收获

考试失误

今日未解决后期解决问题

其他想记录的

2021年7月13日

内容主题

考场题目总结

考后总结

收获

考试失误

今日未解决后期解决问题

其他想记录的

2021年7月14日

内容主题

考场题目总结

考后总结

收获

考试失误

今日未解决后期解决问题

其他想记录的

2021年7月15日

内容主题

收获

今日未解决后期解决问题

其他想记录的

2021年7月16日

内容主题

考场题目总结

考后总结

收获

考试失误

今日未解决后期解决问题

其他想记录的

2021年7月17日

内容主题

考场题目总结

考后总结

收获

考试失误

今日未解决后期解决问题

其他想记录的

最新文章

热门文章