2019.07.06 纪中_B
2024-09-05 17:54:32
今天的题看起来都很简单，结果就爆炸了
做题时:怎么都是图论???
结果最后好多是DP(最恐怖的是还有我没学过的状压DP)
2019.07.06【NOIP提高组】模拟 B 组
做了两题（稍微腐败了一下），最后0+63.6+100+0=163.6，Rank=22/82
先膜拜：
lh大佬orz
xd大佬orz
T0
当时的思路是贪心,感觉在最短路上修改需要更改的值最小所以需要更改的边最少,现在一想显然是错的
大佬思路是DP,f(i,j)表示点i修改j次的值
T1
题意：给你一棵树，动态改变树上点的权值，求任意两点间路径上点的权值和
我直接暴力操作，修改耗时O(1)，操作耗时O(n)，最终耗时O(mn)
T2
树的遍历+DP;(就是这题我竟然会)
对于每个点及以其为根的子树,我们可以选择将整个子树砍掉或者只砍子树的树枝
所以转移式就是 DP[点i]=min(E[点i->他爸],sum(DP[儿子1]+DP[儿子2]... ...))
点权初始化为0,遇到必删的点直接返回E[点->他爸],因为该子树必删
顺带提一下,最原始的题意就是最小割,所以我们可以把所有要删除的点看为汇点做最大流.因为最大流=最小割(但是最大流我没学过)
T3
据说是状压DP+搜索
我慢慢摸索吧...
最新文章
- 解决 Springboot Unable to build Hibernate SessionFactory @Column命名不起作用
- [ubuntu]用ubuntu开发的日子----win7 ubuntu双系统
- import pysam 出错解决办法
- 猿团YTFCloud--5分钟自制APP，开发从未如此简单
- [转载]html中DTD使用小结
- Struts2中重定向和请求转发配置
- C# 同步/并发队列ConcurrentQueue
- spring来了-01-概述
- Android中visibility属性VISIBLE、INVISIBLE、GONE的区别
- 模仿ViewPager控件
- Jquery datatables 重载数据方法
- MyBatis(3.2.3) - Cache
- String的equals方法和==
- 记一次 nginx 504 Gateway Time-out
- pycharm中Django的安装和简单使用
- :after伪类+content经典应用举例
- Unity3d插件Master Audio AAA Sound v3.5
- spring mvc requestmapping 配置多个
- 第三次作业：结对编程--实现表格在APP的导入和显示
- html超链接，锚点以及特殊字符