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
1221 Risk
1230 Legendary Pokemon
1249 Pushing Boxes
1364 Machine Schedule
1368 BOAT

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
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 亦夏 阅读(348) | 评论 (0)编辑 收藏
2009年4月27日
摘要: /** Stack(use array to implement) Version: 2.0  Member function as follow:  Size()  Push(T)        // inset an elm  ...  阅读全文
posted @ 2009-04-27 16:33 亦夏 阅读(229) | 评论 (0)编辑 收藏
2009年4月19日

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 = 0break; }
}

if(temp) {
token
+= temp;
word
++;
}

}

if(!word) return 250;

if(token / word <= 3return 250;

if(token / word <= 5return 500;

return 1000;
}

}
;

1#include <string>
2using namespace std;
3class HowEasy
4{
5public:  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 亦夏 阅读(417) | 评论 (0)编辑 收藏
2009年4月16日
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>
3using namespace std;
4// Global variables
5char maze[9][9];
6int x, y , n, desx, desy,temp; // x is row y is cow n is steps
7bool escape; //run or not
8int d[4][2= {{01},{0-1},{10},{-10}}// stand for four directions
9
10void 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 & 1return;
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
32int main() {
33    int stax, stay;
34    while(cin >> x >> y >> n  && x + y + n) {
35        escape = falseint 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 亦夏 阅读(893) | 评论 (0)编辑 收藏
2009年3月24日
摘要:  1/**//** 2        Binary Search Tree 3        Version: 1.0 4    ...  阅读全文
posted @ 2009-03-24 00:13 亦夏 阅读(206) | 评论 (0)编辑 收藏
2009年3月20日
摘要:     1/**//**  2        Queue (Liked structure)  3        Version: 1.0...  阅读全文
posted @ 2009-03-20 02:33 亦夏 阅读(416) | 评论 (0)编辑 收藏
摘要:  1/**//** 2        Queue 3        Version: 1.0 4        ...  阅读全文
posted @ 2009-03-20 02:18 亦夏 阅读(213) | 评论 (0)编辑 收藏
2009年3月18日
摘要:  1/**//** 2        Stack(use linked structure to implement) 3        Version: 1....  阅读全文
posted @ 2009-03-18 22:46 亦夏 阅读(224) | 评论 (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
17using namespace std;
18#ifndef SQSTACK_H
19#define SQSTACK_H
20
21template<typename T>
22class sqStack
23{
24public:
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);};
32private:
33    static const int MaxSize = 200;
34    T elem[MaxSize];
35    int top;
36}
;
37
38template<typename T> void sqStack<T>::Push(const T& one)
39{
40    assert(top <= MaxSize - 1);
41    top++;
42    elem[top] = one;
43}

44
45template<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
2int 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    forint 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 functionYes or No" << endl;
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 亦夏 阅读(227) | 评论 (0)编辑 收藏
2009年2月24日
摘要:   1/**//**  2        Loop List (just like LinkedList)  3        Versio...  阅读全文
posted @ 2009-02-24 23:16 亦夏 阅读(215) | 评论 (0)编辑 收藏