博文
ACM题目分类总结(2005-09-21 02:05:00)
摘要：ACM-题型分类的代码
主流算法：
Ø 1.搜索 //回溯
Ø 2.DP（动态规划）
Ø 3.贪心
Ø 4.图论 //Dijkstra、最小生成树、网络流
Ø 5.数论 //解模线性方程
Ø 6.计算几何 //凸壳、同等安置矩形的并的面积与周长
Ø 7.组合数学 //Polya定理
Ø 8.模拟
Ø 9.数据结构 //并查集、堆
Ø 10.博弈论
1、 排序
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,
1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树......
续pku（2567）（1）(2005-09-08 04:57:00)
摘要： //求出孩子节点
for(j=1;j<=len;j++)
{
for(i=1; i<=len; i++)
{
if(nd[i].parent!=0 && nd[i].parent == j)
{
nd[j].child[i] = i;
}
}
}
&nbs......
pku(2567)(1)(2005-09-08 04:56:00)
摘要：#include <iostream>
#include <stack>
using namespace std;
struct node
{
int parent;
int child[51];
int du;
}nd[51];
void doRun()
{
int i,j,k,len,temp,root;
char s[256],b[2];
stack<int> sp;
int p[51];
while(gets(s)!=NULL)
{
for(i=0;i<51;i++)
{
nd[i].du = 1;
nd[i].parent = 0;
for(j=0;j<51;j++)
nd[i].child[j] = 0;
&n......
pku(1767)(pascal)(2005-09-08 04:50:00)
摘要：Var
n:longint;
a:array[1..30]of integer;
k,i,j,s:integer;
Procedure print;
var
n1:longint;
i:integer;
begin
n1:=0;
for i:=k to 30 do
n1:=n1*2+a[i];
writeln(n1);
halt;
end;
Begin
readln(n);
k:=31;
while n>0 do
begin
dec(k);
a[k]:=n mod 2;
n:=n div 2;
end;
for i:=30 downto k+1 do
if (a[i]=1)and(a[i-1]=0) then
begin
a[i]:=0;
a[i-1]:=1;
&n......
pku（1767）(2005-09-08 04:49:00)
摘要：#include <iostream>
#include <string>
#include <stack>
using namespace std;
long NextTreeIdentify(string t)
{
string s,t2,t001("001");
s = t;
long res;
int node,i,posof0,posof001;
bool end = true;
for(i=0;i<=s.size()-3;i++)
{
t2 = s.substr(i,3);
if(t2.compare(t001)==0)
{
posof001 = i;
break;
}
}
end = true;
for(i=posof001+3;i<s.size();i++)
{
&nb......
pku（2567）（2）(2005-09-08 04:49:00)
摘要：#include <cstdio>
#include <memory.h>
#include <cctype>
#define MAXN 100
int degree[MAXN];
bool adj[MAXN][MAXN];
int n;
int ni;
char line[1000];
void make(int root,int &k)
{
if (root>n) n=root;
while (line[k]=='(')
{
int now;
k++;
sscanf(line+k,"%d",&now);
while (isdigit(line[k])) k++;
degree[root]++;
degree[now]++;
adj[root][now]=adj[now][root]=true;
......
pku题目类型划分（9）(2005-09-08 04:41:00)
摘要：Instruction：
加*的题目再note：部分有注释。
For freshman:
1001 1002 1007 1008 1012 1016 1068 1163 1218(*)
1281 1316 1326 1411 1552 1647 1650 1658 1659 1663
1666 1928 1936 2013 2014 2017 2080 2083 2105 2136
2141 2163 2242 2244 2328 2386 2403 2405 2413 2419
A little skill needed:
1013 1026 1029(similar to 1013) 1147 1152 1405 1649 1657 1922
2081 2085 2140 2159 2247 2309 2402
Math problem:
1006 1061 1095 1183 1700(*) 1844 1862 2084(*) 2232 2234(*)
Search:
1011(*) 1129 2078(*) 2362(similar to 1011)
Graph:
1062 1094 1125 1128 1130 1655 1661 1674(*) 1909 2049 2195(*) 2395(*)
2421
DP problems:
1029 1050 1080 1088 1651 1664 1742(*) 2181 2192 2392(similar to 1742)
2397 2411(*)
Greedy:
1017(*) 1065 1083(*) 1089 1323 1328 1505(*) 1828 2082(*) 2393
Data Structure :
1988(*) 2051(*) 2182(*) 2236(*) 2424
Others:
1150(*) 1654(*) 1833 1835 2299(*) 2406(*) 2407
A bit complicated:
1021(*) 1054 1863(*) 2015
Great Challenging
1014(*)
Note:
1011: 很经典的剪支
1014: 难在数学上
1017: 严格的数学证明貌似不容易
1021: 有点繁,......
pku题目类型划分（8）(2005-09-08 04:34:00)
摘要：说明：递推算动归， 离散化算数据结构， 并查集算数据结构， 博弈算动归， 麻烦题一般都是不错的综合题， 最短路算图论，数据的有序化算排序
麻烦题：
1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237,
简单题目：
1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419,
推荐：
1063, 1064, 1131, 1140, 1715, 2163,
杂题：
1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407,
推荐：
1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420,
高精度：
1001, 1220, 1405, 1503,
排序：
1002, 1318, 1877, 1928, ......
pku题目类型划分（7）(2005-09-08 04:31:00)
摘要：主流算法：
1.搜索 //回溯
2.DP（动态规划）
3.贪心
4.图论 //Dijkstra、最小生成树、网络流
5.数论 //解模线性方程
6.计算几何 //凸壳、同等安置矩形的并的面积与周长
7.组合数学 //Polya定理
8.模拟
9.数据结构 //并查集、堆
10.博弈论
//表示举例
非主流算法：
1.送分题
2.构造
3.高精度
4.几何
5.排序
6.日期/时间处理 （这类题目相当多的）
7.数学方法
8.枚举
9.递推
10.递归
11.分治
说明：
显然“送分题”不是一种算法。但是ACM竞赛中经常有一些很简单很简单的题目，具体涉及内容繁杂，难以归类，干脆就管他们叫送分题。
几何不同于计算几何，计算几何或者叫S计算几何，以Shamos在1975年发表的一篇论文为诞生标志。其实两者有很大的不同。
部分题目分类统计：
网络流：
最大流：
1087 a plug for UNIX
1149 PIGS
1273 drainage ditches
1274 the perfect stall
1325 machine schedule
1459 power network
2239 selecting courses
最小费用最大流：
2195 going home
?2400 supervisor, supervisee
压缩存储的DP
1038 bugs integrated inc
1185 炮兵阵地
2430 lazy cow
最长公共子串（LCS）：
1080 human gene functions
1159 palindrome
1458 common subsequence
2192 zipper
凸包
1113 wall
2187 beauty contest
......
pku题目类型划分（6）(2005-09-08 04:29:00)
摘要：一、按类型
基础题:
1000,1003,1004,1005，2013，2017
模拟题:
1281 1922 1928
2080 （细心）
排序分治:
1002
动态规划:
1037（大规模）
2084 （做高精度）
贪心:
2054
数论:
1001 整数运算（作高精度）
1014 集合划分，与分治
1147 1163 2081 2085数列问题
几何有关的题目：
1054 解析几何+搜索
2014
2016计算几何
2082集合的合并，运算（几何角度）
2083 分形（纯数学）
图：
1125
利用题目所给信息来推演：
2015
二、按难易
简单题
最基础的适应POJ的习题：1000 1003 1004 1005 2013 2017
需要根据情景稍微动下脑筋的习题：1922
需要对语言有很深刻的了解，锻炼基本功的：1002 1281 2014 2081
要求初步熟练算法的习题：1928
中档题：
锻炼细心考虑问题全面的习题：1001 2015 2080
要求熟练算法的习题：1054 1163 2084
难题：
对数学要求很高的题目：2083 2085
对算法要求很高的题目：1125 2054
对综合能力要求很高的题目：1037 2016 2082
技巧性高的题目：1147
锻炼英文读题的题目：2015 2082
三、需要有很强的判断力的题目：
判断高精度： 2084
判断耗时：1002
判断变量类型：1001
要求会寻找题目以外的信息：2080
......