[心得]暑假DAY 5
2024-09-02 20:06:42
好久没更新博客了
最近事情太多太多
tarjan进阶，点双边双
T2压力
最大坑点：点双缩点
它不是直接把割点连成树（割点会有环）
而是用割点作”中介“，联接点双构成一颗树（所谓圆方树）
接着在上面进行lca或树剖即可
（树剖版，本人打了八九个小时。。）
那么7-14迎来了NOIP三模，也是第一次和外校比拼/外校出题
挺惨
T1打dp得了35分（正解二分答案+枚举）
dp的缺陷在于无法处理重复元素
为每一个状态加入一个set维护当前数值即可AC（其实挺牵强，MAXQ开100，1w ms可过）
正解的话需要求两项之间的最小公比
让 z=x/y,然后把 z 质因数分解,z=p1^q1*p2^q2*p3^q3......,设 g=gcd(q1,q2,q3...),那么当前序
列的最小公比就是 p1^(q1/g)*p2^(q2/h)*......
其实和gcd有很大关系
设最小公比为q，一定有z=q^(m*k)，m是p1,p2...的最大公因数
于是乎诞生了exhx（雾）算法，由hx（%%%）在考试时想出
我们在枚举前两项时，先不必直接求最小公比，而是暂存“公比的某次幂”
随着枚举，这个“幂”可能越来越小，最终如果不满足“幂”是共比，那么就不能满足
十分优秀，yu-shi大神用其294 ms AC
T2的话拿到了刺猬图的10分，写的dp骗了10分（仅符合完全二叉树）
蛇图的特判失败，因为它不一定是蛇头/尾为根
正解及std没看懂
在学长wq讲解下，习得另一种解法，同时开坑树上dp，不过我还没有入
T3。。。槽点很多
题解dp式子实在看不懂，全机房联合攻克中。。。
明天又要一场比赛
fighting
最新文章
- PHP-解析验证码类--学习笔记
- linux系统硬件配置查看方法
- C++ 基础知识复习（五）
- String类和StringBuffer类的区别
- 9本java程序员必读的书（附下载地址）
- javascript双击事件取消默认的两次单击事件
- 2.4.2电子书fb.c文件
- Git的分支与合并
- （转载）php flush()刷新不能输出缓冲的原因分析
- STL 查找vector容器中的指定对象：find(）与find_if()算法
- c# 配置连接 mysql
- oracle归档日志
- Jenkins+Gitlab CE+Robot Framework持续集成
- PLECS—模型仿真——第十一周作业
- js基础面试篇
- 使用gitbook plugin
- SQL Server Service Broker（简称SSB）资料
- 微信公众平台开发----自定义菜单、消息处理及获取OpenID(C#)
- Git: fatal: Pathspec is in submodule
- 18-[JavaScript]-函数，Object对象，定时器，正则表达式