dd's site \#

Posted on In ,

题意 八数码问题

还是八数码问题 只是要输出路径了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<cstring>
using namespace std;
const int M = 1000003;
int e[9] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
int x[4] = { -1, 1, 0, 0}, y[4] = {0, 0, -1, 1};
int dir[M], pre[M], h[M], s[M][9];
char pri[5] = "udlr";

int aton(int a[])
{
    int t = 0;
    for(int i = 0; i < 9; ++i)
        t = t * 10 + a[i];
    return t;
}

int search_hash(int a[])
{
    int t = aton(a), p = t % M;
    while(h[p])
    {
        if(h[p] == t) return p;
        ++p;
        if(p >= M) p = 0;
    }
    return p;
}

void print(int p)
{
    if(pre[p])
    {
        print(pre[p]);
        printf("%c", pri[dir[p]]);
    }
}

int bfs()
{
    memset(h, 0, sizeof(h));
    h[aton(s[1]) % M] = aton(s[1]);
    int fro = 1, rear = 2, r, c, k = 0, nr, nc, nk, p;
    int t[9], tmp, cur;

    while(fro < rear)
    {
        memcpy(t, s[fro], sizeof(t));
        cur = search_hash(t);
        if(memcmp(t, e, sizeof(t)) == 0) return cur;
        for(k = 0; t[k];) ++k;
        r = k / 3, c = k % 3;
        for(int i = 0; i < 4; ++i)
        {
            memcpy(t, s[fro], sizeof(t));
            nr = r + x[i], nc = c + y[i], nk = nr * 3 + nc;
            if(nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            tmp = t[nk];
            t[nk] = 0;
            t[k] = tmp;
            p = search_hash(t);
            if(h[p] == 0)
            {
                h[p] = aton(t);
                dir[p] = i;
                pre[p] = cur;
                memcpy(s[rear], t, sizeof(t));
                ++rear;
            }
        }
        ++fro;
    }
    return 0;
}

int main()
{
    char c;
    while(~scanf("%d", &s[1][0]))
    {
        memset(dir, 0, sizeof(dir));
        memset(pre, 0, sizeof(pre));
        for(int i = 1; i < 9; ++i)
        {
            scanf(" %c", &c);
            if(c == 'x') s[1][i] = 0;
            else s[1][i] = c - '0';
        }
        int ans = bfs();
        if(ans) print(ans);
        else  printf("unsolvable");
        printf("\n");
    }
    return 0;
}
/*
2 3 4 1 5 0 7 6 8
*/

Eight

Description
The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let’s call the missing tile ‘x’; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x
where the only legal operation is to exchange ‘x’ with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x r-> d-> r->
The letters in the previous row indicate which neighbor of the ‘x’ tile is swapped with the ‘x’ tile at each step; legal values are ‘r’,’l’,’u’ and ‘d’, for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing ‘x’ tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.

Input

You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus ‘x’. For example, this puzzle
1 2 3 x 4 6 7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable’’, if the puzzle has no solution, or a string consisting entirely of the letters ‘r’, ‘l’, ‘u’ and ‘d’ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.

Sample Input

2 3 4 1 5 x 7 6 8

Sample Output

ullddrurdllurdruldr

Source

South Central USA 1998

Posted on In ,

题意 中文

最基础的字典树应用噢噢噢噢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>
#include<cstring>
using namespace std;
struct trie
{
    trie *chi[26];
    int num;
    trie()
    {
        num = 0;
        for(int i = 0; i < 26; ++i)
            chi[i] = NULL;
    }
}*root;

void insertTrie(char s[])
{
    trie *p = root;
    p->num++;
    for(int i = 0; s[i]; ++i)
    {
        int j = s[i] - 'a';
        if(p->chi[j] == NULL)
            p->chi[j] = new trie;
        p = p->chi[j];
        p->num++;
    }
}

int searchTrie(char s[])
{
    trie *p = root;
    for(int i = 0; p && s[i]; ++i)
    {
        int j = s[i] - 'a';
        p = p->chi[j];
    }
    if(!p) return 0;
    else return p->num;
}

int main()
{
    char s[12];
    int n, m;
    while(~scanf("%d", &n))
    {
        root = new trie;
        while(n--)
        {
            scanf("%s", s);
            insertTrie(s);
        }
        scanf("%d", &m);
        while(m--)
        {
            scanf("%s", s);
            printf("%d\n", searchTrie(s));
        }
    }
    return 0;
}

时间限制: 10000ms

单点时限: 1000ms
内存限制: 256MB

小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。

这一天，他们遇到了一本词典，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能对于每一个我给出的字符串，都在这个词典里面找到以这个字符串开头的所有单词呢？”

身经百战的小Ho答道：“怎么会不能呢！你每给我一个字符串，我就依次遍历词典里的所有单词，检查你给我的字符串是不是这个单词的前缀不就是了？”

小Hi笑道：“你啊，还是太年轻了！~假设这本词典里有10万个单词，我询问你一万次，你得要算到哪年哪月去？”

小Ho低头算了一算，看着那一堆堆的0，顿时感觉自己这辈子都要花在上面了…

小Hi看着小Ho的囧样，也是继续笑道：“让我来提高一下你的知识水平吧~你知道树这样一种数据结构么？”

小Ho想了想，说道：“知道~它是一种基础的数据结构，就像这里说的一样！”

小Hi满意的点了点头，说道：“那你知道我怎么样用一棵树来表示整个词典么？”

小Ho摇摇头表示自己不清楚。

提示一：Trie树的建立

“你看，我们现在得到了这样一棵树，那么你看，如果我给你一个字符串ap，你要怎么找到所有以ap开头的单词呢？”小Hi又开始考校小Ho。

“唔…一个个遍历所有的单词？”小Ho还是不忘自己最开始提出来的算法。

“笨！这棵树难道就白构建了！”小Hi教训完小Ho，继续道：“看好了！”

提示二：如何使用Trie树

提示三：在建立Trie树时同时进行统计！

“那么现在！赶紧去用代码实现吧！”小Hi如是说道

输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。

在20%的数据中n, m<=10，词典的字母表大小<=2.

在60%的数据中n, m<=1000，词典的字母表大小<=5.

在100%的数据中n, m<=100000，词典的字母表大小<=26.

本题按通过的数据量排名哦～

对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。
样例输入 5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab 样例输出 1 0 3 0 0

Posted on In ,

题意 中文

最基础的线段树了 只涉及到了点的修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
using namespace std;
const int N = 200005;
int maxv[N << 2];

void pushup(int p)
{
    maxv[p] = max(maxv[p << 1], maxv[p << 1 | 1]);
}

void build(int p, int s, int e)
{
    if(s == e) scanf("%d", &maxv[p]);
    else
    {
        build(lc);
        build(rc);
        pushup(p);
    }
}

void update(int p, int s, int e, int a, int b)
{
    if(s == e && e == a)
    {
        maxv[p] = b;
        return;
    }
    if(a <= mid) update(lc, a, b);
    else update(rc, a, b);
    pushup(p);
}

int query(int p, int s, int e, int l, int r)
{
    if(s >= l && e <= r) return maxv[p];
    if(r <= mid) return query(lc, l, r);
    if(l > mid) return query(rc, l, r);
    return max(query(lc, l, mid), query(rc, mid + 1, r));
}

int main()
{
    int n, m, a, b;
    char c[2];
    while(~scanf("%d%d", &n, &m))
    {
        build(1, 1, n);
        while(m--)
        {
            scanf("%s%d%d", c, &a, &b);
            if(c[0] == 'Q') printf("%d\n", query(1, 1, n, a, b));
            else update(1, 1, n, a, b);
        }
    }
    return 0;
}

I Hate It

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input

本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。
当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output

对于每一次询问操作，在一行里面输出最高成绩。
Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5
Sample Output

5 6 5 9

Hint Huge input,the C function scanf() will work better than cin

Posted on In ,

继续最水的线段树 简单粗暴

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
using namespace std;
const int N = 100005;
int add[4 * N], maxv[4 * N];

void pushup(int p)
{
    maxv[p] = max(maxv[p << 1], maxv[p << 1 | 1]);
}

void pushdown(int p)
{
    add[p << 1] += add[p];
    add[p << 1 | 1] += add[p];
    maxv[p << 1] += add[p];
    maxv[p << 1 | 1] += add[p];
    add[p] = 0;
}

void build(int p, int s, int e)
{
    add[p] = 0;
    if(s == e) scanf("%d", &maxv[p]);
    else
    {
        build(lc);
        build(rc);
        pushup(p);
    }
}

void update(int p, int s, int e, int l, int r, int v, int op)
{
    if(s == l && e == r)
    {
        if(op)
        {
            add[p] += v;
            maxv[p] += v;
        }
        else maxv[p] = v;
        return;
    }
    pushdown(p);
    if(r <= mid) update(lc, l, r, v, op);
    else if(l > mid) update(rc, l, r, v, op);
    else update(lc, l, mid, v, op), update(rc, mid + 1, r, v, op);
    pushup(p);
}

int query(int p, int s, int e, int l, int r)
{
    if(s == l && e == r) return maxv[p];
    pushdown(p);
    if(r <= mid) return query(lc, l, r);
    if(l > mid) return query(rc, l, r);
    return max(query(lc, l, mid), query(rc, mid + 1, r));
}

int main()
{
    int n, m, x, y;
    char cmd[10];
    while(~scanf("%d%d", &n, &m))
    {
        build(1, 1, n);
        while(m--)
        {
            scanf("%s", cmd);
            if(!strcmp(cmd, "Ask"))
            {
                scanf("%d", &x);
                printf("%d\n", query(1, 1, n, x + 1, x + 1));
                continue;
            }
            scanf("%d%d", &x, &y);
            if(cmd[0] == 'Q')
                printf("%d\n", query(1, 1, n, x + 1, y + 1));
            else if(cmd[0] == 'C')
                update(1, 1, n, x + 1, x + 1, y, 0);
            else
                update(1, 1, n, x + 1, y + 1, 1, 1);
        }
    }
    return 0;
}

1355: 巧克力

Problem Description

TY最喜欢做的事情就是吃巧克力，经常幻想拥有吃不完的巧克力，作为一个acmer(菜机），IcY出了个问题准备考考她，如果回答出来，那巧克力自然是源源不断的啦。

IcY给出了一列排好的的巧克力，有的是德芙，有的是费列罗，它们都拥有不同的美味值……现在IcY通过魔法更改了这些巧克力，TY必须能指出排列中第K个是巧克力的美味值是多少和某一段巧克力中最美味的值是多少，才能吃到巧克力，否则，哼哼，就去乖乖的做题吧。现在，TY来寻求你的帮助，你能让poor TY吃上巧克力吗？

Input

输入数据有很多组，以EOF结尾。

每组数据第一行是2个整数N，M。N代表初始的巧克力数目，M代表操作数。

第二行含有n个正整数，代表每块巧克力的美味值wi。每块巧克力的下标从0–n-1。

接下来的M行，表示M个操作。

操作分4种：

Query x y 代表查询某一个区间内的美味最大值。

Ask x 代表查询某一块巧克力的美味值。

Change x y 代表将第x块的美味值变成y

Add x y 代表讲从第x块到第y块巧克力的美味值分别增加1.

（1 <= N<= 1000001<= M <= 100000Wi <= 5000）

Output

对于每一个Query输出一个整数，代表区间内的美味最大值。

对于每一个Ask 输出一个整数，代表这块巧克力的美味值。

Sample Input

10 4 1 2 3 4 5 6 7 8 9 10 Ask 0 Change 0 1 Add 0 2 Query 0 2

Sample Output

1 4

Posted on In ,

还是最基础的线段树噢 这次是区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid (s+e)/2

using namespace std;
const int N = 100005;
int sum[4 * N], setv[4 * N];
void pushup(int p)
{
    sum[p] = (sum[p << 1] + sum[p << 1 | 1]);
}

void pushdown(int p, int s, int e)
{
    if(setv[p] == 0) return;
    sum[p << 1] = (mid - s + 1) * setv[p];
    sum[p << 1 | 1] = (e - mid) * setv[p];
    setv[p << 1] = setv[p];
    setv[p << 1 | 1] = setv[p];
    setv[p] = 0;
}

void build(int p, int s, int e)
{
    setv[p] = 0;
    if(s == e) scanf("%d", &sum[p]);
    else
    {
        build(lc);
        build(rc);
        pushup(p);
    }
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(s >= l && e <= r)
    {
        setv[p] = v;
        sum[p] = (e - s + 1) * v;
        return;
    }
    pushdown(p, s, e);
    if(r <= mid) update(lc, l, r, v);
    else if(l > mid) update(rc, l, r, v);
    else update(lc, l, mid, v), update(rc, mid + 1, r, v);
    pushup(p);
}

int query(int p, int s, int e, int l, int r)
{
    if(s >= l && e <= r) return sum[p];
    pushdown(p, s, e);
    if(r <= mid) return query(lc, l, r);
    if(l > mid) return query(rc, l, r);
    return query(lc, l, mid) + query(rc, mid + 1, r);
}

int main()
{
    int n, m, a, b, c, op;
    while(~scanf("%d", &n))
    {
        build(1, 1, n);
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d", &op);
            if(op)
            {
                scanf("%d%d%d", &a, &b, &c);
                update(1, 1, n, a, b, c);
            }
            else
            {
                scanf("%d%d", &a, &b);
                printf("%d\n", query(1, 1, n, a, b));
            }
        }
    }
    return 0;
}

时间限制: 10000ms

单点时限: 1000ms
内存限制: 256MB

描述

对于小Ho表现出的对线段树的理解，小Hi表示挺满意的，但是满意就够了么？于是小Hi将问题改了改，又出给了小Ho：

假设货架上从左到右摆放了N种商品，并且依次标号为1到N，其中标号为i的商品的价格为Pi。小Hi的每次操作分为两种可能，第一种是修改价格——小Hi给出一段区间[L, R]和一个新的价格NewP，所有标号在这段区间中的商品的价格都变成NewP。第二种操作是询问——小Hi给出一段区间[L, R]，而小Ho要做的便是计算出所有标号在这段区间中的商品的总价格，然后告诉小Hi。

那么这样的一个问题，小Ho该如何解决呢？

提示：推动科学发展的除了人的好奇心之外还有人的懒惰心！

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为一个整数N，意义如前文所述。

每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量Pi。

每组测试数据的第3行为一个整数Q，表示小Hi进行的操作数。

每组测试数据的第N+4~N+Q+3行，每行分别描述一次操作，每行的开头均为一个属于0或1的数字，分别表示该行描述一个询问和一次商品的价格的更改两种情况。对于第N+i+3行，如果该行描述一个询问，则接下来为两个整数Li, Ri，表示小Hi询问的一个区间[Li, Ri]；如果该行描述一次商品的价格的更改，则接下来为三个整数Li，Ri，NewP，表示标号在区间[Li, Ri]的商品的价格全部修改为NewP。

对于100%的数据，满足N<=10^5，Q<=10^5, 1<=Li<=Ri<=N，1<=Pi<=N, 0<Pi, NewP<=10^4。

输出

对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的所有商品的价格之和。
样例输入 10 4733 6570 8363 7391 4511 1433 2281 187 5166 378 6 1 5 10 1577 1 1 7 3649 0 8 10 0 1 4 1 6 8 157 1 3 4 1557 样例输出 4731 14596

Posted on In ,

题意 求一组数中只出现过奇数次的数 输入保证只有一个数满足

知道一个数与自己的异或等于0 与0的异或等于自己就行咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
using namespace std;
int main()
{
    int n, t, ans;
    while(scanf("%d", &n), n)
    {
        ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &t);
            ans = ans ^ t;
        }
        printf("%d\n", ans);
    }
    return 0;
}

find your present (2)

Problem Description

In the new year party, everybody will get a “special present”.Now it’s your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.Each present has a card number on it, and your present’s card number will be the one that different from all the others, and you can assume that only one number appear odd times.For example, there are 5 present, and their card numbers are 1, 2, 3, 2, 1.so your present will be the one with the card number of 3, because 3 is the number that different from all the others.
Input

The input file will consist of several cases.
Each case will be presented by an integer n (1<=n<1000000, and n is odd) at first. Following that, n positive integers will be given in a line, all integers will smaller than 2^31. These numbers indicate the card numbers of the presents.n = 0 ends the input.
Output

For each case, output an integer in a line, which is the card number of your present.
Sample Input

5 1 1 3 2 2 3 1 2 1 0
Sample Output

3 2

Posted on In ,

题意 有一个无向图 对于其所有顶点的一个排列 称一顶点与所有与其有边的其它顶点在排列中下标差的最大值为这个顶点的带宽 而所有顶点带宽的最大值为这个排列的带宽 求这个图带宽最小的排列

枚举排列 ans记录当前找到的最小带宽 枚举过程中一旦出现带宽大于ans的也就不用再扩展了 这样枚举完就得到了答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 50;
int n, ans, h[N], vis[N], a[N], d[N][N], p[N];

void dfs(int cur, int band)
{
    if(cur >= n && band < ans)
    {
        ans = band;
        for(int i = 0; i < cur; ++i)
            p[i] = a[i];//p数组记录最优解路径
    }

    for(int i = 0; cur < n && i < 26; ++i)
    {
        if(vis[i] || !h[i]) continue;

        a[cur] = i , vis[i] = 1;
        for(int j = 0; j < cur; ++j)
            if(d[i][a[j]] && band < cur - j) band = cur - j;

        if(band > ans)
        {
            vis[i] = 0;
            return;
        }
        dfs(cur + 1, band);
        vis[i] = 0;
    }
}

int main()
{
    char s[N];
    while(scanf("%s", s), strcmp(s, "#"))
    {
        memset(d, 0, sizeof(d));
        memset(h, 0, sizeof(h));
        //h数组记录字母'A'+i是否在图中出现  n为顶点个数
        int i = n = 0, u, v;
        while(s[i])
        {
            u = s[i] - 'A';
            if(!h[u]) h[u] = ++n;
            i += 2;
            while(s[i] && s[i] != ';')
            {
                v = s[i++] - 'A';
                if(!h[v]) h[v] = ++n;
                d[u][v] = d[v][u] =  1;
            }
            if(!s[i++]) break;
        }

        ans = N;
        memset(vis, 0, sizeof(vis));
        dfs(0, 0);
        for(int i = 0; i < n; ++i)
            printf("%c ", 'A' + p[i]);
        printf("-> %d\n", ans);
    }
    return 0;
}

Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and an ordering on the elements in V, then the bandwidth of a node v is defined as the maximum distance in the ordering between v and any node to which it is connected in the graph. The bandwidth of the ordering is then defined as the maximum of the individual bandwidths. For example, consider the following graph:

picture25

This can be ordered in many ways, two of which are illustrated below:

picture47

For these orderings, the bandwidths of the nodes (in order) are 6, 6, 1, 4, 1, 1, 6, 6 giving an ordering bandwidth of 6, and 5, 3, 1, 4, 3, 5, 1, 4 giving an ordering bandwidth of 5.

Write a program that will find the ordering of a graph that minimises the bandwidth.

Input

Input will consist of a series of graphs. Each graph will appear on a line by itself. The entire file will be terminated by a line consisting of a single /#. For each graph, the input will consist of a series of records separated by ;'. Each record will consist of a node name (a single upper case character in the the range A’ to Z'), followed by a :’ and at least one of its neighbours. The graph will contain no more than 8 nodes.

Output

Output will consist of one line for each graph, listing the ordering of the nodes followed by an arrow (->) and the bandwidth for that ordering. All items must be separated from their neighbours by exactly one space. If more than one ordering produces the same bandwidth, then choose the smallest in lexicographic ordering, that is the one that would appear first in an alphabetic listing.

Sample input

A:FB;B:GC;D:GC;F:AGH;E:HD /#

Sample output

A B C F G D H E -> 3

Posted on In ,

题意 把1到n这n个数以1为首位围成一圈 输出所有满足任意相邻两数之和均为素数的所有排列

直接枚举排列看是否符合肯定会超时的 n最大为16 利用回溯法 边生成边判断 就要快很多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
using namespace std;
const int N = 50;
int p[N], vis[N], a[N], n;

int isPrime(int k)
{
    for(int i = 2; i * i <= k; ++i)
        if(k % i == 0) return 0;
    return 1;
}

void dfs(int cur)
{
    if(cur == n && p[a[n - 1] + 1])
    {
        printf("%d", a[0]);
        for(int i = 1; i < n; ++i)
            printf(" %d", a[i]);
        printf("\n");
    }

    for(int i = 2; cur < n && i <= n; ++i)
    {
        if(!vis[i] && p[a[cur - 1] + i])
        {
            vis[i] = a[cur] = i;
            dfs(cur + 1);
            vis[i] = 0;
        }
    }
}

int main()
{
    int cas = 0;
    a[0] = 1;
    for(int i = 2; i < N; ++i)
        p[i] = isPrime(i);

    while(~scanf("%d", &n))
    {
        if(cas) printf("\n");
        printf("Case %d:\n", ++cas);
        dfs(1);
    }

    return 0;
}

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers $1, 2, \dots, n$into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

n (0 < n <= 16)

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.

You are to write a program that completes above process.

6 8

Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2

Posted on In ,

题意 中文n/*n的棋盘放n个皇后(攻击同行/列/主副对角线) 使任何两个都不互相攻击 有多少种方法

枚举每一行 用vis[3][i]记录列 主对角线 副对角线是否被占 同列和对角线都没被占就继续枚举下一行 当枚举到n+1行的时候就是一个合法答案了

注: n/*n的方阵中主对角线可以用(i-j+n)标号 副对角线可以用(i+j)标号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//ans[]={0,1,0,0,2,10,4,40,92,352,724};
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 50;
int n, cnt, vis[3][N], ans[N];

void getans(int cur)
{
    if(cur == n)  ++cnt;

    for(int i = 0; cur < n && i < n; ++i)
    {
        if(vis[0][i] || vis[1][cur + i] || vis[2][cur - i + n]) continue;
        vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
        getans(cur + 1);
        vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
    }
}

int main()
{
    for(int i=1;i<=10;++i)
    {
        cnt = 0,n=i;
        getans(0);
        ans[i]=cnt;
    }
    while(scanf("%d", &n), n)
        printf("%d\n", ans[n]);
    return 0;
}

非递归的回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cmath>
using namespace std;
const int M = 20,  N = 8;
int col[M], vis[3][M], last[M], cnt;

bool check(int r) //判断前r行是否有冲突
{
    for(int i = 1; i < r; ++i) //主i + col[i] == r + col[r], 副i - col[i] == r - col[r]
        if(i + col[i] == r + col[r] || i - col[i] == r - col[r] || col[i] == col[r])
            return false;
    return true;
}

void gao()
{
    int r = 1;
    col[1] = 0;
    while(r)
    {
        col[r] = col[r] + 1; //第r行的皇后换新位置
        if(col[r] > N) {--r; continue;}
        if(!check(r)) continue;
        if(r == N)
        {
            for(int i = 1; i <= N; ++i)
                printf("%d ", col[i]);
            puts("");
            ++cnt;
        }
        else col[++r] = 0;
    }
}

int main()
{
    cnt = 0;
    gao();
    printf("%d\n", cnt);
    return 0;
}

还有可以打印答案的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000;
int n, cnt, c[N], col[N][N], vis[3][N];

void getans(int cur)
{
    if(cur == n)
    {
        ++cnt;
        for(int i = 0; i < n; ++i)
            col[cnt][i] = c[i];
    }
    else
    {
        for(int i = 0; i < n; ++i)
            if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n])
            {
                c[cur] = i;
                vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
                getans(cur + 1);
                vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
            }
    }
}

int main()
{
    while(scanf("%d", &n))
    {
        memset(vis, 0, sizeof(vis));
        cnt = 0;
        getans(0);
        printf("%d皇后问题共有%d组解:\n\n", n, cnt);

        for(int k = 1; k <= cnt; ++k)
        {
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                    printf("%d ", j == col[k][i]);
                printf("\n");
            }
            printf("\n");
        }
    }
    return 0;
}

N皇后问题

Problem Description

在N/*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input

1 8 5 0
Sample Output

1 92 10

Posted on In ,

题意 如果一个正整数y满足 将任意正整数x放到y的左边得到的数z满足 z%y==0 那么这个数就是个Magic Number 给你一个范围 求这个范围内Magic Number的个数

令 l表示y的位数 ly=10^l 那么z=x/*ly + y 要z%y==0 容易看出 只需 x/*ly%y==0

又因为x是任意的 所以一个Magic Number必须满足 ly%y==0

y<2^31 所以l最大为10 直接枚举l 找到所有符合的y就行了

当ly%y==0时y>=ly/10&&y<ly即ly是比y多一位数的令t=ly/y 那么肯定有1<t<=10对于每个ly 我们就只用枚举t了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 50;
typedef long long ll;
ll p[N], n, m;

int main()
{
    int cnt = 0, ans;   //ly为10^l
    for(ll ly = 10; ly < 1e11; ly *= 10)
    {
        for(ll t = 10; t > 1; --t)  //若(ly/y==t) 必有1<t<=10
            if(ly % t == 0) p[cnt++] = ly / t;
    }

    while(~scanf("%lld%lld", &n, &m))
    {
        ans = upper_bound(p, p + cnt, m) - lower_bound(p, p + cnt, n);
        printf("%d\n", ans);
    }
    return 0;
}

Magic Number Time Limit:2 Seconds Memory Limit:32768 KB

A positive number y is called magic number if for every positive integer x it satisfies that put y to the right of x, which will form a new integer z, z mod y = 0.

Input

The input has multiple cases, each case contains two positve integers m, n(1 <= m <= n <= 2^31-1), proceed to the end of file.

Output

For each case, output the total number of magic numbers between m and n(m, n inclusively).

Sample Input

1 1 1 10

Sample Output

1 4

0%