Codeforces Round #488 by NEAR (Div. 2)
A
开个桶记录是否出现即可。
时间复杂度 \(O\left(n+m\right)\)。
B
按能力值从小到大依次加入,然后维护前 \(k\) 大的金币数即可。
时间复杂度 \(O\left(n\log n\right)\)。
C
发现如果两个正方形有交,那么必定有一个整点被两个正方形同时包含。
然后暴力枚举正方形内的每个整点即可。
时间复杂度 \(O\left(S\right)\)。
D
如果有且仅有一个数在两人那里都出现了,就输出这个数。
如果有任意一对数中的两个数在两人那里都出现了,即存在至少一个人不知道相同的数,就输出 -1
。
如:
1 2
1 2
1 3 2 4
第一个人是 \(1,2\),第二个人是 \(1,3\)。
第一个人不知道相同的是 \(1\) 还是 \(2\),但第二个人却知道是 \(1\)。
2 2
1 2 3 5
1 3 2 4
第一个人是 \(1,2\),第二个人是 \(1,3\)。
第一个人不知道相同的是 \(1\) 还是 \(2\),第二个人也不知道相同的是 \(1\) 还是 \(3\)。
剩下的情况输出 0
。
如:
2 1
1 2 4 5
1 3 4 6
第一个人是 \(1,2\),第二个人是 \(1,3\)。
你并不知道相同的数是 \(1\) 还是 \(4\),但两个人显然都能判断出来相同的数是 \(1\)。
时间复杂度 \(O\left(n+m\right)\)。
E
\(n\) 和 \(m\) 同阶,统一用 \(n\) 代替。
首先敌方自残的发生肯定是一对一对的。
其次,我方战斗机的位置至少能引发一对战斗机自残,否则没有意义。
所以我们可以 \(n^4\) 枚举我方战斗机的位置。
问题是怎么判断击落几架战斗机(可能一边击落两架另一边击落一架)。
直接做是 \(O\left(n\right)\) 的。
考虑在处理位置时把能击落战斗机的位置塞进一个 bitset
里。
然后两个位置并起来就是答案。
时间复杂度 \(O\left(\frac{n^5}{w}\right)\)。
F
01 分数规划。
假设答案是 \(x\),也就是说要满足
\]
\]
先按 \(a\) 从大到小排序,然后把有相同 \(a\) 的任务放到一起处理。显然,之前处理过的任务都可以在当前任务作为第二次执行的任务的情况下作为第一次执行的任务。
因为第二次执行的个数不能多于第一次执行的个数,每次在处理一些有相同 \(a\) 的任务之后都要满足:之前第一次执行完,还未有第二次执行的个数大于等于当前第二次执行的个数。
即:之前第一次执行的个数减去之前第二次执行的个数大于等于当前第二次执行的个数
移项:之前第一次执行的个数大于等于总共第二次执行的个数。
整理得到:总共第一次执行的个数减去当前第一次执行的个数大于等于总共执行的个数减去总共第一次执行的个数。注意此处是为了方便代码的实现。
我们令 \(f_{i,j}\) 表示总共处理了前 \(i\) 种不同 \(a\) 的任务,有 \(j\) 个任务是第一次执行的最大值。有
\]
其中 \(w_{i,j}\) 表示第 \(i\) 种任务选 \(j\) 个的最大值。因为 \(a\) 相同,所以显然是 \(b\) 最大的 \(j\) 个。
然后就做完了,时间复杂度 \(O\left(n^2\log a\right)\)。
最新文章
- 如何在ashx页面获取Session值
- 关于JS 事件冒泡和onclick,click,on()事件触发顺序
- python学习笔记-(五)字符串&;字典
- iOS摄像头和相册-UIImagePickerController常用操作
- webqq 获得好友列表hash算法 获得最新hash的方法
- ALTIUM DESIGNER怎么定义差分对布线
- Unity 读取Excel
- IIS 批处理 bat
- GoldenGate 复制进程报错";OGG-01296 Error mapping";,丢弃文件报错“Mapping problem with delete record (target format)”,且实际条目存在
- mongodb3.6 (五)net 客户端访问mongodb设置超时时间踩过的“坑”
- WAMP中的MySQL设置用户、密码 及 phpmyadmin的配置
- python 可迭代对象 迭代器 生成器总结
- 如何编译luabind支持vs2010之后所有版本
- 一个解决过程:Servlet [某路径xxx] in web application [/项目xxx] threw load() exception和java.lang.ClassNotFoundException XXX
- web前端(11)—— 页面布局1
- 深入理解Plasma(一)Plasma 框架
- learning makefile automatic dependency generation
- awk 和 sed (Stream Editor)
- 牛客练习赛24题解(搜索,DP)
- 哨兵查找法(明解c语言) + 函数式宏