方案尝试

• 32-bit ELF

1
2
3

nasm -f elf t.asm
ld -m elf_i386 -o t t.o  -Ttext 0x1000
gdb t

• 64-bit ELF

1
2
3

nasm -f elf64 t.asm
ld -o t t.o  -Ttext 0x1000
gdb t

• 带符号表

1
2
3

nasm -f elf64 t.asm -g -F stabs
gcc -o t t.o -g
gdb t

超市收银问题

L最近在工大外面开了一个小超市。由于该超市物美价廉，且服务态度热情，因此刚开业就十分火爆。可是，这个超市目前只有两个收银台，以至于最近经常有顾客抱怨等待交款的时间太长。

这个超市目前暂时没有办法增加新的收银台，因此，L想通过别的办法缓解这个问题。现在，假设有N个顾客在等待交款。显然，前两个顾客可以马上得到服务，而后面的就得排队等候。L想重新调整一下两支队伍，使得这N个顾客们的平均等待时间最小。假设这N个顾客交完费之前不会来新的顾客。请你帮他完成这个任务。

URL: SOJ1824

Description

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.

In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).

Once a member in a group is a suspect, all members in the group are suspects.

However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

URL: http://poj.org/problem?id=1185

题目描述

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用”H”表示），也可能是平原（用”P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 

算法模板

KM算法是在匈牙利算法的基础上扩展出来的，具体原理不再赘述，算法模版如下：

URL : POJ 1182

Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

原题链接： http://codeforces.com/contest/429/problem/A

Xor-tree

Iahub is very proud of his recent discovery, propagating trees. Right now, he invented a new tree, called xor-tree. After this new revolutionary discovery, he invented a game for kids which uses xor-trees.

The game is played on a tree having n nodes, numbered from 1 to n. Each node i has an initial value initi, which is either 0 or 1. The root of the tree is node 1.

One can perform several (possibly, zero) operations on the tree during the game. The only available type of operation is to pick a node x. Right after someone has picked node x, the value of node x flips, the values of sons of x remain the same, the values of sons of sons of x flips, the values of sons of sons of sons of x remain the same and so on.

The goal of the game is to get each node i to have value goali, which can also be only 0 or 1. You need to reach the goal of the game by using minimum number of operations.

原题链接 ：http://codeforces.com/contest/425/problem/C

Sereja and Two Sequences

sereja has two sequences a1, a2, …, an and b1, b2, …, bm, consisting of integers. One day Sereja got bored and he decided two play with them. The rules of the game was very simple. Sereja makes several moves, in one move he can perform one of the following actions:

1. Choose several (at least one) first elements of sequence a (non-empty prefix of a), choose several (at least one) first elements of sequence b (non-empty prefix of b); the element of sequence a with the maximum index among the chosen ones must be equal to the element of sequenceb with the maximum index among the chosen ones; remove the chosen elements from the sequences.
   2. Remove all elements of both sequences.

The first action is worth e energy units and adds one dollar to Sereja’s electronic account. The second action is worth the number of energy units equal to the number of elements Sereja removed from the sequences before performing this action. After Sereja performed the second action, he gets all the money that he earned on his electronic account during the game.

Initially Sereja has s energy units and no money on his account. What maximum number of money can Sereja get? Note, the amount of Seraja’s energy mustn’t be negative at any time moment.

URL：http://codeforces.com/contest/425/problem/A

题目描述

A. Sereja and Swaps

As usual, Sereja has array a, its elements are integers: a[1],a[2],...,a[n]. Let’s introduce notation:

$$
f \left( a, l, r \right) = \sum_{i=l}^{r} a \left[ i \right]; \ m \left( a \right) = \underset{1 \leq l \leq r \leq n}{max} f \left( a, l, r \right)
$$

A swap operation is the following sequence of actions:

• choose two indexes i, j (i ≠ j);
• perform assignments tmp = a[i], a[i] = a[j], a[j] = tmp.