//GDKOI 2012之前涉及的题目, 由此可见寒假真的什么都没做
1.25
air[二分图最大匹配 -> 最大流], 1h
[建图]
(1) 在飞行员u和外籍飞行员v间增加有向边(u,v), 同时增加源S到u的边(S,u), 以及v到汇T的边(v,T).
(2) 考虑到n<=100, 利用邻接矩阵存储, 上文增加边容量为1, 其余为0, S到T的最大流即为答案.
(3) 直接利用map记录u和v的对应关系
*数据的方案似乎不是最小字典序, 此外题目中未涉及方案的顺序问题, 暂不考虑.
path[最小路径覆盖 -> 二分图最大匹配 -> 最大流], 1h
注意到在路径覆盖中, 每个点只能被覆盖一次.
[建图]
将每个点拆分, 然后源S和汇T分别连边, 点间按照题目要求连边, 求最大流f即可.
显然如果要增加一个路径覆盖, 必须存在某点没有前驱(或后继), n-f即为所求.
[输出方案]
利用flow数组从1开始遍历, 用vis标记已访问点即可.
某题 by ftiasch
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
[O(log(n+m))做法]
你假设求第k大嘛, 肯定是这边来前i个, 那边来前j个. 然后二分i, 就有j了. 然后check一下合法否.
1.27
poj 2976[分数规划 -> 参数搜索]
[定义]一般地, 求max{a(x)/b(x)}, a(x) b(x)是实值函数, 且b(x)>0.
特别地, 如果max{a(x)/b(x)} ∈ (0,1), 称为0/1分数规划
[解法]
不妨设lambda即为所求.
显然满足 a(x)/b(x) >= lambda (注意大于等于号)
整理可得 a(x) - b(x)*lambda >= 0
显然存在任意x值满足lambda即可, 比如在这种情况下可以求函数最大值, 若最大值不满足, 那么显然这个lambda不会得到满足.
设g(lambda) = max{a(x) - lambda*b(x)}
分析可知:
g(λ) > 0 <=> λ' < λ
g(λ) = 0 <=> λ' = λ
g(λ) < 0 <=> λ' > λ
转换为0/1分数规划后, lambda ∈ (0, 1), 可以二分lambda, 注意a(x)和b(x)的求法因题目而异.
*比如最优比率生成树问题
*可以利用qsort直接对double排序, 写法和int一致, 需要注意排序时return x > 0 ? 1 : -1;不要返回0
*对于浮点误差, EPS = 1e-8, 越小越好(时间代价?)
1.31
GDKOI 2010分析[未验证]
30 + 20 + 12 + 12 = 74
30 + 40 + 20 + 12 = 102
考虑到实际情况, 以及对拍时间, 似乎150+并非不可能.
Day1
[1]load
AC, 改变松弛条件的最短路, 可以使用Floyd
[2]goodjob
30%, 裸DFS
AC, 状压DP
[3]pizza
30%-50% 乱搞, 利用最大m段和或者分数规划
AC 利用周期数列的性质?不明.
[4]plan
30% 暴搜?
AC 费用流
Day2
[1]collection
数学题, 通过简单的变形得到函数, 可以利用三分法或者Cauthy不等式求解
[2]cook
10% 暴搜, 生成全排列
AC 4维DP
[3]table
50% BFS
AC 双向BFS
[4]push
30% 模拟
AC 利用扫描线思想, 对坐标排序[具体不明...]
GDKOI 2011分析[未验证]
30 + 20 + 8 + 12 = 70
24 + 20 + 12 + 12 = 68
考虑到考场上可能的问题, 大概能保证100.
Day1
[1]sewer
DFS/BFS/...随便模拟
*小数据验证
[2]park
50% 对于每个长方形, 枚举每棵树是否在其上, O(NM)
AC 通过某种操作把验证某个树在某个矩形上, 由O(N)降至O(logN), 比如平衡树
*小数据验证, 如果构造AC算法必须对拍
[3]mission
20% 模拟
AC T_T我不会
[4]move
30% BFS
AC A*/状压DP
*小数据验证
Day2
[1]weight
30% DFS, O(3^N)
AC 分成两堆, 分别进行DFS, 然后对于每个砝码组合m, 在另外一堆里找n, 使得m+n满足题意即可.
*两种思路对拍
[2]ponytail
50% 简单分析之后利用整除性和打表暴力
AC 进一步的分析, 利用欧拉函数求解
根据题意
s >= x + y ...(1)
1/x + 1/y = 1/z ...(2)
由(2)可得, x+y | xy ...(*)
设(x, y) = d
可得x = d * x1, y = d * y1
代入(*)可得 x1+y1 | dx1y1
易证x, y分别和x+y互质
令d = t(x1 + y1), 代入即得
s = x + y = t(x1 + y1)^2
令n = x1 + y1, 显然满足题意的n的个数为欧拉函数φ(n), 满足题意的t的个数为[S/n]
综上可得, Σφ(n)*[S/n]即为所求.
[3]bright
30% 最大流
AC T_T我不会
[4]eight
30% DFS
AC 状压DP
=> 导出结论, 主要复习暴搜, 其次复习基本算法, 如图论若干, ST等.
2.1
rqnoj 70 八数码难题[BFS+hash], 2h
BFS实现, 利用hash判重(简单的取余法)
*移动步骤考虑不周, 可以直接利用数组存储, 四个方向分别为±1或3; 需要注意±1, 即左右移动后, 0必须在同一行
*hash写错
双向广搜, 扩展完一边的该层节点, 再扩展另一边的一层节点, 直到两边状态相遇.
http://longxiaozhi.is-programmer.com/posts/24858.html
实现无能, 遂放弃.