Standing on Shoulders of Giants

URAL 1030 Titanic

摘要: 以地球球心为坐标原点，建立三维坐标系，求出两点坐标，计算直线距离，求出夹角，再乘以半径。阅读全文

posted @ 2008-11-04 16:05 Joseph 阅读(232) | 评论 (0) | 编辑收藏

URAL 1029 Ministry

摘要: DP,对每一层扫描两遍阅读全文

posted @ 2008-11-04 14:33 Joseph 阅读(173) | 评论 (0) | 编辑收藏

URAL 1024 Permutations

摘要: 找出所有的循环，计算循环长度的最小公倍数阅读全文

posted @ 2008-11-04 11:23 Joseph 阅读(318) | 评论 (2) | 编辑收藏

URAL 1022 Genealogical tree

http://acm.timus.ru/problem.aspx?space=1&num=1022
拓扑排序

1 #include <iostream>
2 using namespace std;
3 int n;
4 int link[111][111];
5 int ru[111];
6 int q[111],st,en;
7 bool v[111];
8 int fn,flist[111];
9 bool first=true;
10
11 void del(int x){
12     for (int i=1;i<=link[x][0];++i){
13         --ru[link[x][i]];
14         }
15     }
16
17 void ou(int x){
18     del(x);
19     if (first){
20         printf("%d",x);
21         first=false;
22         }
23     else printf(" %d",x);
24     }
25
26 void find(){
27     fn=0;
28     for (int i=1;i<=n;++i) if (!v[i]&&ru[i]==0){
29         v[i]=true;
30         flist[++fn]=i;
31         }
32     }
33
34 int main(){
35     scanf("%d",&n);
36     for (int i=1;i<=n;++i){
37         int x;
38         scanf("%d",&x);
39         while (x!=0){
40             link[i][++link[i][0]]=x;
41             ++ru[x];
42             scanf("%d",&x);
43             }
44         }
45     find();
46     while (fn>0){
47         for (int i=1;i<=fn;++i) ou(flist[i]);
48         find();
49         }
50     }
51

posted @ 2008-11-04 10:25 Joseph 阅读(116) | 评论 (0) | 编辑收藏

URAL 1004 Sightseeing trip

http://acm.timus.ru/problem.aspx?space=1&num=1004
计算最小非负环

1 #include <iostream>
2 using namespace std;
3 const int OO=10000000;
4 int n,m;
5 int map[111][111];
6 int d[111];
7 int pre[111];
8 int ans,alist[111],an;
9 bool v[111];
10
11 int findmin(){
12     int mm=OO,re=0;
13     for (int i=1;i<=n;++i) if (d[i]<mm&&!v[i]){
14         mm=d[i];
15         re=i;
16         }
17     return re;
18     }
19
20 void dij(int a,int b){
21     for (int k=1;k<n;++k){
22         int f=findmin();
23         if (f==0) break;
24         v[f]=true;
25         for (int i=1;i<=n;++i) if (d[f]+map[f][i]<d[i]){
26             d[i]=map[f][i]+d[f];
27             pre[i]=f;
28             }
29         }
30     }
31
32 void work(int a,int b){
33     int dis=map[a][b];
34     map[a][b]=map[b][a]=OO;
35     for (int i=1;i<=n;++i) d[i]=OO;
36     for (int i=1;i<=n;++i) v[i]=0;
37     for (int i=1;i<=n;++i) pre[i]=0;
38     d[a]=0;
39     dij(a,b);
40     if (d[b]+dis<ans){
41         ans=d[b]+dis;
42         int x=b;
43         an=0;
44         while (x!=0){
45             alist[++an]=x;
46             x=pre[x];
47             }
48         }
49     map[a][b]=map[b][a]=dis;
50     }
51
52 int main(){
53     scanf("%d",&n);
54     while (n!=-1){
55         for (int i=1;i<=n;++i)
56             for (int j=1;j<=n;++j) map[i][j]=OO;
57         scanf("%d",&m);
58         for (int i=1;i<=m;++i){
59             int a,b,c;
60             scanf("%d %d %d",&a,&b,&c);
61             if (c<map[a][b]) map[a][b]=map[b][a]=c;
62             }
63         ans=OO;
64         an=0;
65         for (int i=1;i<n;++i)
66             for (int j=i+1;j<=n;++j) if (map[i][j]<OO) work(i,j);
67         if (an==0) printf("No solution.\n");
68         else{
69             printf("%d",alist[an]);
70             for (int i=an-1;i>0;--i) printf(" %d",alist[i]);
71             cout<<endl;
72             }
73         scanf("%d",&n);
74         }
75     }
76

posted @ 2008-11-04 09:48 Joseph 阅读(255) | 评论 (0) | 编辑收藏

URAL 1018 A Binary Apple Tree

http://acm.timus.ru/problem.aspx?space=1&num=1018
树型DP

1 #include <iostream>
2 using namespace std;
3 const int OO=20000000;
4 int n,m;
5 int q[111];
6 int apple[111];
7 int link[111][2];
8 int son[111];
9 int applesum[111];
10 int dp[111][111],st,en;
11 bool v[111];
12 int map[111][111];
13 int sum;
14
15 void bfs(){
16     st=0; en=1;
17     q[1]=1;
18     v[1]=true;
19     while (st<en){
20         ++st;
21         int nx=q[st];
22         for (int i=1;i<=n;++i) if (!v[i]&&map[nx][i]){
23             ++en;
24             q[en]=i;
25             v[i]=true;
26             apple[i]=map[nx][i];
27             if (link[nx][0]){
28                 link[nx][1]=i;
29                 break;
30                 }
31             else link[nx][0]=i;
32             }
33         }
34     }
35
36 int max(int a,int b){
37     return a>b?a:b;
38     }
39
40 void calc(int x){
41     dp[x][son[x]]=max(dp[x][son[x]],applesum[x]);
42     dp[x][1]=apple[x];
43     int l=link[x][0],r=link[x][1];
44     for (int i=0;i<=m;++i)
45         for (int j=0;j<=m;++j){
46             dp[x][i+j+1]=max(dp[x][i+j+1],dp[l][i]+dp[r][j]+apple[x]);
47             }
48     }
49
50 int main(){
51     scanf("%d %d",&n,&m);
52     ++m;
53     for (int i=1;i<n;++i){
54         int a,b,c;
55         scanf("%d %d %d",&a,&b,&c);
56         map[a][b]=map[b][a]=c;
57         sum+=c;
58         }
59     bfs();
60     for (int i=n;i>0;--i){
61         son[q[i]]=son[link[q[i]][0]]+son[link[q[i]][1]]+1;
62         applesum[q[i]]=applesum[link[q[i]][0]]+applesum[link[q[i]][1]]+apple[q[i]];
63         }
64     for (int i=n;i>0;--i) calc(q[i]);
65     cout<<dp[1][m];
66     }
67

posted @ 2008-11-04 09:36 Joseph 阅读(162) | 评论 (0) | 编辑收藏

pku题目分类

麻烦题：
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, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 2388, 2418,
推荐：
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,

搜索
容易：
1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,
不易：
1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349,
推荐：
1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,

数据结构
容易：
1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395,
不易：
1145, 1177, 1195, 1227, 1661, 1834,
推荐：
1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274,

动态规划
容易：
1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2033, 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424,
不易：
1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737, 1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178,
推荐：
1015, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411,

字符串：
1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 1951, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408,

贪心：
1042, 1065, 1230, 1323, 1477, 1716, 1784,

图论
容易：
1161, 1164, 1258, 1175, 1308, 1364, 1776, 1789, 1861, 1939, 1940, 1943, 2075, 2139, 2387, 2394, 2421,
不易：
1041, 1062, 1158, 1172, 1201, 1275, 1718, 1734, 1751, 1904, 1932, 2173, 2175, 2296,
网络流：
1087, 1273, 1698, 1815, 2195,
匹配：
1274, 1422, 1469, 1719, 2060, 2239,
Euler：
1237, 1637, 1394, 2230,
推荐：
2049, 2186,

计算几何
容易：
1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318,
不易：
1685, 1687, 1696, 1873, 1901, 2172, 2333,
凸包：
1113, 1228, 1794, 2007, 2187,

模拟
容易：
1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390,
不易：
1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,

数学
容易：
1061, 1091, 1142, 1289, 1305, 1306, 1320, 1565, 1665, 1666, 1730, 1894, 1914, 2006, 2042, 2142, 2158, 2174, 2262, 2305, 2321, 2348,
不易：
1067, 1183, 1430, 1759, 1868, 1942, 2167, 2171, 2327,
推荐：
1423, 1450, 1640, 1702, 1710, 1721, 1761, 1830, 1930, 2140,

posted @ 2008-06-20 17:50 Joseph 阅读(1084) | 评论 (0) | 编辑收藏

pku 1019

不需要使用字符串，用数学方法计算就可以了。

#include <iostream>

#include <math.h>

using namespace std;

int main(){

int test;

scanf("%d",&test);

for (;test>0;--test) {

unsigned long int n;

scanf("%d",&n);

unsigned long int now(0),i(0),last(0),m;

while (now<n) now+=last+=(int)log10(++i)+1;

now-=last;

n-=now;

now=0;

i=0;

while (now<n) now+=(int)log10(++i)+1;

now-=(int)log10(i)+1;

n-=now;

int j=(int)log10(i)+2;

j=j-n;

for (int k=1;k<j;++k) i/=10;

printf("%d\n",i%10);

}

posted @ 2008-04-13 11:14 Joseph 阅读(316) | 评论 (0) | 编辑收藏

关于floyd求多源最短路循环顺序

根据floyd算法，三重循环即可求出有向图中每一对顶点间的最短距离。

……
2

for (int k=1;k<=n;++k)
3

for (int i=1;i<=n;++i)
4

for (int j=1;j<=n;++j)
5

if (dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
6

……

但是，中间节点k一定要处在最外层循环。
考虑 dis[i][j]>dis[i][k]+dis[k][j] 的情况。如果继续循环，dis[i][k]与dis[k][j]的距离都有可能被更新。如果 i、j 是外层循环，dis[i][j]将不再被更新。这样便不能保证dis[i][j]的最优解。

posted @ 2008-04-11 21:42 Joseph 阅读(379) | 评论 (0) | 编辑收藏

pku 1161

预处理麻烦一些的floyd。
值得注意的是 floyd 循环的顺序千万不能搞错。

#include <iostream>
2

using namespace std;
3

const int OO(1000000);
4

int m,n,mem,mlist[31],dis[201][201],ans[201];
5

bool map[201][251][251];
6

bool con[251][201];
7

int main(){
8

cin>>m;
9

cin>>n;
10

cin>>mem;
11

for (int i=1;i<=m;++i)
13

for (int j=1;j<=m;++j) dis[i][j]=OO;
14

for (int i=1;i<=m;++i) dis[i][i]=0;
15

for (int i=1;i<=mem;++i) scanf("%d",&mlist[i]);
17

for (int i=1;i<=m;++i) {
18

int num,list[251];
19

scanf("%d",&num);
20

for (int j=1;j<=num;++j) {
21

scanf("%d",&list[j]);
22

con[list[j]][i]=true;
23

if (j>1) {
24

map[i][list[j]][list[j-1]]=true;
25

map[i][list[j-1]][list[j]]=true;
26

for (int k=1;k<i;++k) if (map[k][list[j]][list[j-1]]) {
27

dis[i][k]=1;
28

dis[k][i]=1;
29

}
30

}
31

}
32

map[i][list[1]][list[num]]=true;
33

map[i][list[num]][list[1]]=true;
34

for (int j=1;j<i;++j) if (map[j][list[1]][list[num]]) {
35

dis[i][j]=1;
36

dis[j][i]=1;
37

}
38

}
39

for (int k=1;k<=m;++k)
41

for (int i=1;i<=m;++i)
42

for (int j=1;j<=m;++j) if (dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
43

for (int i=1;i<=mem;++i)
45

for (int j=1;j<=m;++j) {
46

int min=OO;
47

for (int k=1;k<=m;++k) if ((con[mlist[i]][k])&&(dis[k][j]<min)) min=dis[k][j];
48

ans[j]+=min;
49

}
50

int min=OO;
51

for (int i=1;i<=m;++i) if (ans[i]<min) min=ans[i];
52

cout<<min<<endl;
53

}
54

posted @ 2008-04-11 21:33 Joseph 阅读(177) | 评论 (0) | 编辑收藏

仅列出标题

常用链接

留言簿(3)

随笔档案

文章档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜