10.22
P1326, SPFA.
最短路模板题
P2022, 模拟.
维护长度为N的序列即可, 对于每个操作注意细节.
P2017, 搜索
贪心上界, 累加下界, 中间暴搜. 昨天打漏了\sum C_i的初始化, 把C_i和A_i打混了.
*据说数据弱到直接交下界就A
*需要复习下gen怎么写了
P2021, 位运算+DP
and, 统计连续的1, 直接计算
or, 统计连续的0, 间接计算
10.27
Vijos Monthly Oct12
P1742, 模拟.
平均数 加权累加即可;
中位数 qsort排序, 按照奇偶分类输出;
众数 排序后累计不同的值和出现次数, 排序输出;
P1745, 贪心?
数据范围否定了DP, 但是作为贪心范围确实有点小. 按照切割的权w_i排序, 如果w_i相等, 则行/列多的先切. 排序后累加即可.
如果f[i][j]来dp的话, 大概是O(N^3)的时间, O(N^4)的空间...
-> 很好, 爆longlong了...T_T
P1746, 图论.
最短路变形, N = 300. 直接利用Floyd得到所有最短路, 对于一对u,v, 分别枚举N个节点, min{G[u][i] + G[i][v]}即为所求.
P1747, ?.
30%明显是搜索, 但是我实在不会暴力了, 连方向都不知道. 我想起来今天AIME那几个暴力算的圆...
*对于算法, 在实现前必须充分讨论细节. 在实现过程中修改细节及其浪费时间.
*对拍 & 特别小数据的构造需要复习, 正确率.
*各类算法模板的整理.
-> 150/300, 实现能力啊啊啊啊
http://www.vijos.org/Discuss_Show.asp?DisID=55613
10.28
Vijos T1062, 实在没动力写, 就YY了一下(...
P1, 十进制小数转二进制小数
不会...乘二取整法套不上
P2, ?
只会暴力做法, O(N!)生成序列, 然后根据约束条件剪枝, 譬如:
(1) 贺卡的时间顺序
(2) 每个人的时区互异性
(3) 时间范围
其实手算可容易了...(
P3, 模拟
[70%做法]
(1) O(N^2)把每个区域盖房子的权值预处理一遍
(2) 盖N次房子, 每次扫一遍找最小值, 然后标记相关区域不可用O(N^3)
*可能的房子数量上限好像是大于N的 ...
[AC做法]
(1) O(N^2)把每个区域盖房子的权值预处理一遍
(2) 把每个区域的权值升序排序, 依次选择, 对于选中的区域, 标记其周边区域不可用, 复杂度O(N^2)