博文

续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;
                }
            }
        }
&n......

阅读全文(3602) | 评论:0 | 复制链接

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++)
          &n......

阅读全文(3704) | 评论:0 | 复制链接

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
        &nbs......

阅读全文(3858) | 评论:0 | 复制链接

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;
   &......

阅读全文(3602) | 评论:0 | 复制链接

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]++;
           a......

阅读全文(3416) | 评论:0 | 复制链接

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(*) 165......

阅读全文(4393) | 评论:1 | 复制链接

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,

......

阅读全文(4137) | 评论:0 | 复制链接

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
2......

阅读全文(3714) | 评论:0 | 复制链接

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

......

阅读全文(3643) | 评论:0 | 复制链接

pku题目类型划分(5)(2005-09-08 04:28:00)

摘要:

归类:
分类原则:以算法核心指向为主
算法
题目
枚举
1012 1046 1387 1411 2245 2326 2363 2381
搜索、回溯、遍历
1010 1011 1022 1054 1111 1118 1129 1190 1562 1564 1573 1655 2078 2184 2225 2243 2312 2362 2378 2386
动态规划
1015 1018 1050 1088 1159 1163 1221 1322 1458 1579 1651 1664 1742 1745 1953 2033 2084 2229 2385 2392 2393
图论(不含图遍历)
1125 1128 1130 2320 2387 2394 2395
贪心
1017 1328 1862 1922 2054 2209 2313 2325 2370
计算几何
1648 1654 1927 2007 2098 2208 2242 2276 2318
数论
1061 1320 1597 1808 1811 1845
其他数学、历法
1005 1006 1008 1032 1067 1152 1183 1209 1401 1423 1491 1517 1528 1543 1707 1799 1844 1905 1914 1942 2080 2126 2140 2190 2210 2234 2249 2299 2321 2348 2354 2365
任意精度运算、数字游戏
1001 1023 1047 1060 1079 1131 1140 1142 1207 1220 1284 1289 1306 1316 1338 1405 1454 1503 1504 1519 1565 1650 1969 2000 2006 2081 2247 2262 2305 2316 2389
基础算法、数据结构
1002 1007 1028 1281 1308 2092 2104 2106 2340 2352 2366 2371
字符串处理
1016 10......

阅读全文(4184) | 评论:0 | 复制链接