--author: Answeror ---title: [HDU][2492][Ping pong] ----link: http://acm.hdu.edu.cn/showproblem.php?pid=2492 ----date: 2009-09-17 -problem: 给你长度为n的一个正整数序列v, 每个元素值唯一, 问能组成多少个形如v[i]≤v[j]≤v[k] or v[i]≥v[j]≥v[k], i<j<k的三元组. solution: 开两个树状数组, 一个在输入时建好用于求i右边比i大或小的元素个数, 另一个在输入后边遍历边建, 用于求i左边比i大或小的元素个数. -----tag: 树状数组 ----code: http://docs.google.com/View?id=dgtsspfh_95c99rm5cw
Helanic Abyss
I am the answer.
[HDU][2492][Ping pong]
[UVA][3562][Remember the A La Mode!]
--author: Answeror ---title: [UVA][3562][Remember the A La Mode!] ----link: http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3562 ----date: 2009-09-14 -problem: 一个人要把p种派和l种冰淇淋配对, 配对矩阵是浮点型, 表示利益, 元素0则表示不能配对, 每种派和冰淇淋都有若干个, 但保证总数相同, 并且一定有解, 问当完美匹配时, 利益最小值和最大值分别是多少. solution: 最小费用流和最大费用流 -----tag: STL,二分图,匹配,费用流,仿函数,模板特化 ----code: http://docs.google.com/View?id=dgtsspfh_94d98cn7gm
[ZJU][2364][Data Transmission]
--author: Answeror ---title: [ZJU][2364][Data Transmission] ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2364 ----date: 2009-09-14 -problem: 1500个点, 300000条有向边的分层图(边都是由低层指向高层), 求最底层到最高层的最大流.solution: 贪心初始流, Dinic -----tag: Dinic,最大流,二分图,预处理,贪心初始流,有向无环图 ----code: http://docs.google.com/View?id=dgtsspfh_92jxtdtm2m
[HDU][2489][Minimal Ratio Tree]
--author: Answeror ---title: [HDU][2489][Minimal Ratio Tree] ----link: http://acm.hdu.edu.cn/showproblem.php?pid=2489 ----date: 2009-09-05 -problem: 给你n个点的无向完全图, 有点权vc[i], 边权ec[i][j]求包含m个点的一个生成树, 使得此树的sum{ec}/sum{vc}最小. solution: 枚举m个点, 做最小生成树. -----tag: Prim,枚举,最小生成树,最优比率生成树 ----code: http://docs.google.com/View?id=dgtsspfh_91fqtj4xgv
[PKU][1904][King's Quest]
--author: Answeror ---title: [PKU][1904][King's Quest] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1904 ----date: 2009-07-14 -problem: N男N女, 每个男的喜欢若干女的, 给出一个初始配对, 求每个男的在所有男的都有女的可配的前提下, 所有可能配对. solution: 以人为顶点建图, 求强连通分量, 在同一分量内的人可以配对. -----tag: 建图,连通性,二分图,匹配,增广路,强连通分量 ----code: http://docs.google.com/View?id=dgtsspfh_90f3zm2ptg
[USTC][34th ACM/ICPC Asia Regional, Hefei, Preliminary]
contest: [USTC][34th ACM/ICPC Asia Regional, Hefei, Preliminary] ---date: 20090906 ---team: Overmind -author: Answeror ---link: http://acm.ustc.edu.cn/ustcoj/contest.php?contest=6 ----tag: NP,Floyd,LCIS,DP,完全背包,同构,最大团,计算几何,高精度,最短路,枚举,树的最小表示
[USTC][1119][Graph]
--author: Answeror ---title: [USTC][1119][Graph] ----link: http://acm.ustc.edu.cn/ustcoj/problem.php?id=1119 ----date: 2009-09-09 -problem: 判无向图同构, 可能有重边, 自环. (n<=25) solution: 先统计度, 排序, 序列判等, 然后枚举第二个图映射到第一个图的关系, 度相同的才尝试映射, 加入一个映射的时候就判断一次当前子图是否相符. -----tag: NP,同构,排序,度,预处理 ----code: http://docs.google.com/View?id=dgtsspfh_89qgtnzch2
[USTC][1117][Bean Language]
--author: Answeror ---title: [USTC][1117][Bean Language] ----link: http://acm.ustc.edu.cn/ustcoj/problem.php?id=1117 ----date: 2009-09-07 -problem: 判无根树的同构 solution: 将两棵树最小表示, 枚举第二棵树的根, 最小表示两树后判等. -----tag: 树,同构,排序,枚举,树的最小表示 ----code: http://docs.google.com/View?id=dgtsspfh_88d6597qc8
[PKU][1635][HDU][1954][Subway tree systems]
--author: Answeror ---title: [PKU][1635][HDU][1954][Subway tree systems] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1635 ----link: http://acm.hdu.edu.cn/showproblem.php?pid=1954 ----date: 2009-09-07 -problem: 给你一个二进制字符串, 0表示往远根一步走, 反之, 问两个串表示的树是否同构. solution: 将两棵树最小表示, 再判字符串相等. -----tag: 树,同构,排序,字符串,树的最小表示 ----code: http://docs.google.com/View?id=dgtsspfh_86gw937jfs
[USTC][1044][A Puzzle of Two Cities]
--author: Answeror ---title: [USTC][1044][A Puzzle of Two Cities] ----link: http://acm.ustc.edu.cn/ustcoj/problem.php?id=1044 ----date: 2009-09-08 -problem: 给你一个n*m的二维字符矩阵, 'A'在左上角, 为起点, 'B'在右下角, 为终点, '#'表示不可走, '.'和'*'表示可走, 要你找一个'*', 使得它在从A到B的唯一路径上, 并且离A最近. solution: 以A为根求割点, 要求此割点必须是'*', 并且其后继节点可以到达B, 然后从A做BFS, 找到第一个割点即是答案. -----tag: DFS,BFS,连通性,割点,搜索 ----code: http://docs.google.com/View?id=dgtsspfh_85fgjz8pgr