Code – 第267页

POJ1426-Find The Multiple-深度优先搜索BFS

Find The Multiple

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 24137		Accepted: 9997		Special Judge

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

继续阅读POJ1426-Find The Multiple-深度优先搜索BFS

poj1207-The 3n + 1 problem

poj1207-The 3n + 1 problem
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 55398 Accepted: 17651
Description

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n <-- 3n+1
5. else n <-- n/2
6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).
Sample Input

1 10
100 200
201 210
900 1000
Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

#include <iostream>
using namespace std;
int main() {
    int a, b;
    while (cin >> a >> b) {
        int max = 0;
        int low = a > b ? b : a;
        int high = a > b ? a : b;
        for (int i = low; i <= high; i++) {
            int cou = 1;
            int t = i;
            while (t != 1) {
                if (t % 2 == 1) {
                    t = 3 * t + 1;
                } else
                    t = t / 2;
                cou++;
            }
            if (cou > max) {
                max = cou;
            }
        }
        cout << a << " " << b << " " << max << endl;
    }
    return 0;
}

poj1207-The 3n + 1 problem

Time Limit: 1000MS Memory Limit: 10000K

Total Submissions: 55398 Accepted: 17651

Description

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

Consider the following algorithm:

1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then n <-- 3n+1

5. else n <-- n/2

6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10

100 200

201 210

900 1000

Sample Output

1 10 20

100 200 125

201 210 89

900 1000 174

#include <iostream>

using namespace std;

int main() {

int a, b;

while (cin >> a >> b) {

int max = 0;

int low = a > b ? b : a;

int high = a > b ? a : b;

for (int i = low; i <= high; i++) {

int cou = 1;

int t = i;

while (t != 1) {

if (t % 2 == 1) {

t = 3 * t + 1;

} else

t = t / 2;

cou++;

}

if (cou > max) {

max = cou;

}

cout << a << " " << b << " " << max << endl;

}

return 0;

}

POJ-2488 A Knights Journey-深度优先搜索DFS

POJ-2488 A Knights Journey-深度优先搜索
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 37974 Accepted: 12896
Description

Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
Sample Input

3
1 1
2 3
4 3
Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
Source

TUD Programming Contest 2005, Darmstadt, Germany
#include <iostream>
using namespace std;
int next1[8][2]={
    {-2, -1},
    {-2, 1},
    {-1, -2},
    {-1, 2},
    {1, -2},
    {1, 2},
    {2, -1},
    {2, 1}
}; //记录方向
int a, b, flag;
int book[26][26], path[26][2];
void dfs(int i, int j, int k) {
    if (k == a * b) {
        for (int t = 0; t < k; t++) {
            printf("%c", path[t][0] + 'A');
            cout << path[t][1]+1;
        }
        cout << endl;
        flag = 1;
    } else {
        for (int t = 0; t < 8; t++) {
            int n = i + next1[t][0];
            int m = j + next1[t][1];
            if (n >= 0 && n < b && m >= 0 && m < a && book[n][m] == 0 && flag == 0) {
                book[n][m] = 1;
                path[k][0] = n;
                path[k][1] = m;
                dfs(n, m, k + 1);
                book[n][m] = 0;
            }
        }
    }
}

int main() {
    int N;
    cin >> N;
    for (int m = 0; m < N; m++) {
        flag = 0;
        cin >> a >> b;
        for (int i = 0; i < a; i++)
            for (int j = 0; j < b; j++)
                book[i][j] = 0;
        book[0][0] = 1;
        path[0][0] = 0,path[0][1] = 0;
        cout << "Scenario #" << m + 1 << ":" << endl;
        dfs(0, 0, 1);
        if (!flag)
            cout << "impossible" << endl;
        cout << endl;
    }
    return 0;
}

POJ-2488 A Knights Journey-深度优先搜索

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 37974 Accepted: 12896

Description

Background

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey

around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem

Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.

If no such path exist, you should output impossible on a single line.

Sample Input

1 1

2 3

4 3

Sample Output

Scenario #1:

Scenario #2:

impossible

Scenario #3:

A1B3C1A2B4C2A3B1C3A4B2C4

Source

TUD Programming Contest 2005, Darmstadt, Germany

#include <iostream>

using namespace std;

int next1[8][2]={

{-2, -1},

{-2, 1},

{-1, -2},

{-1, 2},

{1, -2},

{1, 2},

{2, -1},

{2, 1}

}; //记录方向

int a, b, flag;

int book[26][26], path[26][2];

void dfs(int i, int j, int k) {

if (k == a * b) {

for (int t = 0; t < k; t++) {

printf("%c", path[t][0] + 'A');

cout << path[t][1]+1;

}

cout << endl;

flag = 1;

} else {

for (int t = 0; t < 8; t++) {

int n = i + next1[t][0];

int m = j + next1[t][1];

if (n >= 0 && n < b && m >= 0 && m < a && book[n][m] == 0 && flag == 0) {

book[n][m] = 1;

path[k][0] = n;

path[k][1] = m;

dfs(n, m, k + 1);

book[n][m] = 0;

}

int main() {

int N;

cin >> N;

for (int m = 0; m < N; m++) {

flag = 0;

cin >> a >> b;

for (int i = 0; i < a; i++)

for (int j = 0; j < b; j++)

book[i][j] = 0;

book[0][0] = 1;

path[0][0] = 0,path[0][1] = 0;

cout << "Scenario #" << m + 1 << ":" << endl;

dfs(0, 0, 1);

if (!flag)

cout << "impossible" << endl;

cout << endl;

}

return 0;

}

POJ 1321-棋盘问题-简单搜索DFS

POJ 1321-棋盘问题-简单搜索DFS
Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output

2
1

#include <iostream>
using namespace std;
int col[10];
char pic[8][8];
int cou = 0;
int n, k;
void dfs(int begin, int num) {
    for (int j = 0; j < n; j++) {
        if (pic[begin][j] == '#' && col[j] == 0) {
            if (num == 1) {
                cou++;
            } else {
                col[j] = 1;
                for (int h = begin + 1; h <= n - num + 1; h++) {
                    dfs(h, num - 1);
                }
                col[j] = 0;
            }
        }
    }
}

int main() {
    while ((cin >> n >> k) && !(n == -1 && k == -1)) {
        cou = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> pic[i][j];
            }
        }
        for (int i = 0; i <= n - k; i++) {
            dfs(i, k);
        }
        cout << cou << endl;
    }
    return 0;
}

POJ 1321-棋盘问题-简单搜索DFS

Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。

每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n

当为-1 -1时表示输入结束。

随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1

4 4

...#

..#.

.#..

#...

-1 -1

Sample Output

#include <iostream>

using namespace std;

int col[10];

char pic[8][8];

int cou = 0;

int n, k;

void dfs(int begin, int num) {

for (int j = 0; j < n; j++) {

if (pic[begin][j] == '#' && col[j] == 0) {

if (num == 1) {

cou++;

} else {

col[j] = 1;

for (int h = begin + 1; h <= n - num + 1; h++) {

dfs(h, num - 1);

}

col[j] = 0;

}

int main() {

while ((cin >> n >> k) && !(n == -1 && k == -1)) {

cou = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> pic[i][j];

}

for (int i = 0; i <= n - k; i++) {

dfs(i, k);

}

cout << cou << endl;

}

return 0;

}

1048. 数字加密(20)-PAT乙级真题

本题要求实现一种数字加密方法。首先固定一个加密用正整数A，对任一正整数B，将其每1位数字与A的对应位置上的数字进行以下运算：对奇数位，对应位的数字相加后对13取余——这里用J代表10、Q代表11、K代表12；对偶数位，用B的数字减去A的数字，若结果为负数，则再加10。这里令个位为第1位。
输入格式：
输入在一行中依次给出A和B，均为不超过100位的正整数，其间以空格分隔。
输出格式：
在一行中输出加密后的结果。
输入样例：
1234567 368782971
输出样例：
3695Q8118

分析：首先将a和b倒置，将字符串a和b中较短的那个末尾添加0直到两个字符串长度相等，然后从0开始依次处理每一位，如果当前位是奇数位（i % 2 == 0）则将a[i]的数字加上b[i]的数字再对13取余，结果添加在字符串c的末尾；如果是偶数位，计算b[i]和a[i]的差值，如果小于0就加10，然后将结果添加在字符串c的末尾，最后倒序输出字符串c～

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string a, b, c;
    cin >> a >> b;
    int lena = a.length(), lenb = b.length();
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    if (lena > lenb) 
        b.append(lena - lenb, '0');
    else
        a.append(lenb - lena, '0');
    char str[14] = {"0123456789JQK"};
    for (int i = 0; i < a.length(); i++) {
        if (i % 2 == 0) {
            c += str[(a[i] - '0' + b[i] - '0') % 13];
        } else {
            int temp = b[i] - a[i];
            if (temp < 0) temp = temp + 10;
            c += str[temp];
        }
    }
    for (int i = c.length() - 1; i >= 0; i--)
        cout << c[i];
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string a, b, c;

cin >> a >> b;

int lena = a.length(), lenb = b.length();

reverse(a.begin(), a.end());

reverse(b.begin(), b.end());

if (lena > lenb)

b.append(lena - lenb, '0');

else

a.append(lenb - lena, '0');

char str[14] = {"0123456789JQK"};

for (int i = 0; i < a.length(); i++) {

if (i % 2 == 0) {

c += str[(a[i] - '0' + b[i] - '0') % 13];

} else {

int temp = b[i] - a[i];

if (temp < 0) temp = temp + 10;

c += str[temp];

}

for (int i = c.length() - 1; i >= 0; i--)

cout << c[i];

return 0;

}

1025. 反转链表 (25)-PAT乙级真题

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

分析：输入样例正确连接顺序应该是：
/*
00100 1 12309
12309 2 33218
33218 3 00000
00000 4 99999
99999 5 68237
68237 6 -1
*/
还应该考虑输入样例中有不在链表中的结点的情况。所以用个sum计数~

而且，algorithm头文件里面有reverse函数可以直接调用～

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int first, k, n, temp;
    cin >> first >> n >> k;
    int data[100005], next[100005], list[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }
    int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < (sum - sum % k); i += k)
        reverse(begin(list) + i, begin(list) + i + k);
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
    printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int first, k, n, temp;

cin >> first >> n >> k;

int data[100005], next[100005], list[100005];

for (int i = 0; i < n; i++) {

cin >> temp;

cin >> data[temp] >> next[temp];

}

int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器

while (first != -1) {

list[sum++] = first;

first = next[first];

}

for (int i = 0; i < (sum - sum % k); i += k)

reverse(begin(list) + i, begin(list) + i + k);

for (int i = 0; i < sum - 1; i++)

printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);

printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);

return 0;

}