上题目……本来以为这道题目不用写个日志了的……最后还是悲剧……动规做得少了最近……竟然范这种低级错误……

Gangsters

Description

N gangsters are going to a restaurant. The i-th gangster comes at the time Ti and has the prosperity Pi. The door of the restaurant has K+1 states of openness expressed by the integers in the range [0, K]. The state of openness can change by one in one unit of time; i.e. it either opens by one, closes by one or remains the same. At the initial moment of time the door is closed (state 0). The i-th gangster enters the restaurant only if the door is opened specially for him, i.e. when the state of openness coincides with his stoutness Si. If at the moment of time when the gangster comes to the restaurant the state of openness is not equal to his stoutness, then the gangster goes away and never returns.

The restaurant works in the interval of time [0, T].

The goal is to gather the gangsters with the maximal total prosperity in the restaurant by opening and closing the door appropriately.

Input

?The first line of the input file contains the values N, K, and T, separated by spaces. (1 <= N <= 100 ,1 <= K <= 100 ,0 <= T <= 30000 )

?The second line of the input file contains the moments of time when gangsters come to the restaurant T1, T2, …, TN, separated by spaces. ( 0 <= Ti <= T for i = 1, 2, …, N)

?The third line of the input file contains the values of the prosperity of gangsters P1, P2, …, PN, separated by spaces. ( 0 <= Pi <= 300 for i = 1, 2, …, N)

?The forth line of the input file contains the values of the stoutness of gangsters S1, S2, …, SN, separated by spaces. ( 1 <= Si <= K for i = 1, 2, …, N)

All values in the input file are integers.

Output

Print to the output file the single integer ?the maximal sum of prosperity of gangsters in the restaurant. In case when no gangster can enter the restaurant the output should be 0.

Sample Input

4 10 20<br></br>10 16 8 16<br></br>10 11 15 1<br></br>10 7 1 8<br></br>

Sample Output

26<br></br><br></br>题目意思有点难懂……感觉……看了好几次才看懂到底啥意思，英语水平不够还……其实意思就是门的值没一个time unit可以＋1，－1或者不变，然后对于某一个客人，必须在门的值跟他自己所拥有的一个值相等时才进门，要求总体的P相加最大……典型的动规……当即就想到了方程，直接写程序……写了20分钟吧……感觉最近用VIM写了这么多个程序，速度快了些了……<br></br>然后提交，发现尽然MLE了……仔细一看，发现数组是开大了……于是改成循环数组，循环数组已经很熟了反正……改好再提交，尽然WA了……看了好几遍代码……没有发现错误……最后看时间不早了，就去了Discuss……把里面的测试数据都试了一遍，还是没有找到错误……然后发现这道题目跟上次下的官方数据是一个系列的……于是就拿官方数据测试……发现问题所在了……<br></br>问题在于初始化的时候没有把k＋1的位置初始化，然后在动规的时候又没有检查边界……<br></br>这个问题其实我有两次机会可以避免……第一是初始化的时候……不知道咋想的没有初始化完……话说数组都特意开大了的……以后初始化一定多初始化几位……<br></br>第二是在动规的时候其实可以检查一下边界……对于下界我特意注意过了……对于上界竟然忽略了……不知道当时写代码的时候怎么想的……其实考虑过可能会出问题……但是就是没有去动它……想着少写几行代码……<br></br>不过话说回来……一开始那种单独写一个循环特殊处理下界的办法其实挺dirty的……虽然速度会快一点……dirty的代价就是没有考虑周全……哎……<br></br>话说这么简单的题目……悲剧……多做做题目应该会好些<br></br>

.

先贴题目……这题目犯了个小错误……记下来……

The dog task

Description

Hunter Bob often walks with his dog Ralph. Bob walks with a constant speed and his route is a polygonal line (possibly self-intersecting) whose vertices are specified by N pairs of integers (Xi, Yi) ? their Cartesian coordinates.

Ralph walks on his own way but always meets his master at the specified N points. The dog starts his journey simultaneously with Bob at the point (X1, Y1) and finishes it also simultaneously with Bob at the point (XN, YN). Ralph can travel at a speed that is up to two times greater than his master’s speed. While Bob travels in a straight line from one point to another the cheerful dog seeks trees, bushes, hummocks and all other kinds of interesting places of the local landscape which are specified by M pairs of integers (Xj’,Yj’). However, after leaving his master at the point (Xi, Yi) (where 1 <= i < N) the dog visits at most one interesting place before meeting his master again at the point (Xi+1, Yi+1). Your task is to find the dog’s route, which meets the above requirements and allows him to visit the maximal possible number of interesting places. The answer should be presented as a polygonal line that represents Ralph’s route. The vertices of this route should be all points (Xi, Yi) and the maximal number of interesting places (Xj’,Yj’). The latter should be visited (i.e. listed in the route description) at most once.

An example of Bob’s route (solid line), a set of interesting places (dots) and one of the best Ralph’s routes (dotted line) are presented in the following picture:

Input

The first line of the input contains two integers N and M, separated by a space ( 2 <= N <= 100 ,0 <= M <=100 ). The second line contains N pairs of integers X1, Y1, …, XN, YN, separated by spaces, that represent Bob’s route. The third line contains M pairs of integers X1’,Y1’,…,XM’,YM’, separated by spaces, that represent interesting places. All points in the input file are different and their coordinates are integers not greater than 1000 by the absolute value.

Output

The first line of the output should contain the single integer K ? the number of vertices of the best dog’s route. The second line should contain K pairs of coordinates X1’‘,Y1’’ , …,Xk’‘,Yk’’, separated by spaces, that represent this route. If there are several such routes, then you may write any of them.

Sample Input

4 5
1 4 5 7 5 2 -2 4
-4 -2 3 9 1 2 -1 3 8 -3

Sample Output

6
1 4 3 9 5 7 5 2 1 2 -2 4

题目意思绕了一大通，实际上是个简单的二分图匹配……构图比较麻烦。大概就是1到n－1号表示从第i个点到i+1点,n+1到n＋m表示第i－n个“好玩的地方”，然后如果主人经过这两个点的时间狗来得及逛这个好玩的地方就加一条边……然后就是二分图匹配……
构图的时候犯了个小错误……WA了几次才找出来……一开始为了节约一个sqrt然后直接把
        length1 = sqrt(sqr(route[i].x-route[i+1].x)
                +sqr(route[i].y-route[i+1].y));
        for(j=1; j<=m; j++){
            length2 = sqrt(sqr(route[i].x-place[j].x)
                    +sqr(route[i].y-place[j].y))
                    +sqrt(sqr(route[i+1].x-place[j].x)
                    +sqr(route[i+1].y-place[j].y));
            if(length2 <= length1*2)
                a[i][n+j] = a[n+j][i] = 1;
写成
        length1 = sqr(route[i].x-route[i+1].x)
                +sqr(route[i].y-route[i+1].y));
        for(j=1; j<=m; j++){
            length2 = sqr(route[i].x-place[j].x)
                    +sqr(route[i].y-place[j].y)
                    ＋sqr(route[i+1].x-place[j].x)
                    +sqr(route[i+1].y-place[j].y)；
            if(length2 <= length1*2)
                a[i][n+j] = a[n+j][i] = 1;





还以为结果一样对……然后改的时候继续犯迷糊，把下面的两倍改成4倍……然后有点醒悟，把sqrt加上去了……但是length2的sqrt竟然忘了加……不过所幸这次发现错误没花多久时间……直接静态的看代码就发现错误了……没有到出动GDB的程度还万幸……

悲剧的一道题目……
先上题目吧……
Fence
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 1998 Accepted: 627
Description
There is an area bounded by a fence on some flat field. The fence has the height h and in the plane projection it has a form of a closed polygonal line (without self-intersections), which is specified by Cartesian coordinates (Xi, Yi) of its N vertices. At the point with coordinates (0, 0) a lamp stands on the field. The lamp may be located either outside or inside the fence, but not on its side as it is shown in the following sample pictures (parts shown in a thin line are not illuminated by the lamp):

The fence is perfectly black, i.e. it is neither reflecting, nor diffusing, nor letting the light through. Research and experiments showed that the following law expresses the intensity of light falling on an arbitrary illuminated point of this fence:
I0=k/r

where k is a known constant value not depending on the point in question, r is the distance between this point and the lamp in the plane projection. The illumination of an infinitesimal narrow vertical board with the width dl and the height h is
dI=I0|cosα|dl*h

where I0is the intensity of light on that board of the fence, α is the angle in the plane projection between the normal to the side of the fence at this point and the direction to the lamp.
You are to write a program that will find the total illumination of the fence that is defined as the sum of illuminations of all its illuminated boards.
Input
The first line of the input file contains the numbers k, h and N, separated by spaces. k and h are real constants. N (3 <= N <= 100) is the number of vertices of the fence. Then N lines follow, every line contains two real numbers Xi and Yi, separated by a space.
Output
Write to the output file the total illumination of the fence rounded to the second digit after the decimal point.
Sample Input
0.5 1.7 3
1.0 3.0
2.0 -1.0
-4.0 -1.0
Sample Output
5.34

题目名字是fence，让我想起了悲剧的fence4……记得fence4让我卡了1个多月……这次的fence也很悲剧……
题目是计算几何的，意思其实听简单的，分析过后，其实就是先判断点是不是在多边形里面，是的话就输出hk2PI,不是的话就求出张角，然后输出hk*张角。
判断点是否在多边形内部有经典算法，直接baidu。搞定之后就是求张角的问题了。话说计算几何这东西真麻烦……本来挺直观的几何，到了计算机里面反而变 得这么麻烦了……想了半天想不到怎么弄……然后这会儿同寝室的星星正在Dota＋音乐……思绪更加乱了……最后想到一个很猥琐的办法……把每一条边的两个 端点与原点连线的倾斜角都求出来，然后按照逆时针方向，前面的放在数组rad1，后面的放在rad2里面，这样最后的张角就因该是rad2逆时针最外的角 度减去rad1中顺时针最外的角度。具体判断的时候可以把rad1里面的每一个点都减去一个很小的角度，再跟没一条边判断是否相交。只有最靠外的点才能够 满足不与任何一条边相交。rad2也用类似的处理方法。
写好程序之后提交了一下，几乎是不抱希望的……事实也很凄惨，直接WA了……调试了一下最后还是决定找官方测试数据……找到官方测试数据之后调试，最终发现了3个错误。
错误1：忘记考虑一种伪包围的情况，也就是多边形的两个端点重合或者在同一条直线上，这时候利用经典算法判断结果是不包围，但是在判断张角的时候又会出错，解决办法就是在判断张角的时候特殊处理一下伪包围的情况。
错误2：尽然在判断是否相交的函数里面把一个x写成了y，泪奔……

这时候提交了一次，发现还是WA，但是此时已经手动测试通过了官方的所有数据，于是在POJ里面换编译器为C＋＋，居然就AC了……当然不能就这样 善罢甘休，于是引出了问题3：为什么C＋＋可以AC，G＋＋就不能……看到Discuz有人说把％lf换成％f就可以。于是就把所有的％lf都换成 了％f，然后还是WA，这时候连C＋＋都WA了……又换回去，试着只改printf里面的％lf，然后发现AC了。也就是说在G＋＋里面printf必须 用％f，而C＋＋里面都可以，但是scanf里面必须都是％lf……真复杂……于是baidu了一下，还真发现原因了……
地址：http://book.csdn.net/bookfiles/892/10089228074.shtml
问：有人告诉我不能在printf中使用%lf。为什么printf()用%f输出double型，而scanf却用%lf呢？
答：printf 的%f说明符的确既可以输出float型又可以输出double型。根据“默认参数提升”规则（在 printf这样的函数的可变参数列表中，不论作用域内有没有原型，都适用这一规则）float型会被提升为double型。因此printf()只会看 到双精度数。参见问题15.2。

对于scanf，情况就完全不同了，它接受指针，这里没有类似的类型提升。（通过指针）向float存储和向double存储大不一样，因此，scanf区别%f和%lf。

居然还有这玄机……算是这道题目的另外一个收获吧……

上题目：

Description

One of the participants of both regional contests which took place in St. Petersburg decided to determine overall rating for all teams that took part in at least one contest.
This participant assigned each team a unique team identifier, which was an integer from 1 to 100 inclusively. For each contest team identifiers of the participating teams were written in a column according to their place in that contest. Identifiers of the teams that had equal results were written on the same line. The participant started with the team(s) that was(were) the best in that contest (writing them on the first line) and continued in the order of decreasing results.
Definition: Let’s say that the team has place K in the contest if exactly K-1 teams performed in that contest better.

Consider the following examples of two contests’ results:

The overall rating for the teams which took part in both contests is defined in the following way:

1) If some team performed better in both contests than some other team (or better in one contest and with the same result in the other contest) then the overall rating of the former team is higher than the rating of the latter team.

2) If one of the teams in question performed better in one contest and the other team performed better in another contest then their overall rating depends on the difference of their places in both contests. So, in our example team 1 is better than team 5 in the first contest with a difference of 3 places and worse in the second contest with a difference of only 1 place, therefore the overall rating of team 1 is higher than team 5’s one. If the difference of the places is the same for both contests then that teams have the equal overall ratings. The latter is also true for the teams that performed equally in both contests.

In our example only teams 1, 4, 5, and 9 participated twice. Team 1 has the highest rating, teams 5 and 9 with the equal rating follow, and team 4 has the lowest rating.

For the teams that participated in one contest only the overall rating and their position in the resulting list cannot be always determined. They are included in the overall list (where the teams which participated twice already placed according to the rules above) if one of the following takes place:

A) If there is a team that participated in both contests and shared the place in one of the contests with the team in question then the latter team shares the overall rating with this team too (if there is more than one such team, then they all should have the same overall rating, otherwise the overall rating of the team in question cannot be determined).

B) If there is a position in the overall list (either at the beginning of the list, at the end of the list, or between some lines), such that before this position only the teams are located which performed better in the same contest as the team in question and after this position only the teams are located which performed worse in the same contest as the team in question, then the team in question occupies this position in the overall list. If more than one team claim to have the same position in the overall list, then their mutual order is defined by their places in their contests (look at the example below for details).

?Team 3 will occupy the first place in the overall list (rule B).

?The positions of teams 6 and 7 cannot be determined.

?Team 10 will share the overall rating with team 1 (rule A).

?Team 20 will share the overall rating with team 4 (rule A).

?Team 19 will occupy the position between teams 9, 5 and team 4 (rule B).

?Teams 8, 15, 17, 18, 21, and 31 will finish the overall list (rule B). But the first of them will be teams 15 and 8 (that took 6th place) followed by teams 31 and 18 (that took 8th place) and teams 17 and 21 (that took 10th place).

Your task is to write a program that will create the overall rating list using the result tables of two contests and the given rules.

Input

The input file contains a description of the two contests, which are separated by an empty line. Each description starts with a line containing the single integer N (1 <= N <= 100) that indicates how many lines of the contest result table follow. Each line of the contest result table consists of one or more team identifiers separated by spaces.

Every team identifier occurs at most once in the description of each contest.

Output

Write to the output file one or more lines with the team identifiers (separated by spaces) that represent the overall rating list. The teams that share the same rating (thus written on the same line) is written in ascending order. The teams for which the overall rating is not determined should be absent in the output file.

Sample Input

6<br></br>9<br></br>7 1 4<br></br>5<br></br>15 8<br></br>31 18<br></br>17<br></br><br></br>8<br></br>3<br></br>5<br></br>1 10<br></br>6<br></br>9<br></br>19<br></br>4 20<br></br>21<br></br>

Sample Output

3<br></br>1 10<br></br>5 9<br></br>19<br></br>4 20<br></br>8 15<br></br>18 31<br></br>17 21

看到这题目通过率16％一下子就有点怕怕……看了题目感觉还行，就是很烦。想了一下，大概想出个思路，就是把参加了两次比赛的队伍的两次比赛名次分别加起来，然后排序，就能够得到前两条规则需要的排名，第三条规则也比较方便，只要遍历一次就OK了。第四条规则一开始没想清楚，主要是对于没有同时参加同一场比赛的队伍的排名理解没有搞清楚。这时候犯了个错误，急着写代码了。写出来代码很乱，有7层嵌套居然……看得都头晕……自然没有AC。WA了，受不了，直接找比赛当年的测试数据。20个数据对了17个，18，只有一点点错误，19，20就错的很离谱。仔细调试了一下数据18，发现算法有问题……悲剧中的悲剧……时间不早了，于是睡觉。睡觉前仔细地想了一下第四条规则，想出一个比较方便的办法。

前三条规则不变，数组多开1位，存放表示只参加了某场比赛的那场的名次，然后插入的时候直接把名次复制上面那位，到时候排序的时候进行双关键字排序。具体执行的时候又可以把第一个关键字乘以一个很大的数字，比如10000，然后加上第二个关键字，这样子只要一次排序。不过就是因为这个小技巧……又WA了一次。把无法确定位置的队伍排序进去了。

贴代码：

#include #include

const int n = 100;

int rate[110][5];
//rate[i][0]表示第一次比赛排名,[i][1]表示第二次比赛排名,
//对于[i][2]，两次比赛都参加的就是前两次比赛相加，通过第3条规则确定排名的就是复制与他对应的队伍的排名
//通过第4条规则确定排名的就是复制他上面离他最近的那个队伍的数值。
//[i][3]对于参加了两次比赛以及通过第3条规则确定排名的队伍都是0，通过第四条规则确定排名的队伍就是参加
//的那次比赛的排名。这样子进行一次排序，[i][2]为主关键字，[i][3]为次关键字就能得到答案
int a[110][2];
char tmp[10000];

void aSort(int a[110][2])
{
int i, j, tmp;
for(i=1; i<=n; i++){
for(j=n; j>i; j–){
if(a[j][0] < a[j-1][0]){
tmp = a[j][0];
a[j][0] = a[j-1][0];
a[j-1][0] = tmp;
tmp = a[j][1];
a[j][1] = a[j-1][1];
a[j-1][1] = tmp;
}
}
}
}

int main()
{
int n1, n2, now, num, i, j, k, t, Changed, upMax, upMin, downMax, downMin;
memset(rate, 0, sizeof(rate));
for (t = 0; t < 2; t++) {
scanf(“%d\n”, &n1);
now = 1;
for (i = 1; i <= n1; i++) {
num = 0;
gets(tmp);
while(strlen(tmp) == 0)
gets(tmp);
for (j = 0; j < strlen(tmp); j++) {
if (tmp[j] <= ‘9’ && tmp[j] >= ‘0’) {
sscanf(tmp + j, “%d”, &k);
rate[k][t] = now;
num++;
while (tmp[j] <= ‘9’ && tmp[j] >= ‘0’) {
j++;
}
}
}
now += num;
}
}
for (i = 1; i <= n; i++) {
if (rate[i][0] != 0 && rate[i][1] != 0) {
rate[i][2] = (rate[i][0] + rate[i][1]);
}
if (rate[i][0] == 0 || rate[i][1] == 0){
rate[i][3] = rate[i][0] + rate[i][1];
}
}

Changed = true;
Changed = false;
for (t = 0; t <= 1; t++) {
for (i = 1; i <= n; i++) {
if (rate[i][2] == 0 && rate[i][t] != 0) {
//通过规则A确定排名
for (j = 1; j <= n; j++){
if (rate[j][2] != 0 && rate[j][3] == 0 && rate[j][t] == rate[i][t]) {
if(rate[i][2] == 0 || rate[i][2] == rate[j][2])
rate[i][2] = rate[j][2];
else{
rate[i][2] = 0;
Changed = 3;//多种不同位置冲突，
&nbs; p; break;
}
}
}
if(rate[i][2] != 0){
Changed = true;
rate[i][3] = 0;
continue;
}
if(Changed == 3){//多种不同位置冲突
Changed = false;
continue;
}
//通过规则B确定排名
upMax = downMax = -100000000;
upMin = downMin = 100000000;
for (j=1; j<=n; j++){
if (rate[j][2] != 0 && rate[j][3] == 0){
if(rate[j][t] != 0 && rate[j][t] < rate[i][t]){
if(upMax < rate[j][2])
upMax = rate[j][2];
if(upMin > rate[j][2])
upMin = rate[j][2];
}
if(rate[j][t] != 0 && rate[j][t] > rate[i][t]){
if(downMax < rate[j][2])
downMax = rate[j][2];
if(downMin > rate[j][2])
downMin = rate[j][2];
}
}
}
if(upMax >= downMin)
continue;
if(upMax == -100000000 && upMin == 100000000 && downMin != 100000000){
Changed = true;
rate[i][2] = downMin - 1;
continue;
}
if(downMax == -100000000 && downMin == 100000000 && upMax != -100000000){
Changed = true;
rate[i][2] = upMax + 1;
continue;
}
rate[i][2] = upMax;
Changed = true;
continue;
}
}
}

memset(a, 0, sizeof(a));
for(i=1; i<=n; i++) {
if (rate[i][2] != 0) {
a[i][0] = rate[i][2]*10000 + rate[i][3];
a[i][1] = i;
}
}
aSort(a);
for(i=1; i<=n; i++){
if(a[i][0] == 0)
continue;
memset(tmp, 0, sizeof(tmp));
for(j=1; j<=n; j++){
if(a[j][0] == a[i][0])
sprintf(tmp + strlen(tmp), “%d “, a[j][1]);
}
tmp[strlen(tmp)-1] = ‘\0’;
printf(“%s\n”, tmp);
while(a[i][0] == a[i+1][0] && i <= n)

; i++;
}
/for(i=1; i<=n; i++){
if(a[i][0] == 0)
continue;
printf(“%d %d %d %d\n”, a[i][1], a[i][0], rate[a[i][1]][2], rate[a[i][1]][3]);
}/
}

Description

Bob and Alice started to use a brand-new encoding scheme. Surprisingly it is not a Public Key Cryptosystem, but their encoding and decoding is based on secret keys. They chose the secret key at their last meeting in Philadelphia on February 16th, 1996. They chose as a secret key a sequence of n distinct integers, a1 ; . . .; an, greater than zero and less or equal to n. The encoding is based on the following principle. The message is written down below the key, so that characters in the message and numbers in the key are correspondingly aligned. Character in the message at the position i is written in the encoded message at the position ai, where ai is the corresponding number in the key. And then the encoded message is encoded in the same way. This process is repeated k times. After kth encoding they exchange their message.

The length of the message is always less or equal than n. If the message is shorter than n, then spaces are added to the end of the message to get the message with the length n.

Help Alice and Bob and write program which reads the key and then a sequence of pairs consisting of k and message to be encoded k times and produces a list of encoded messages.

Input

The input file consists of several blocks. Each block has a number 0 < n <= 200 in the first line. The next line contains a sequence of n numbers pairwise distinct and each greater than zero and less or equal than n. Next lines contain integer number k and one message of ascii characters separated by one space. The lines are ended with eol, this eol does not belong to the message. The block ends with the separate line with the number 0. After the last block there is in separate line the number 0.

Output

Output is divided into blocks corresponding to the input blocks. Each block contains the encoded input messages in the same order as in input file. Each encoded message in the output file has the lenght n. After each block there is one empty line.

Sample Input

10<br></br>4 5 3 7 2 8 1 6 10 9<br></br>1 Hello Bob<br></br>1995 CERC<br></br>0<br></br>0<br></br>

Sample Output

BolHeol  b<br></br>C RCE<br></br><br></br>题目的难点在于K很大，直接想到利用二进制思想，先求出每一位经过2^k次加密所得的位置，然后再求经过t次加密所得的位置，Discuz里面很多人提到直接求出每一位多少次能够循环，然后再取模，感觉比我的方法写起来要方便不少应该……<br></br>做的时候出现了几个小错误，都是出在预处理。一个是在预处理的时候下标顺序出错了，应该把j放在外循环。另外一个是不知道怎么的昏头了预处理的时候折腾出来一个i-1，囧……<br></br>贴代码：<br></br>#include <stdio.h><br></br>#include <string.h><br></br><br></br>int a[220][40];//a[i][j]表示第i个字母经过2^j次加密后所在的位置<br></br>int b[220], c[220];<br></br><br></br>int main(){<br></br>    int n, i, j, time;<br></br>    char s[220], tmp[220];<br></br>    i = 1;<br></br>    while(1){<br></br>        scanf("%d", &n);<br></br>        if(n <= 0)<br></br>            return 0;<br></br>        memset(a, 0, sizeof(a));<br></br>        memset(b, 0, sizeof(b));<br></br>        for(i=1; i<=n; i++)<br></br>            scanf("%d", &b[i]);<br></br>        for(i=1; i<=n; i++){<br></br>            a[b[i]][0] = i;<br></br>        }<br></br>for(j=1; j<40; j++){<br></br>            for(i=1; i<=n; i++){<br></br>                a[i][j] = a[a[i][j-1]][j-1];<br></br>time = i;<br></br>            }<br></br>        }<br></br>        while(1){<br></br>            scanf("%d", &time);<br></br>            if(time <= 0)<br></br>                break;<br></br>            gets(s);<br></br>            for(i=strlen(s); i<=n; i++)<br></br>                s[i] = ' ';<br></br>            s[i+1] = '\0';<br></br>            for(i=1; i<=n; i++)<br></br>                c[i] = i;<br></br>            j = 0;<br></br>            while(time > 0){<br></br>                if(time % 2 > 0){<br></br>                    for(i=1; i<=n; i++)<br></br>                        c[i] = a[c[i]][j];<br></br>                }<br></br>time = time / 2;<br></br>j++;<br></br>}<br></br>for (i = 1; i <= n; i++) {<br></br>tmp[i-1] = s[c[i]];<br></br>//printf("%c", s[c[i]]);<br></br>}<br></br>tmp[i-1] = '\0';<br></br>printf("%s\n", tmp);<br></br>//printf("\n");<br></br>}<br></br>printf("\n");<br></br>}<br></br>}<br></br><br></br>

又一道悲剧的题目……不过这次的悲剧更多的是POJ的悲剧……

题目意思其实不太复杂，赤裸裸的模拟题，非常烦的模拟……据说做的时候会有人看直播围观……

Description

The Department of Security has a new headquarters building. The building has several floors, and on each floor there are rooms numbered xxyy where yy stands for the room number and xx for the floor number, 0 < xx; yy <= 10. The building has ‘pater-noster’ elevator, i.e. elevator build up from several cabins running all around. From time to time the agents must visit the headquarters. During their visit they want to visit several rooms and in each room they want to stay for some time. Due to the security reasons, there can be only one agent in the same room at the same time, The same rule applies to the elevators. The visits are planned in the way ensuring they can be accomplished within one day. Each agent visits the headquarters at most once a day.

Each agent enters the building at the 1st floor, passes the reception and then starts to visit the rooms according to his/her list. Agents always visit the rooms by the increasing room numbers. The agents form a linear hierarchy according to which they have assigned their one letter personal codes. The agents with higher seniority have lexicographically smaller codes. No two agents have the same code.

If more then one agent want to enter a room, or an elevator, the agents have to form a queue. In each queue, they always stand according to their codes. The higher the seniority of the agent, the closer to the top of the queue he stands. Every 5 s (seconds) the first agent in the queue in front of the elevator enters the elevator. After visiting the last room in the headquarters each agent uses if necessary elevator to the first floor and exits the building.

The times necessary to move from a certain point in the headquarters to another are set as follows: Entering the building, i.e. passing the reception and reaching the elevator, or a room on the first floor takes 30 s. Exiting the building, i.e. stepping out of the elevator or a room on the first floor and passing the reception takes also 30 s. On the same floor, the transfer from the elevator to the room (or to the queue in front of the room), or from the room to the elevator (or to the queue in front of the elevator), or from one room to another (or to the queue in front of the room) takes 10 s. The transfer from one floor to the next floor above or below in an elevator takes 30 s. Write a program that determines time course of agent’s visits in the headquarters.

Input

The input file contains the descriptions of n >= 0 visits of different agents. The first line of the description of each visit consists of agent’s one character code C, C = A, . . ., Z, and the time when the agent enters the headquarters. The time is in the format HH:MM:SS (hours, minutes, seconds). The next lines (there will be at least one) contain the room number, and the length of time intended to stay in the room, time is in seconds. Each room is in a separate line. The list of rooms is sorted according to the increasing room number. The list of rooms ends by the line containing 0. The list of the descriptions of visits ends by the line containing the character dot.

Output

The output contains detailed records of each agent’s visit in the headquarters. For each agent, there will be a block. Blocks are ordered in the order of increasing agent’s codes. Blocks are separated by an empty line. After the last block there is an empty line too. The first line of a block contains the code of agent. Next lines contain the starting and ending time (in format HH:MM:SS) and the descriptions of his/her activity. Time data will be separated by one blank character. Description will be separated from time by one blank character. Description will have a form Entry, Exit or Message. The Message can be one of the following: Waiting in elevator queue, Waiting in front of room RoomNumber, Transfer from room RoomNumber to room RoomNumber, Transfer from elevator to room RoomNumber, Transfer from RoomNumber to elevator, Stay in room RoomNumber, Stay in elevator.

Sample Input

A 10:00:00<br></br>0101 100<br></br>0110 50<br></br>0202 90<br></br>0205 50<br></br>0<br></br>B 10:01:00<br></br>0105 100<br></br>0201 5<br></br>0205 200<br></br>0<br></br>.<br></br>

Sample Output

A<br></br>10:00:00 10:00:30 Entry<br></br>10:00:30 10:02:10 Stay in room 0101<br></br>10:02:10 10:02:20 Transfer from room 0101 to room 0110<br></br>10:02:20 10:03:10 Stay in room 0110<br></br>10:03:10 10:03:20 Transfer from room 0110 to elevator<br></br>10:03:20 10:03:50 Stay in elevator<br></br>10:03:50 10:04:00 Transfer from elevator to room 0202<br></br>10:04:00 10:05:30 Stay in room 0202<br></br>10:05:30 10:05:40 Transfer from room 0202 to room 0205<br></br>10:05:40 10:07:40 Waiting in front of room 0205<br></br>10:07:40 10:08:30 Stay in room 0205<br></br>10:08:30 10:08:40 Transfer from room 0205 to elevator<br></br>10:08:40 10:09:10 Stay in elevator<br></br>10:09:10 10:09:40 Exit<br></br><br></br>B<br></br>10:01:00 10:01:30 Entry<br></br>10:01:30 10:03:10 Stay in room 0105<br></br>10:03:10 10:03:20 Transfer from room 0105 to elevator<br></br>10:03:20 10:03:25 Waiting in elevator queue<br></br>10:03:25 10:03:55 Stay in elevator<br></br>10:03:55 10:04:05 Transfer from elevator to room 0201<br></br>10:04:05 10:04:10 Stay in room 0201<br></br>10:04:10 10:04:20 Transfer from room 0201 to room 0205<br></br>10:04:20 10:07:40 Stay in room 0205<br></br>10:07:40 10:07:50 Transfer from room 0205 to elevator<br></br>10:07:50 10:08:20 Stay in elevator<br></br>10:08:20 10:08:50 Exit<br></br>

做的时候用到了链表，然后运行结果是Runtime error…于是找可能超界或者其他啥导致Runtime error的地方，找到了一些没注意到的可能产生错误的地方，比如一个地方合并Waiting状态的时候没有考虑node->next是NULL的情况，不过改了还是继续Runtime error。找到原题的测试数据，基本上对的上，最后一点点明显是原题的结果有问题，排除了程序错误。最后没办法，就一点点注释掉代码来找错误的地方……（我可怜的通过率。。。。。。）最后发现竟然是在遍历链表的时候出错……看了一遍又一遍我的链表程序，确认没有出错……最后没办法，把动态申请链表空间改成一次性开了一个20W的数组，尽然就AC了……通过的时候内存只1500多K，离超内存还很远……POJ的BUG了……悲剧的……

说一下这道题目吧，关于电梯容易理解错，其实题目的意思是没5秒钟没层楼都有一部电梯，这部电梯既可以向上，也可以向下……然后各层楼电梯不会相撞以及其他更加诡异的……

具体做的时候我没有创建排队这么个东西，而是记录每个人当前的时间以及所处状态，然后循环找到时间最靠前的人，应为编号小的人优先级高，这样子很方便的处理了排队问题。然后通过当前状态推得下一步状态，继续刷时间啥的……悲剧，说不清楚……贴代码……写了300行不到点，有些东西有点多余，重写的话估计能够200行左右写完。

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  

#define max(a, b) ((a)>(b)?(a):(b))  
enum ActiveType{Waiting, Going, Staying};  

typedef struct Active{  
	ActiveType activeType;  
	int PlaceStart;//前两位表示层数，后一位0表示刚刚到这层，1到10表示10个房间，  
	int PlaceEnd; //11表示上楼或下楼的电梯，0112表示下到底层电梯,0113表示已经出楼  
	int TimeStart;  
	int TimeOver;  
	Active *Next;  
}Active;  

int toView[35][100][100];  
int enterTime[35];  
Active Actives[35];  
Active *Status[35];//当前状态  
int now;  
int roomFree[15][100];  
Active aaaaa[200000];  
int bbbbb;  

void printRoom(int room)  
{  
	if(room%100 == 0 || room%100 == 11 || room%100 == 12)  
		printf("elevator");  
	else{  
		char tmp[100];  
		sprintf(tmp, "%2d%2d", room/100, room%100);  
		for(int i=0; i<10; i++)  
			if(tmp[i] == ' ')  
				tmp[i] = '0';  
		printf("room %s", tmp);  
	}  
}  

void printTime(int time)  
{  
	char tmp[100];  
	sprintf(tmp, "%2d:%2d:%2d", time/3600, time/60%60, time%60);  
	int i;  
	for(i=0; i<8; i++)  
		if(tmp[i] == ' ')  
			tmp[i] = '0';  
	printf("%s ", tmp);  
}  

void printnode(Active *active)  
{  
	if(active->PlaceEnd == 100 || active->TimeOver == 100000000)  
		return;  
	else{  
		printTime(active->TimeStart);  
		printTime(active->TimeOver);  
	}  
	if(active->PlaceStart == 100){  
		printf("Entry\n");  
	}  
	else if(active->PlaceEnd == 113){  
		printf("Exit\n");  
	}  
	else if(active->PlaceEnd % 100 == 0){  
		printf("Stay in elevator\n");  
	}  
	else if(active->activeType == Waiting){  
		if(active->PlaceEnd % 100 == 11)  
			printf("Waiting in elevator queue\n");  
		else{  
			printf("Waiting in front of ");  
			printRoom(active->PlaceEnd);  
			printf("\n");  
		}  
	}  
	else if(active->activeType == Going){  
		printf("Transfer from ");  
		printRoom(active->PlaceStart);  
		printf(" to ");  
		printRoom(active->PlaceEnd);  
		printf("\n");  
	}  
	else if (active->activeType == Staying){  
		printf("Stay in ");  
		printRoom(active->PlaceEnd);  
		printf("\n");  
	}  
}  

void print(int code)  
{  
	Active *tmp;  
	tmp = &Actives[code];  

	printf("%c\n", 'A'+code);  
	while(tmp!= NULL) {  
		if (tmp->Next != NULL) {  
			if (tmp->activeType == Waiting && tmp->Next->activeType == Waiting)  
				&nbs;
			p; tmp->Next->TimeStart = tmp->TimeStart;  
			else  
				printnode(tmp);  
		} else  
			printnode(tmp);  
		tmp = tmp->Next;  
	}  
	printf("\n");  
}  

int Time2Int(char time[])  
{  
	int a, b, c;  
	sscanf(time, "%d:%d:%d", &a, &b, &c);  
	return (a*60+b)*60+c;  
}  

int InitList(char code)  
{  
	int a, b;  
	char s[100];  
	scanf("%s", s);  
	if(code < 'A' || code > 'Z')  
		exit(0);  
	enterTime[code-'A'] = Time2Int(s);  
	while(1){  
		scanf("%d", &a);  
		if(a == 0)  
			return 0;  
		scanf("%d", &b);  
		toView[code-'A'][a/100][a%100] = b;  
	}  
	return 0;  
}  

int GetNextActive(int code, int *timeEnd, ActiveType *active, int *PlaceStart, int *PlaceEnd)  
{  
	int i, j, k, tt;  
	tt=Status[code]->activeType;  
	k = Status[code]->PlaceEnd;  
	if(k / 100 > 10 || k / 100 < 0 || k % 100 > 13 || k % 100 < 0)  
		exit(0);  
	if(code > 26 || code < 0)  
		exit(0);  
	roomFree[k/100][11] = (max(roomFree[k/100][11], now)-1)/5*5+5;  
	if (tt == Staying) {//刚刚从某个房间或者电梯出来  
		i = k / 100;  
		j = k % 100;  
		if (i == 0)  
			i ++;  
		if(k == 112){//准备出楼  
			*timeEnd = now+30;  
			*active = Going;  
			*PlaceStart = k;  
			*PlaceEnd = 113;  
			return 0;  
		}  
		for (; j <= 10; j++)  
			if (toView[code][i][j] > 0) {//本层还有房间要参观,走到那个房间  
				if(k != 100)  
					*timeEnd = now+10;  
				else  
					*timeEnd = now+30;  
				*active = Going;  
				*PlaceStart = k;  
				*PlaceEnd = i*100+j;  
				return 0;  
			}  
		for(i=i+1; i<=10; i++)  
			for(j=1; j<=10; j++)  
				if(toView[code][i][j] > 0){//上层有房间要参观，走到电梯  
					if (k != 100)  
						*timeEnd = now+10;  
					else  
						*timeEnd = now+30;  
					*active = Going;  
					*PlaceStart = k;  
					if (k != 0)  
						*PlaceEnd = k/100*100+11;  
					else  
						*PlaceEnd = 100+11;  
					return 0;  
				}  
		//无房间参观，出楼  
		if (k / 100 == 1) {//在一楼  
			*timeEnd = now + 30;  
			*active = Going;  
			*PlaceStart = k;  
			*PlaceEnd = 113;  
			return 0;  
		} else {//去电梯下1楼  
			*timeEnd = now+10;  
			*active = Going;  
			*PlaceStart = k;  
			*PlaceEnd = k/100*100+11;  
			return 0;  
		}  
	}  
	else if (tt == Waiting || tt == Going){//正在某个房间或者电梯等待以及走向某个房间或者电梯  
		if (k == 113) {//已经出楼  
			*timeEnd = 100000000;  
			*active = Staying;  
			&
				nbsp; *PlaceStart = *PlaceEnd = 113;  
			return 0;  

		}  
		if(roomFree[k/100][k%100] > now){//继续等待  
			*active = Waiting;  
			*timeEnd = roomFree[k/100][k%100];  
			*PlaceStart = *PlaceEnd = k;  
			return 0;  
		}  
		else {  
			*active = Staying;  
			if (k % 100 == 11) {//进电梯  
				roomFree[k / 100][k % 100] = now + 5;  
				for (i = k / 100 + 1; i <= 10; i++){  
					for (j = 1; j <= 10; j++)  
						if (toView[code][i][j] > 0) {//上楼  
							*timeEnd = now + (i - k / 100)*30;  
							*active = Staying;  
							*PlaceStart = k;  
							*PlaceEnd = i * 100;  
							roomFree[k/100][k%100] = now+5;  
							return 0;  
						}  
				}  
				*timeEnd = now + (k / 100 - 1)*30;  
				*active = Staying;  
				*PlaceStart = k;  
				*PlaceEnd = 112;  
				roomFree[k/100][k%100] = now+5;  
				return 0;  
			} else {//进房间  
				*timeEnd = now + toView[code][k / 100][k % 100];  
				*active = Staying;  
				*PlaceStart = *PlaceEnd = k;  
				toView[code][k / 100][k % 100] = 0;  
				roomFree[k / 100][k%100] = *timeEnd;  
				return 0;  
			}  
		}  
	}  
	return 0;  
}  

int main()  
{  
	bbbbb=0;  
	char s[100];  
	int i, k;  
	memset(toView, 0, sizeof(toView));  
	memset(enterTime, 0, sizeof(enterTime));  
	memset(Actives, 0, sizeof(Actives));  
	memset(roomFree, 0, sizeof(roomFree));  
	while(1){  
		scanf("%s", s);  
		if(s[0] == '.')  
			break;  
		InitList(s[0]);  
	}  
	for(i=0; i<30; i++)  
		if(enterTime[i] > 0){  
			Actives[i].PlaceStart = Actives[i].PlaceEnd= 100;  
			Actives[i].Next = NULL;  
			Actives[i].TimeStart = Actives[i].TimeOver = enterTime[i];  
			Actives[i].activeType = Staying;  
			Status[i] = &Actives[i];  
		}  
		else{  
			Actives[i].TimeOver = 100000000;  
			Actives[i].Next = NULL;  
			Status[i] = &Actives[i];  
		}  
	Status[29]->TimeOver = 100000000;  
	while(1){  
		k = 29;  
		for(i=0; i<26; i++)  
			if(Status[i]->TimeOver < Status[k]->TimeOver)  
				k = i;  
		if (Status[k]->TimeOver == 100000000)  
			break;  
		now = Status[k]->TimeOver;  
		//Active *tmp = &aaaaa[bbbbb++];  
		Active *tmp = new Active;  
		if(bbbbb >= 200000)  
			exit(0);  
		tmp->TimeStart = Status[k]->TimeOver;  
		GetNextActive(k, &tmp->TimeOver, &tmp->activeType, &tmp->PlaceStart, &tmp->PlaceEnd);  
		tmp->Next == NULL;  
		Status[k]->Next = tmp;  
		Status[k] = tmp;  
	}  
	for(i=0; i<26; i++)  
		&nbs;
	p; if(enterTime[i]> 0)  
		print(i);  
	return 0;  
} 

今晚搞了很久各种电脑，最后亲亲断网了才开起电脑，于是在POJ找了道简单的题目做，看了POJ1050通过率50%多，想着应该用不了多久，就准备做这个了。

Description

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:

9 2
-4 1
-1 8
and has a sum of 15.

Input

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

Output

Output the sum of the maximal sub-rectangle.

Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

Sample Output

15

初看题目，第一感觉是直接枚举，复杂度是1亿级别的……显然不行，仔细想想，发现可以做一个优化，直接开两个数组，在100100100的时间里面可以算出同一行或者同一列任意两个点范围内的和，这两个数组显然可以让题目做出来方便很多，但是枚举估计还是不行。再想想，题目应该可以动规，a[i][j][k]表示左边界为k的情况下，右下角点为i,j时所能达到的最大值。递推方程找到了。于是开工。具体写的时候思路很混乱……i,j,k具体表示什么搞得越来越糊涂，最后写递推的时候发现预处理出来的两个和数组只需要用一个，先用了其中一个，发现答案不对，于是另外一个，样例答案对了，直接提交，MLE……悲剧……发现内存只有10M,于是删掉不用的那个数组，提交,WA了……大悲剧……不过也在意料之中，因为思路太混乱了……自己想到个特殊情况的测试数据，3*3的矩阵全是-1，测试了一下，发现不能过。于是就开始检查，越检查发现思路越混乱……于是拿了张纸把数组具体表示什么仔仔细细的写下来……终于思路清晰了……修改了一下程序，终于过了……

最近一直没做题目的关系吧……思路太混乱了……多练练应该会好点……还有把思路写下来确实挺有效的……话说以前写程序都不用这样子的……悲剧……

悲剧的题目，写出来之后调试了好久，最后对着测试数据调试，终于找到错的地方。写错变量名啊啥的错误……还有一个是忘记考虑边界清空。如果在重置数组的时候没有贪时间把整个数组都重置的话应该是能够早一点发现错误的吧应该……忘记考虑边界……很悲剧……还有一个是strlen搞错……更加悲剧……POJVolume1，还有69道……

第一章 抽象 将公共的抽象提取出来放到基类中。 一个类应该能够描述一组对象。 如果派生类之间的区别在于属性，则用数据成员来表示；如果在于行为，则用虚函数来表示。 如果通过共有继承来产生派生类，那么这个派生类应该是其基类的特化。 多态性并不是所有程序设计问题的解决方案 第二章 一致性 构造函数应该使得对象处于定义明确的状态。 我们应该考虑使用默认参数的形式来代替函数重载的形式。 用一致的方式来定义对象的状态——这需要识别出类不变性。 类的接口定义应该是一致的——避免产生困惑。 对于每个new操作，都有相应的delete操作。 避免对从不使用的状态信息进行计算和储存。 在定义operator=时，我们要注意x=x这种情况。 用一个通用的函数来代替重复的表达式序列。 第三章 不必要的继承 我们要找出简单的抽象。 我们要识别出队实现的继承；可以使用私有基类或者（更好的办法是）使用成员对象。 我们应该考虑使用默认参数的形式来代替函数重载的形式。 第四章虚函数 派生类在处理继承而来的状态时必须与基类保持一致。 如果在共有基类中没有定义虚析构函数，那么在所有的派生类或者派生类的数据成员中都应该没有定义析构函数。 通常情况下，共有基类的析构函数应该被声明为虚函数。 将共同的行为迁移到基类中。 降低耦合性——将类之间的交互最小化。 如果派生类之间的区别在于属性，则用数据成员来表示；如果在于行为，则用虚函数来表示。 没有哪个类是完美的；过窄的设计要好于过宽的设计。 第五章 运算符的重载 我们应该编写出清晰的程序——而不是为了展示自己聪明的程序。 重载运算符的含义必须是自然的，而不是为了展示程序员的聪明。 重载运算符必须能够与其他的运算符进行正确的交互。 我们要保持重载运算符的行为是一致的。 我们喜爱重载运算符时，应该保持一组相关运算符的完整性。 在定义operator=时，我们要注意x=x这种特殊情况。 在对运算符进行重载时，我们要避免使其他的程序员产生困惑。 我们要识别出对实现的继承；可以使用私有基类或者（更好的方法是）使用成员对象。 第六章 包装 我们需要知道从函数中返回的指针的有效生存期。 独立的对象应该有独立的行为。 不要对某些基本的信息进行完全的封装——我们要使得这些信息可以通过某些方法来进行访问。 在发生错误时，对象的行为应该是明确定义的。 我们要使得C++包装类能够改善C接口。 第七章 效率 降低耦合性——将类之间的交互最小化。 我们不能只通过主观臆测就做出判断， 而是应该通过执行性能分析的结果来找出问题所在。 我们需要对类的实现进行分析，以找出性能问题的根源。 我们也可以通过分析客户代码来找出性能问题的根源。 完整的接口将有助于实现搞笑的客户代码。 我们要找出简单的抽象。 第八章 案例研究 我们要始终记住结束空字符串的存在——正确的表达式应该是new char[strlen(s)+1]。 不要使用构造函数来初始化静态数据成员。 降低耦合性——将类之间的交互最小化。 每个类都应该只有唯一的、内聚的功能。 我们应该将类设计成抽象数据类型而不是模块类。 如果派生类之间的区别在于属性，则用数据成员来表示；如果在于行为，则用虚函数来表示。 如果泛化的情形同样简单时，那么我们最好不要只实现某种具体的情形。 通常情况下，共有基类的析构函数应该被声明为虚函数。 第九章 多重继承 在使用虚基类之前，我们需要彻底地理解它们。 不要试图从你正在使用的编译器中来学习多重继承的语义。 我们要避免人为地将一个类限制为只能被用作基类。 如果在共有基类中没有定义虚析构函数，那么在所有的派生类或者派生类的数据成员中都应该没有定义析构函数。 如果在多重继承的层次结构中存在着析构函数， 那么每个基类的析构函数都应该是虚函数。 如果在客户对象中需要包含某种服务，那么我们应该使用成员对象，而不是继承。 一个类应该能够描述一组对象。