Posts Tagged ‘算法’

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.
 
 

 

Be the first to comment - What do you think?  Posted by zausiu - December 26, 2011 at 13:12

Categories: Tech Articles   Tags: ,

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

 

Be the first to comment - What do you think?  Posted by zausiu - December 17, 2011 at 20:05

Categories: Tech Articles   Tags:

中大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
 
 

 

Be the first to comment - What do you think?  Posted by zausiu - December 11, 2011 at 23:50

Categories: Tech Articles   Tags:

Next Page »