# 落絮飞雁的个人网站

READ MORE →

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

```#include
#include
#include
char num;
using namespace std;
int main()
{
int p, n, cache;
scanf("%d", &p);
while (p--)
{
memset(num, 0, sizeof(num));
cache = n = 0;
scanf("%d", &cache);
scanf("%s", num);
printf("%d ", cache);
if (next_permutation(num, num + strlen(num)))
puts(num);
else printf("BIGGESTn");
}
return 0;
}
```

## POJ1833：排列——全排列问题

Description

Input

Output

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

```#include
#include
using namespace std;
int cache;
int main()
{
int N;
scanf("%d", &N);
while (N--)
{
int n, k, i;
scanf("%d%d",&n,&k);
for (i = 0; i < n; i++)
scanf("%d", &cache[i]);
for (i = 0; i < k; i++)
next_permutation(cache, cache + n);
printf("%d", cache);
for (i = 1; i < n; i++)
printf(" %d", cache[i]);
printf("n");
}
return 0;
}
```

## 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类问题，查找排序中的下一序列。

```#include
#include
using namespace std;
int main()
{
int lenth;
char s;
while (scanf("%s", s) != EOF)
{
if (s == '#')
break;
lenth = strlen(s);
if (next_permutation(s, s + lenth))
printf("%sn", s);
else
printf("No Successorn");
}
return 0;
}
```

## 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

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

```#include
#include
#include
int N,i;
const int MAX_N = 2000;
char S[MAX_N + 1];

int main()
{
while (~scanf("%d", &N))
{
for (i = 0; i < N; i++)
{
getchar();
scanf("%c", &S[i]);
}
int a = 0, b = N - 1, cnt;
cnt = 0;
while (a <= b)
{
bool left = false;//比较左侧和右侧的字符串
for (int i = 0; a + i <= b; i++)
{
if (S[a + i] < S[b - i])
{
left = true;
break;
}
else if (S[a + i]>S[b - i])
{
left = false;
break;
}
}
if (left)putchar(S[a++]);
else putchar(S[b--]);
cnt++;
if (cnt % 80 == 0)
putchar('n');
}
}
return 0;
}
```

## 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

```2
10 3
2 6 7
214 7
11 12 7 13 176 23 191
```

Sample Output

```4 8
38 207```

```#include
#include
#include
#include
using namespace std;
int main()
{
int j;
scanf("%d", &j);
while (j--)
{
int L, n,ni;
int x;
memset(0, L, sizeof L);
memset(0, n, sizeof n);
scanf("%d,%d", &L, &n);
for (ni = 0; ni < n; ni++)
{
scanf("%d", x[ni]);
}
int minT = 0;//求最短时间
for (int i = 0; i < n; i++){
minT = max(minT, min(x[i], L - x[i]));
}
int maxT = 0;//求最长时间
for (int i = 0; i < n; i++){
maxT = max(maxT, max(maxT, max(x[i], L - x[i])));
}
printf("%d %d n", minT, maxT);
return 0;
}
}

```

## 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

```#include

int main()
{
int a,b;
scanf("%d %d",&a, &b);
printf("%dn",a+b);
return 0;
}
```

## 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)

```#include
using namespace std;
#define n 1000
int main()
{
int r[n],g[n],b[n],flag=0;
int d=0;
int i=0,j=0,k=0;
int temp;
while (cin>>r[i]>>g[i]>>b[i],r[i]!=-1&&g[i]!=-1&&b[i]!=-1)
{
j=i;
if(j>=16)
{
d=(r[j]-r)*(r[j]-r)+(g[j]-g)*(g[j]-g)+(b[j]-b)*(b[j]-b);
for(flag=k=0;k<16;k++)
{
temp=(r[j]-r[k])*(r[j]-r[k])+(g[j]-g[k])*(g[j]-g[k])+(b[j]-b[k])*(b[j]-b[k]);
if(d>temp)
{
d=temp;
flag=k;
}
}
cout<<"("<

```