国产亚洲欧美精品久久久,久久久精品久久久久特色影视,国产精品久久久久免费a∨

poj 3414解题报告(�q�搜�?

WORM — Sun, 08 Mar 2009 10:40:00 GMT

摘要: 郁闷那，写了(ji��n)七个��时�Q�一直在调试错误�?ji��n)！fuck it�Q?�q�个与别的BFS题的主要不同是要记录正确��序的�\�?我用path[i][j] = {way�Q�a,b}表示状态（i�Q�j�Q�是��q��态（a�Q�b�Q�经�q�方式way�Q�一共六�U?.. 阅读全文

WORM 2009-03-08 18:40 发表评论

poj 3191解题报告

WORM — Sun, 08 Mar 2009 04:37:00 GMT

The Moronic Cowmpouter

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1344		Accepted: 676

Description

Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it's a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base −2 do not have a sign bit.

You know number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base^1, base^2, and so on. In base −2, the place values are 1, −2, 4, −8, 16, −32, ... (reading from right to left). Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Eerily, negative numbers are also represented with 1's and 0's but no sign. Consider counting from −1 downward: 11, 10, 1101, 1100, 1111, and so on.

Please help the cows convert ordinary decimal integers (range -2,000,000,000..2,000,000,000) to their counterpart representation in base −2.

Input

Line 1: A single integer to be converted to base −2

Output

Line 1: A single integer with no leading zeroes that is the input integer converted to base −2. The value 0 is expressed as 0, with exactly one 0.

Sample Input

-13

Sample Output

Hint

Explanation of the sample:

Reading from right-to-left:

1*1 + 1*-2 + 1*4 + 0*-8 +1*16 + 1*-32 = -13

题目的意思就是让你把一个数转换�?2�q�制�Q?br>基本原理:
如果n为奇敎ͼ�那么末位肯定�?�Q�因此就可以转�ؓ(f��)�?x-1)/-2 的子问题?sh��)��(ji��n)�?�Q�除�?2可以�c�L��十进制就能理解了(ji��n)�Q?br> 如果n为偶敎ͼ�末位必�ؓ(f��)0�Q�然后再转�ؓ(f��)求x/-2的子问题�Q?br>�l�束条�g�?n=1�?br>思�\很简单，但是有两个小斚w��要提提，一定要考虑n(y��u)=0的情况，我就是没考虑而一直超�Ӟ��郁闷�Q�还找不出错误，陷入�?ji��n)死循环怪不得超�Ӟ��q�有注意球的�l�果是逆序的！�Q�呵呵下面是代码�Q?br>

1//============================================================================
2// Name        : poj 3191.cpp
3// Author      : worm
4// Copyright   : Your copyright notice
5// Description :把一个十�q�制的数转换�?2�q�制的数
6//============================================================================
7
8#include <iostream>
9#include <stdio.h>
10#include <string>
11#include <math.h>
12using namespace std;
13string a= "";
14int main() {
15    int x;
16    cin >> x;
17    if (x == 0) {
18        cout <<"0"<<endl;
19        return 0;
20    }
21
22    while (x != 1) {
23        if (abs(x) % 2 == 1) {
24            a += '1';
25            x = (x-1)/-2;
26            continue;
27        }
28        a += '0';
29        x /= -2;
30    }
31    cout <<"1";
32    for (int i = a.length() - 1; i >= 0; i--) {
33        printf("%c",a[i]);
34    }
35
36    return 0;
37}
38

WORM 2009-03-08 12:37 发表评论

poj 3126 Prim Path �W�一道BFS

WORM — Sun, 08 Mar 2009 02:36:00 GMT

对于一个四位数�Q�对于它某一位变化之后的素数�Q�即“盔R��的素�?#8221;�Q�进行广度搜索，知道搜烦(ch��)��Cؓ(f��)止！
挺简单，看代码应该可以看懂，下面是代�?

9#include <iostream>
10#include <queue>
11#include <math.h>
12using namespace std;
13int a, b;
14int p[9999] = { 0 };
15int visited[9999] = { 0 };
16bool isprime(int x) {
17
18    for (int i = 2; i <= sqrt((double) x); ++i) {
19        if (x % i == 0)
20            return false;
21    }
22    return true;
23}
24int BFS(int s, int r) {
25    queue<int> q;
26    q.push(s);
27    p[s] = 0;
28    visited[s] = 1;
29    while (!q.empty()) {
30        int temp = q.front();
31        q.pop();
32        for (int i = 0; i <= 9; i++) {
33            int y1 = (temp / 10) * 10 + i;
34            if (isprime(y1) && !visited[y1]) {
35                q.push(y1);
36                p[y1] = p[temp] + 1;
37                visited[y1] = 1;
38            }
39            int y2 = temp % 10 + (temp / 100) * 100 + i * 10;
40            if (isprime(y2) && !visited[y2]) {
41                q.push(y2);
42                p[y2] = p[temp] + 1;
43                visited[y2] = 1;
44            }
45            int y3 = temp % 100 + (temp / 1000) * 1000 + 100 * i;
46            if (isprime(y3) && !visited[y3]) {
47                q.push(y3);
48                p[y3] = p[temp] + 1;
49                visited[y3] = 1;
50            }
51            if (i != 0) {
52                int y4 = temp % 1000 + i * 1000;
53                if (isprime(y4) && !visited[y4]) {
54                    q.push(y4);
55                    p[y4] = p[temp] + 1;
56                    visited[y4] = 1;
57                }
58            }
59            if (visited[r])
60                return p[r];
61        }
62
63    }
64    return 0;
65}
66int main() {
67    int n;
68    cin >> n;
69    while (n--) {
70        memset(visited,0,sizeof(visited));
71        memset(p,0,sizeof(p));
72        cin >> a >> b;
73        cout << BFS(a, b) << endl;
74
75    }
76    return 0;
77}
78

WORM 2009-03-08 10:36 发表评论

WORM — Sat, 07 Mar 2009 10:31:00 GMT

参考了(ji��n)别�h的思�\�Q�做��Z��(ji��n)�W�一道BFS�Q�虽然在大牛们看来不屑一��?but about me,I really happy for it, I'm coming ! worm never give up!!

1//============================================================================
2// Name        : poj.cpp
3// Author      :
4// Version     :
5// Copyright   : Your copyright notice
6// Description : Hello World in C++, Ansi-style
7//============================================================================
8
9#include <iostream>
10#include <queue>
11using namespace std;
12queue<int> q;
13int    result[100001];
14int visited[100001] = {0};
15int BFS(int start,int end) {
16    if (start == end)
17        return 0;
18    q.push(start);
19    result[start] = 0;
20    visited[start] = 1;
21    while(!q.empty()) {
22        int temp = q.front();
23        q.pop();
24        int next;
25        for (int i = 0; i < 3; ++i) {
26            if (i == 0)
27                next = temp - 1;
28            if (i == 1)
29                next = temp + 1;
30            if (i == 2)
31                next = temp*2;
32            if(next > 100000 || next < 0) {
33                continue;
34            }
35            if (visited[next] != 1) {
36                q.push(next);
37                result[next] = result[temp] + 1;
38                visited[next] = 1;
39            }
40            if (next == end)
41                return result[next];
42        }
43    }
44    return 0;
45}
46int main() {
47    int n,k;
48    cin >> n >> k;
49    cout << BFS(n,k) << endl;
50    return 0;
51}
52

WORM 2009-03-07 18:31 发表评论

WORM — Fri, 06 Mar 2009 00:52:00 GMT

1//============================================================================
2// Name        : poj.cpp
3// Author      :
4// Version     :
5// Copyright   : Your copyright notice
6// Description : 题目大意��是��正序数�?,2,3,,n,通过最��的“复制�_�脓(chu��ng)”�?br> 7// 变�(sh��)ؓ(f��)逆序序列的问题�?br> 8//基本思想�Q?nbsp; 如果n为奇敎ͼ�假设n = 7�Q?br> 9// 1 2 3 4 5 6 7          ��n左边的最中间的两个数依次�U�d��7的右�?br>10// 1 2 5 6 7 3 4       的最中间
11// 1 6 7 3 2 5 4
12// 7 3 2 1 6 5 4          ��?nbsp;3 2 1�?nbsp;6 5 4 交换
13// 7 6 5 4 3 2 1
14//�ȝ��ơ数�?n+1)/2;
15// n =  偶数�Ӟ��可以先把n不管�Q�这样n-1��׃ؓ(f��)奇数的情况，求出后的序列在和n交换一�?br>16//卛_��Q�结果�ؓ(f��)n/2 + 1;
17//============================================================================
18
19#include <iostream>
20using namespace std;
21void solve(int n) {
22    int x = (n+1)/2 - 1;
23    int y = n;
24    for (int i = 0; i < x; ++i) {
25        cout << n/2 << " " << 2 << " " << y-2-i << endl;
26        n -= 2;
27    }
28    cout <<"2 " << x << " " << x + 1 << endl;
29}
30
31int main() {
32    int n;
33    cin >> n;
34    if (n == 1) {
35        cout << 0 <<endl;
36        return 0;
37    }
38    if (n == 2) {
39        cout << "1" <<endl;
40        cout << "1 1 1" <<endl;
41        return 0;
42    }
43    if (n % 2 != 0) {
44        cout << (n+1)/2 <<endl;
45         solve(n);
46    }
47    else {
48        cout << n/2 + 1 << endl;
49        solve(n-1);
50        cout << 1 << " "<< n-1 <<" 1" <<endl;
51    }
52
53    return 0;
54}
55

最后一定要注意1 �?2 的情况，我因为忘?sh��)��(ji��n)考虑�Q�wa�?ji��n)几�ơ，呵�?..

WORM 2009-03-06 08:52 发表评论