[考试总结]noip8
又是一个题的正解都没有打出来的一天
但是自己独创了 \(lca\) 的求法, 然而如果去掉求 \(lca\) 的过程,就不会 \(TLE\) 了。 \(\huge{\text{囧}}\)
然后就是对性质不是十分熟悉。。。
\(T1\) 的欧拉路我是真的忘干净了,别说什么性质了,提起来只还记得一个一笔画。。。
然后还有就是单调性的误判,然而拿了很多分,但是写了一个错解。。。
超级树上花费了不少时间,然后什么都没有打出来。。。
骗了5分 \(\huge{\text{囧}}\)
对于最后一个题目,自己估计的复杂度为 \(\mathcal O(nm)\)。
然而因为数据过水
过了一批。。。。
然而我的独创 \(lca\) 求法还是 \(TLE\) 了
所以对于这批数据,不求 \(lca\) 才是最快的解法。。。。
T1
这道题目其实就是考察欧拉路,欧拉路的很多很多性质记住之后就能秒掉这个题目。。。
题目的要求其实就是 把每条边加倍,然后将这个图变成欧拉路就行了
然后就是不太难的排列组合问题
考虑几个情况。
- 去掉两个自环。
- 去掉一个自环和一条边。
- 去掉两个相连的边。
然后就是判断这个图是否是 边联通图。。。
这个图和点联通图不是很一样,即使点不全部联通这个图也可能是边联通图
所以可以考虑从一个度不为 \(0\) 的点开始拓扑,然后如果发现有的点没有到过并且存在度或者是存在自环,那么就可以输出 \(0\) 走人了。
对于排列:
\]
T2
其实式子很简单,就是数列分块的思想。。
\]
然后就可以在线性再乘上根号的复杂度去搞了。
T3
我是真想不出来。。。
就是用 \(f_{i,j}\) , \(i\) 是深度 ,\(j\) 是枚举的 \(l\) \(r\) 边的个数。。。。
方程五个就不放了。。。
T4
先预处理出来所要的值。
然后对于没一个询问向上爬取。
先使两个点深度相同。
然后再一起向上爬取。。。
就这。。。
然而这并不是正解。。。
正解还是要 \(lca\) 的,然后向上处理前缀和。
差分也行。。。
复杂度稳定。。。
最新文章
- 用CIL写程序:你好,沃尔德
- java多线程系类:JUC线程池:06之Callable和Future(转)
- iphone中input标签会多出一块的解决办法
- MVC简单分层思想(连接数据库)
- 结对编程—黄金点游戏WinForm单机版
- java中多线程中Runnable接口和Thread类介绍
- 跳台阶 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
- struts2中各种值栈问题
- Linux下解决“shutdown: command not found";问题
- 关于sources.list和apt-get [转载]
- gdb调试多线程程序总结
- 20140708郑州培训第二题Impossible Game
- 转载:JAVA 正则表达式 (超详细)
- Linux C 语言 获取系统时间信息
- Python 正确重载运算符
- SD 笔记01
- log4j控制指定包下的日志
- OCP考试062题库出现大量新题-19
- Mac 10.12安装Git管理工具SourceTree
- 洛谷 P3338 [ZJOI2014]力 解题报告
热门文章
- 重新整理 .net core 实践篇—————中间件[十九]
- pytest skip的使用
- Centos Yum 安装 Mysql 5.7
- 【VBA】查找字符串
- 04:Django生命周期流程图
- MySQL零散知识点(01)
- 【Azure 机器人】微软Azure Bot 编辑器系列(6) : 添加LUIS,理解自然语言 (The Bot Framework Composer tutorials)
- spring赌上未来的一击:WebFlux性能实测
- excel VBA正则匹配单元格符号,并按符号把单元格拆分行(这里是按第一列分行,分行是从活动单元格的行开始,分行前需要选择所有需要填充内容的列,否则需要后期手动填充)
- Android开发万能Utils(工具大全)