contest: 34th ACM/ICPC Asia Regional Hefei ---date: 20091011 ---team: Overmind -author: Answeror ----tag: Java,KMP,容斥原理,多串匹配,后缀数组,AC自动机,字符串,博弈,树形DP
Helanic Abyss
I am the answer.
34th ACM/ICPC Asia Regional Hefei
[HDU][3120][Dolphin]
--author: Answeror ---title: [HDU][3120][Dolphin] ----link: http://acm.hdu.edu.cn/showproblem.php?pid=3120 ----date: 2009-08-18 -problem: 有一只脑残的海豚, 在一个有自环有重边的无向图上从起点去终点, 每个顶点上有一条鱼, 每条鱼有各自的种类, 海豚经过一个点就会吃, 现在海豚要求不吃同一种鱼两次, 问去终点的最短路, 不存在则输出-1. solution: 二分答案, 预处理终点到各点的最短路, DFS每层都求一次当前点到终点的最短路做剪枝. -----tag: SPFA,DFS,二分答案,最短路,搜索,剪枝,预处理 ----code: http://docs.google.com/View?id=dgtsspfh_104cccpr3d4
[PKU][3267][The Cow Lexicon]
--author: Answeror ---title: [PKU][3267][The Cow Lexicon] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3267 ----date: 2009-09-25 -problem: 有一个串和一个字典, 问最小从串中去掉多少个字符使得此串可以由字典中的串组成(可以重叠). solution: DP -----tag: DP,字符串,匹配,多阶段决策 ----code: http://docs.google.com/View?id=dgtsspfh_103gwtfrvd9
[PKU][1639][Picnic Planning]
--author: Answeror ---title: [PKU][1639][Picnic Planning] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1639 ----date: 2009-09-23 -problem: 有n个点, 求一棵最小生成树, 使得1号点满足度数不大于s. solution: 最小度限制生成树, 详见刘汝佳黑书P300. -----tag: Prim,最小度限制生成树,黑书 ----code: http://docs.google.com/View?id=dgtsspfh_102hg45bpdx
[PKU][2482][Stars in Your Window]
--author: Answeror ---title: [PKU][2482][Stars in Your Window] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2482 ----date: 2009-09-23 -problem: 二维整数坐标系上有n个点, 点i有权值v[i], 给你一个w*h的矩形框, 问最多能框多少权值(边界上不算), 框可以平移, 不能旋转. solution: 扫描线+静态二叉排序树, 详见刘汝佳黑书P102. -----tag: 静态二叉排序树,完全二叉树,黑书,扫描线 ----code: http://docs.google.com/View?id=dgtsspfh_101g782gffz
[PKU][1737][Connected Graph]
--author: Answeror ---title: [PKU][1737][Connected Graph] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1737 ----date: 2009-09-22 -problem: 给你n个有编号的点, 问能生成多少个不同的无向连通图. solution: 推公式. -----tag: 组合,递推,公式,高精度,连通性,逆向思维 ----code: http://docs.google.com/View?id=dgtsspfh_99dvwtq4gv
[HDU][2989][Elias gamma coding]
--author: Answeror ---title: [HDU][2989][Elias gamma coding] ----link: http://acm.hdu.edu.cn/showproblem.php?pid=2989 ----date: 2009-09-21 -problem: 一种对整数编码的方法(Elias gamma code)是把待编码的整数写成二进制, 假设此二进制整数有k位, 则在这个整数前面加一个k-1个0和1个1的前缀以标识此整数的长度. 现在有若干个不同长度的整数, 二进制长度范围[1,n], n≤128, 现在若直接用上述编码方案编码则总长度增加一倍, 现在有两个优化: 1. 若长度为k的数字没有, 则长度为k的前缀可以用来表示长度为k+1的树, 同时长度为k+1的前缀又可以用来表示k+2的... 2. 可以在长度为k的数前面加一个前缀0使得可以运用优化1. 求最短编码长度. solution: 预处理出长度为i以后所有数字总个数, 状态f[i]为长度为i到n的数的最短编码长度, 记忆化搜索. -----tag: DP,预处理,记忆化搜索,编码,逆向思维 ----code: http://docs.google.com/View?id=dgtsspfh_98cxkb7tws
[PKU][2464][Brownie Points II]
--author: Answeror ---title: [PKU][2464][Brownie Points II] ----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2464 ----date: 2009-09-20 -problem: 二维整数坐标系上有n(<=200000)个点, A用一条竖线穿过某个点, B再用一条横线穿过这条竖线上的某个点, 点被划分为4块(不包含线上), 右上+左下的点数是A的得分, 左上+右下的点数是B的得分, 现在A要选一条竖线, 使得自己可能得到的最小分数最大化, 要求输出这个A的最大化的最小分数, 以及在A得到这个分数的前提下, B可能得到哪些分数, B的分数输出按升序排列. solution: 离散化y坐标, 点排序, 两个一维树状数组一个用于预处理, 一个用于实时统计. -----tag: 预处理,排序,离散化,树状数组 ----code: http://docs.google.com/View?id=dgtsspfh_97hhctphfw
[DHU][2009东华网络赛热身赛]
contest: [DHU][2009东华网络赛热身赛] ---date: 20090919 ---team: BlueGene -author: Answeror ---link: PDF file ----tag: DP,概率,模拟,最小生成树,计算几何,最短路