Sicily 1031 Campus 解题报告.

 

1 原题中文大意;
 
Sicily 1031 Campus实际上就是求一个图中给出两点的最短路径的问题。
 
2 算法思想及解题用到的主要数据结构;
 
用 dijkstra 算法求给定两点的最短路径.
 
按路径长度递增次序产生最短路径算法:   把V分成两组:   (1)S:已求出最短路径的顶点的集合   (2)V-S=T:尚未确定最短路径的顶点集合   将T中顶点按最短路径递增的次序加入到S中,   保证:(1)从源点V0到S中各顶点的最短路径长度都不大于   从V0到T中任何顶点的最短路径长度   (2)每个顶点对应一个距离值   S中顶点:从V0到此顶点的最短路径长度   T中顶点:从V0到此顶点的只包括S中顶点作中间   顶点的最短路径长度   依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的   直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和。
 
3  逐步求精算法描述
 
用邻接矩阵存放图.1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值   若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值   若不存在<V0,Vi>,d(V0,Vi)为∝   2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S   3. 对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的   距离值比不加W的路径要短,则修改此距离值   重复上述步骤2、3,直到S中包含所有顶点,即S=T为止
 
3 程序注释清单 // 这份代码通不过sicily。有case错误。我实在找不到原因。
 
#include <map>

#include <vector>

#include <string>

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cassert>



#define INFINITE 0x0FFFFFFF



// 这个类的函数几乎不做参数有效性的检查. 

class graph_t

{

public:

// 构建一个 num x num 的邻接矩阵

graph_t(int num)

{

m_matrix = new int[num*num];

m_sunit = new bool[num];

m_spath_table = new int[num];

// memset(m_matrix, INFINITE, num*num);  // INFINITE 表示无穷远. 

for ( int i = 0; i < num*num; i++ )

{

m_matrix[i] = INFINITE;

}

m_num = num;

}



// row,column 取 [0, m_num)

int& operator()(int row, int column)

{

return m_matrix[row * m_num + column];

}



// vtx_start, vtx_end 取 [vtx_start, vtx_end)

int shortestpath_dij(int vtx_start, int vtx_end)

{

init_dij(vtx_start);  // 初始化dijkstra算法需要的一些数据. 



if ( vtx_end == vtx_start )

{

return this->operator()(vtx_start, vtx_end);

}



// 还剩 m_num - 1 个点. 

for ( int i = 1; i < m_num; i++ )

{

// 找下一个最近的点. 

int vtx = -1, min = INFINITE;

for ( int j = 0; j < m_num; j++ )

{

if ( m_sunit[j] )  // 这个点已经在已经求得最短路径的点的集合中了. 

continue;



if ( m_spath_table[j] < min )

{

vtx = j;

min = m_spath_table[j];

}

}

// 已经没有连通的顶点了. 

if ( vtx == -1 )

{

return -1;

}

m_sunit[vtx] = true;  // 把这个点加入集合中. 



// 这个点是终点.  http://blog.ykyi.net

if ( vtx == vtx_end )

{

return min;

}



// 因为找到了一个新的点加入了集合,更新最短路径表. 

for ( int k = 0; k < m_num; k++ )

{

if ( m_sunit[k] )

continue;



if (  min + this->operator()(vtx, k) < m_spath_table[k] )

{

m_spath_table[k] = min + this->operator()(vtx, k);

}

}

}



assert(0); // it's not suppossed to reach here.

return -1;

}



~graph_t()

{

delete m_matrix;

delete m_sunit;

delete m_spath_table;

}



private:

void init_dij(int vtx_start)

{

memset(m_sunit, 0, m_num);   // 初始化为没有点加入这个已求得最短路径的终点集合.

for ( int i = 0; i < m_num; i++ )

{

m_spath_table[i] = this->operator()(vtx_start, i);

}

assert( 0 == m_spath_table[vtx_start] );

m_sunit[vtx_start] = true;

}



private:

int   m_num;

int*  m_matrix;  // 存邻接矩阵

bool* m_sunit;   // 在dijkstra计算过程中用来存某点是否已经是最短路径中的点.

int*  m_spath_table;  // 在dijkstra计算过程中存到某点是的最短路径是多少.

};





int main(int argc, char* argv[])

{

int case_count, path_count, weight, next_ava_vtx;

int vtx_start, vtx_end;

std::map<std::string, int> loc2vtx;  // 存地点字符串到图的顶点号的映射. 

std::vector<int> spirit;

std::string line;



std::cin >> case_count;

for ( int i = 0; i < case_count; i++ )

{

loc2vtx.clear();

spirit.clear();

next_ava_vtx = 0;



std::cin >> path_count;

for ( int j = 0; j < path_count; j++ )

{

// 得到起点地址字符串. 

std::cin >> line;

std::map<std::string, int>::iterator ite = loc2vtx.find(line);

if ( loc2vtx.end() != ite )

{

vtx_start = ite->second;

}

else

{

vtx_start = next_ava_vtx;

loc2vtx[line] = vtx_start;

next_ava_vtx++;

}

spirit.push_back(vtx_start);



// 得到终点地址字符串. 

std::cin >> line;

ite = loc2vtx.find(line);

if ( loc2vtx.end() != ite )

{

vtx_end = ite->second;

}

else

{

vtx_end = next_ava_vtx;

loc2vtx[line] = vtx_end;

next_ava_vtx++;

}

spirit.push_back(vtx_end);



// 得到权重

std::cin >> weight;

spirit.push_back(weight);

}



// 至此 next_ava_vtx 中存放的实际上是邻接方阵的阶. 

graph_t graph(next_ava_vtx);

for ( int i = 0; i < spirit.size()/3; i++ )

{

int x = spirit[3*i];

int y = spirit[3*i+1];

int w = spirit[3*i+2];

graph(x, y) = w;

graph(y, x) = w;

}

for ( int i = 0; i < next_ava_vtx; i++ )

{

graph(i, i) = 0;

}



std::cin >> line;

std::map<std::string, int>::iterator ite = loc2vtx.find(line);

if ( ite == loc2vtx.end() )

{

std::cout << "-1\n";

continue;

}

vtx_start = loc2vtx[line];



std::cin >> line;

ite = loc2vtx.find(line);

if ( ite == loc2vtx.end() )

{

std::cout << "-1\n";

continue;

}

vtx_end = loc2vtx[line];



if ( vtx_start == vtx_end )

{

std::cout << "0\n";

continue;

}



std::cout << graph.shortestpath_dij(vtx_start, vtx_end) << std::endl;

}



return 0;

}

 

 
4 对时间复杂度,空间复杂度方面的分析、估算。
 
时间复杂度和空间复杂度都是O(n*n).   http://blog.ykyi.net
 
///////////// 原题
 
 
 
 
 
1031. Campus
 
 
 
 
 
Description
 
At present, Zhongshan University has 4 campuses with a total area of 6.17 square kilometers sitting respectively on both sides of the Pearl River or facing the South China Sea. The Guangzhou South Campus covers an area of 1.17 square kilometers, the North Campus covers an area of 0.39 square kilometers, the Guangzhou East Campus has an area of 1.13 square kilometers and the Zhuhai Campus covers an area of 3.48 square kilometers. All campuses have exuberance of green trees, abundance of lawns and beautiful sceneries, and are ideal for molding the temperaments, studying and doing research.
 
 
 
 
       Sometime, the professors and students have to go from one place to another place in one campus or between campuses. They want to find the shortest path between their source place S and target place T. Can you help them?
 
 
Input
 
The first line of the input is a positive integer C. C is the number of test cases followed. In each test case, the first line is a positive integer N (0<N<=100) that represents the number of roads. After that, N lines follow. The i-th(1<=i<=N) line contains two strings Si, Ti and one integer Di (0<=Di<=100). It means that there is a road whose length is Di between Si and Ti. Finally, there are two strings S and T, you have to find the shortest path between S and T. S, T, Si(1<=i<=N) and Ti(1<=i<=N) are all given in the following format: str_Campus.str_Place. str_Campus represents the name of the campus, and str_Place represents the place in str_Campus. str_Campus is "North", "South", "East" or "Zhuhai". str_Place is a string which has less than one hundred lowercase characters from "a-z". You can assume that there is at most one road directly between any two places.
 
Output
 
The output of the program should consist of C lines, one line for each test case. For each test case, the output is a single line containing one integer. If there is a path between S and T, output the length of the shortest path between them. Otherwise just output "-1" (without quotation mark). No redundant spaces are needed.
 
 

 

sicily 2014. Dairy Queen 解题报告

Sun Yat-sen University ACM 2014. Dairy Queen

1. 原题中文大意;

给出一个在 [1, 300] 之间的数字N。然后给出一个集合,这个集合中有个数字,C[1, 8]之间。该集合中的每个数字在[1, 200]之间。问如何用这个集合中的数字组合(数字可以重复使用),使它们的总和等于N

2. 解这种题毫不犹豫地想到用动态规划。

3. 设一个数组 ways[301]; ways[n]表示有多少种方法可以组合成和n。假设集合中只一个数字x。那么问题就非常简单,只能取n个该数字,和的集合为{x, 2x, 3x},即ways[x]=1ways[2x]=1, ways[3x]=1 ….。如果集合中有m数字,假设我们已经求得了用这m个数字的组合可以得到的和的数目存到了ways数组里。即对于m个数字,已求得 ways[1] = ?, ways[2] = ?, ways[3] = ? ….. Ways[300] = ?。 那么在此基础上,再加多一个数字,即 m+1个数字的情况会是如何呢。设新加入的这个数字的值是p,则应该是 ways[q] += ways[q-p]。(q > p

 

4. 程序注释清单.

#include <string.h>

#include <stdlib.h>

#include <stdio.h>



int main(int argc, char* argv[])

{

int N, C, coin;  // N为题意中的N,C即题意中的C. coin作临时变量用,不解释,可见下面的代码。

int ways[301] = { 0 };  // 见第三部分的分析。

ways[0] = 1;  // 没有实际意义。为了方便计算.



scanf("%d %d", &N, &C);

for ( int i = 0; i < C; i++)

{

scanf("%d", &coin);

for ( int j = coin; j <= N; j++ )

{

ways[j] += ways[j-coin];  // 见第3部分的分析.

}

}

printf("%d\n", ways[N]);



return 0;

}

 

5.时间复杂度,空间复杂度分析。

空间复杂度是确定的常数。时间复杂度是o(n). n为有多少种面值的硬币。

http://blog.ykyi.net zausiu's blog

原题:

Description

Bessie, always in need of an income, has decided to leverage her dairy skills by taking a part-time job at the local Dairy Queen restaurant. She is running a special cash register (since she has hooves instead of fingers and thus requires special accommodation). Her job is making change for customers as they make a purchase.

As she was counting out 83 cents in change, she wondered: "How many ways can I count out 83 cents? I can use three quarters and eight pennies, seven dimes and three pennies, 83 pennies… there must be a zillion ways!"

How many different ways can one make change for N (1 ≤ N ≤ 300) cents using coins from a set of C (1 ≤ C ≤ 8) coins of supplied values C_i (1 ≤ C_i ≤ 200)? "Different" means differing counts of coins.

Thus, 8 cents can be made, in American currency, with 1 five-cent piece + 3 one-cent pieces and also with 8 one-cent pieces. Using 3 one-cent pieces + 1 five-cent piece is the same as 1 five-cent piece + 3 one-cent pieces, so one can create eight cents in just two different ways. Note that some coin systems are poor at making change and result in an answer of '0'.

Coin values in the input file are listed in descending order from largest to smallest. All coin values will be distinct.

Input

 

Line 1: Two space-separated integers: N and C
Lines 2..C+1: Line i+1 contains a single integer: C_i

 

Output

Line 1: A single line with a single integer that is the number of ways to create N cents of change using the supplied coins. The answer is guaranteed to fit into a signed 32-bit int

 

Sample Input

83 5
50
25
10
5
1

Sample Output

159

 

copyright blog.ykyi.net

 

中大sicily 1426. Phone List 解题报告

 

1.原题中文大意;
 
给出一组数字,最多一万个,判断这组数字中是否存在一个数字是其它一个数字的前缀。
 
2.算法思想及解题用到的主要数据结构;
 
每读入一个数字字符串,则把该数字串从高位到低位分解成一个个数字字符。然后开始以最高位数字为树的根,第二个数字为根的子孙结点,第三个数字为第二个数字的子孙结点。如果碰到最后一个数字,如果这组数字符合要求的话则最后一个数字字符一定是叶子结点。不断的加入新的数字字符串到树中,如果在加入的过程中使以前的叶子结点变成了非叶子结点,或者新加入的数字字符串的最后一个数字在树中不是一个叶子结点,则报告这组数字字符串不符合要求。反之,则符合要求。
 
3.逐步求精算法描述(含过程及变量说明);
 
每个结点记下关键信息,一个数字字符。再加上一个指向其它信息的指针. 这个指针指向一个node_data_t结构。结构体中放置了一个tag标签,记字是不是一个数字字符串的最后一个数字;以及一个指向STL的set容器,容器中放置了所有子孙结点。如下代码描述。
 
struct node_t
 
{
 
char _ch;
 
node_data_t* _data;
 
};
 
struct node_data_t
 
{
 
set<node_t, node_comp>  _nodes;
 
bool _terminal;
 
};
 
剩下的逻辑便是分析数字字符串,把每个字符拆出加入树中。
 
4.程序注释清单
 
#include <set>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cstdio>



using namespace std;



struct node_comp;

struct node_data_t;



struct node_t

{

char _ch;

node_data_t* _data;

};



struct node_comp  // 给STL的set容器的排序算子。

{

bool operator()(const node_t& left, const node_t& right)const

{

return left._ch < right._ch;

}

};
http://ykyi.net zausiu's blog
struct node_data_t

{

set<node_t, node_comp>  _nodes;

bool _terminal;  // 标记是不是一个电话号码的终点字符了。

};



typedef set<node_t, node_comp> nodes_set;



nodes_set top_nodes;



// 如果已经可以判断电话号码不满足要求就返回false.

// 递归调用该函数。

bool odyssey(nodes_set& nodes, const char* num)

{

if ( 0 == *num )

{

return true;

}

//

node_t node;

node._ch = *num;

node._data = new node_data_t;

node._data->_terminal = !num[1];



pair<nodes_set::iterator, bool> retval = nodes.insert(node);

if ( retval.second )  // 还没有这个数字的结点.新插入的.

{

bool b;

b = odyssey(retval.first->_data->_nodes, num+1);

return b;

}

else  // 已经存在

{

delete node._data;

// 并且已经是之前一个数字串的最后一个数字字符.或者现在这个字符是最后一个. 

if ( retval.first->_data->_terminal || !num[1] )

{

return false;

}

else if ( !num[1] )

{

retval.first->_data->_terminal = true;

return true;

}

else

{

retval.first->_data->_terminal = false;

bool b;

b = odyssey(retval.first->_data->_nodes, num+1); // 递归

return b;

}

}

}

// 释放内存.

void free_mem(nodes_set& nodes)

{

for ( nodes_set::const_iterator ite = nodes.begin();

ite != nodes.end();

++ite )

{

free_mem(ite->_data->_nodes);

delete ite->_data;

}

nodes.clear();

}



int main(int argc, char* argv[])

{

int case_count;   // 有多少个case

int phone_num_count;    // 多少个电话霖巴

char phone_num_str[11];   // 存电话霖巴

bool successed;  // 一组数字字符串是否符合要求



scanf("%d", &case_count);

for ( int i = 0; i < case_count; i++ )

{

scanf("%d", &phone_num_count);



successed = true;

for ( int j = 0; j < phone_num_count; j++ )

{

scanf("%s", phone_num_str);



if ( successed )

{

successed = odyssey(top_nodes, phone_num_str);

}

}

if ( successed )

{

printf("YES\n");

}

else

{

printf("NO\n");

}



free_mem(top_nodes);

}



return 0;

}

 

 
5.测试数据
 
用简单的脚本帮助生成测试数据.
 
#!/bin/bash
 
INDEX=0
 
if [ -e $1 ];then
 
COUNT=200
 
else
 
COUNT=$1
 
fi
 
while [ $INDEX -lt $COUNT ];do
 
let "INDEX=$INDEX+1"
 
echo $RANDOM
 
done
 
6.对时间复杂度,空间复杂度方面的分析.
 
本算法的时间复杂度的空间复杂度一般都介于O(logN)和O(N)之间。
 
//////////////// 原题  //////////////
 
1426. Phone List
 
 
 
 
 
Description
 
 
 
 
 
 
 
Given a list of phone numbers, determine if it is consistent in the sense that no number is the pre?x of another. Let’s say the phone catalogue listed these numbers:
? Emergency 911
? Alice 97 625 999
? Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the ?rst three digits of Bob’s phone number. So this list would not be consistent.
 
 
 
 
 
 
 
Input
 
 
 
 
 
 
 
The ?rst line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
 
 
 
 
 
 
 
Output
 
 
 
 
 
 
 
For each test case, output “YES” if the list is consistent, or “NO” otherwise.
 
 
 
 
 
 
 
Sample Input
 
 
 
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
 
 
Sample Output
 
 
 
NO
YES
 
 

 

sicily 1022 Poor contestant Prob 解题报告。

 

         解  题  报  告
 
1 1022 Poor contestant Prob原题中文大意;
 
对于大约十万条数据:如果共奇数条数据则找到最中间那条记录。如果有偶数条记录则忽略。
 
2 算法思想及解题用到的主要数据结构;
 
因为数据的规模比较大。如果给十万条记录排序的话显然会超时。考虑到题目只需要找到最中间那条。易想到把数据平分成两部分,第一部分的数据全部大于第二部分的数据。创建两个堆结构。第一部分的较大数据建大小顶堆,第二部分的较小数据建成大顶堆。在插入数据的过程中,动态维护这两个堆,使小顶堆的元素数等于大顶堆的元素数或者小顶堆的元素比大顶堆的元素多一。本题用性线表来存储堆。
 
3 详细解题思路;
 
因为最终需要输出一个字符串。为了节省拷贝字符串的开销,把字符串存到一个字符串池中,而每个堆中的元素只维护这个字符串池的索引号。
 
初始时,小顶堆和大顶堆的大小都是0。
 
1. 当输入第一条数据时,把这条数据放入小顶堆中。
 
2. 当输入更多数据时:
 
2.1 如果小顶堆和大顶堆的元素个数一样多。为保证添加新数据后,我们需要的最中间的数据在小顶堆的上部。又分两种情况处理:
 
2.1.1 如果待加入数据大于或等于大顶堆的堆顶元素。则把这个待加入数据加入小顶堆。调整小顶堆.
 
2.1.2 如果待加入数据小于大顶堆的堆顶元素.则把大顶堆的堆顶元素弹出添加到小顶堆,调整这两个堆。之后,把待加入数据加入大顶堆。
 
2.2 如果小顶堆和大顶堆的元素个数不一样多。因为前面的约定,那么必定是小顶堆的元素个数比大顶堆的元素个数多一个。仍然分两种情况:
 
2.2.1 如果待加入数据大于小顶堆的堆顶元素。则把待加入数据加入小顶堆并调整,调整后把小顶堆的堆顶弹出加入大顶堆并调整。小顶堆在弹出堆顶元素后再调整一次。
 
2.2.1 如果待加入数据不大于小顶堆的堆顶元素。则把该数据加入大顶堆,调整大顶堆。
 
输入结束时直接取小顶堆的堆顶元素即要求的解。根据元素中的字符串索引可以拿到需要打印的字符串,本题中即那位poor contestant。
 
4 逐步求精算法描述(含过程及变量说明);
int g_name_pool_index = 0;   // 名字池的当前索引号.

char g_name_pool[100001][11];  // 用来存名字的字符串池.



下面是堆相关的描述。

struct heap_elem_t

{

// string _name;

int _name_index;  // 名字的索引

int _solved_count;  // 原题意中表示解决了多少个问题.用这个数量比较堆元素的大小。

};

// STL 用的堆算法的比较算子.

struct heap_elem_less_comparator

{

bool operator()(const heap_elem_t& left,  const heap_elem_t& right)

{

return left._solved_count < right._solved_count;

}

};



// STL 用的堆算法的比较算子.

struct heap_elem_larger_comparator

{

bool operator()(const heap_elem_t& left,  const heap_elem_t& right)

{

return left._solved_count > right._solved_count;

}

};

heap_elem_less_comparator less_comp;

heap_elem_larger_comparator larger_comp;

// 从下往而上调整堆。用到了STL的堆调整算法。堆元素存在线性表中,但不用第一个元素。因为之前的版本用自己写的堆调整算法为了计算坐标方便就不用第一个元素。

inline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)

{

if ( inc )

{

push_heap(heap+1, heap+tail_pos+1, larger_comp);

}

else

{

push_heap(heap+1, heap+tail_pos+1, less_comp);

}

}

// 把堆顶元素弹出.并调整余下的元素仍然是一个堆。也用了STL的算法.

inline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)

{

if ( inc )

{

pop_heap(heap+1, heap+tail_pos+1, larger_comp);

}

else

{

pop_heap(heap+1, heap+tail_pos+1, less_comp);

}

}

// 下面是自已写的堆调整算法。有从上而下的调整,也有从下而上的调整。

/** 调整堆.从下往下调整.

* @param heap 堆的首地址.用顺序表存放堆.但不用下标为0的元素.这个元素可用来作临时存储.

* @param summit_pos 堆顶的位置.summit_pos > 0

* @param tail_pos 最后一个元素的位置.tail_pos > 0

* @param inc 是否建小顶堆.如果false则大顶堆.

*/

void adjust_heap_top2bottom(heap_elem_t heap[], int summit_pos, int tail_pos, bool inc)

{

int i;

heap[0] = heap[summit_pos];  // 存下堆顶的元素先.

for ( i = 2 * summit_pos; i <= tail_pos; i *= 2 )

{

if ( inc )  // 调整小顶堆

{

if ( i < tail_pos && heap[i]._solved_count > heap[i+1]._solved_count )

i++;

if ( ! (heap[0]._solved_count > heap[i]._solved_count) )

break;

}

else  // 调整大顶堆

{

if ( i < tail_pos && heap[i]._solved_count < heap[i+1]._solved_count )

i++;

if ( ! (heap[0]._solved_count < heap[i]._solved_count) )

break;

}

heap[summit_pos] = heap[i];

summit_pos = i;

}

heap[summit_pos] = heap[0];

}



/** 调整堆.从下往上调整.

* @param heap 堆的首地址.用顺序表存放堆.但不用下标为0的元素.这个元素可用来作临时存储.

* @param tail_pos 最后一个元素的位置.tail_pos > 0

* @param inc 是否建小顶堆.如果false则大顶堆.

*/

void adjust_heap_bottom2top(heap_elem_t heap[], int tail_pos, bool inc)

{

int i;

heap[0] = heap[tail_pos];

for ( i = tail_pos; i > 1; i /= 2 )

{

int parent_pos = i / 2;

if ( inc )  // 调整小顶堆

{

if ( heap[parent_pos]._solved_count > heap[0]._solved_count )

{

heap[i] = heap[parent_pos];

}

else

{

break;

}

}

else  // 调整大顶堆

{

if ( heap[parent_pos]._solved_count < heap[0]._solved_count )

{

heap[i] = heap[parent_pos];

}

else

{

break;

}

}

}



heap[i] = heap[0];

}

5 程序注释清单(重要过程的说明);

// poor_guy.cpp : Defines the entry point for the console application.
//

#include <algorithm>
#include <string>
#include <vector>
#include <string.h>
#include <stdio.h>

using namespace std;

template<typename T> class my_vector
{
public:
my_vector(T* addr)
{
m_ary = addr;
m_ava_idx = 0;
}
~my_vector()
{
//  delete []m_ary;
}

T& operator[](int index)
{
return m_ary[index];
}

void push_back(const T& v)
{
m_ary[m_ava_idx++] = v;
}

void resize(int size)
{
m_ava_idx = size;
}

void shrink(int dec)
{
m_ava_idx -= dec;
}

int size()
{
return m_ava_idx;
}
private:
T*   m_ary;
int  m_ava_idx;
};

// 堆的结点定义
int g_name_pool_index = 0;
char g_name_pool[100001][11];

struct heap_elem_t
{
// string _name;
int _name_index;
int _solved_count;
};

heap_elem_t g_heap_elems0[50002];
heap_elem_t g_heap_elems1[50002];

struct heap_elem_less_comparator
{
bool operator()(const heap_elem_t& left,  const heap_elem_t& right)
{
return left._solved_count < right._solved_count;
}
};

struct heap_elem_larger_comparator
{
bool operator()(const heap_elem_t& left,  const heap_elem_t& right)
{
return left._solved_count > right._solved_count;
}
};

heap_elem_less_comparator less_comp;
heap_elem_larger_comparator larger_comp;

/************************************************************************/
/* inc 为真时调整为小顶堆,为false时调整为大顶堆。                      */
/************************************************************************/
inline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)
{
if ( inc )
{
push_heap(heap+1, heap+tail_pos+1, larger_comp);
}
else
{
push_heap(heap+1, heap+tail_pos+1, less_comp);
}
}

inline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)
{
if ( inc )
{
pop_heap(heap+1, heap+tail_pos+1, larger_comp);
}
else
{
pop_heap(heap+1, heap+tail_pos+1, less_comp);
}
}

int main(int argc, char* argv[])
{
const int BUFF_LEN = 64;
char buff[BUFF_LEN];
int case_count;  // 记有多少个case;
int contestant_count;
my_vector<heap_elem_t> littletop_heap(g_heap_elems0);
my_vector<heap_elem_t> bigtop_heap(g_heap_elems1);
heap_elem_t contestant;
string name;
// vector<string> output_vec;

scanf("%d", &case_count);
for ( int i = 0; i < case_count; i++ )
{
littletop_heap.resize(1);  // 为了方便计算.下标0的位置不存堆的元素.
bigtop_heap.resize(1);
g_name_pool_index = 0;
contestant_count = 0;

while(true)
{
scanf("%s", buff);

int little_heap_count = littletop_heap.size() - 1;
int big_heap_count = bigtop_heap.size() - 1;

if ( buff[0] == 'Q' )  // 查询. Querry
{
if ( little_heap_count == big_heap_count || 0 == contestant_count )
{
printf("No one!\n");
//output_vec.push_back("No one!\n");
}
else
{
printf("%s\n", g_name_pool[littletop_heap[1]._name_index]);
//output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]);
//output_vec.push_back("\n");
}
}
else if ( buff[0] == 'E' )  // 结束.
{
if ( little_heap_count == big_heap_count || 0 == contestant_count )
{
printf("Happy BG meeting!!\n");
//output_vec.push_back("Happy BG meeting!!\n");
}
else
{
printf("%s%s",g_name_pool[littletop_heap[1]._name_index], " is so poor.\n");
//output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]);
//output_vec.push_back(" is so poor.\n");
}

break;
}
else if( buff[0] == 'A' )// 加入参赛者数据.
{
contestant_count ++;

scanf("%s", g_name_pool[g_name_pool_index]);
contestant._name_index = g_name_pool_index;
g_name_pool_index++;
scanf("%d", &contestant._solved_count);

if ( 1 == contestant_count )  // 第一个参赛者数据.
{
littletop_heap.push_back(contestant);
}
else if ( little_heap_count == big_heap_count )  // 两个堆的元素相等.
{
// 新元素大于大顶堆的堆顶元素,所以插入小顶堆.
if ( contestant._solved_count >= bigtop_heap[1]._solved_count )
{
littletop_heap.push_back(contestant);
adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);
}
else
{
heap_elem_t top = bigtop_heap[1];
popup_the_top(&bigtop_heap[0], bigtop_heap.size()-1, false);
bigtop_heap.shrink(1);

bigtop_heap.push_back(contestant);
adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);

littletop_heap.push_back(top);
adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);
}
}
else  // 不等.只可能是小顶堆比大顶堆多1.
{
if ( contestant._solved_count > littletop_heap[1]._solved_count )
{
littletop_heap.push_back(contestant);
adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);

heap_elem_t top = littletop_heap[1];
popup_the_top(&littletop_heap[0], littletop_heap.size()-1, true);
littletop_heap.shrink(1);

bigtop_heap.push_back(top);
adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);
}
else
{
bigtop_heap.push_back(contestant);
adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);
}
}
}
}

if ( i + 1 < case_count )
{
printf("\n");
//output_vec.push_back("\n");
}
}

//for ( int i = 0; i < output_vec.size(); i++ )
//{
// cout << output_vec[i];
//}

return 0;
}

 

 
//////// 上面的代码在中山大学ACM网站 www.soj.me 上通过.目前的成绩是第14名.
 
Rank  14    2011-12-07 10:00:19    0.18 sec    2160 KB    6971 Bytes     C++   zausiu
 
注意上面的代码绝不能用C++的标准IO cin cout 做输入输出.如果用C++的IO流会造成超时。我为了调这个超时问题调了整整一天!死活想不到是因为C++ IO的问题.童鞋,一定要用 scanf 和 printf 啊。面对十万级的IO,尤其是在做ACM题,cin cout 是魔鬼。
 
原因是:
 
More should be noted about I/O operations in C++. Due to their complex underlying implementation  models, cin and cout are comparatively slower than scanf and printf. The difference in performance is shown by many experiences to be more significant if the program is compiled by G++. Therefore if a problem has huge input, using cin and cout will possibly lead to Time Limit Exceed.
 
6 测试数据;
 
用一个简单的BASH脚本来创建测试用例。
 
#! /bin/bash

INDEX=1

SHRESHOLD=100000   // 建十万条数据. 



while [ $INDEX -lt $SHRESHOLD ]

do

echo "ADD name$INDEX $RANDOM"

let "INDEX=$INDEX+1"

done

 

 
 
7 对时间复杂度,空间复杂度方面的分析.
 
时间复杂度是O(log n), 空间复杂度是 O(n).
 
 
 
附原题:
 
 
 
 
 
1022. Poor contestant Prob
 
Description
 
 
 
As everybody known, “BG meeting” is very very popular in the ACM training team of ZSU.
After each online contest, they will go out for “smoking”. Who will be the poor ones that have to BG the others? Of course, the half who solve less problems.
The rule runs well when the number of the contestants is even. But if the number is odd, it is impossible to divide them into two equal parts. It gives a dilemma to the BG meeting committee. After a careful discussion with Mr. Guo, a new rule emerged: if the number of the contestant is odd, the committee will first sort the contestants according to the number of problems they solved, and then they will pick out the middle one. This poor boy or girl will have no chance to attend the BG meeting.
Strange rule, isn`t it?
As the number of the contestants is becoming more and more large, the committee need to write a program which will pick out the poor one efficiently.
Note that: Every contestant solves different number of problems. The total number of the contestants will not exceed 10^5.
 
 
 
Input
 
 
 
There are several cases in the input. The first line of the input will be an integer M, the number of the cases.
Each case is consisted of a list of commands. There are 3 types of commands.
1. Add xxx n : add a record to the data base, where xxx is the name of the contestant, which is only consisted of at most 10 letters or digits, n is the number of problems he/she solved. (Each name will appear in Add commands only once).
2.Query :
3.End :End of the case.
 
 
 
Output
 
 
 
1.For the Query command: If the current number of contestants is odd, the program should output the poor contestant’s name currently even if there is only one contestants, otherwise, just out put “No one!” (without quotes).
2.For the End command:
If the total number of contestants in the data base is even, you should out put “Happy BG meeting!!”(without quotes),otherwise, you should out put the “xxx is so poor. ”(without quotes) where xxx is the name of the poor one.
3.Each case should be separated by a blank line.
 
 
 
Sample Input
 
2
Add Magicpig 100
Add Radium 600
Add Kingfkong 300
Add Dynamic 700
Query
Add Axing 400
Query
Add Inkfish 1000
Add Carp 800
End
 
Add Radium 100
Add Magicpig 200
End
Sample Output
 
No one!
Axing
Radium is so poor.
 
Happy BG meeting!!
Problem Source
 
ZSUACM Team Member
 

 

熬夜完成 sicily1153 马周游解题报告。困死哥了.

唉!!! 上次交作业写错题目了,做了简单的马周游 sicily 1152。补上新的,应该是sicily 1153.为了解决规模太大的问题。加上了优化算法。

 
中大ACM实验题。
 
(1)原题中文大意
 
中国象棋的马按照象棋的规则在8 x 8 的棋盘上跑64步跑完所有的格子。
 
 
 
(2)算法思想及解题用到的主要数据结构
 
 
 
从每一个点往下走第二步,会有几点有效的行走位置。 把当前位置记在栈里面,以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过,则从栈顶弹出上一位置,恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别,用函数递归调用即可解决问题。
 
软之简单的马周游,8 x 8 棋盘的规模非常大。需要在可选下一步中找到最接近正确路线的点。求该点的办法是把所以的可选点先找出,再给这些可选点按权重排序,从最优的解依次向次优,次次优…..的点试探。重点在权重的算法。这里的权重的计算法则是指一个点的下一次可走的点的个数。
 
主要的数据结构有:
 
// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位

// 置.elocution[x][0]用下标0记个数。最多8个有效可走位置。

char elocution[ELEM_COUNT][9];

// stamps数组记每个点是否已经走过了。0表示没走过,1表示走过了。

char stamps[ELEM_COUNT];

// track数组记路径的顺序。

char track[ELEM_COUNT];

通过结合stamps数组和elocution数组可以算出下一步的每个点的权重。



(3)详细解题思路

1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.

2. 写一个一般的递归调用自己的函数,表示马在走第几步时到了哪个位置,然后求出余下的所有可走位置。

3. 余下的所有位置按照上文提到的权重排序。

4. 对于排序后的可选点数组,按顺序依次用递归函数尝试。

5. 递归函数有三个退出条件。1.下一个要尝试的点已经走过了,2.试完了所有的可选下一步无解。3.走到了最后一步,即得解!



(4)算法描述

初如化上文提到的elocution数组,清空stamps和tracks.从起点开始调用递归函数。

http://blog.ykyi.net  zausiu's blog.



(5)程序注释清单

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <csetjmp>

//#include <cassert>



using namespace std;



#define  ROW_NUM     8

#define  COLUMN_NUM  8

#define  ELEM_COUNT ROW_NUM * COLUMN_NUM



jmp_buf jmpbuffer;  // 很深的函数递归调用时用longjmp快速退出.



// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位

// 置.elocution[x][0]用下标0记个数。最多8个有效可走位置。

char elocution[ELEM_COUNT][9];



// stamps数组记每个点是否已经走过了。0表示没走过,1表示走过了。

char stamps[ELEM_COUNT];



struct coordinate  // 二维坐标

{

char _x;  // start from zero.

char _y;

};



// 作标转序号

char coordinate2serial_num(coordinate co)

{

char num = co._x * COLUMN_NUM + co._y + 1;

return num;

}

// 序号转坐标

coordinate serial_num2coordinate(char sn)

{

coordinate co;

co._x = (sn - 1) / COLUMN_NUM;

co._y = sn - co._x * COLUMN_NUM - 1;

return co;

}



// ((x:1;y:-2),(x:2;y:-1),(x:2;y:1),(x:1;y:2) (x:-1;y:2),(x:-2;y:1),(x:-2;y:-1),(x:-1;y:-2));

char increments[8][2] =

{

1, -2, 2, -1, 2, 1, 1, 2,

-1, 2, -2, 1, -2, -1, -1, -2

};

void next_step(char pos, char steps[])  // 把位置在pos序号的点的每一个下一个可选位置记在数组中。

{

char valid_count = 0;

coordinate co = serial_num2coordinate(pos);

coordinate tmp;

char serial_num;

for ( int i = 0; i < 8; i++ )

{

tmp._x = co._x + increments[i][0];

tmp._y = co._y + increments[i][1];

if ( tmp._x < 0 || tmp._x >= ROW_NUM || tmp._y < 0 || tmp._y >= COLUMN_NUM )  // 保证位置有效

{

continue;

}

serial_num = coordinate2serial_num(tmp);

if ( serial_num >= 1 && serial_num <= ELEM_COUNT )

{

valid_count++;

steps[valid_count] = serial_num;

}

else

{

cerr << "Not expected to reach here.\n";

}

}

steps[0] = valid_count;

}



// 下面的逻辑以每个点的下一步可跳点的数目作为权重排序。

struct pos_weight

{

char _pos;

char _weight;

};

// 又是用递归。这里为了实现快速排序

int partition(pos_weight poses[], int low, int high)

{

pos_weight pivot = poses[low];

while (low < high)

{

while (low < high && pivot._weight < poses[high]._weight)

high--;

poses[low] = poses[high];

while (low < high && pivot._weight >= poses[low]._weight)

low++;

poses[high] = poses[low];

}

poses[low] = pivot;

return low;

}

// 快速排序。

void quick_sort_steps(pos_weight poses[], int low, int high)

{

if ( low < high )

{

int pivot_loc = partition(poses, low, high);

quick_sort_steps(poses, low, pivot_loc-1);

quick_sort_steps(poses, pivot_loc+1, high);

}

}

void rearrage_steps(char poses[], int len) // poese里放置了下一个位置数组。Len是数组长度。

{

char weight, pos, next_step_count;

vector<pos_weight> vec(len);

for ( int i = 0; i < len; i++ ) // 计算权重.

{

weight = 0;

pos = poses[i];

next_step_count = elocution[pos-1][0];

for ( int j = 0; j < next_step_count; j++ )

{

char next_step_pos = elocution[pos-1][j+1];

if ( 0 == stamps[next_step_pos-1] )

{

weight++;  // 如果有一下一跳点没走过则权重加1.

}

}

vec[i]._pos = pos;

vec[i]._weight = weight;

}

quick_sort_steps(&vec[0], 0, len-1);  // 根据权重排序.

for ( int i = 0; i < len; i++ ) // 把排序后的位置写回原始数组.

{

poses[i] = vec[i]._pos;

}

}



void init_elocution()

{

memset(stamps, 0, sizeof(stamps));

for ( int i = 1; i <= ELEM_COUNT; i++ )

{

next_step(i, elocution[i-1]);

}

}



char track[ELEM_COUNT];

void run_horse(char start_pos, char step_count) // step_count [0 -- 64)

{

// 如果已经经过这点就立即退出函数。

if ( 1 == stamps[start_pos-1] )

{

return;

}



track[step_count] = start_pos;



if ( step_count == COLUMN_NUM * ROW_NUM - 1 )  // 是不是最后一步。

{

for ( int i = 0; i < sizeof(track); i++ )

{

cout << (int)track[i];

if ( i + 1 != sizeof(track) )

{

cout << " ";

}

}

cout << endl;

longjmp(jmpbuffer, 0x1);

return;

}



// 记下已经走了这一步。

stamps[start_pos-1] = 1;   rearrage_steps(elocution[start_pos-1]+1, elocution[start_pos-1][0]);

for ( int i = 0; i < elocution[start_pos-1][0]; i++ )

{

run_horse(elocution[start_pos-1][i+1], step_count+1);

}

stamps[start_pos-1] = 0;  // 试完了所有可走步.退出这个函数.重置这个位置为没有走过。

}



int main(int argc, char* argv[])

{

int pos;

vector<int> vec;



while(true)

{

cin >> pos;

if (pos==-1)

{

break;

}

vec.push_back(pos);

}



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

{

if(setjmp(jmpbuffer) == 0)  // 为了很深的递归函数快速回退到这里。

{

init_elocution();

memset(track, 0, sizeof(track));

memset(stamps, 0, sizeof(stamps));

run_horse(vec[i], 0);

}

}



return 0;

}

 

(6)该算法的时间复杂度是 O(8 ^ (m * n))   m,n分别为棋盘的长和宽。
 
 
 
/////////////////// 原题目如下:
 
 
 
1153. 马的周游问题
 
 
 
Description
 
和题目C同样的任务,这里只是把棋盘扩大到标准的国际象棋。对这样一个8 * 8的棋盘用同样的方法编号如下:
 
1     2     3       4     5     6       7     8
 
9     10       11    12       13    14       15    16
 
17    18       19    20       21    22       23    24
 
25    26       27    28       29    30       31    32
 
33    34       35    36       37    38       39    40
 
41    42       43    44       45    46       47    48
 
49    50       51    52       53    54       55    56
 
57    58       59    60       61    62       63    64
 
Input
 
输入有若干行。每行一个整数N(1<=N<=64),表示马的起点。最后一行用-1表示结束,不用处理。
 
Output
 
对输入的每一个起点,求一条周游线路。对应地输出一行,有64个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
 
Sample Input
 
4
-1
Sample Output
 
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。
 
 
 

 

又是数组越界造成的bug.

又一次遇到数组越界造成的奇怪的,难以调试的,诡异的bug.

前几天做ACM题。‘简单的马周游’。

http://blog.ykyi.net/2011/11/acm-%E9%A9%AC%E5%91%A8%E6%B8%B8%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

因为我的解法用了函数递归调用,函数求到最终解的栈的调用层次非常深。第一版用置一个全局变量的方式让这么深调用的函数快速依次退出。但我也知道还有另外一种解法就是用C语言的setjmp 和 longjmp。用这两个函数可以快速退栈。

 

今天晚上就想用setjmplongjmp改写一下。本来以为是非常简单的事情。结果改完以的程序只能正确求解第一个请求,然后程序看起来就像是死了。Debug时发现程序似乎跑飞了。哎(脑子不灵光,发现程序跑飞竟然没有立即想到是数组越界把堆栈写坏了)。因为我改动的代码非常少,只是用setjmplongjmp快速退出递归取代之前的稍微比较慢的做法。而其它的代码改动的非常之少。于是我当时分析错误的出发点就是比较两份代码的异同。比较来比较去,就只有退出方式不同而已。相当相当地困惑。费了很多时间都没有找到原因。

实在搞不定了。冲了个热水澡,又回来看代码。还是没有发现这个改动在哪里引入了错误。不断反复地看代码,突然灵光一现看到写一个全局数组的语句,下标变量越界!越界!越界!!!啊~~惊喜!于是把数组下标的相关的代码纠正了,于是setjmp版本的代码也运行正常啊。

这次的经验是。操作数组的时候一定要一定要一定要非常非常非常之小心~~在调试程序发现程序跑飞的情况下马上要意识到是写坏了堆栈。

 

另外还有一个疑问是第一版的代码也有写坏栈的问题为什么就一切正常呢。这就是C/C++程序数组危险的地方啊~~第一版本的代码退栈的方式和第二版不一样,于是这个bug就在第一版隐藏了起来。于是第二版出问题时我的思路集中在比较代码差异是如何引入问题的。而这个bug并不是新代码引入的,而是在旧代码隐藏起来的,第二代的新代码让触发了这个bug

总结下经验:

一定要一定要非常小心C/C++的数组越界问题啊!!!操作很多数组时,有很多下标要计算时。千万要注意是从0还是从1开始计算下标。要根据约定多下诊断!!!及时发现隐藏的错误。越界写数组的bug有时发生,可能在引入的当时被隐藏,隐藏的很深很深。但越界读数组的bug隐藏得更深更深更深啊。

copyright blog.ykyi.net