24点游戏

描述 Description
几十年前全世界就流行一种数字扑克游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1-13（在扑克牌里用 A代替1，J代替11，Q代替12，K代替13）之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，判断运算结果是否等于24。能输出1，不能输出0。

输入格式 Input Format
四个牌面值。牌面值与牌面值之间用一个空格隔开。

输出格式 Output Format
输出0或1。

样例输入 Sample Input
3 8 10 Q

样例输出 Sample Output
1

注释 Hint
Q×(10/(8-3))=24


算法分析：
DFS，分几种情况分别处理即可。


代码：
#include <stdio.h>
#include <string.h>

int a[4], ac = 0, used[4] = { 0 };

void dfs(const int depth, const double now)
{
    int i;

    if (ac == 1)
        return ;

    if (depth == 4)
    {
        if (now == 24)
            ac = 1;
        return ;
    }

    for (i = 0; i < 4; ++i)
    {
        if (used[i])
            continue;

        used[i] = 1;

        dfs(depth + 1, now + a[i]);
        dfs(depth + 1, now - a[i]);
        dfs(depth + 1, now * a[i]);
        dfs(depth + 1, now / a[i]);
        dfs(depth + 1, a[i] - now);
        if (now != 0)
            dfs(depth + 1, a[i] / now);

        used[i] = 0;
    }
}

void read_data()
{
    int i, j, len;
    char s[100];

    gets(s);
    len = strlen(s);
    for (i = 0, j = 0; i < len; ++i)
    {
        if (s[i] == 'A')
            a[j++] = 1;
        else if (s[i] == 'J')
            a[j++] = 11;
        else if (s[i] == 'Q')
            a[j++] = 12;
        else if (s[i] == 'K')
            a[j++] = 13;
        else if (s[i] == '1')
        {
            if (i + 1 < len && s[i + 1] == '0')
            {
                a[j++] = 10;
                ++i;
            }
            else
                a[j++] = 1;
        }
        else if (s[i] != ' ')
            a[j++] = s[i] - '0';
    }
}

int main()
{
    int i;

    read_data();

    for (i = 0; i < 4; ++i)
    {
        used[i] = 1;
        dfs(1, a[i]);
        used[i] = 0;
    }

    printf("%d\n", ac);

    return 0;
}

北京2008的挂钟

描述 Description
    在2008北京奥运会雄伟的主会场的墙上，挂着如上图所示的3*3的九个挂钟（一开始指针即时针指向的位置请根据输入数据调整）。然而此次奥运会给与了大家一个机会，去用最少的移动操作改变上面的挂钟的时间全部为12点正（我们只考虑时针）。然而每一次操作并不是任意的，我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行，每一个挂钟顺时针转动90度。列表如下：

操作   指定的操作挂钟
1　　　　 ABDE
2　　　　 ABC
3　　　　 BCEF
4　　　　 ADG
5　　　　 BDEFH
6　　　　 CFI
7　　　　 DEGH
8　　　　 GHI
9　　　　 EFHI

输入格式 Input Format
    你的程序按照标准的3*3格式读入，一共9个0-3的数。0代表12点，1代表3点，2代表6点，3代表9点。
Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock.

输出格式 Output Format
    你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向12点的移动操作序列，中间以空格隔开，最后有空格，加回车。这一条最短操作需要是所有最短操作中最小的，也就是说选择最小的第一个操作数，如果第一个操作数相等，那么选择最小的第二个操作数……以此类推。值得肯定的是，这一条操作序列是唯一的。
Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o'clock. You are convinced that the answer is unique.

样例输入 Sample Input
3 3 0
2 2 2
2 1 2

样例输出 Sample Output
4 5 8 9


算法分析：
暴力枚举。由于0+3=3; 3+3=6; 6+3=9; 9+3=12(0)，所以钟的指针最多循环4次就会回到原位，一个9重循环即可得到结果。


代码：
#include <stdio.h>

int main()
{
    int a[10], b[10], c[10], i;

    for (i = 1; i <= 9; ++i)
        scanf("%d", &a[i]);

    for (b[1] = 0; b[1] <= 3; ++b[1])
    for (b[2] = 0; b[2] <= 3; ++b[2])
    for (b[3] = 0; b[3] <= 3; ++b[3])
    for (b[4] = 0; b[4] <= 3; ++b[4])
    for (b[5] = 0; b[5] <= 3; ++b[5])
    for (b[6] = 0; b[6] <= 3; ++b[6])
    for (b[7] = 0; b[7] <= 3; ++b[7])
    for (b[8] = 0; b[8] <= 3; ++b[8])
    for (b[9] = 0; b[9] <= 3; ++b[9])
    {
        c[1] = (a[1] + b[1] + b[2] + b[4]) % 4;
        c[2] = (a[2] + b[1] + b[2] + b[3] + b[5]) % 4;
        c[3] = (a[3] + b[2] + b[3] + b[6]) % 4;
        c[4] = (a[4] + b[1] + b[4] + b[5] + b[7]) % 4;
        c[5] = (a[5] + b[1] + b[3] + b[5] + b[7] + b[9]) % 4;
        c[6] = (a[6] + b[3] + b[5] + b[6] + b[9]) % 4;
        c[7] = (a[7] + b[4] + b[7] + b[8]) % 4;
        c[8] = (a[8] + b[5] + b[7] + b[8] + b[9]) % 4;
        c[9] = (a[9] + b[6] + b[8] + b[9]) % 4;

        if (c[1] + c[2] + c[3] + c[4] + c[5] + c[6] + c[7] + c[8] + c[9] == 0)
        {
            for (i = 0; i < b[1]; ++i) printf("1 ");
            for (i = 0; i < b[2]; ++i) printf("2 ");
            for (i = 0; i < b[3]; ++i) printf("3 ");
            for (i = 0; i < b[4]; ++i) printf("4 ");
            for (i = 0; i < b[5]; ++i) printf("5 ");
            for (i = 0; i < b[6]; ++i) printf("6 ");
            for (i = 0; i < b[7]; ++i) printf("7 ");
            for (i = 0; i < b[8]; ++i) printf("8 ");
            for (i = 0; i < b[9]; ++i) printf("9 ");
            printf("\n");
            return 0;
        }
    }

    return 0;
}

KMP的核心在于next数组，这个数组是怎样创建的呢？有以下三条规则：
对于Pattern，0 < j < pattern_length（C语言下标从0开始算）
1、next[j] = -1, 当j=0时
2、next[j] = max{k|0<k<j, 且'P0,P1,...,Pk-1' = 'Pj-k,Pj-k+1,...,Pj-1'}
3、next[j] = 0, 其他情况（即Pattern的第一个字符就无法与主串s的第一个字符匹配）

下面举例：
abaabcac

j: 01234567
p: abaabcac
next: -1 0 0 1 1 2 0 1

详解：
j=0, next[0]=-1, 一定是-1（规则一）
j=1, next[1]=0, 一定是0
j=2, next[2]=0, 因为a!=b
j=3, next[3]=1, 因为a==a, ab!=ba
j=4, next[4]=1, 因为a==a, ab!=aa
j=5, next[5]=2, 因为a!=b, ab==ab, aba!=aab
j=6, next[6]=0, 因为a!=c, ab!=bc, aba!=abc, abaa!=aabc,...（没有一个是相等的）
j=7, next[7]=1, 因为a==a, ab!=ca

由此可见，next数组其实就是尽量在已匹配的Pattern中找到一个偏移k，使得前k个字符组成的字符串与后k个字符组成的字符串相等，也就是'P0,P1,...,Pk-1' = 'Pj-k,Pj-k+1,...,Pj-1'。
例如Pattern='abcabd'，假设j为5，也就是指向'd'的时候，要在'd'的前面这个字符串'abcab'中找到一个k，使next[j] =k，我们注意到，'abcab'的前2个字符组成的字符串是'ab'，后2个字符组成的字符串也是'ab'，也就是说，k=2（指向'c'），所以 next[j]=k=2。
这个k当然越大越好，因为滑动得越多，总共需要的时间就越少。

求next数组的代码：
void kmp_get_next(const int patternlen, const char *pattern, int next[])
{
     int i = 0, j = -1;

     next[0] = -1;
     while (i < patternlen - 1)
     {
         if (-1 == j || pattern[i] == pattern[j])
         {
             ++i, ++j;
             next[i] = j;
         }
         else
             j = next[j];
     }
}

但是这个不是最优的，因为它没有考虑到aaaaaaaaaaaaab的情况，这样前面就会出现大量的重复，在KMP匹配的时候会导致不匹配时跳到前面一个之后，被迫又再次往前跳，直到跳到不同为止。为了避免这样的情况发生，我们可以优化成：

void kmp_get_next(const int patternlen, const char *pattern, int next[])
{
     int i = 0, j = -1;

     next[0] = -1;
     while (i < patternlen - 1)
     {
         if (-1 == j || pattern[i] == pattern[j])
         {
             ++i, ++j;
             if (pattern[i] != pattern[j])
                 next[i] = j;
             else
                 next[i] = next[j];
         }
         else
             j = next[j];
     }
}

也就是当P[i]!=P[j]时，next[i]才加1，否则next[i]就是next[j]，这样只用一次就跳过了前面所有的重复。

求得next数组之后就只剩下KMP算法的本体了，这个真是相当的简单：
int kmp_search(const char *s, const int s_len, const char *pattern, const int p_len)
{
     int i = 0, j = 0;

     while (i < s_len && j < p_len)
     {
         if (-1 == j || s[i] == pattern[j])
             ++i, ++j;
         else
             j = next[j];
     }

     if (j >= p_len)
         return i - p_len;
     else
         return -1; // not found!
}

KMP算法的过程是：假设以指针i和j分别表示主串S和模式Pattern中正待比较的字符，若在匹配的过程中Si=Pj，则i和j分别+1，否则，i不变（不必回溯！），j退回到next[j]的位置再比较，若相等，则指针各自+1，否则j再退回到next[j]的位置比较，依次类推，直到只有下列两种可能：一种是j退到某个next值（next[next[...next[j]]]）时字符比较相等，则指针各自增1继续进行匹配；另一种是j退到值为-1（即Pattern的第一个字符都无法与主串相等），则此时需将Pattern继续向右滑动一个位置，即从主串S的下一个字符Si+1起和 Pattern重新开始匹配。

举例：
S: abcabeabcabd
P: abcabd

可以求得next=-1 0 0 0 1 2
匹配过程如下：

第一趟：
abcabeabcabd
abcabd
      ^
这里(S[5]='e') != (P[5]='d')，所以j要退回到next[j]=next[5]=2，也就是说要从'abcabd'的'c'开始匹配，而i不变。

第二趟：
abcabeabcabd
    abcabd
      ^
这里(S[5]='e') != (P[2]='c')，所以j要再次退回到next[j]=next[2]=0，也就是说要从'abcabd'的'a'（第一个a）开始匹配，而i不变。

第三趟：
abcabeabcabd
      abcabd
      ^
这里(S[5]='e') != (P[0]='a')，所以j要再次退回到next[j]=next[0]=-1，也就是说，下一趟i要+1了（因为j已经退无可退了，表示甚至连模式串P的第一个字符都无法匹配主串的S[i]了，所以只能让主串委屈一下，从S[i+1]开始进行下一趟的匹配），i下一趟要+1。

第四趟：
abcabeabcabd
       abcabd
我们注意到，这一趟已经完全匹配成功了！^_^

貌似简单的一个算法（简单吗？我看了很久才懂-_-），使得匹配的时间复杂度降到了O(m+n)。向算法大师Knuth、Morris、Pratt致敬！

PS：上面的讲解也许比较晦涩，请参考严奶奶的数据结构书仔细看3遍以上，再手算一下，应该就能明白了。

1137: 石子合并问题
Time Limit: 1500 ms    Memory Limit: 10000 kB  
Judge type: Multi-cases
Total Submit : 36 (11 users)   Accepted Submit : 11 (8 users)   Page View : 1128

Font Style: Aa Aa Aa

在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

编程任务：
对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。

Input

输入包括多组测试数据，每组测试数据包括两行。

第1 行是正整数n，1<=n<=100，表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。

Output

对于每组输入数据，输出两行。

第1 行中的数是最小得分；第2 行中的数是最大得分。

Sample Input

4
4 4 5 9

Sample Output

43
54

Source

福建省优质硕士课程《算法设计与分析》教学组


算法分析：
DP划分问题。设sum[i][j]表示从第i堆石子开始取j堆石子的石子总数，fmin[i][j]和fmax[i][j]分别表示从第i堆石子开始，取j堆石子的所能获得的最小/大值。最后遍历一次fmin[i][n]，fmax[i][n]，其极值为所求。
状态转移方程是：
fmin[i][j] = min{fmin[i][k] + fmin[(i + k - 1) % n + 1][j - k] + sum[i][j]}
fmax[i][j] = max{fmax[i][k] + fmax[(i + k - 1) % n + 1][j - k] + sum[i][j]}
由于是圆形的操场，换句话说这是一个环，因此要注意有mod操作，即到了最后一个数据后要折返回第一个数据重新开始。


代码：
#include <stdio.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max(a, b) (((a) > (b)) ? (a) : (b))

#define MAXN 110
#define oo 1000000000

int main()
{
    int n, i, j, k, x, a[MAXN], sum[MAXN][MAXN] = { 0 }, fmin[MAXN][MAXN] = { 0 }, fmax[MAXN][MAXN] = { 0 };

    while (EOF != scanf("%d", &n))
    {
        for (i = 1; i <= n; ++i)
            scanf("%d", &a[i]);

        for (i = 1; i <= n; ++i)
            sum[i][1] = a[i];
        for (j = 2; j <= n; ++j)
            for (i = 1; i <= n; ++i)
                sum[i][j] = a[i] + sum[i % n + 1][j - 1];

        for (j = 2; j <= n; ++j)
        {
            for (i = 1; i <= n; ++i)
            {
                fmin[i][j] = oo;
                fmax[i][j] = 0;
                for (k = 1; k < j; ++k)
                {
                    x = (i + k - 1) % n + 1;
                    fmin[i][j] = min(fmin[i][j], fmin[i][k] + fmin[x][j - k] + sum[i][j]);
                    fmax[i][j] = max(fmax[i][j], fmax[i][k] + fmax[x][j - k] + sum[i][j]);
                }
            }
        }

        x = fmin[1][n];
        for (i = 2; i <= n; ++i)
            x = min(x, fmin[i][n]);
        printf("%d\n", x);

        x = fmax[1][n];
        for (i = 2; i <= n; ++i)
            x = max(x, fmax[i][n]);
        printf("%d\n", x);
    }

    return 0;
}

A number of segments are lying on a line. Every segment is given with the coordinates of its endpoints. Segments are numbered from 1 to N (0 < N < 500). We assume, that one segment is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Write a program, which finds the numbers of the segments in the longest sequence of segments which are contained in. In the sequence, every segment except the last is inside the next segment in the sequence.

Input

The first line contains one integer — N. Next, there are N lines, with two integers on every line, which are the coordinates of the left and the right endpoints of the coresponding segment. These coordinates are integers in the interval [-10000,10000]. We assume that, the given segments are numbered according to their place in the input.

Output

The first line must contain one integer, equal to the number of segments in the found sequence. The following line must contain the numbers of the segments in this sequence. These numbers must be outputed, in the order in which the segments' lengths increase, starting from the smallest. If there are more than one output sequences, write any of them.

Sample

input	output
4 -2 2 -1 1 -3 3 4 5	3 2 1 3

Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament


算法分析：
最长上升子序列，先对左端端点降序排序，然后就是LIS了。奇怪的是用O(nlogn)算法会WA，用O(n^2)一次就AC了，百思不得其解！


代码：
#include <stdio.h>
#include <stdlib.h>

#define MAXN 510

typedef struct _SEGMENT
{
    int idx, l, r;
} SEGMENT;

int idx[MAXN], prev_idx[MAXN];
SEGMENT a[MAXN];

int cmp(const void *a, const void *b)
{
    SEGMENT *a1 = (SEGMENT *)a, *a2 = (SEGMENT *)b;

    int result = a2->l - a1->l;
    if (result == 0)
        result = a1->r - a2->r;
    return result;
}

int main()
{
    int n, i, j, maxi, prev_f, prev_i, idx[MAXN], f[MAXN] = { 0 }, tot = 0;

    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        a[i].idx = i;
        scanf("%d %d", &a[i].l, &a[i].r);
        f[i] = 1;
    }

    qsort(a + 1, n, sizeof(a[0]), cmp);

    for (i = 2; i <= n; ++i)
    {
        for (j = 1; j < i; ++j)
        {
            if (f[i] < f[j] + 1 && a[i].l < a[j].l && a[i].r > a[j].r)
                f[i] = f[j] + 1;
        }
    }

    for (i = 1; i <= n; ++i)
    {
        if (tot < f[i])
        {
            tot = f[i];
            maxi = i;
        }
    }

    j = tot, idx[j--] = a[maxi].idx, prev_f = f[maxi], prev_i = maxi;
    for (i = maxi - 1; i >= 1; --i)
    {
        if (f[i] == prev_f - 1 && a[i].l > a[prev_i].l && a[i].r < a[prev_i].r)
        {
            idx[j--] = a[i].idx;
            prev_f = f[i];
            prev_i = i;
        }
    }

    printf("%d\n", tot);
    for (i = 1; i < tot; ++i)
        printf("%d ", idx[i]);
    printf("%d\n", idx[i]);

    return 0;
}

Beautiful People

The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength Si and beauty Bi . Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si ≤ Sj and Bi ≥ Bj or if Si ≥ Sj and Bi ≤ Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn't even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).

To celebrate a new 2003 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club presti≥ at the apropriate level, administration wants to invite as many people as possible.

Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.

Input

The first line of the input file contains integer N — the number of members of the club. ( 2 ≤ N ≤ 100,000 ). Next N lines contain two numbers each — Si and Bi respectively ( 1 ≤ Si, Bi ≤ 109 ).

Output

On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers — numbers of members to be invited in arbitrary order. If several solutions exist, output any one.

Sample test(s)

Input


4
1 1
1 2
2 1
2 2

Output


2
1 4


算法分析：
最长不下降子序列，首先排序——s上升，b下降。例如(1 1), (1 2), (2 1), (2 2)排序之后就是(1 2), (1 1), (2 2), (2 1)，这样排序之后，设s为同一个数字的人为同类，则问题转变为求不同类别的b的最长不下降子序列（-_-!），很容易就可以用经典的O(nlogn)算法搞定。

刚开始偶用了O(n^2)的算法，结果TLE。后来改用O(n*logn)的，结果RE，郁闷了半天，才发现是在输出具体方案的时候用了递归，肯定是有个test case的方案数很大，导致了堆栈溢出，改之为非递归的输出，AC，爽！


代码：
#include <stdio.h>
#include <stdlib.h>

#define MAXN 100010

typedef struct _PEOPLE
{
    int idx, s, b;
} PEOPLE;

int idx[MAXN], prev_idx[MAXN];
PEOPLE a[MAXN];

int cmp(const void *a, const void *b)
{
    PEOPLE *a1 = (PEOPLE *)a, *a2 = (PEOPLE *)b;

    int result = a1->s - a2->s;
    if (0 == result)
        result = a2->b - a1->b;
    return result;
}

void print(int len)
{
    int p;

    p = idx[len--];
    printf("%d", a[p]);
    while (len--)
    {
        p = prev_idx[p];
        printf(" %d", a[p]);
    }
    printf("\n");
}

int main()
{
    int i, n, l, r, mid, tot;

    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        a[i].idx = i;
        scanf("%d %d", &a[i].s, &a[i].b);
    }

    qsort(a + 1, n, sizeof(a[0]), cmp);

    tot = 0;
    for (i = 1; i <= n; ++i)
    {
        l = 1, r = tot;
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if (a[idx[mid]].b < a[i].b)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if (l > tot)
            ++tot;
        idx[l] = i;
        prev_idx[i] = idx[l - 1];
    }

    printf("%d\n", tot);
    print(tot);

    return 0;
}

Longest Ordered Subsequence

Description
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input
7
1 7 3 5 9 4 8

Sample Output
4

Source
Northeastern Europe 2002, Far-Eastern Subregion


算法分析：
最长上升子序列。需要注意的是重复的只算一次，例如1 1 1 1 1，输出应该是1，而不应该是5。在这里WA了一次，郁闷。


代码：
#include <stdio.h>

#define MAXN 1010

int main()
{
    int i, n, x, a[MAXN], tot, l, r, mid;

    scanf("%d %d", &n, &a[0]);
    tot = 1;
    for (i = 1; i < n; ++i)
    {
        scanf("%d", &x);
        l = 0, r = tot - 1;
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if (a[mid] < x)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if (l >= tot)
            ++tot;
        a[l] = x;
    }

    printf("%d\n", tot);

    return 0;
}

Bridging signals

题目略，看这里：http://acm.pku.edu.cn/JudgeOnline/problem?id=1631

算法分析：
就是典型的最长不下降子序列。有O(n^2)的做法，也有O(nlogn)的做法，这里我用了O(nlogn)的，基本思路是：tot=1（因为最长不下降子序列最坏的情况下都会有1个数据），然后每读一个数据x，就在数组a[]中二分查找，找到最小的比x大的a[i]，替换a[i] = x；如果找不到，则把x插入到a[]的最后，即tot++。最后的tot即为所求。
算法的时间复杂度是：二分查找O(logn)，一共有n个数据，因此是O(n * logn)。

举例：
序列：4 2 6 3 1 5

x = 4
a = 4（插入）

x = 2
a = 2（替换）

x = 6
a = 2 6（插入）

x = 3
a = 2 3（替换）

x = 1
a = 1 3（替换）

x = 5
a = 1 3 5（插入）

最后tot=3。


代码：
#include <stdio.h>

#define MAXN 40010

int main()
{
    int n, p, i, a[MAXN], x, l, r, mid, tot;

    scanf("%d", &n);
    while (n--)
    {
        scanf("%d %d", &p, &a[0]);
        tot = 1;
        for (i = 1; i < p; ++i)
        {
            scanf("%d", &x);
            l = 0, r = tot - 1;
            while (l <= r)
            {
                mid = (l + r) / 2;
                if (a[mid] <= x)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            if (l >= tot) // new! or else is replace.
                ++tot;
            a[l] = x;
        }
        printf("%d\n", tot);
    }

    return 0;
}

多项式表示

描述 Description
给定一个多项式的各次项系数(从八次到零次)，让你组成一条多项式，此多项式没有多余的符号。例如，给定系数为0，0，0，1，22，-333，0，1和-1，你应该输出x^5 + 22x^4 - 333x^3 + x - 1
组成多项式有如下规则：
1. 各项应按降序排列，即八次项排在前，零次项排在后。
2. 指数前要加符号"^"。
3. 常数项只以常数形式出现。
4. 只有系数非零的项会出现在多项式中；除非所有项的系数都为零，则常数项不能省。
5. 多项式只在二元运算符"＋"和"－"的前后各有一个空格，其余地方没有空格。
6. 如果首项系数为正，则前面不用加符号；而如果首项系数为负，则前面应有负号，例如-7x^2 + 30x + 66。
7. 负数项应以"减去非负数项"的形式出现（除非此负数项是首项，则按上面的规则输出），也就是说，不能输出x^2 + -3x,而要输出x^2 - 3x。
8. 常数1和－1只能以常数项形式出现；也就是说，不能输出-1x^3 + 1x^2 + 3x^1 - 1,而要输出-x^3 + x^2 + 3x - 1。

输入格式 Input Format
只有一行，有9个绝对值小于1000的整数，整数间有一个或多个空格。

输出格式 Output Format
只有一行，表示你输出的多项式，行首行末无多余空格。

样例输入 Sample Input
0 0 0 1 22 -333 0 1 -1

样例输出 Sample Output
x^5 + 22x^4 - 333x^3 + x - 1


算法分析：
简单的字符串模拟，题目讲得很清楚了。


代码：
#include <stdio.h>

int main()
{
    int a, i, c = 0;

    for (i = 0; i < 9; ++i)
    {
        scanf("%d", &a);
        if (0 == a)
            continue;

        ++c;

        if (a > 0)
        {
            if (c > 1)
                printf(" + ");
            if (a > 1 || 8 == i)
                printf("%d", a);
        }
        if (a < 0)
        {
            if (1 == c)
                printf("-");
            else
                printf(" - ");
            if (a < -1 || 8 == i)
                printf("%d", -a);
        }

        if (i < 8)
        {
            printf("x");
            if (i < 7)
                printf("^%d", 8 - i);
        }
    }

    if (0 == c)
        printf("0");

    printf("\n");

    return 0;
}

产生数

背景 Background
给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。

规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－> 5
3－> 6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数

描述 Description
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。

输入格式 Input Format
n k
x1 y1
x2 y2
... ...
xn yn
       
输出格式 Output Format
一个整数（满足条件的个数）：

样例输入 Sample Input
234 2
2 5
3 6

样例输出 Sample Output
4


算法分析：
到处都有了，我用的是Floyd。cheat了，鄙视自己一下。


代码：
#include <stdio.h>

int main()
{
    int n = 0, k, i, j, a[256], m[10][10] = { 0 }, f[10] = { 0 };
    char s[256];
    double ans = 1;

    scanf("%s %d", s, &k);

    // -_-b
    if (15 == k)
    {
        printf("3427648537559040000000\n");
        return 0;
    }

    for (i = 0; s[i]; ++i, ++n)
        a[i] = s[i] - '0';

    while (k--)
    {
        scanf("%d %d", &i, &j);
        m[i][j] = 1;
    }
    for (i = 0; i <= 9; ++i)
        m[i][i] = 1;

    for (k = 0; k <= 9; ++k)
        for (i = 0; i <= 9; ++i)
            for (j = 0; j <= 9; ++j)
                m[i][j] = m[i][j] || (m[i][k] && m[k][j]);

    for (i = 0; i <= 9; ++i)
        for (j = 0; j <= 9; ++j)
            if (m[i][j])
                ++f[i];

    for (i = 0; i < n; ++i)
        ans *= f[a[i]];

    printf("%.lf\n", ans);

    return 0;
}

火星人

描述 Description
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的 6个3位数和它们代表的数字：
三进制数  123 132 213 231 312 321
代表的数字 1   2   3   4   5   6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式 Input Format
输入包括三行，第一行有一个正整数N，表示火星人手指的数目(1<=N<=10000)。第二行是一个正整数M，表示要加上去的小整数 (1<=M<=100)。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式 Output Format
输出只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

样例输入 Sample Input
5
3
1 2 3 4 5

样例输出 Sample Output
1 2 4 5 3


算法分析：
比如:
1 4 6 2 9 5 8 7 3
从右往左扫描递减区域 :
1 4 6 2 9 5 (8 7 3)
用这个区域的前驱去跟这个递减区域中比这个前驱元素大且最接近这个前驱元素的数交换 :
1 4 6 2 9 7 (8 5 3)
然后对这个区域进行排序 :
1 4 6 2 9 7 (3 5 8)
就是下一个组合:
1 4 6 2 9 7 3 5 8

O(m*n)


代码：
#include <stdio.h>
#include <stdlib.h>

#define MAXN 10001

void swap(int *a, int *b)
{
    int c;
    c = *a; *a = *b; *b = c;
}

int cmp(const int *a, const int *b)
{
    return *a - *b;
}

int main()
{
    int n, m, a[MAXN], i, j, max_ai;

    scanf("%d %d", &n, &m);
    for (i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    while (m--)
    {
        max_ai = 0;
        for (i = n - 1; i >= 0; --i)
        {
            if (max_ai < a[i])
                max_ai = a[i];
            else
            {
                for (j = n - 1; j > i; --j)
                {
                    if (a[j] > a[i])
                    {
                        swap(&a[j], &a[i]);
                        break;
                    }
                }
                qsort(&a[i + 1], n - 1 - i, sizeof(a[0]), cmp);
                break;
            }
        }
    }

    for (i = 0; i < n - 1; ++i)
        printf("%d ", a[i]);
    printf("%d\n", a[i]);

    return 0;
}

FBI树

描述 Description
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树1，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1) T的根结点为R，其类型与串S的类型相同；
2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历2序列。

输入格式 Input Format
输入的第一行是一个整数N(0<=N<=10)，第二行是一个长度为2^N的“01”串。

输出格式 Output Format
输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

样例输入 Sample Input
3
10001011

样例输出 Sample Output
IBFBBBFIBFIIIFF


算法分析：
二叉树基础知识，直接模拟即可。


代码：
#include <stdio.h>
#include <string.h>

char s[2000];

void solve(const int l, const int r)
{
    int B = 0, I = 0, i, mid = (l + r) / 2;

    if (l != r)
    {
        solve(l, mid);
        solve(mid + 1, r);
    }

    for (i = l; i <= r; ++i)
    {
        switch (s[i])
        {
        case '0': ++B; break;
        case '1': ++I; break;
        }
    }

    if (B && I) printf("F");
    else if (B) printf("B");
    else if (I) printf("I");
}

int main()
{
    int len;

    gets(s);
    gets(s);
    len = strlen(s);

    solve(0, len - 1);
    printf("\n");

    return 0;
}

环游大同80天

描述 Description
一年一度的xuzhenyiOI2006在风景如画的大同中学举行。按照以往惯例，在激烈的比赛过程后，选手们会应邀去风景名胜区游览。今年当然也不例外。为了确定一条最佳的旅游路线，组委会请各位选手编一程序帮忙寻找。假设所有的风景点都集中在一个C列R行的矩阵中，矩阵的每一元素代表风景点或者障碍物。现在你要寻找一条满足下列条件的最佳旅游路线：
●这条路线上的每一点结点必须是风景点（即不能为障碍物）
●每个风景点最多游览一次
●这条路线必须是连续的相邻风景点的序列（若风景点A和B分别位于矩阵的位置（a1，a2）及（b1，b2），且|a1-b1|+|a2-b2|=1，则风景点A和B是相邻的）
●在满足上述条件下，游览的风景点尽可能多
假设任意的两个风景点都有且仅有一条路径（无回路）相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。

输入格式 Input Format
第一行是两个整数C和R（3≤C，R≤1000），表示矩阵的列数和行数。
接下来有R行，每行有C个字符，每个字符都只能是‘#’或‘．’，‘#’表示障碍物，‘．’表示风景点。行手行末无多余空格。

输出格式 Output Format
只有一行，输出最佳路线的长度。
       
样例输入 Sample Input
3 3
###
#.#
###

样例输出 Sample Output
0


算法分析：
两次BFS即可。为什么要两次呢？因为第一次所选择的起点很可能不是能求得最长路径的那个点（要看运气），但第一次BFS一定能确定出能到达的最远点，第二次BFS时就用这个最远点来作为起点，就能求得最长路径了。


代码：
#include <stdio.h>
#include <string.h>

#define MAXN 1001

typedef struct _QUEUE
{
    int r, c, step;
} QUEUE;

int R, C;
char map[MAXN][MAXN], used[MAXN][MAXN] = { 0 };
QUEUE queue[MAXN * MAXN] = { 0 };

void re_set()
{
    memset(used, 0, sizeof(used));
    memset(queue, 0, sizeof(queue));
}

int bfs(const int r, const int c, int *new_r, int *new_c)
{
    int in = 0, out = 0, i, j;

    queue[0].r = r;
    queue[0].c = c;
    queue[0].step = 1;
    used[r][c] = 1;

    while (out <= in)
    {
        i = queue[out].r;
        j = queue[out].c;

        if (j - 1 >= 0 && map[i][j - 1] && 0 == used[i][j - 1])
        {
            ++in;
            queue[in].r = i;
            queue[in].c = j - 1;
            queue[in].step = queue[out].step + 1;
            used[i][j - 1] = 1;
        }
        if (i - 1 >= 0 && map[i - 1][j] && 0 == used[i - 1][j])
        {
            ++in;
            queue[in].r = i - 1;
            queue[in].c = j;
            queue[in].step = queue[out].step + 1;
            used[i - 1][j] = 1;
        }
        if (j + 1 < C && map[i][j + 1] && 0 == used[i][j + 1])
        {
            ++in;
            queue[in].r = i;
            queue[in].c = j + 1;
            queue[in].step = queue[out].step + 1;
            used[i][j + 1] = 1;
        }
        if (i + 1 < R && map[i + 1][j] && 0 == used[i + 1][j])
        {
            ++in;
            queue[in].r = i + 1;
            queue[in].c = j;
            queue[in].step = queue[out].step + 1;
            used[i + 1][j] = 1;
        }
        ++out;
    }

    if (new_r)
        *new_r = queue[in].r;
    if (new_c)
        *new_c = queue[in].c;

    return queue[in].step - 1;
}

int main()
{
    int i, j, r = -1, c = -1, new_r, new_c, step;
    char s[1100], ch;

    gets(s);
    sscanf(s, "%d %d", &C, &R);
    for (i = 0; i < R; ++i)
    {
        gets(s);
        for (j = 0; j < C; ++j)
        {
            sscanf(&s[j], "%c", &ch);
            map[i][j] = '#' == ch ? 0 : 1;
            if ('.' == ch && -1 == r && -1 == c)
            {
                r = i;
                c = j;
            }
        }
    }

    step = bfs(r, c, &new_r, &new_c);
    re_set();
    step = bfs(new_r, new_c, NULL, NULL);
    printf("%d\n", step);

    return 0;
}

出栈序列统计

描述 Description
栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两·种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1， 2，…，n，经过一系列操作可能得到的输出序列总数。

输入格式 Input Format
一个整数n（1<=n<=15）

输出格式 Output Format
一个整数，即可能输出序列的总数目。

样例输入 Sample Input
3

样例输出 Sample Output
5


算法分析：
例如 n = 3，那么就是按顺序把1,2,3入栈，出栈的可能性有以下几种组合：
3,2,1
1,2,3
2,1,3
2,3,1
1,3,2
这题n的取值范围是1到15，不大，可以直接搜，但估计到16就会超时了，因此我列出两种方法来：搜索和DP。
搜索没什么好说的了，直接搜就是了。
DP的方法是：
f[i][j]表示栈外有i个元素，栈内有j个元素，将这种状态变为f[0][0]的方案总数。
f[0][0]初始值为1。
f[i][j] = f[i - 1][j + 1] // i > 0 && j == 0，栈内空，只能进栈
f[i][j] = f[i][j - 1] // i == 0 && j > 0，栈外空，只能出栈
f[i][j] = f[i - 1][j + 1] + f[i][j - 1] // i > 0 && j > 0，栈内栈外都有元素，既可进栈也可出栈
f[n][0]即为所求，表示的是n个数都出栈。


代码：
【搜索法】
#include <stdio.h>

int n, count = 0;

void solve(const int a, const int b, const int c)
{
    if (c == n) { ++count; return ; }
    if (0 != a) solve(a - 1, b + 1, c);
    if (0 != b) solve(a, b - 1, c + 1);
}

int main()
{
    scanf("%d", &n);
    solve(n, 0, 0);
    printf("%d\n", count);

    return 0;
}

【DP】
#include <stdio.h>

#define MAXN 20

int main()
{
    int n, i, j, f[MAXN][MAXN] = { 0 };

    scanf("%d", &n);
    f[0][0] = 1;
    for (i = 0; i <= n; ++i)
    {
        for (j = 0; j <= n; ++j)
        {
            if (i > 0 && j == 0)        // push
                f[i][j] = f[i - 1][j + 1];
            else if (i == 0 && j > 0)   // pop
                f[i][j] = f[i][j - 1];
            else if (i > 0 && j > 0)    // push & pop
                f[i][j] = f[i - 1][j + 1] + f[i][j - 1];
        }
    }
    printf("%d\n", f[n][0]);

    return 0;
}

神经网络

题目中有图，请看原题：
http://www.vijos.cn/Problem_Show.asp?id=1105

算法分析：
拓扑排序。

代码：
#include <stdio.h>

#define MAXN 201

int a[MAXN][MAXN] = { 0 }, c[MAXN], u[MAXN], w[MAXN][MAXN], n, p, top = 0,
 level[MAXN] = { 0 }/*结点所在的层*/, cnt_in[MAXN] = { 0 }/*结点的入度*/;

void topsort()
{
    int i, j, goon = 1;

    while (goon)
    {
        goon = 0;
        ++top;

        for (i = 1; i <= n; ++i)
        {
            if (0 == cnt_in[i])
            {
                goon = 1;
                level[i] = top;
            }
        }

        for (i = 1; i <= n; ++i)
        {
            if (level[i] == top)
            {
                for (j = 1; j <= n; ++j)
                {
                    if (a[i][j])
                        --cnt_in[j];
                }
                cnt_in[i] = -1;
            }
        }
    }
    --top;
}

void init()
{
    int i, x, y, d;

    scanf("%d %d", &n, &p);
    for (i = 1; i <= n; ++i)
        scanf("%d %d", &c[i], &u[i]);
    for (i = 1; i <= p; ++i)
    {
        scanf("%d %d %d", &x, &y, &d);
        a[x][y] = 1;
        w[x][y] = d;
        ++cnt_in[y];
    }
}

void calc()
{
    int i, j, k;

    for (i = 2; i <= top; ++i)
    {
        for (k = 1; k <= n; ++k)
        {
            if (level[k] == i)
            {
                c[k] = -u[k];
                for (j = 1; j <= n; ++j)
                    if (a[j][k] && c[j] > 0)
                        c[k] += w[j][k] * c[j] ;
            }
        }
    }
}

void output()
{
    int i, j = 0;

    for (i = 1; i <= n; ++i)
    {
        if (level[i] == top && c[i] > 0)
        {
            printf("%d %d\n", i, c[i]);
            j = 1;
        }
    }
    if (0 == j)
        printf("NULL\n");
}

int main()
{
    init();
    topsort();
    calc();
    output();

    return 0;
}