HOJ题目分类

xnby

整合HOJ discussboard上的几个分类：

hoj稍有难度题目分类（数论篇） hft777 2008-11-16 20:35:43.0
在做这些题目前　请学会　在线性时间内　筛选素数　
建议　在Search Problem里　
1输入：prime
2输入：number
把这些题目练练

10007Miller-Rabin + Pollard
10070RSA,Pollard
10174数的质数表示
10195扩展欧几里德
10297数的素数分解 + Euler定理
10247欧拉函数
10544数的素数分解
10621中国剩余定理
10694数的原根
10853LCM
10977梅森数
11099RSA ,扩展欧几里德
11103数的素数分解
11126广义　GCD
11134欧拉函数
11145RSA , 扩展欧几里德 + Pollard
11181中国剩余定理
11262欧拉函数

hoj稍有难度题目分类（搜索与图论篇） reason 2008-11-07 23:39:33.0
Hoj稍有难度题目分类

1.搜索，最短路：
IDA*即迭代加深A*搜索， 个人认为IDA*是对迭代加深搜索的一个强剪枝
在此给出迭代加深搜索框架， 大家有兴趣的可研究其与dfs的区别

int max_depth;
void dfs( int depth )
{
if ( depth > max_depth )return;
操作
}

10020状态广搜，可用位运算以及A*加速
10034 同余类的应用， 可说是最短路变形
102058数码问题，A*或者双向广搜或者IDA*
10321bfs
10466 bfs
10901IDA*
11016同上，得有比较好的剪枝函数
11168状态bfs
11108状态bfs
11240找出规律就简单了
11284应该是个很简单的bfs， 但比赛时犯傻了。。。。
11159bfs+2分枚举答案， zfy有3次bfs的解法， 参见解题报告
11227有点意思的， 不太难， 想不到再看解题报告
11072优先队列bfs
11207 同上
11244双向bfs
10183dfs，最优性剪枝
11019最短路+dp， 应该也可直接用dijkstra做

搜索还有不少好题的，大家有兴趣可在poj在找些好题做做
Hoj应该也还有不少， 限于篇幅， 只写以上这些

2.图论以及博弈

109802分图最大权匹配， km算法
110682分图最大匹配
112232分图最大匹配
10128 博弈， SG函数应用
11117博弈， SG函数应用
10187强连通分支应用
10537割点
10929割边
10801拓扑排序
10420差分约束系统
10035最小费用最大流
10465最小费用最大流
10284最小度限制生成树

图论题建议多去poj做， hoj比较少


hoj题目分类 reason 2008-09-09 21:51:16.0
入门题， 旨在熟悉OJ环境
10000 10005 10006

简单模拟，还有些数学题
包括（基本的筛法求素数， 简单递推， 辗转相除求GCD， 基本位操作， 排序）
10010 10015 10017 10022 10038
10039 10042 10045 10047 10048
10049 10050 10051 10052 10058
10062 10067 10072 10073 10074
10082 10141 10144 10146 10148
10149 10150 10151 10160 10173
10178 10182 10184 10185 10189
10190 10225 10238 10281 10307
10337 10360 10373 10378 10395
10400 10404 10406 10475 10477
10483 10485 10493 10509 10512
10556 10558 10562 10568 10606
10624 10675 10724 10735 10747
10759 10797 10809 10826 10840
10880 10952 10981 11069 11084
11116 11148 1115011172 10013

经典贪心， 一般还得用到排序， 经典动态规划， 二分的应用
10001 10003 10014 10063 10102
10106 10179 10181 10192 10233
10279 10290 10023 11018 10761
10768 10145 10011 10089 10019

基本的搜索， dfs， bfs
10109 10166 10250 10265 10641
10147 11017 10844 10865 11159

下面是较难的题目， 有些也不太难， ：）
10009catalan数， 要用大数
10020较难的bfs， 需要用位表示状态
10018dp， 递推公式出来应该不太难
100212分图最小覆盖， 最小覆盖 = 最大匹配
10024算是dp吧
10053可用随机算法
10068归并排序求逆序
10071TSP问题
10080递推， 大数
100812分法解方程
10088树形dp
10096利用2次函数的性质
10128博弈问题， SG函数求解
10163可分治， 快速求幂， 复杂度O( logn )
10205A*搜索
10233可用2叉搜索树
10247数论， 费马小定理
10280并查集入门
103442维凸包问题， Graphm扫描算法
10372建议用堆
10374prim算法应用
10457可以看作是joseph问题， 线段树求解， 好像有递归的方法
104952维背包问题
10497可参考discuss的解题报告
10508递归应用
10534置换群
10680欧拉函数的应用
10696线段树入门， 也可用树状数组
10733dp
10758基本栈应用
10790数论好题
10801拓扑排序
10850bfs好题， 虽然暴力能过， 建议用状态dp
10929无向图割边
10935很好的一道数学题
109802分图最小权匹配， 也可用最小费用最大流
11016IDA*搜索
11067trie树应用
11120扩展欧几里德应用
11121矩阵快速乘法
11134polya计数定理
11151dijkstra求最短路
112232分图最大匹配
10153floyd求最短路
10284最小度限制生成树

此较难分类旨在让大学了解些算法， 拓宽视野
因此较难的分类我大概就是每类大概找了1个题， 有时间我再把相关的分类补上

HOJ题目分类 给选修课的同学 huicpc11 2006-03-21 01:59:59.0
10000 弱
10001 DP 讨论版里有解题报告
10002 费马点 难
10003 拆分成两个过程DP O(n)
10004 fft 快速傅立叶变换
10005 弱
10006 弱
10007 miller_robin pollar_rho分解
10008 递归的画图 一般
10009 组合数学 好像是卡特兰数
10010 简单，一个数组存状态一个存数值 纯暴力
10011 数学题 有规律
10012 纯暴力
10013 一般难度 算个万年历
10014 简单 DP，每次向下加最大的
10015 弱
10016 弱
10017 贪心+回溯 好像暴扫也出结果
10018
10019 简单 贪心
10020
10021
10022 简单 读题和格式很讨厌
10023 贪心 我在讨论版里有解题报告
10024
10025
10026 弱
10027 同10001 最长递增子序列 不过用二分查当前递增的子序列
10028
10029
10030 纯编译原理 也算基础题了
10031
10032
10033
10034
10035
10036
10037
10038 弱
10039 弱
10040 一般 从后向前扫 好像奇数层取最大 偶数层取最小
10041 纯代码量的题
10042
10043
10044
10045 简单 Joseph Ring 考试的经典题目
10046
10047 简单 字符串模拟加法
10048 简单 两个字符串比较公共字符
10049 简单
10050 简单 开个状态数组hash
10051 简单
10052 简单 有规律
10053 稍难 随机和两层循环降解状态都可以出结果
10054 贪心+递增子序列
10055
10056
10057 讨厌读题 简单的计算题
10058 弱
10059
10060 稍难 模拟
10061
10062 简单 10进制转9进制
10063 稍难的贪心
10064
10065
10066
10067 简单 有点递归交换的意味
10068 稍难 必须归并排序才能过 bubble TLE 老大给了16M测试数据，哭吧
10069 稍难 好像还是归并
10070
10071
10072 弱
10073 弱
10074 DP 加f[1],f[2],f[3]
10075
10076
10077
10078
10079
10080 一般 大数加法
10081 简单 推出一个超越方程 只好二分了 其实应该归到数值算法
10082 简单 贪心，不过有公式可推 数学题
10083
10084
10085
10086
10087
10088
10089 一般 DP 定义一个maxa[251][251]的数组 query 只需要O（N*K）的时间复杂度
10090
10091 一般 排序以后暴搜4种可能组合
10092
10093 极其恶心的题目 居然抛随机种子
10094
10095 暴搜 我在讨论版里有解题报告
10096
10097 简单题 一个qsort，写的暴痛苦
10098 纯代码量题 排序然后扫完9种情况
10099 推公式
10100
10101 烂题
10102 DP 二维的最大加和子段
10103
10104
10105
10106 一般 用匹配和离散化都可以把区间扫出来
10107 一般 DP
10108
10109 floodfill 种子染色法
10110
10111
10112 不是太复杂的模拟 不过不好想
10113
10114 编译原理 表达式的计算
10115 一般 7进制
10116
10117
10118
10119
10120
10121
10122 贪心暴搜 我在讨论版有解题报告
10123
10124
10125 简单的贪心
10126
10127 DP
10128
10129
10130
10131
10132
10133
10134
10135 简单
10136 简单
10137 一般 并查集
10138 简单的排序
10139
10140
10141 简单 strtok函数的使用
10142 简单 前缀表达式的计算
10143 简单 模拟位操作
10144 简单 9进制加法
10145 一般 赤裸裸的背包
10146 高精度乘法
10147
10148 一般 空间换时间找素数
10149 简单 暴搜和位操作
10150 高精度乘法
10151 简单
10152
10153
10154 简单 高精度乘法
10155 贪心+回溯
10156 稍难吧 找重复单词 DP和二叉查找树都可以 不过推荐后者
10157
10158 简单 暴力题
10159 简单 表达式计算
10160 弱
10161
10162 讨厌的模拟
10163 简单 看讨论版解题报告
10164
10165
10166
10167 简单 搜索
10168
10169
10170
10171
10172
10173 弱
10174 简单 开个素数表方便些
10175
10176 简单 表达式计算
10177
10178 弱
10179 做了n遍了 以前做过就归为简单
10180
10181
10182 简单 两个数组匹配
10183
10184 简单 用__int64
10185 简单 推出等差公式暴搜
10186
10187
10188 稍难 模拟一个队列
10189 弱
10190 简单 模拟
10191
10192 简单 DP O(Nlog(N))和暴搜O(N^2))都可以出来
10193
10194
10195
10196
10197
10198
10199
10200
10201 一般 英文转数字 模拟题
10202
10203
10204 简单
10205
10206
10207
10208
10209
10210
10211 简单
10212 简单 暴搜过
10213
10214
10215 简单 排序 然后搜索
10216 弱 排序
10217
10218
10219
10220
10221
10222 一般 高精度乘法
10223
10224 一般 状态机
10225 简单 01状态转换
10226
10227
10228
10229
10230
10231
10232
10233 这题数据太弱了 让你们都过了
10234 简单 暴搜
10235
10236
10237
10238 简单 找规律 注意精度 真不行__int64
10239
10240 简单 注意汉字编码方式
10241 一般 表达式编译
10242 一般 表达式编译
10243 一般 KMP匹配
10244
10245 一般 队列的模拟
10246 一般 暴搜
10247
10248
10249
10250
10251
10252
10253
10254 一般 最长递增子序列
10255
10256
10257
10258
10259
10260
10261
10262 简单 压栈模拟
10263
10264
10265
10266
10267
10268
10269
10270
10271
10272
10273
10274
10275
10276
10277
10278

re ACM200408103252006-03-21 11:20:41.0
感谢，这样好找自己需要针对的题进行练习
也拉点人气，最后一页补几个 xnby2006-03-21 13:32:24.0

10252 一般 搜索＋剪枝
10272 一般 看懂题就可以模拟了
10275 简单 暴力
10277 一般 二分图匹配（男女匹配）
10278 一般 模拟找规律题
这么庞大的工作，一定很辛苦呢。 ACM200407105092006-03-21 13:42:23.0

补充一点 yiyiyi43212006-03-21 22:55:27.0
10021 二分图匹配
10024 动态规划
10025 递推+欧拉公式
10032 (状态压缩)动态规划
10033搜索
10043 动态规划
10055 贪心
10056 并查集判连通+欧拉回路(字典的处理有很多办法)
10111 二分图匹配
10152 暴搜可以过
10183 DFS+剪枝

赞 我也来顶下 huicpc3022008-04-12 18:34:47.0
11075 动态规划
11079 二分 Dijstra
11099 数论 欧拉定理 扩展欧几里德
11102 排序
11103 数论
11104 动态规划 组合数学
11107 线段树
11111 数学 找规律
11112 数学 找规律
11113 数学 DP
11114 母函数 DP
11115 组合数学 递推公式
11117 博弈 nim游戏
11118 计算几何
11119 概率公式
11120 扩展欧几里德
接着顶 huicpc3022008-04-12 18:50:26.0
10496 组合数学 置换群
10508 搜索
10696 线段树
10738 数学 找规律
10798 搜索
10808 拓扑排序
10830 搜索 BFS
10843 拓扑排序
10861 二分
10867 组合数学 置换群
10939 搜索
10953 模拟
10958 图论
11042 建图 搜索
11048 数学
狂顶!! reach2008-04-13 10:30:55.0
几位大侠造福人间啊
我也加上一些简单的 huicpc392008-04-13 12:19:44.0
10961 一般 麻烦的模拟
10963 有点难度 可以作为计通院程序设计的研究生能力题
10965 简单看懂题即可
10969 简单超递增数列
10974 有点难度 找规律，可以直接生成答案，可以看我的解题报告
10976 简单 倒推，打表都可
10986 中等 但数据很弱，暴力能过
10987 简单 数学公式推导
10990 简单 阅读理解题
11009 一般 找规律
11023 简单 进制
11090 简单 进制
11098 简单 二叉树遍历
11105 一般 计算几何
11106 一般 概率
11109 简单 二叉树遍历
11100 一般 卡特兰数和大数运算

再补充一些 huicpc392009-03-24 09:00:42.0
10018 中等 数学公式推导，马尔科夫链，注意n〉800就收敛到稳定
10020 中等 优先队列广搜
10021 中等 最小覆盖
10024 中等 数据较弱，贪心加暴力可过
10025 较难 数论，可以看解题报告
10029 一般 推导公式
10042 简单 取模运算
10043 较难 网络流或回溯，数据较弱
10044 唬人题 不难，阅读理解，二进制或分治
10046 中等 非线性方程数值解法（二分即可）
10055 一般 贪心或DP

flymanma

很多OJ上的题型分类！练习的时候很有针对性！

0lily

[s:330][s:330][s:330][s:330][s:330][s:330][s:330]

0lily

我这智商看不懂。