My road to c++ - C++博客

2009年5月5日

ZOJ
Plan to do:
Problem: Link: Status: Summary:
1002 Fire Net
1004 Anagrams by Stack
1005 Jugs
1008 Gnome Tetravex
1091 Knight Moves
1101 Gamblers
1204 Additive equations
1221 Risk
1230 Legendary Pokemon
1249 Pushing Boxes
1364 Machine Schedule
1368 BOAT
1406 Jungle Roads

1411 Anniversary
1453 Surround the Trees
1516 Uncle Tom's Inherited Land
1525 Air Raid
1586 QS Network
1602 Multiplication Puzzle dp
1649 Rescue
1671 Walking Ant

1711 Sum It Up
1901 A Star not a Tree?
1940 Dungeon Master
2100 Seeding
2110 Tempter of the Bone
2140 Ball
（27道）上面的题可能比较简单，练练基本算法

难题&经典

1003 Crashing Balloon
1015 Fishing Net 完美图
1144 Robbery
1149 Dividing up
1161 Gone Fishing
1197 Sorting Slides
1217 Eight
1228 Farewell, My Friend
1237 Fans and Gems
1455 Schedule Problem
1456 Minimum Transport Cost 图论最短路径要保存路径
1492 Maximum Clique 图论经典算法--最大团
1600 Market Place
1605 One-way Traffic
1568 WishingBone's Room Plan
1742 Gap
1743 Concert Hall Scheduling
1827 The Game of 31 博弈
1855 Maze
1903 Jogging Trails 中国邮路问题
1909 Square 经典的dfs.
2064 Bomberman - Just Search! 经典！
2094 Max Angle 计算几何+博弈
2125 Rocket Mania
2126 Rocket Mania Plus
2127 Zuma
2128 Seven Seas
2129 Mummy Maze
2142 Light The Square （24道）
===========================================
dp
50道dp的题

1499 Increasing Sequences 经典题{}
1107 FatMouse and Cheese 很好的一题
1039 Number Game 没有完美解决的题，感觉可以直接以所有剩下的数作为状态DP，但是缺乏明……
1227 Free Candies SRbGa的经典题
1234 Chopsticks SRbGa的经典题……
1554 Folding 推荐
2059 The Twin Towers 推荐
2097 Walking on a Chessboard 推荐
1011 NTA 可用dp，也可以不用
1013 Great Equipment
1024 Calendar Game
1027 Human Gene Functions
1037 Gridland
1052 Algernon's Noxious Emissions
1058 Currency Exchange
1076 Gene Assembly
1092 Arbitrage
1093 Monkey and Banana
1094 Matrix Chain Multiplication
1100 Mondriaan's Dream DP可以过，不过有组合公式
1103 Hike on a Graph
1134 Strategic Game
1147 Formatting Text
1148 The Game
1161 Gone Fishing
1180 Self Numbers
1192 It's not a Bug, It's a Feature!
1196 Fast Food
1136 Multiple ，BFS
1276 Optimal Array Multiplication Sequence
1255 The Path
1250 Always On the Run
1213 Lumber Cutting
1206 Win the Bonus
1301 The New Villa
1303 Jury Compromise 其实不是很难，但是很容易错
1345 Best Deal
1360 Radar Installation
1396 The Umbrella Problem: 2054
1425 Crossed Matchings
1438 Asteroids!
1459 String Distance and Transform Process
1462 Team Them Up!
1556 Heroes Of Might And Magic
1520 Duty Free Shop
1524 Supermarket
1536 Labyrinth
1479 Dweep
1245 Triangles 可用dp也可搜索

posted @ 2009-05-05 23:40 亦夏阅读(399) | 评论 (0) | 编辑收藏

2009年4月27日

栈的实现（顺序结构）Alpha 2.0

摘要: /** Stack(use array to implement) Version: 2.0 Member function as follow: Size() Push(T) // inset an elm ... 阅读全文

posted @ 2009-04-27 16:33 亦夏阅读(245) | 评论 (0) | 编辑收藏

2009年4月19日

HowEasy

Problem Statement

***Note:  Please keep programs under 7000 characters in length.  Thank you
            Class Name: HowEasy
            Method Name: pointVal
            Parameters: String
            Returns: int
            TopCoder has decided to automate the process of assigning problem difficulty
            levels to problems.  TopCoder developers have concluded that problem difficulty
            is related only to the Average Word Length of Words in the problem statement:
            If the Average Word Length is less than or equal to 3,  the problem is a 250
            point problem.
            If the Average Word Length is equal to 4 or 5, the problem is a 500 point
            problem.
            If the Average Word Length is greater than or equal to 6, the problem is a 1000
            point problem.
            Definitions:
            Token - a set of characters bound on either side by spaces, the beginning of
            the input String parameter or the end of the input String parameter.
            Word - a Token that contains only letters (a-z or A-Z) and may end with a
            single period. A Word must have at least one letter.
            Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)
            The following are Words :
            "ab",  "ab."
            The following are not Words :
            "ab..", "a.b", ".ab", "a.b.", "a2b.", "."
            Average Word Length - the sum of the Word Lengths of every Word in the problem
            statement divided by the number of Words in the problem statement.  The
            division is integer division. If the number of Words is 0, the Average Word
            Length is 0.
            Implement a class HowEasy, which contains a method pointVal.  The method takes
            a String as a parameter that is the problem statement and returns an int that
            is the point value of the problem (250, 500, or 1000). The problem statement
            should be processed from left to right.
            Here is the method signature (be sure your method is public):
            int pointVal(String problemStatement);
            problemStatement is a String containing between 1 and 50 letters, numbers,
            spaces, or periods.  TopCoder will ensure the input is valid.
            Examples:
            If problemStatement="This is a problem statement", the Average Word Length is
            23/5=4, so the method should return 500.
            If problemStatement="523hi.", there are no Words, so the Average Word Length is
            0, and the method should return 250.
            If problemStatement="Implement a class H5 which contains some method." the
            Average Word Length is 38/7=5 and the method should return 500.
            If problemStatement=" no9 . wor7ds he8re. hj.." the Average Word Length is 0,
            and the method should return 250.

Definition

Class:	HowEasy
Method:	pointVal
Parameters:	string
Returns:	int
Method signature:	int pointVal(string param0)
(be sure your method is public)

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Class:

HowEasy

Method:

pointVal

Parameters:

string

Returns:

int

Method signature:

int pointVal(string param0)

(be sure your method is public)

Accept: 79.60

#include<string>

#include<cctype>

#include<sstream>

using namespace std;

class HowEasy {

public:

int pointVal(string param0){

istringstream is(param0);

string str;

int word = 0, token = 0;

while(is >> str) {

int temp = 0;

if(str == ".") continue;

for(int i = 0; i < str.size(); i++) {

if(isalpha(str[i])) temp++;

else if(str[i] == '.' && str.size() - 1 == i)

break;

else { temp = 0; break; }

}

if(temp) {

token += temp;

word++;

}

if(!word) return 250;

if(token / word <= 3) return 250;

if(token / word <= 5) return 500;

return 1000;

}

};

比较受打击。才那么点分数，以后要加油啊。
贴一个249.97 的代码。

1

#include <string>
2

using namespace std;
3

class HowEasy
4

{
5

public: int pointVal(string param0)
6

{
7

int i=0,j=0,k=0,t=0,ac=0;
8

for(;param0[i-1]!=0;i++)
9

if(param0[i]==0||param0[i]==' ')
10

{
11

j++;
12

ac+=(t==0)*k;
13

t=k=0;
14

}
15

else if(t==0)
16

if(param0[i]>57)
17

k++;
18

else if(!(param0[i]=='.'&& param0[i+1]==0&&k>0)&&!(param0[i]=='.'&& param0[i+1]==' '&&k>0))
19

t=1;
20

if(j==0)
21

return(250);
22

if(ac/j<=3)
23

return(250);
24

if(ac/j<=5)
25

return(500);
26

return(1000);
27

}
28

};
29

posted @ 2009-04-19 20:37 亦夏阅读(435) | 评论 (0) | 编辑收藏

2009年4月16日

HDOJ_1010.Tempter of the Bone(DFS)

Problem:
From: http://acm.hdu.edu.cn/showproblem.php?pid=1010
Accept: 2009.4.14
@author fleap.
Tempter of the Bone

Problem Description

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.

The input is terminated with three 0's. This test case is not to be processed.

Output

For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.

Sample Input

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

Sample Output

NO
YES

1

// DFS
2

#include<iostream>
3

using namespace std;
4

// Global variables
5

char maze[9][9];
6

int x, y , n, desx, desy,temp; // x is row y is cow n is steps
7

bool escape; //run or not
8

int d[4][2] = {{0, 1},{0, -1},{1, 0},{-1, 0}}; // stand for four directions
9

10

void DFS(int stax, int stay, int step) {
11

if( stax > x || stay > y ||
12

stay <= 0 || stax <= 0 )
13

return;
14

if( stax == desx && stay == desy && step == n){
15

escape = true;
16

return;
17

}
18

if(escape) return;
19

// cut tree
20

temp = n - step - abs(stax - desx) - abs(stay - desy);
21

if(temp < 0 || temp & 1) return;
22

for(int i = 0; i < 4; i++) {
23

if(maze[stax + d[i][0]][stay + d[i][1]] != 'X'){
24

maze[stax + d[i][0]][stay + d[i][1]] = 'X';
25

DFS(stax + d[i][0], stay + d[i][1], step + 1);
26

maze[stax + d[i][0]][stay + d[i][1]] = '.'; // back
27

}
28

}
29

return;
30

}
31

32

int main() {
33

int stax, stay;
34

while(cin >> x >> y >> n && x + y + n) {
35

escape = false; int wall = 0;
36

for(int i = 1; i <= x; i++) {
37

for(int j = 1; j <= y; j++) {
38

cin >> maze[i][j];
39

if(maze[i][j] == 'S') {
40

stax = i;
41

stay = j;
42

}
43

if(maze[i][j] == 'D') {
44

desx = i;
45

desy = j;
46

}
47

if(maze[i][j] == 'X'){
48

wall++;
49

}
50

}
51

}
52

if( x * y - wall <= n ) {
53

cout << "NO\n";
54

continue;
55

}
56

maze[stax][stay] = 'X';
57

DFS(stax, stay, 0);
58

cout << ( escape ? "YES" : "NO" ) << endl;
59

}
60

return 0;
61

}

posted @ 2009-04-16 00:29 亦夏阅读(906) | 评论 (0) | 编辑收藏

2009年3月24日

二查查找树的实现(链式) Alpha1.0

摘要: 1/**//** 2 Binary Search Tree 3 Version: 1.0 4 ... 阅读全文

posted @ 2009-03-24 00:13 亦夏阅读(229) | 评论 (0) | 编辑收藏

2009年3月20日

队列的实现(链式结构) Alpha 1.0

摘要: 1/**//** 2 Queue (Liked structure) 3 Version: 1.0... 阅读全文

posted @ 2009-03-20 02:33 亦夏阅读(464) | 评论 (0) | 编辑收藏

队列的实现(数组结构) Alpha 1.0

摘要: 1/**//** 2 Queue 3 Version: 1.0 4 ... 阅读全文

posted @ 2009-03-20 02:18 亦夏阅读(224) | 评论 (0) | 编辑收藏

2009年3月18日

栈的实现（链式结构）Alpha 1.0

摘要: 1/**//** 2 Stack(use linked structure to implement) 3 Version: 1.... 阅读全文

posted @ 2009-03-18 22:46 亦夏阅读(235) | 评论 (0) | 编辑收藏

栈的实现（顺序结构）Alpha 1.0

1

/**
2

Stack(use array to implement)
3

Version: 1.0
4

Member function as follow:
5

size()
6

push(T) // inset an elm
7

pop() // delete the last elm
8

empty() // if it is an empty list
9

print()
10

11

Use C++ template
12

**/
13

#include<iostream>
14

#include<string>
15

16

17

using namespace std;
18

#ifndef SQSTACK_H
19

#define SQSTACK_H
20

21

template<typename T>
22

class sqStack
23

{
24

public:
25

sqStack():top(-1){}
26

~sqStack(){ top = -1; };
27

bool Empty()const { return top == -1; }
28

void Push(const T&);
29

void Pop(){ assert(top > -1); top--;};
30

void Print() const;
31

int Size() const { return (top + 1);};
32

private:
33

static const int MaxSize = 200;
34

T elem[MaxSize];
35

int top;
36

};
37

38

template<typename T> void sqStack<T>::Push(const T& one)
39

{
40

assert(top <= MaxSize - 1);
41

top++;
42

elem[top] = one;
43

}
44

45

template<typename T> void sqStack<T>::Print() const
46

{
47

for(int i = 0; i < top; i++ )
48

cout << elem[i] << " ";
49

cout << elem[top] << endl;
50

}
51

52

#endif

//Test Function

1

// Test Function
2

int main()
3

{
4

using namespace std;
5

sqStack<int> stack;
6

cout << "----------------Display the stack program-----------------------" << endl;
7

cout << "\n Initial the stack,please input the number of element to push stack "<< endl;
8

cout << "number = " ;
9

int number;
10

cin >> number;
11

cout << "Secondly input the number in the following\n" << endl;
12

int temp;
13

for( int i = 0; i < number; i++ )
14

{
15

cin >> temp;
16

stack.Push(temp);
17

}
18

cout << "You Input As Follow

" << endl;
19

stack.Print();
20

cout << "Would you like to display the pop function

Yes or No" << endl;
21

string answer;
22

cin >> answer;
23

if( answer == "yes" || answer == "YES" )
24

{
25

stack.Pop();
26

stack.Print();
27

}
28

cout <<"-----------------------------------------------------------------" << endl;
29

system("pause");
30

return 0;
31

32

}
33

posted @ 2009-03-18 22:44 亦夏阅读(237) | 评论 (0) | 编辑收藏

2009年2月24日

循环链表的实现（Alpha）

摘要: 1/**//** 2 Loop List (just like LinkedList) 3 Versio... 阅读全文

posted @ 2009-02-24 23:16 亦夏阅读(225) | 评论 (0) | 编辑收藏

Problem Statement

Definition

常用链接

留言簿(1)

随笔分类(13)

随笔档案(13)

文章分类(2)

文章档案(2)

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜