周小结1(2023.6.5-2023.6.9)

题目概要

Day-1：

1、Two Currencies

题目链接：AT_abc164_e。

分层图最短路便可过。

2、Serval and Rooted Tree

题目链接：CF1153D。

贪心+动态规划便可过。

3、Donation

题目链接：AT_arc098_d。

需要发现一些性质，经过每个点 $i$ 后至少得有 $c_i=\max (a_i-b_i,0)$ 的钱，然后，所以对于每一条边 $(u,v)$ 经过它至少得有 $\max(c_u,c_v)$ 的钱。

最后用一下超纲知识 Kruskal重构树 维护一个树形 DP 就行了。

4、Colorful Balls

题目链接：AT_arc012_d。

计数DP一下便可过。

5、已经没有什么好害怕的了

题目链接：洛谷 P4859。

主要还是计数DP，但是最后需要用到第二种容斥，即 $ans=\sum_{i=k}^n (-1)^{i-k} f_i$ 这个公式才能解决。

Day-2：

1、Make M

题目链接：AT_arc161_a。

贪心之后判定一下便可过，但是题目有坑点。

2、Exactly Three Bits

题目链接：AT_arc161_b。

贪心或者动态规划便可过。

3、Dyed by Majority (Odd Tree)

题目链接：AT_arc161_c。

动态规划可以过，但是代码有点麻烦。

4、Everywhere is Sparser than Whole (Construction)

题目链接：AT_arc161_d。

简单构造题。

5、棠梨煎雪

题目链接：洛谷 P5522。

数据结构（线段树+位运算）便可解决。

6、线段树：关于时间

题目链接：LOJ P6346。

其实很简单，考虑把所有集合里面的运算提到最前面去，统计答案时减去多余的即可（用两棵线段树维护）。

7、Points

题目链接：CF19D。

线段树+平衡树，但是为了避免双 $\log$，在线段树上二分就可以求出来答案。

Day-3：

1、午餐

题目链接：洛谷 P2577。

排序后DP便可过。

2、Removing Coins

题目链接：AT_agc033_c。

求出最长链（每次都会对最长链造成影响），用博弈论式子推一下就可以了。

3、大师

题目链接：洛谷 P4933。

只用动态规划便可过。

4、绝世好题

题目链接：洛谷 P4310。

简单动态规划题。

5、Median Pyramid Hard

题目链接：AT_agc006_d。

看到中位数，首先想到二分，然后发现题目中的一些性质就可以快速AC了。

Day-4：

1、ST and TS Palindrome

题目链接：AT_arc155_a。

毒瘤题，但是仔细分析一下AC还是没问题的。

2、Abs Abs Function

题目链接：AT_arc155_b。

数学题，用 $\text{set}$ 维护就可以了。

3、YY Square

题目链接：AT_arc157_c。

简单动态规划题。

4、Power Up

题目链接：AT_arc160_c。

简单动态规划题。

5、Median Pyramid Hard

题目链接：AT_arc159_d。

动态规划，但是要用线段树维护。

6、Even Sum Triplet

题目链接：AT_arc155_c。

要发现题目中的一些性质：

• 如果有三个或多个连续的偶数，那么这些偶数都可以任意交换。
• 如果有三个连续的数中存在两个奇数，一个偶数，则奇数可以任意交换。

抓住这两条性质，这道题就做完了。

其他教训

Day1-C

这道题怪就怪在对题目的性质把握得不够，而且 kruskal重构树 也不是那么熟练。性质快要推出来了，但是在一个未经严谨的证明上耗时太久，浪费了很多时间。而且也耽误了后面比这道题稍稍简单一点的 E题 的解决。

Day2-6

不知道为什么人傻了，这么简单的一道大水题都没做出来，考场上一直在考虑正着分析，却没考虑倒着分析的情况，也是耽误了 G题 的解决。

Day4-6

这道题也是因为在错误的解法上僵持太久，导致所有其它的方法都没有考虑，进而错失了 AC 的机会。

总结

1、在一道题上耗费时间太多会影响到后面题目的解决，一定要放下心专心做某道题，才会有更大几率成功。

2、如果一个做法有很大概率有问题，那么不妨尝试一下其它做法，说不定其它做法会更优。

3、做题时不能焦躁，这样子会导致简单的题反而想复杂做不起。

4、还要善于发现题目的性质，数学功底要扎实，最好把题目内容用公式表达出来，这样更加清晰明了。

5、最后，本周总评：85/100分。