落絮飞雁的个人网站

顺流而下,把梦做完

POJ3279:Fliptile——搜索、开关问题

约翰又来折腾牛了……
READ MORE →

POJ3276:Face The Right Way——开关问题、简单DP

牛头人约翰和牛的故事。
READ MORE →

POJ3785:The Next Permutation——全排列问题

Description

For this problem, you will write a program that takes a (possibly long) string of decimal digits, and outputs the permutation of those decimal digits that has the next larger value (as a decimal number) than the input number. For example:

123 -> 132
279134399742 -> 279134423799

It is possible that no permutation of the input digits has a larger value. For example, 987.
Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by up to 80 decimal digits which is the input value.
Output

For each data set there is one line of output. If there is no larger permutation of the input digits, the output should be the data set number followed by a single space, followed by the string BIGGEST. If there is a solution, the output should be the data set number, a single space and the next larger permutation of the input digits.
Sample Input

3
1 123
2 279134399742
3 987
Sample Output

1 132
2 279134423799
3 BIGGEST


在STL下瞬间变水题……

输入数组时用scanf()而不用gets()。原因是scanf()遇到空格时认为输入结束,而gets()会输入空格:样例显然是以空格而非结束标志来判断的。所以,乖乖scanf()吧。

还有就是注意格式,这题又PE了,郁闷……看了看是IDE坏掉了。

放上代码:

 

 

POJ1833:排列——全排列问题

Description

题目描述:
大家知道,给出正整数n,则1到n这n个数可以构成n!种排列,把这些排列按照从小到大的顺序(字典顺序)列出,如n=3时,列出1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1六个排列。

任务描述:
给出某个排列,求出这个排列的下k个排列,如果遇到最后一个排列,则下1排列为第1个排列,即排列1 2 3…n。
比如:n = 3,k=2 给出排列2 3 1,则它的下1个排列为3 1 2,下2个排列为3 2 1,因此答案为3 2 1。
Input

第一行是一个正整数m,表示测试数据的个数,下面是m组测试数据,每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64),第二行有n个正整数,是1,2 … n的一个排列。
Output

对于每组输入数据,输出一行,n个数,中间用空格隔开,表示输入排列的下k个排列。
Sample Input

3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
Sample Output

3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10

一道全排列问题。用next_permutation轻松AC。注意头文件是algorithm即可。


 

POJ1146:ID Codes——全排列问题

Description

It is 2084 and the year of Big Brother has finally arrived, albeit a century late. In order to exercise greater control over its citizens and thereby to counter a chronic breakdown in law and order, the Government decides on a radical measure–all citizens are to have a tiny microcomputer surgically implanted in their left wrists. This computer will contains all sorts of personal information as well as a transmitter which will allow people’s movements to be logged and monitored by a central computer. (A desirable side effect of this process is that it will shorten the dole queue for plastic surgeons.)

An essential component of each computer will be a unique identification code, consisting of up to 50 characters drawn from the 26 lower case letters. The set of characters for any given code is chosen somewhat haphazardly. The complicated way in which the code is imprinted into the chip makes it much easier for the manufacturer to produce codes which are rearrangements of other codes than to produce new codes with a different selection of letters. Thus, once a set of letters has been chosen all possible codes derivable from it are used before changing the set.

For example, suppose it is decided that a code will contain exactly 3 occurrences of a', 2 of b’ and 1 of c', then three of the allowable 60 codes under these conditions are:
abaabc

abaacb

ababac

These three codes are listed from top to bottom in alphabetic order. Among all codes generated with this set of characters, these codes appear consecutively in this order.

Write a program to assist in the issuing of these identification codes. Your program will accept a sequence of no more than 50 lower case letters (which may contain repeated characters) and print the successor code if one exists or the message No Successor’ if the given code is the last in the sequence for that set of characters.
Input

Input will consist of a series of lines each containing a string representing a code. The entire file will be terminated by a line consisting of a single #.
Output

Output will consist of one line for each code read containing the successor code or the words ‘No Successor’.
Sample Input

abaacb
cbbaa
#
Sample Output

ababac
No Successor


 

C++中STL的next_permutation类问题,查找排序中的下一序列。

简单AC代码:

 

嘘,老大哥在盯着你…………

POJ3617:Best Cow Line——字典序最小问题

Description

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual”Farmer of the Year” competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows’ names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he’s finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single initial (‘A’..’Z’) of the cow in the ith position in the original line

Output

The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows (‘A’..’Z’) in the new line.

Sample Input

6
A
C
D
B
C
B
Sample Output

ABCBCD


题目大意是给定一个长度为N的字符串S,要求构造一个字符串T。T的默认状态为空。然后随机将S的头部(或尾部)删除一个字符,加到T的尾部。

要求构造一个字典序尽可能小的字符串T。

思路:

  1. 按照字典序比较S和反转后的字符串S’
  2. 如果S较小,就从S开头取出字符,放到T的末尾
  3. 如果S’较小,就从S末位取出字符,放到T的末尾
  4. 如果相同,则比较(S+1)和(S’-1)两字符的大小;相同则继续。

字典序+贪心问题。

出现PE问题:每行最多80个字符

 

 

POJ1852:Ants

Description
An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.

Input

The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.

Output

For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.

Sample Input

Sample Output

可以认为所有的蚂蚁都朝着竿的两端前进,并且两只蚂蚁相遇时可以无视。(即,两只蚂蚁穿过对方,而没有反方向爬回去)。所以求最长最短时间,只需求蚂蚁到竿子一端的最大最小距离即可。
代码:

POJ1000:A+B Problem

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 329741 Accepted: 182697

Description

Calculate a+b
Input

Two integer a,b (0<=a,b<=10) Output

Output a+b
Sample Input

1 2
Sample Output

3

POJ1046:Color Me Less

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 30310 Accepted: 14732

Description

A color reduction is a mapping from a set of discrete colors to a smaller one. The solution to this problem requires that you perform just such a mapping in a standard twenty-four bit RGB color space. The input consists of a target set of sixteen RGB color values, and a collection of arbitrary RGB colors to be mapped to their closest color in the target set. For our purposes, an RGB color is defined as an ordered triple (R,G,B) where each value of the triple is an integer from 0 to 255. The distance between two colors is defined as the Euclidean distance between two three-dimensional points. That is, given two colors (R1,G1,B1) and (R2,G2,B2), their distance D is given by the equation

Input

The input is a list of RGB colors, one color per line, specified as three integers from 0 to 255 delimited by a single space. The first sixteen colors form the target set of colors to which the remaining colors will be mapped. The input is terminated by a line containing three -1 values.
Output

For each color to be mapped, output the color and its nearest color from the target set.

If there are more than one color with the same smallest distance, please output the color given first in the color set.
Sample Input

0 0 0
255 255 255
0 0 1
1 1 1
128 0 0
0 128 0
128 128 0
0 0 128
126 168 9
35 86 34
133 41 193
128 0 128
0 128 128
128 128 128
255 0 0
0 1 0
0 0 0
255 255 255
253 254 255
77 79 134
81 218 0
-1 -1 -1
Sample Output

(0,0,0) maps to (0,0,0)
(255,255,255) maps to (255,255,255)
(253,254,255) maps to (255,255,255)
(77,79,134) maps to (128,128,128)
(81,218,0) maps to (126,168,9)
放上AC代码

不能帮硕士哥哥看代码诶,好悲伤呢……