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://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://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.
 
 

 

Unix 网络编程 第十章 SCTP Client/Server Example

这一章的内容还是满少的。也就是给出一个SCTP的简单例子。所以也没有太多需要做笔记的。

1. 什么是 head-of-line blocking.

Head-of-line blocking occurs when a TCP segment is lost and a subsequent TCP segment arrives out of order. That subsequent segment is held until the first TCP segment is retransmitted and arrives at the receiver.

2. 怎么更改SCTP连接的stream的数量。

SCTP连接的streams的数量是在association的握手之前协商好的。对于FreeBSD的KAME实现,SCTP的outbound streams默认为10。这个值可以用setsocket函数更改。与SCTP_INITMSG scoket option相关,设置struct sctp_initmsg结构体。

也可以用sendmsg函数发送ancillary数据来到达同样的目标。但发送ancillary data只对one-to-many形式的sctp socket有效。

3. 怎么结束一个SCTP连接。

可以设置sctp_sndrcvinfo结构的sinfo_flags值的MSG_EOF flag来关闭一个sctp连接gracefully. This flag forces an association to shut down after the message being sent is acknowledged.

还可以给sinfo_flags设置 MSG_ABORT。这样就会立即发送一个ABORT给peer端。任何还没来得及发送出的数据会被丢弃。

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://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 ykyi.net

 

Unix网络编程.第九章笔记

# TCP 协议在1981年标准化,而SCTP协议则是在2000年由IETF组织标准化。IETF: Internet Engineering Task Force 互联网工程任务组成立于1985年。

# SCTP支持两种类型的socket. one to one(为了方便现有的tcp程序迁移到sctp) 和 one to many.

# sctp的sctp_bindx可以绑定多个地址,并且可以动态增删。但动态增删不影响已经存在的associations.不过各个unix分支不一定支持这个特性。

# sctp_getpaddrs和sctp_getladdrs分别是getpeername和gethostname的sctp版。They are designed with the concept of a multihoming aware transport protocol.

# sctp传输的报文是有边界的。sctp在传输层支持传输超大的message.

Unix网络编程.第七章笔记

1. 有一个 Generic Socket OptionSO_BROADCAST 用来开启是否充许广播。2. 仅有TCP支持SO_DEBUGKernel把详细的发送包的接收包信息存在一个环路buffer里。可以用trpt查看它。3. SO_ERROR套接字选项只能被取得,不能被设置。如果进程阻塞在select调用里,不论是读还是写,select都会返回conditions set。如果进程使用signal-driven I/O,则SIGIO信号会被发到这个进程或者它所在的进程组。进程用getsockopt得到so_error后,so_error就会被重置为0.如果so_error不为0,此时调用 read 或者 write 就会立即返回-1errno被置为so_error的值。

 

 

4. SO_KEEPALIVE在一个tcp连接没有任何收发达两个小时时会发一个prob给对方。两个钟喔。好长的时间啊!!!Richard Stevens认为SO_KEEPALIVE应该改叫 make-dead。大多Unixkernel把这个两小时时长存为一个系统级的变量。这意味着如果你用某种方法改变了这个时长,会影响这个操作系统的所有socket.Richard Stevens认为想把这个时长改短的想法是错误理解了这个选项的意义。

5. SO_LINGER仅仅适用于面向连接的socket,比如TCPSCTP,因此不适用UDP

Struct linger{

int l_onofff;

int l_linger;

};

L_onoff为零是,closebehavior就是默认情况:close立即返回,kernel继续发送缓冲区内未发送的数据。当l_onoff不为零,而l_linger0TCP协议则会立即终止连接,发送RSTpeer端,这样做避免了TCPTIME_WAIT状态,这样的坏处是: leaves open the possibility of another incarnation of this connection being created within 2MSL seconds and having old duplicate segments from the just-terminated connection being incorrectly delivered to the new incarnation.对于SCTP, 也会发送一个ABORT chunkpeer.第三种情况:如果l_onoff为真,l_linger不为0.close不会立即返回,会最多等待指定的时长,在这段时间里kernel发送缓冲区内的数据给peer。如果在这段时间内发送完则close返回0.如果没有发送完毕,close就会返回EWOULDBLOCKsend buffer里的数据会被丢弃。

6. MSL: maximum segment lifetime.

7. 因此close默认情况下立即返回,即使用SO_LINGER设置等待时间也在理论上存在close先于发送缓冲区的数据被peeracknowleded的情况。因此一个更好的解决方案是用shutdown系统调用with a second argument of SHUT_WR。在调用shutdown后,用read调用直到read返回0,即收到peer端的FIN

8. UDP没有congestion control,如果发得太快,不仅仅peer端来不及收。A fast sender can overwhelm its own network interface, causing datagrams to be discarded by the sender itself.

9. 因为tcp在三次握手阶段的SYN segment里交换窗口大小(windows scale)。所以tcp的接收缓冲大小必须在shank hands之前就设置好。Connected socketlistening socket继承这个选项。

10. TCP的套接字缓冲区大小至少需要是4MSS的大小。这里指的套接字缓冲,如果是针对单向的传输,比如单向传一个文件,指的是发送方的发送缓冲和接收方的接收缓冲。如果是双向的传输,则指的是双方的接收和发送缓冲。为什么tcp套接字的缓冲区需要至少   是4MSS的大小呢?这是因为tcp的快恢复(fast recovery)算法。快恢复算法定义:如果接收端连续收到三个同样的ACK,就认为有packet丢失了。而接收端在segment丢失后,每收到新的segment就不停地重发一个重复的acksender。如果窗口大小小于4segments,就不会有三个重复的ACK,所以快恢复算法就没办法工作了。

11. What is bandwidth-delay product.

A: The capacity of the pipe is called the bandwidth-delay product and we calculate this by multiplying the bandwidth(in bits/sec) times the RTT(in seconds), converting the result from bits to bytes. 即网速乘上RTT.

12. UDP没有send buffer,但有一个send buffer size.只要socketbuffer size大于LO_WATER,就永远是可写的。

13. SO_REUSEADDR有四种用途。好难写。见Unix Network Programming Section 7.5 影印版第211页啦。

14. It's Ok for the MSS to be different in each direction.

15. Nagle算法是为了减少small package的数量.The algorithm states that if a given connection has outstanding data, then no small packets will be sent on the connection in response to a user write operation until the existing data is acknowledged. Small package 指的是任何比MSS小的package.

16. Delayed ACK algorithm: This algorithm causes TCP to not send an ACK immediately when it receives data; instead, TCP will wait some small amount of time (typically 50-200ms)and only then send the ACK.

17. SCTP有一个SCTP_AUTOCLOSE套接字选项。This option allows us to fetch or set the autoclose time for an SCTP endpoint. The autoclose time is the number of seconds an SCTP association will remain open when idle.SCTP association能够保持空闲状态的最长时间。超时就会被关闭。

中大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 -ltCOUNT ];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
 
 

 

Unix网络编程.第五,六章笔记.

# Unix世界里经常看到的 pst  是 pseudo terminal 的意思啊。

# ps -t pts/6 -o pid,ppid,tty,stat,args,wchan

ps 命令的进程状态。 S表示进程在睡眠,I表示进程在等待输入,O表示进程在等待输出。当进程在S状态时,wlan指示了更详细的状态信息。

# SIGSTOP 和 SIGKILL 两个posix信号不可以被caught.

# 缺省情况下,Unix的信号是不排在队列中的。这意味着多个相同signal到达的时候如果没有来得及处理,就只会记下一个signal.如果需要稳定的信号支持,就要使用RealTime Posix接口。

# init 进程的PID是 1.

# 可以用sigprocmask函数block和unblock信号。This let us protect a critical region of code by preventing certain signals from being caught while that region of code is executing.

# 对于 Unix System V 和 Unix98, the child of a process does not become a zombie if the process sets the disposition of SIGCHLD to SIG_IGN. unfortunately, tis works only under System V & Unix98. Posix明确指票这个行为是未定义的。The portable way to handle zombies is to catch SIGCHILD & call wait or waitpid.

# waitpid 有个 WNOHANG 选项可以让waitpid立即返回。

# POSIX定义了asynchronous I/O model .但是 few systems support POSIX asynchronous I/O. The main difference between asynchronous I/O model and signal-driven I/O model is that with signal-driven I/O, the kernel tells us when an I/O operation can be initiated but with asynchronous I/O, the kernel tells us when an I/O operation is completed.

# 想得到本机到某台机的RTT。怎么做呢?kao,不要太容易啊。用 ping 啊!!!

使用Necessitas在Android平台上运行Qt程序失败

什么是 Necessitas?

NecessitasQtAndroid操作系统上的一个移植,同时提供了Qt CreatorAndroid的集成。Necessitas计划为你提供了Android平台下的Qt,以及一个一流的平易近人的IDE,方便你在安卓平台下管理,开发,部署,运行 调试你的Qt应用。

什么是Minstro?

Necessitas也是Ministro的官网。MinistroLGPL Qt共享库提供了一个系统范围的下载器(downloader)和安装器(installer)。你可以在Andorid软体市场获得Ministro

如何安装Necessitas SDK开发包?

相当地easy啊!http://sourceforge.net/projects/necessitas/files/ 下载sdk开发包。有linux, win, mac 三个平台下的。安装过程傻瓜式 next next next 。哥尝试在Linux下安装出错了。安装程序没有加载起来。

zausiu@potassium:/tmp$ ./necessitas-0.3-online-sdk-installer-linux 

./necessitas-0.3-online-sdk-installer-linux: error while loading shared libraries: libgobject-2.0.so.0: cannot open shared object file: No such file or directory

 

我先尝试在deibian安装linux版本。结果安装文件启动时加载libglobject.so失败了!但是明明在/lib目录下啊!解决不了,唔知点解!就只好在win7下安装了windows版本。注意要勾选上装 ant,如果你的系统里之前没有安装ant的话。装好ant后还要把ant的路径添加入环境变量里。

如何安装Android SDK开发包?

去官网下载了然后安装。简单地令人发指!!!哥不能讲怎么安装它,免得说我侮辱你的智慧。

http://developer.android.com/sdk/index.html

开始开发

运行在安卓上的Qt程序被编译成共享对象(shared objects)。一个Java Launcher,已经集成在necessitas sdk里,会加载这个shared objects。当然,对于应用开发者,这个Java Launcher是完全透明的。要注意的是,Qt包含了很多互相引用的库,只有Android V1.6以上才支持这个functionality

 

哈。最最重要的。尝试第一个将被部署到android上的Qt应用。用安装好的 Necessitas Qt Creator创建了一个GUI程序。运行。。。运行。报错了!!!哭啊。

ma-make: *** [install_target] Error 2

The process "D:\necessitas\QtCreator\bin\ma-make.exe" exited with code 2.

Error while building project 4android (target: Android)

When executing build step 'Copy application data'

"When executing build step 'Copy application data'"google了一下。木有得到有价值的信息。不知道如何解决啊。哈~~那就不管了!!!

copyright ykyi.net

 

 

linux的soname,链接库的问题.

第一次看到soname是读<程序员的自我修养.第一册:链接库>看来的。顺便说一下,这本书确实是本好书吖,国内出的难得技术好书。后来在公司的项目中把它从windows平台下移植到linux下,写makefile时用到过。

 

再后来又忘记了。今天再次看到soname的时候就有点记不起来了。又只好搜索了一些资料看。趁热打铁把学会的东西记下来。

linux为尝试解决动态链接库版本冲突的问题(windows平台下称之为DLL HELL),引入了soname进制。linux的动态链接库的扩展名约定为.so 即shared object的缩写。下面的makefile语句来自于哥今年上半年写的makefile文件:

VERSION_NUM := 1.0.0
soname = lib(dirname).so.(firstword (subst ., ,(VERSION_NUM)))
LINKFLAGS := -shared -Wl,-soname,$(soname) -L. -lpthread -lrt -lpentagon -lcross_platform
其中的变量$(soname)会被替换为eibcomm.so.1。再看看LINKFLAGS变量指定的几个选项. -shared 表示要生成一个shared object,即动态共享库. -pthread -lrt -lpentagon -lcross_platform 是要链接其它几个库,thread和linux的posix线程库,rt是一个和实时系统相关的库它提供了高精度的时间函数。

比较奇怪的是 -Wl,-soname,$(soname) 它们之前用逗号分开,而不是用空格分开。实际上这几个东东会被gcc传给ld(linux下的链接器)作为链接器的参数。gcc规定的写法就是这样的。指定的soname会被链接器写入到最终生成的elf文件中(linux下的可执行文件格式)。要查看elf文件的段布局什么的,可以用readelf工具。

 

最终生成的文件将命名为 libname.so.x.y.z 的形式。soname是libname.so.x的格式(也不尽然,这只是一个convetion,并非在语法或机制上强行要求)。接着把生成的so文件拷贝到/usr/lib 或者 /lib,这两个文件夹是系统用来放置动态链接库的地方。debian下没有把/usr/local/lib作为默认的动态链接库文件夹.可以通过改/etc/ld.so.conf 文件把更多的路径加入。再运行 ldconfig,更新cache中的库文件信息。为什么要用cache呢,有人就问了!因为library实在太多了咯,cache就被引用了。cache是个好东西啊!!!

这个时候依赖 libname.so.x 的文件就可以找到这个library并加载起来了。但是编译程序时还是找不到呢.编译程序时通常会写 -lname 这个时候会先找 libname.so 再找 libname.a 文件,结果找不到。link就会抱怨没有找到这个库文件。为了让编译通过,于是你就用 ln -sf libname.so libname.so.x.y.z (这个是realname,版本号部分可能只有x.y两个部分) 建一个软链接!搞定!

copyright ykyi.net

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 -ltSHRESHOLD ]

do

echo "ADD nameINDEXRANDOM"

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