Educational Problems

langx_zym · 2024-08-25 19:02:40 · 个人记录

https://ac.nowcoder.com/acm/contest/88455/G

离散化处理的模板，倍增思想藏复杂度也有教育意义。

https://codeforces.com/gym/105336/problem/I

利用了之前整理过的小式子简化问题，dp的处理方式也很有启发性，f_{i,j}表示前i个数选j个行李的方案数，枚举到i首先确定i能选的行李数量rec，然后对于任意选了j-1个行李的方案，rec - (j - 1) 的这些位置都可以随意插入，乘进答案即可。

https://codeforces.com/problemset/problem/1737/D

突击检查：弗洛伊德and脑筋急转弯。

https://www.luogu.com.cn/problem/P5495

将质因子分解作为维度，再加上高维前缀和求解的思想，as筛的复杂度，太精妙。

https://codeforces.com/contest/2001/problem/D

又是一道富有教育意义的毒瘤思维题，方向是明确的直接想就行，居然是输在直线思维上了。然后代码是一坨，呃呃呃。

http://codeforces.com/problemset/problem/2004/F

2600超毒瘤思维题，入手方式值得学习，空区间的处理给我上了一课。

https://codeforces.com/gym/104901/problem/G

矛盾关系二分图染色典题（2-sat?）,又被狠狠教育到了

https://www.luogu.com.cn/problem/P4046

想了知道两个人的位置推第三个人的位置，然后蒙蔽了，没发现可以利用当前位置必有一个人，以及两人走到同一位置不优的条件来直接转移，存在两个人在x y 这种dp设计确实被教育到了。

https://www.luogu.com.cn/problem/P7845

知道怎么做，但细节就是实现不好.

https://codeforces.com/gym/104901/problem/B

大胆乱搞才能过的题。

但在优化常数方面有教育意义，umap常数很大，需要频繁初始化时常数可能比log还要大，而且面对特殊数据时复杂度具有不稳定性。map也有第一个毛病。

而我们看不起的全局数组加size指针可以直接省去所有初始化带来的常数，效率反而极高，即使需要手动sort合并来模拟map的过程也会高效的多，复杂度仅有一个log而不会有什么常数，所以当运行时间紧张时，应该尽可能避免使用umap和map，采取全局数组模拟的方式。

https://codeforces.com/contest/2021/problem/C2

将set map运用到极致，赛中想法是对的，用set维护链表的合法关系数量，但是依托答辩。看了jiangly的代码直呼天人，维护不合法关系的数量，这样直接避免了很多无用的边界问题。用map来实现，也比set好看的多，还学到了很多新用法，太优雅了。这样即使是我也能很轻松写对，保留一份代码。

code：https://www.luogu.com.cn/paste/23b0ahox

https://codeforces.com/gym/104160/problem/A

积分期望,是真的调了一坤年啊.警示后人的小bug,这么长的代码重构真的需要勇气,哎.

code:https://www.luogu.com.cn/paste/1t5enczz

https://codeforces.com/gym/104160/problem/I

很不错的一道权值线段树题目,又学到了很多,比如权值线段树的值域可以包含负数,写法上应该统一为向0取整(l + r >> 1).维护模意义下的排名真的太线段树思维了,他并不是每个节点都满足整体的正确性,但这道题目只需要次根节点正确即可,这里面有种我学不到的灵性啊.

https://ac.nowcoder.com/acm/contest/95336/A

跟上上那道积分期望有异曲同工之妙,甚至可以说是劣化版本,那照理说该拿下的,但是既没有一眼出思路,式子和分类讨论也都没理清楚,哎.脑子不够用呀.

https://atcoder.jp/contests/abc394/tasks/abc394_g

学这么多年竞赛第一次见这种二分,太妙.

https://atcoder.jp/contests/abc395/tasks/abc395_d

我了个小思维噢,绝了.

https://mirror.codeforces.com/group/5H0hEjEiuF/contest/594068/problem/L

位掩码dp，可以的。

https://atcoder.jp/contests/abc390/tasks/abc390_f

好一道简洁有力新颖又教育的数学思维题.

https://codeforces.com/gym/104417/problem/F

归结为典题,难点在于要想到正确的dp方法,线段树优化反而是简单的部分,一发过也是做爽了.

https://acm.hdu.edu.cn/showproblem.php?pid=7464

发现性质，巧妙建图。

拆位方案统计树形dp，难度集大成。

https://www.luogu.com.cn/problem/P9745

直击数学弱点，教育意义过强。。

https://acm.hdu.edu.cn/contest/problem?cid=1154&pid=1009