2017多校Round10(hdu6171~hdu6181)
2024-08-30 18:37:27
补题进度:5/11
1001(双向BFS)
题意:
给你一个类似移子游戏,给你初始状态和终止状态,问初始状态到终止状态至少要移多少步,如果步数>20就-1
分析:
很明显的BFS了,不过普通的BFS会有4^20个节点,会TLE
这里因为移动方式可逆并且两个状态明确,所以可以双向BFS,在中间汇合就行
只需要在某个方向的BFS扩展到12步左右的时候返回-1就行了
1002(BM算法模板)
题意:
给你很复杂的很复杂的递推式,你需要求$\left \lfloor \sqrt a_n \right\rfloor$
分析:
这个有根号还有取整肯定不能直接矩阵乘了
猜测一下结果应该是线性递推,所以手算几个初值丢到杜教的BM板子里就行了
1003(待填坑)
1004(待填坑)
1005(待填坑)
1006(待填坑)
1007(待填坑)
1008(树的最大匹配)
题意:
有一个n个点的树,你需要选择k个点每个点上放一只猴子,树上的n-1条边中你可以选择删掉一些保留一些,但是必须能让每个猴子所在点的连通分块内都有另一只猴子,问最少保留多少条边
分析:
贪心着来,肯定是尽可能往树的最大匹配上丢猴子最优,这样的话2k个猴子只需要保留k条边
最大匹配的点丢完了然后怎么办呢,容易发现这时候往任意一个点丢猴子都会使得结果+1,所以随便将剩余的猴子丢上去就行了
于是只需要用dp跑出最大匹配这题就结束了
时间复杂度O(n)
顺便一提这题卡读入
1009(待填坑)
1010(贪心+堆)
略
1011(裸的次短路)
略
最新文章
- 从零自学Hadoop(10):Hadoop1.x与Hadoop2.x
- chaper3_exerise_UVa455_周期串
- VSFTPD添加用户
- js常见怪异
- 错误 undefined reference to __cxa_guard_acquire/release
- 抽象工厂模式(python版)
- PopupWindow 问题集锦
- Zookeeper全解析——Paxos作为灵魂
- sqlserver2008附加数据库——错误3415
- C# WinForm 和 javascript进行交互 使用HTML做界面
- php事件驱动
- Codeforces 1095F Make It Connected(最小生成树)
- mysql安装出现问题(The service already exists)
- 5、lvs使用进阶(01)
- Python Selenium 文件上传之SendKeys
- tomcat7修改tomcat-users.xml文件,但服务器重启后又自动还原了。
- Java动态代理的两种实现方法
- mark_2017_2_27
- .NET异步多线程,Thread,ThreadPool,Task,Parallel,异常处理,线程取消
- 【CODEFORCES】 A. Keyboard
热门文章
- qt QTableView/QTableWidget样式设置
- (转)使用JDK中的Proxy技术实现AOP功能
- 网页添加tittle前的图标logo
- JAVA Native Interface (JNI)
- Ahoi2014&;Jsoi2014 支线剧情
- c++_最大公共子串
- Python旅途——简单语法
- Python爬虫-抖音小视频-mitmproxy与Appium
- 「LibreOJ β Round #3」绯色 IOI(抵达)
- 杭电 4004 The Frog's Games 青蛙跳水 (二分法,贪心)