{"id":598,"date":"2022-07-12T14:49:37","date_gmt":"2022-07-12T06:49:37","guid":{"rendered":"http:\/\/www.xuanchenbin.cn\/?p=598"},"modified":"2022-07-12T14:49:37","modified_gmt":"2022-07-12T06:49:37","slug":"pat%e4%b9%a0%e9%a2%98%e7%bb%83%e4%b9%a0%e8%ae%b0%e5%bd%95","status":"publish","type":"post","link":"http:\/\/www.xuanchenbin.cn\/?p=598","title":{"rendered":"PAT\u4e60\u9898\u7ec3\u4e60\u8bb0\u5f55"},"content":{"rendered":"

\u4e2d\u56fd\u5927\u5b66MOOC-\u9648\u8d8a\u3001\u4f55\u94a6\u94ed-\u6570\u636e\u7ed3\u6784-2022\u590f<\/h1>\n

\u51fd\u6570\u9898<\/h2>\n

01-\u590d\u6742\u5ea63 \u4e8c\u5206\u67e5\u627e<\/h3>\n

\u672c\u9898\u8981\u6c42\u5b9e\u73b0\u4e8c\u5206\u67e5\u627e\u7b97\u6cd5\u3002<\/strong>
\n\u51fd\u6570\u63a5\u53e3\u5b9a\u4e49\uff1a<\/p>\n

Position BinarySearch( List L, ElementType X );\n<\/code><\/pre>\n
\u5176\u4e2d List \u7ed3\u6784\u5b9a\u4e49\u5982\u4e0b\uff1a<\/strong><\/p>\n
typedef int Position;\ntypedef struct LNode *List;\nstruct LNode {\n    ElementType Data[MAXSIZE];\n    Position Last; \/* \u4fdd\u5b58\u7ebf\u6027\u8868\u4e2d\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u4f4d\u7f6e *\/\n};\n<\/code><\/pre>\n
L\u662f\u7528\u6237\u4f20\u5165\u7684\u4e00\u4e2a\u7ebf\u6027\u8868\uff0c\u5176\u4e2dElementType\u5143\u7d20\u53ef\u4ee5\u901a\u8fc7>\u3001==\u3001<\u8fdb\u884c\u6bd4\u8f83\uff0c\u5e76\u4e14\u9898\u76ee\u4fdd\u8bc1\u4f20\u5165\u7684\u6570\u636e\u662f\u9012\u589e\u6709\u5e8f\u7684\u3002\u51fd\u6570BinarySearch\u8981\u67e5\u627eX\u5728Data\u4e2d\u7684\u4f4d\u7f6e\uff0c\u5373\u6570\u7ec4\u4e0b\u6807\uff08\u6ce8\u610f\uff1a\u5143\u7d20\u4ece\u4e0b\u68071\u5f00\u59cb\u5b58\u50a8\uff09\u3002\u627e\u5230\u5219\u8fd4\u56de\u4e0b\u6807\uff0c\u5426\u5219\u8fd4\u56de\u4e00\u4e2a\u7279\u6b8a\u7684\u5931\u8d25\u6807\u8bb0NotFound\u3002<\/p>\n
\u88c1\u5224\u6d4b\u8bd5\u7a0b\u5e8f\u6837\u4f8b\uff1a<\/strong><\/p>\n
#include <stdio.h>\n#include <stdlib.h>\n#define MAXSIZE 10\n#define NotFound 0\ntypedef int ElementType;\ntypedef int Position;\ntypedef struct LNode *List;\nstruct LNode {\n    ElementType Data[MAXSIZE];\n    Position Last; \/* \u4fdd\u5b58\u7ebf\u6027\u8868\u4e2d\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u4f4d\u7f6e *\/\n};\nList ReadInput(); \/* \u88c1\u5224\u5b9e\u73b0\uff0c\u7ec6\u8282\u4e0d\u8868\u3002\u5143\u7d20\u4ece\u4e0b\u68071\u5f00\u59cb\u5b58\u50a8 *\/\nPosition BinarySearch( List L, ElementType X );\nint main()\n{\n    List L;\n    ElementType X;\n    Position P;\n    L = ReadInput();\n    scanf("%d", &X);\n    P = BinarySearch( L, X );\n    printf("%d\\n", P);\n    return 0;\n}\n\/* \u4f60\u7684\u4ee3\u7801\u5c06\u88ab\u5d4c\u5728\u8fd9\u91cc *\/\n<\/code><\/pre>\n
\u8f93\u5165\u6837\u4f8b1\uff1a<\/strong>
\n5
\n12 31 55 89 101
\n31<\/p>\n
\u8f93\u51fa\u6837\u4f8b1\uff1a<\/strong>
\n2<\/p>\n
\u8f93\u5165\u6837\u4f8b2\uff1a<\/strong>
\n3
\n26 78 233
\n31<\/p>\n
\u8f93\u51fa\u6837\u4f8b2\uff1a<\/strong>
\n0<\/p>\n
\u4ee3\u7801\u957f\u5ea6\u9650\u5236
\n16 KB
\n\u65f6\u95f4\u9650\u5236
\n100 ms
\n\u5185\u5b58\u9650\u5236
\n64MB<\/p>\n
02-\u7ebf\u6027\u7ed3\u67841 \u4e24\u4e2a\u6709\u5e8f\u94fe\u8868\u5e8f\u5217\u7684\u5408\u5e76<\/h3>\n
\u672c\u9898\u8981\u6c42\u5b9e\u73b0\u4e00\u4e2a\u51fd\u6570\uff0c\u5c06\u4e24\u4e2a\u94fe\u8868\u8868\u793a\u7684\u9012\u589e\u6574\u6570\u5e8f\u5217\u5408\u5e76\u4e3a\u4e00\u4e2a\u975e\u9012\u51cf\u7684\u6574\u6570\u5e8f\u5217\u3002<\/p>\n
\u51fd\u6570\u63a5\u53e3\u5b9a\u4e49\uff1a<\/strong><\/p>\n
List Merge( List L1, List L2 );\n<\/code><\/pre>\n
\u5176\u4e2dList\u7ed3\u6784\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n
typedef struct Node *PtrToNode;\nstruct Node {\n    ElementType Data; \/* \u5b58\u50a8\u7ed3\u70b9\u6570\u636e *\/\n    PtrToNode   Next; \/* \u6307\u5411\u4e0b\u4e00\u4e2a\u7ed3\u70b9\u7684\u6307\u9488 *\/\n};\ntypedef PtrToNode List; \/* \u5b9a\u4e49\u5355\u94fe\u8868\u7c7b\u578b *\/\n<\/code><\/pre>\n
L1\u548cL2\u662f\u7ed9\u5b9a\u7684\u5e26\u5934\u7ed3\u70b9\u7684\u5355\u94fe\u8868\uff0c\u5176\u7ed3\u70b9\u5b58\u50a8\u7684\u6570\u636e\u662f\u9012\u589e\u6709\u5e8f\u7684\uff1b\u51fd\u6570Merge\u8981\u5c06L1\u548cL2\u5408\u5e76\u4e3a\u4e00\u4e2a\u975e\u9012\u51cf\u7684\u6574\u6570\u5e8f\u5217\u3002\u5e94\u76f4\u63a5\u4f7f\u7528\u539f\u5e8f\u5217\u4e2d\u7684\u7ed3\u70b9\uff0c\u8fd4\u56de\u5f52\u5e76\u540e\u7684\u5e26\u5934\u7ed3\u70b9\u7684\u94fe\u8868\u5934\u6307\u9488\u3002
\n\u88c1\u5224\u6d4b\u8bd5\u7a0b\u5e8f\u6837\u4f8b\uff1a<\/p>\n
#include <stdio.h>\n#include <stdlib.h>\ntypedef int ElementType;\ntypedef struct Node *PtrToNode;\nstruct Node {\n    ElementType Data;\n    PtrToNode   Next;\n};\ntypedef PtrToNode List;\nList Read(); \/* \u7ec6\u8282\u5728\u6b64\u4e0d\u8868 *\/\nvoid Print( List L ); \/* \u7ec6\u8282\u5728\u6b64\u4e0d\u8868\uff1b\u7a7a\u94fe\u8868\u5c06\u8f93\u51faNULL *\/\nList Merge( List L1, List L2 );\nint main()\n{\n    List L1, L2, L;\n    L1 = Read();\n    L2 = Read();\n    L = Merge(L1, L2);\n    Print(L);\n    Print(L1);\n    Print(L2);\n    return 0;\n}\n\/* \u4f60\u7684\u4ee3\u7801\u5c06\u88ab\u5d4c\u5728\u8fd9\u91cc *\/\n<\/code><\/pre>\n
\u8f93\u5165\u6837\u4f8b\uff1a<\/strong>
\n3
\n1 3 5
\n5
\n2 4 6 8 10<\/p>\n
\u8f93\u51fa\u6837\u4f8b\uff1a<\/strong>
\n1 2 3 4 5 6 8 10
\nNULL
\nNULL<\/p>\n
\u4ee3\u7801\u957f\u5ea6\u9650\u5236
\n16 KB
\n\u65f6\u95f4\u9650\u5236
\n400 ms
\n\u5185\u5b58\u9650\u5236
\n64MB<\/p>\n
04-\u68117 \u4e8c\u53c9\u641c\u7d22\u6811\u7684\u64cd\u4f5c\u96c6<\/h3>\n
\u672c\u9898\u8981\u6c42\u5b9e\u73b0\u7ed9\u5b9a\u4e8c\u53c9\u641c\u7d22\u6811\u76845\u79cd\u5e38\u7528\u64cd\u4f5c\u3002<\/p>\n
\u51fd\u6570\u63a5\u53e3\u5b9a\u4e49\uff1a<\/strong><\/p>\n
BinTree Insert( BinTree BST, ElementType X );\nBinTree Delete( BinTree BST, ElementType X );\nPosition Find( BinTree BST, ElementType X );\nPosition FindMin( BinTree BST );\nPosition FindMax( BinTree BST );\n<\/code><\/pre>\n
\u5176\u4e2dBinTree\u7ed3\u6784\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n
typedef struct TNode *Position;\ntypedef Position BinTree;\nstruct TNode{\n    ElementType Data;\n    BinTree Left;\n    BinTree Right;\n};\n<\/code><\/pre>\n
    \n
  • \u51fd\u6570Insert\u5c06X\u63d2\u5165\u4e8c\u53c9\u641c\u7d22\u6811BST\u5e76\u8fd4\u56de\u7ed3\u679c\u6811\u7684\u6839\u7ed3\u70b9\u6307\u9488\uff1b<\/li>\n
  • \u51fd\u6570Delete\u5c06X\u4ece\u4e8c\u53c9\u641c\u7d22\u6811BST\u4e2d\u5220\u9664\uff0c\u5e76\u8fd4\u56de\u7ed3\u679c\u6811\u7684\u6839\u7ed3\u70b9\u6307\u9488\uff1b\u5982\u679cX\u4e0d\u5728\u6811\u4e2d\uff0c\u5219\u6253\u5370\u4e00\u884cNot Found\u5e76\u8fd4\u56de\u539f\u6811\u7684\u6839\u7ed3\u70b9\u6307\u9488\uff1b<\/li>\n
  • \u51fd\u6570Find\u5728\u4e8c\u53c9\u641c\u7d22\u6811BST\u4e2d\u627e\u5230X\uff0c\u8fd4\u56de\u8be5\u7ed3\u70b9\u7684\u6307\u9488\uff1b\u5982\u679c\u627e\u4e0d\u5230\u5219\u8fd4\u56de\u7a7a\u6307\u9488\uff1b<\/li>\n
  • \u51fd\u6570FindMin\u8fd4\u56de\u4e8c\u53c9\u641c\u7d22\u6811BST\u4e2d\u6700\u5c0f\u5143\u7ed3\u70b9\u7684\u6307\u9488\uff1b<\/li>\n
  • \u51fd\u6570FindMax\u8fd4\u56de\u4e8c\u53c9\u641c\u7d22\u6811BST\u4e2d\u6700\u5927\u5143\u7ed3\u70b9\u7684\u6307\u9488\u3002
    \n\u88c1\u5224\u6d4b\u8bd5\u7a0b\u5e8f\u6837\u4f8b\uff1a<\/li>\n<\/ul>\n
    #include <stdio.h>\n#include <stdlib.h>\ntypedef int ElementType;\ntypedef struct TNode *Position;\ntypedef Position BinTree;\nstruct TNode{\n    ElementType Data;\n    BinTree Left;\n    BinTree Right;\n};\nvoid PreorderTraversal( BinTree BT ); \/* \u5148\u5e8f\u904d\u5386\uff0c\u7531\u88c1\u5224\u5b9e\u73b0\uff0c\u7ec6\u8282\u4e0d\u8868 *\/\nvoid InorderTraversal( BinTree BT );  \/* \u4e2d\u5e8f\u904d\u5386\uff0c\u7531\u88c1\u5224\u5b9e\u73b0\uff0c\u7ec6\u8282\u4e0d\u8868 *\/\nBinTree Insert( BinTree BST, ElementType X );\nBinTree Delete( BinTree BST, ElementType X );\nPosition Find( BinTree BST, ElementType X );\nPosition FindMin( BinTree BST );\nPosition FindMax( BinTree BST );\nint main()\n{\n    BinTree BST, MinP, MaxP, Tmp;\n    ElementType X;\n    int N, i;\n    BST = NULL;\n    scanf("%d", &N);\n    for ( i=0; i<N; i++ ) {\n        scanf("%d", &X);\n        BST = Insert(BST, X);\n    }\n    printf("Preorder:"); PreorderTraversal(BST); printf("\\n");\n    MinP = FindMin(BST);\n    MaxP = FindMax(BST);\n    scanf("%d", &N);\n    for( i=0; i<N; i++ ) {\n        scanf("%d", &X);\n        Tmp = Find(BST, X);\n        if (Tmp == NULL) printf("%d is not found\\n", X);\n        else {\n            printf("%d is found\\n", Tmp->Data);\n            if (Tmp==MinP) printf("%d is the smallest key\\n", Tmp->Data);\n            if (Tmp==MaxP) printf("%d is the largest key\\n", Tmp->Data);\n        }\n    }\n    scanf("%d", &N);\n    for( i=0; i<N; i++ ) {\n        scanf("%d", &X);\n        BST = Delete(BST, X);\n    }\n    printf("Inorder:"); InorderTraversal(BST); printf("\\n");\n    return 0;\n}\n\/* \u4f60\u7684\u4ee3\u7801\u5c06\u88ab\u5d4c\u5728\u8fd9\u91cc *\/\n<\/code><\/pre>\n
    \u8f93\u5165\u6837\u4f8b\uff1a<\/strong>
    \n10
    \n5 8 6 2 4 1 0 10 9 7
    \n5
    \n6 3 10 0 5
    \n5
    \n5 7 0 10 3<\/p>\n
    \u8f93\u51fa\u6837\u4f8b\uff1a<\/strong>
    \nPreorder: 5 2 1 0 4 8 6 7 10 9
    \n6 is found
    \n3 is not found
    \n10 is found
    \n10 is the largest key
    \n0 is found
    \n0 is the smallest key
    \n5 is found
    \nNot Found
    \nInorder: 1 2 4 6 8 9<\/p>\n
    \u4ee3\u7801\u957f\u5ea6\u9650\u5236
    \n16 KB
    \n\u65f6\u95f4\u9650\u5236
    \n400 ms
    \n\u5185\u5b58\u9650\u5236
    \n64MB<\/p>\n
    \u7f16\u7a0b\u9898<\/h2>\n
    01-\u590d\u6742\u5ea61 \u6700\u5927\u5b50\u5217\u548c\u95ee\u9898<\/h3>\n
    \u7ed9\u5b9aK\u4e2a\u6574\u6570\u7ec4\u6210\u7684\u5e8f\u5217{\u00a0N1\u200b,\u00a0N2\u200b, …,\u00a0NK\u200b\u00a0}\uff0c\u201c\u8fde\u7eed\u5b50\u5217\u201d\u88ab\u5b9a\u4e49\u4e3a{\u00a0Ni\u200b,\u00a0Ni+1\u200b, …,\u00a0Nj\u200b\u00a0}\uff0c\u5176\u4e2d\u00a01\u2264i\u2264j\u2264K\u3002\u201c\u6700\u5927\u5b50\u5217\u548c\u201d\u5219\u88ab\u5b9a\u4e49\u4e3a\u6240\u6709\u8fde\u7eed\u5b50\u5217\u5143\u7d20\u7684\u548c\u4e2d\u6700\u5927\u8005\u3002\u4f8b\u5982\u7ed9\u5b9a\u5e8f\u5217{ -2, 11, -4, 13, -5, -2 }\uff0c\u5176\u8fde\u7eed\u5b50\u5217{ 11, -4, 13 }\u6709\u6700\u5927\u7684\u548c20\u3002\u73b0\u8981\u6c42\u4f60\u7f16\u5199\u7a0b\u5e8f\uff0c\u8ba1\u7b97\u7ed9\u5b9a\u6574\u6570\u5e8f\u5217\u7684\u6700\u5927\u5b50\u5217\u548c\u3002
    \n\u672c\u9898\u65e8\u5728\u6d4b\u8bd5\u5404\u79cd\u4e0d\u540c\u7684\u7b97\u6cd5\u5728\u5404\u79cd\u6570\u636e\u60c5\u51b5\u4e0b\u7684\u8868\u73b0\u3002\u5404\u7ec4\u6d4b\u8bd5\u6570\u636e\u7279\u70b9\u5982\u4e0b\uff1a<\/p>\n
      \n
    • \u6570\u636e1\uff1a\u4e0e\u6837\u4f8b\u7b49\u4ef7\uff0c\u6d4b\u8bd5\u57fa\u672c\u6b63\u786e\u6027\uff1b<\/li>\n
    • \u6570\u636e2\uff1a102\u4e2a\u968f\u673a\u6574\u6570\uff1b<\/li>\n
    • \u6570\u636e3\uff1a103\u4e2a\u968f\u673a\u6574\u6570\uff1b<\/li>\n
    • \u6570\u636e4\uff1a104\u4e2a\u968f\u673a\u6574\u6570\uff1b<\/li>\n
    • \u6570\u636e5\uff1a105\u4e2a\u968f\u673a\u6574\u6570\uff1b<\/li>\n<\/ul>\n
      \u8f93\u5165\u683c\u5f0f:<\/strong>
      \n\u8f93\u5165\u7b2c1\u884c\u7ed9\u51fa\u6b63\u6574\u6570K\u00a0(\u2264100000)\uff1b\u7b2c2\u884c\u7ed9\u51faK\u4e2a\u6574\u6570\uff0c\u5176\u95f4\u4ee5\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
      \u8f93\u51fa\u683c\u5f0f:<\/strong>
      \n\u5728\u4e00\u884c\u4e2d\u8f93\u51fa\u6700\u5927\u5b50\u5217\u548c\u3002\u5982\u679c\u5e8f\u5217\u4e2d\u6240\u6709\u6574\u6570\u7686\u4e3a\u8d1f\u6570\uff0c\u5219\u8f93\u51fa0\u3002<\/p>\n
      \u8f93\u5165\u6837\u4f8b:<\/strong>
      \n6
      \n-2 11 -4 13 -5 -2<\/p>\n
      \u8f93\u51fa\u6837\u4f8b:<\/strong>
      \n20<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n50000 ms
      \n\u5185\u5b58\u9650\u5236
      \n64MB
      \n64MB<\/p>\n
      C\u8bed\u8a00<\/h4>\n
      #define _CRT_SECURE_NO_WARNINGS 1\n#include <stdio.h>\n#include <stdlib.h>\n#define MAXSIZE 100000\nint main()\n{\n    int i, k;\n    int ThisSum = 0;\n    int MaxSum = 0;\n    int A[MAXSIZE];\n    scanf("%d", &k);\n    for (i = 0; i < k; i++)\n    {\n        scanf("%d", &A[i]);\n        ThisSum = ThisSum + A[i];\n        if (MaxSum < ThisSum) MaxSum = ThisSum;\n        else if (ThisSum < 0) ThisSum = 0;\n    }\n    printf("%d", MaxSum);\n    return 0;\n}\n<\/code><\/pre>\n
      01-\u590d\u6742\u5ea62 Maximum Subsequence Sum<\/h3>\n
      Given a sequence of\u00a0K\u00a0integers {\u00a0N1\u200b,\u00a0N2\u200b, …,\u00a0NK\u200b\u00a0}. A continuous subsequence is defined to be {\u00a0Ni\u200b,\u00a0Ni+1\u200b, …,\u00a0Nj\u200b\u00a0} where\u00a01\u2264i\u2264j\u2264K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
      \nNow you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.<\/p>\n
      Input Specification:<\/strong>
      \nEach input file contains one test case. Each case occupies two lines. The first line contains a positive integer\u00a0K\u00a0(\u226410000). The second line contains\u00a0K\u00a0numbers, separated by a space.<\/p>\n
      Output Specification:<\/strong>
      \nFor each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices\u00a0i\u00a0and\u00a0j\u00a0(as shown by the sample case). If all the\u00a0K\u00a0numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.<\/p>\n
      Sample Input:<\/strong>
      \n10
      \n-10 1 2 3 4 -5 -23 3 7 -21<\/p>\n
      Sample Output:<\/strong>
      \n10 1 4<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n200 ms
      \n\u5185\u5b58\u9650\u5236
      \n64MB
      \n64MB<\/p>\n
      \u7ffb\u8bd1  \u6700\u5927\u5b50\u5e8f\u5217\u548c<\/h4>\n
      \u7ed9\u5b9a\u4e00\u7cfb\u5217K\u6574\u6570{N1\u200b,N2\u200b, …,NK\u200b\u00a0}. \u8fde\u7eed\u5b50\u5e8f\u5217\u5b9a\u4e49\u4e3a{Ni\u200b,Ni+1\u200b, …,Nj\u200b}\u5176\u4e2d1\u2264i\u2264j\u2264K\u3001 \u6700\u5927\u5b50\u5e8f\u5217\u662f\u8fde\u7eed\u5b50\u5e8f\u5217\uff0c\u5176\u5143\u7d20\u4e4b\u548c\u6700\u5927\u3002\u4f8b\u5982\uff0c\u7ed9\u5b9a\u5e8f\u5217{-2,11\uff0c-4,13\uff0c-5\uff0c-2}\uff0c\u5176\u6700\u5927\u5b50\u5e8f\u5217\u662f{11\uff0c-4,13}\uff0c\u6700\u5927\u548c\u4e3a20\u3002
      \n\u73b0\u5728\uff0c\u60a8\u5e94\u8be5\u627e\u5230\u6700\u5927\u548c\uff0c\u4ee5\u53ca\u6700\u5927\u5b50\u5e8f\u5217\u7684\u7b2c\u4e00\u4e2a\u548c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u3002<\/p>\n
      \u8f93\u5165\u89c4\u8303\uff1a<\/strong>
      \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u6bcf\u79cd\u60c5\u51b5\u5360\u636e\u4e24\u884c\u3002\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570K(\u226410000). \u7b2c\u4e8c\u884c\u5305\u542b\u7531\u7a7a\u683c\u5206\u9694\u7684K\u4e2a\u6570\u5b57\u3002<\/p>\n
      \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
      \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u4e00\u884c\u8f93\u51fa\u6700\u5927\u548c\uff0c\u4ee5\u53ca\u6700\u5927\u5b50\u5e8f\u5217\u7684\u7b2c\u4e00\u4e2a\u548c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u3002\u6570\u5b57\u5fc5\u987b\u7528\u4e00\u4e2a\u7a7a\u683c\u5206\u9694\uff0c\u4f46\u884c\u7684\u672b\u5c3e\u5fc5\u987b\u6ca1\u6709\u989d\u5916\u7684\u7a7a\u683c\u3002\u5982\u679c\u6700\u5927\u5b50\u5e8f\u5217\u4e0d\u662f\u552f\u4e00\u7684\uff0c\u5219\u8f93\u51fa\u5177\u6709\u6700\u5c0f\u7d22\u5f15i\u548cj\u7684\u5b50\u5e8f\u5217\uff08\u5982\u6837\u672c\u60c5\u51b5\u6240\u793a\uff09\u3002\u5982\u679c\u6240\u6709\u7684K\u4e2a\u6570\u5b57\u90fd\u662f\u8d1f\u6570\uff0c\u90a3\u4e48\u5b83\u7684\u6700\u5927\u548c\u88ab\u5b9a\u4e49\u4e3a0\uff0c\u5e76\u4e14\u4f60\u5e94\u8be5\u8f93\u51fa\u6574\u4e2a\u5e8f\u5217\u7684\u7b2c\u4e00\u4e2a\u548c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u3002<\/p>\n
      \u6837\u672c\u8f93\u5165\uff1a<\/strong>
      \n10
      \n-10 1 2 3 4 -5 -23 3 7 -21<\/p>\n
      \u6837\u54c1\u8f93\u51fa\uff1a<\/strong>
      \n10 1 4<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n200\u6beb\u79d2
      \n\u5185\u5b58\u9650\u5236
      \n64MB
      \n64MB<\/p>\n
      C\u8bed\u8a00<\/h4>\n
      #include<stdio.h>\n#define MaxSize 10000\n#define INF 0x3f3f3f3f\nvoid MaxSubseqSum2(int A[], int N){\n    int ThisSum=0, MaxSum = -INF;\n    int i;\n    int temp=0, first=0, last=0;\n\n    for(i=0; i<N; i++){\n        ThisSum += A[i];\n\n        if(ThisSum < 0){  \/\/ThisSum<0\u8868\u793a A[i]<0\n            ThisSum = 0;\n            temp = i + 1;\n        }\n        else if(ThisSum > MaxSum){\n            MaxSum = ThisSum;\n            first = temp;\n            last = i;\n        }\n    }\n    if(MaxSum < 0)\n        printf("0 %d %d", A[0], A[N-1]);\n    else\n        printf("%d %d %d", MaxSum, A[first], A[last]);\n}\nint main(){\n    int i, N;\n    int A[MaxSize];\n\n    scanf("%d", &N);\n    for(i=0; i<N; i++)\n        scanf("%d", &A[i]);\n    MaxSubseqSum2(A, N);\n\n    return 0;\n}\n<\/code><\/pre>\n
      02-\u7ebf\u6027\u7ed3\u67842 \u4e00\u5143\u591a\u9879\u5f0f\u7684\u4e58\u6cd5\u4e0e\u52a0\u6cd5\u8fd0\u7b97<\/h3>\n
      \u8bbe\u8ba1\u51fd\u6570\u5206\u522b\u6c42\u4e24\u4e2a\u4e00\u5143\u591a\u9879\u5f0f\u7684\u4e58\u79ef\u4e0e\u548c\u3002<\/p>\n
      \u8f93\u5165\u683c\u5f0f:<\/strong>
      \n\u8f93\u5165\u52062\u884c\uff0c\u6bcf\u884c\u5206\u522b\u5148\u7ed9\u51fa\u591a\u9879\u5f0f\u975e\u96f6\u9879\u7684\u4e2a\u6570\uff0c\u518d\u4ee5\u6307\u6570\u9012\u964d\u65b9\u5f0f\u8f93\u5165\u4e00\u4e2a\u591a\u9879\u5f0f\u975e\u96f6\u9879\u7cfb\u6570\u548c\u6307\u6570\uff08\u7edd\u5bf9\u503c\u5747\u4e3a\u4e0d\u8d85\u8fc71000\u7684\u6574\u6570\uff09\u3002\u6570\u5b57\u95f4\u4ee5\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
      \u8f93\u51fa\u683c\u5f0f:<\/strong>
      \n\u8f93\u51fa\u52062\u884c\uff0c\u5206\u522b\u4ee5\u6307\u6570\u9012\u964d\u65b9\u5f0f\u8f93\u51fa\u4e58\u79ef\u591a\u9879\u5f0f\u4ee5\u53ca\u548c\u591a\u9879\u5f0f\u975e\u96f6\u9879\u7684\u7cfb\u6570\u548c\u6307\u6570\u3002\u6570\u5b57\u95f4\u4ee5\u7a7a\u683c\u5206\u9694\uff0c\u4f46\u7ed3\u5c3e\u4e0d\u80fd\u6709\u591a\u4f59\u7a7a\u683c\u3002\u96f6\u591a\u9879\u5f0f\u5e94\u8f93\u51fa0 0\u3002<\/p>\n
      \u8f93\u5165\u6837\u4f8b:<\/strong>
      \n4 3 4 -5 2  6 1  -2 0
      \n3 5 20  -7 4  3 1<\/p>\n
      \u8f93\u51fa\u6837\u4f8b:<\/strong>
      \n15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
      \n5 20 -4 4 -5 2 9 1 -2 0<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n200 ms
      \n\u5185\u5b58\u9650\u5236
      \n64MB<\/p>\n
      C\u8bed\u8a00<\/h4>\n
      <\/code><\/pre>\n
      02-\u7ebf\u6027\u7ed3\u67843 Reversing Linked List<\/h3>\n
      Given a constant\u00a0K\u00a0and a singly linked list\u00a0L, you are supposed to reverse the links of every\u00a0K\u00a0elements on\u00a0L. For example, given\u00a0L\u00a0being 1\u21922\u21923\u21924\u21925\u21926, if\u00a0K=3, then you must output 3\u21922\u21921\u21926\u21925\u21924; if\u00a0K=4, you must output 4\u21923\u21922\u21921\u21925\u21926.<\/p>\n
      Input Specification:<\/strong>
      \nEach input file contains one test case. For each case, the first line contains the address of the first node, a positive\u00a0N\u00a0(\u2264105) which is the total number of nodes, and a positive\u00a0K\u00a0(\u2264N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
      \nThen\u00a0N\u00a0lines follow, each describes a node in the format:
      \nAddress Data Next
      \nwhere\u00a0Address\u00a0is the position of the node,\u00a0Data\u00a0is an integer, and\u00a0Next\u00a0is the position of the next node.<\/p>\n
      Output Specification:<\/strong>
      \nFor each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.<\/p>\n
      Sample Input:<\/strong>
      \n00100 6 4
      \n00000 4 99999
      \n00100 1 12309
      \n68237 6 -1
      \n33218 3 00000
      \n99999 5 68237
      \n12309 2 33218<\/p>\n
      Sample Output:<\/strong>
      \n00000 4 33218
      \n33218 3 12309
      \n12309 2 00100
      \n00100 1 99999
      \n99999 5 68237
      \n68237 6 -1<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n400 ms
      \n\u5185\u5b58\u9650\u5236
      \n64MB<\/p>\n
      \u7ffb\u8bd1  \u53cd\u8f6c\u94fe\u63a5\u5217\u8868<\/h4>\n
      \u7ed9\u5b9a\u4e00\u4e2a\u5e38\u6570K\u548c\u4e00\u4e2a\u5355\u72ec\u94fe\u63a5\u7684\u5217\u8868L\uff0c\u4f60\u5e94\u8be5\u53cd\u8f6cL\u4e0a\u6bcf\u4e2aK\u4e2a\u5143\u7d20\u7684\u94fe\u63a5\u3002\u4f8b\u5982\uff0c\u7ed9\u5b9aL\u4e3a1\u21922\u21923\u21924\u21925\u21926\uff0c\u5982\u679cK=3\uff0c\u90a3\u4e48\u4f60\u5fc5\u987b\u8f93\u51fa3\u21922\u21921\u21926\u21925\u21924; \u5982\u679ck=4\uff0c\u4f60\u5fc5\u987b\u8f93\u51fa4\u21923\u21922\u21921\u21925\u21926.<\/p>\n
      \u8f93\u5165\u89c4\u8303\uff1a<\/strong>
      \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u5305\u542b\u7b2c\u4e00\u4e2a\u8282\u70b9\u7684\u5730\u5740\uff0c\u5373\u6b63N(\u226410^5\uff09\u662f\u8282\u70b9\u7684\u603b\u6570\uff0c\u6b63K(\u2264N\uff09 \u8fd9\u662f\u8981\u53cd\u8f6c\u7684\u5b50\u5217\u8868\u7684\u957f\u5ea6\u3002\u8282\u70b9\u7684\u5730\u5740\u662f\u4e00\u4e2a5\u4f4d\u975e\u8d1f\u6574\u6570\uff0c\u7a7a\u503c\u7531-1\u8868\u793a\u3002
      \n\u7136\u540e\u662fN\u884c\uff0c\u6bcf\u884c\u63cf\u8ff0\u4e00\u4e2a\u683c\u5f0f\u7684\u8282\u70b9\uff1a
      \nAddress Data Next
      \n\u5176\u4e2dAddress\u662f\u8282\u70b9\u7684\u4f4d\u7f6e\uff0cData\u662f\u6574\u6570\uff0cNext\u662f\u4e0b\u4e00\u4e2a\u8282\u70b9\u7684\u4f4d\u7f6e\u3002<\/p>\n
      \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
      \n\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u8f93\u51fa\u7ed3\u679c\u7684\u6709\u5e8f\u94fe\u63a5\u5217\u8868\u3002\u6bcf\u4e2a\u8282\u70b9\u5360\u636e\u4e00\u6761\u7ebf\uff0c\u5e76\u4ee5\u4e0e\u8f93\u5165\u4e2d\u76f8\u540c\u7684\u683c\u5f0f\u6253\u5370\u3002<\/p>\n
      \u6837\u672c\u8f93\u5165\uff1a<\/strong>
      \n00100 6 4
      \n00000 4 99999
      \n00100 1 12309
      \n68237 6 -1
      \n33218 3 00000
      \n99999 5 68237
      \n12309 2 33218<\/p>\n
      \u6837\u54c1\u8f93\u51fa\uff1a<\/strong>
      \n00000 4 33218
      \n33218 3 12309
      \n12309 2 00100
      \n00100 1 99999
      \n99999 5 68237
      \n68237 6 -1<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n400\u6beb\u79d2
      \n\u5185\u5b58\u9650\u5236
      \n64MB<\/p>\n
      02-\u7ebf\u6027\u7ed3\u67844 Pop Sequence<\/h3>\n
      Given a stack which can keep\u00a0M\u00a0numbers at most. Push\u00a0N\u00a0numbers in the order of 1, 2, 3, …,\u00a0N\u00a0and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if\u00a0M\u00a0is 5 and\u00a0N\u00a0is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.<\/p>\n
      Input Specification:<\/strong>
      \nEach input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000):\u00a0M\u00a0(the maximum capacity of the stack),\u00a0N\u00a0(the length of push sequence), and\u00a0K\u00a0(the number of pop sequences to be checked). Then\u00a0K\u00a0lines follow, each contains a pop sequence of\u00a0N\u00a0numbers. All the numbers in a line are separated by a space.<\/p>\n
      Output Specification:<\/strong>
      \nFor each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.<\/p>\n
      Sample Input:<\/strong>
      \n5 7 5
      \n1 2 3 4 5 6 7
      \n3 2 1 7 5 6 4
      \n7 6 5 4 3 2 1
      \n5 6 4 3 7 2 1
      \n1 7 6 5 4 3 2<\/p>\n
      Sample Output:<\/strong>
      \nYES
      \nNO
      \nNO
      \nYES
      \nNO<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n400 ms
      \n\u5185\u5b58\u9650\u5236
      \n64MB<\/p>\n
      \u7ffb\u8bd1  02-\u7ebf\u6027\u7ed3\u67844 Pop\u5e8f\u5217<\/h4>\n
      \u7ed9\u5b9a\u4e00\u4e2a\u6700\u591a\u53ef\u4ee5\u4fdd\u5b58M\u4e2a\u6570\u5b57\u7684\u5806\u6808\u3002\u63091\u30012\u30013\u3001\u2026\u3001N\u548c\u968f\u673a\u5f39\u51fa\u7684\u987a\u5e8f\u6309\u4e0bN\u4e2a\u6570\u5b57\u3002\u60a8\u5e94\u8be5\u77e5\u9053\u7ed9\u5b9a\u7684\u6570\u5b57\u5e8f\u5217\u662f\u5426\u662f\u5806\u6808\u4e2d\u53ef\u80fd\u7684pop\u5e8f\u5217\u3002\u4f8b\u5982\uff0c\u5982\u679cM\u662f5\uff0cN\u662f7\uff0c\u6211\u4eec\u53ef\u4ee5\u4ece\u5806\u6808\u4e2d\u83b7\u5f971\uff0c2\uff0c3\uff0c4\uff0c5\uff0c6\uff0c7\uff0c\u4f46\u4e0d\u662f3\uff0c2\uff0c1\uff0c7\uff0c5\uff0c\u516d\uff0c4\u3002<\/p>\n
      \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
      \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u5305\u542b3\u4e2a\u6570\u5b57\uff08\u5747\u4e0d\u8d85\u8fc71000\uff09\uff1aM\uff08\u5806\u6808\u7684\u6700\u5927\u5bb9\u91cf\uff09\u3001N\uff08\u63a8\u9001\u5e8f\u5217\u7684\u957f\u5ea6\uff09\u548cK\uff08\u8981\u68c0\u67e5\u7684pop\u5e8f\u5217\u7684\u6570\u91cf\uff09\u3002\u63a5\u7740\u662fK\u884c\uff0c\u6bcf\u884c\u5305\u542b\u4e00\u4e2a\u7531N\u4e2a\u6570\u5b57\u7ec4\u6210\u7684pop\u5e8f\u5217\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
      \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
      \n\u5bf9\u4e8e\u6bcf\u4e2apop\u5e8f\u5217\uff0c\u5982\u679c\u786e\u5b9e\u662f\u5806\u6808\u4e2d\u53ef\u80fd\u7684pop\u5e8f\u5217\u5219\u6253\u5370\u4e00\u884c\u201c\u662f\u201d\uff0c\u5982\u679c\u4e0d\u662f\uff0c\u5219\u6253\u5370\u201c\u5426\u201d\u3002<\/p>\n
      \u6837\u672c\u8f93\u5165\uff1a<\/strong>
      \n5 7 5
      \n1 2 3 4 5 6 7
      \n3 2 1 7 5 6 4
      \n7 6 5 4 3 2 1
      \n5 6 4 3 7 2 1
      \n1 7 6 5 4 3 2<\/p>\n
      \u6837\u672c\u8f93\u51fa\uff1a<\/strong>
      \n\u5bf9
      \n\u4e0d
      \n\u4e0d
      \n\u5bf9
      \n\u4e0d<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16kb
      \n\u65f6\u95f4\u9650\u5236
      \n400\u6beb\u79d2
      \n\u5185\u5b58\u9650\u5236
      \n64MB<\/p>\n
      03-\u68111 \u6811\u7684\u540c\u678403-\u68111 \u6811\u7684\u540c\u6784<\/h3>\n
      \u7ed9\u5b9a\u4e24\u68f5\u6811T1\u548cT2\u3002\u5982\u679cT1\u53ef\u4ee5\u901a\u8fc7\u82e5\u5e72\u6b21\u5de6\u53f3\u5b69\u5b50\u4e92\u6362\u5c31\u53d8\u6210T2\uff0c\u5219\u6211\u4eec\u79f0\u4e24\u68f5\u6811\u662f\u201c\u540c\u6784\u201d\u7684\u3002\u4f8b\u5982\u56fe1\u7ed9\u51fa\u7684\u4e24\u68f5\u6811\u5c31\u662f\u540c\u6784\u7684\uff0c\u56e0\u4e3a\u6211\u4eec\u628a\u5176\u4e2d\u4e00\u68f5\u6811\u7684\u7ed3\u70b9A\u3001B\u3001G\u7684\u5de6\u53f3\u5b69\u5b50\u4e92\u6362\u540e\uff0c\u5c31\u5f97\u5230\u53e6\u5916\u4e00\u68f5\u6811\u3002\u800c\u56fe2\u5c31\u4e0d\u662f\u540c\u6784\u7684\u3002
      \n\u56fe1
      \n\u56fe2
      \n\u73b0\u7ed9\u5b9a\u4e24\u68f5\u6811\uff0c\u8bf7\u4f60\u5224\u65ad\u5b83\u4eec\u662f\u5426\u662f\u540c\u6784\u7684\u3002<\/p>\n
      \u8f93\u5165\u683c\u5f0f:<\/strong>
      \n\u8f93\u5165\u7ed9\u51fa2\u68f5\u4e8c\u53c9\u6811\u6811\u7684\u4fe1\u606f\u3002\u5bf9\u4e8e\u6bcf\u68f5\u6811\uff0c\u9996\u5148\u5728\u4e00\u884c\u4e2d\u7ed9\u51fa\u4e00\u4e2a\u975e\u8d1f\u6574\u6570N\u00a0(\u226410)\uff0c\u5373\u8be5\u6811\u7684\u7ed3\u70b9\u6570\uff08\u6b64\u65f6\u5047\u8bbe\u7ed3\u70b9\u4ece0\u5230N\u22121\u7f16\u53f7\uff09\uff1b\u968f\u540eN\u884c\uff0c\u7b2ci\u884c\u5bf9\u5e94\u7f16\u53f7\u7b2ci\u4e2a\u7ed3\u70b9\uff0c\u7ed9\u51fa\u8be5\u7ed3\u70b9\u4e2d\u5b58\u50a8\u76841\u4e2a\u82f1\u6587\u5927\u5199\u5b57\u6bcd\u3001\u5176\u5de6\u5b69\u5b50\u7ed3\u70b9\u7684\u7f16\u53f7\u3001\u53f3\u5b69\u5b50\u7ed3\u70b9\u7684\u7f16\u53f7\u3002\u5982\u679c\u5b69\u5b50\u7ed3\u70b9\u4e3a\u7a7a\uff0c\u5219\u5728\u76f8\u5e94\u4f4d\u7f6e\u4e0a\u7ed9\u51fa\u201c-\u201d\u3002\u7ed9\u51fa\u7684\u6570\u636e\u95f4\u7528\u4e00\u4e2a\u7a7a\u683c\u5206\u9694\u3002\u6ce8\u610f\uff1a\u9898\u76ee\u4fdd\u8bc1\u6bcf\u4e2a\u7ed3\u70b9\u4e2d\u5b58\u50a8\u7684\u5b57\u6bcd\u662f\u4e0d\u540c\u7684\u3002<\/p>\n
      \u8f93\u51fa\u683c\u5f0f:<\/strong>
      \n\u5982\u679c\u4e24\u68f5\u6811\u662f\u540c\u6784\u7684\uff0c\u8f93\u51fa\u201cYes\u201d\uff0c\u5426\u5219\u8f93\u51fa\u201cNo\u201d\u3002<\/p>\n
      \u8f93\u5165\u6837\u4f8b1\uff08\u5bf9\u5e94\u56fe1\uff09\uff1a<\/strong>
      \n8
      \nA 1 2
      \nB 3 4
      \nC 5 –
      \nD – –
      \nE 6 –
      \nG 7 –
      \nF – –
      \nH – –
      \n8
      \nG – 4
      \nB 7 6
      \nF – –
      \nA 5 1
      \nH – –
      \nC 0 –
      \nD – –
      \nE 2 –<\/p>\n
      \u8f93\u51fa\u6837\u4f8b1:<\/strong>
      \nYes<\/p>\n
      \u8f93\u5165\u6837\u4f8b2\uff08\u5bf9\u5e94\u56fe2\uff09\uff1a<\/strong>
      \n8
      \nB 5 7
      \nF – –
      \nA 0 3
      \nC 6 –
      \nH – –
      \nD – –
      \nG 4 –
      \nE 1 –
      \n8
      \nD 6 –
      \nB 5 –
      \nE – –
      \nH – –
      \nC 0 2
      \nG – 3
      \nF – –
      \nA 1 4<\/p>\n
      \u8f93\u51fa\u6837\u4f8b2:<\/strong>
      \nNo<\/p>\n
      \u4ee3\u7801\u957f\u5ea6\u9650\u5236
      \n16 KB
      \n\u65f6\u95f4\u9650\u5236
      \n400 ms
      \n\u5185\u5b58\u9650\u5236
      \n64MB<\/p>\n
      03-\u68112 List Leaves<\/h3>\n
      Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.<\/p>\n
      Input Specification:<\/strong>
      \nEach input file contains one test case. For each case, the first line gives a positive integer\u00a0N\u00a0(\u226410) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to\u00a0N\u22121. Then\u00a0N\u00a0lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.<\/p>\n
      Output Specification:<\/strong>
      \nFor each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.<\/p>\n
      Sample Input:<\/strong>
      \n8
      \n1 –<\/p>\n
        \n
      • –
        \n0 –
        \n2 7<\/li>\n
      • –<\/li>\n
      • –
        \n5 –
        \n4 6<\/li>\n<\/ul>\n
        Sample Output:<\/strong>
        \n4 1 5<\/p>\n
        \u4ee3\u7801\u957f\u5ea6\u9650\u5236
        \n16 KB
        \n\u65f6\u95f4\u9650\u5236
        \n400 ms
        \n\u5185\u5b58\u9650\u5236
        \n64MB<\/p>\n
        \u7ffb\u8bd1  03-\u68112.\u6811\u53f6\u5217\u8868<\/h4>\n
        \u7ed9\u5b9a\u4e00\u68f5\u6811\uff0c\u4f60\u5e94\u8be5\u6309\u7167\u4ece\u4e0a\u5230\u4e0b\u3001\u4ece\u5de6\u5230\u53f3\u7684\u987a\u5e8f\u5217\u51fa\u6240\u6709\u7684\u53f6\u5b50\u3002<\/p>\n
        \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
        \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570N(\u226410\uff09 \u8fd9\u662f\u6811\u4e2d\u8282\u70b9\u7684\u603b\u6570\uff0c\u56e0\u6b64\u8282\u70b9\u7684\u7f16\u53f7\u4ece0\u5230N\u22121.\u7136\u540e\u8ddf\u968fN\u6761\u7ebf\uff0c\u6bcf\u6761\u7ebf\u5bf9\u5e94\u4e8e\u4e00\u4e2a\u8282\u70b9\uff0c\u5e76\u7ed9\u51fa\u8be5\u8282\u70b9\u5de6\u53f3\u5b50\u8282\u70b9\u7684\u7d22\u5f15\u3002\u5982\u679c\u8be5\u5b50\u9879\u4e0d\u5b58\u5728\uff0c\u5219\u5728\u8be5\u4f4d\u7f6e\u5c06\u653e\u7f6e\u4e00\u4e2a\u201c-\u201d\u3002\u4efb\u4f55\u4e00\u5bf9\u5b69\u5b50\u90fd\u88ab\u4e00\u4e2a\u7a7a\u683c\u9694\u5f00\u3002<\/p>\n
        \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
        \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u6309\u4ece\u4e0a\u5230\u4e0b\u3001\u4ece\u5de6\u5230\u53f3\u7684\u987a\u5e8f\u5728\u4e00\u884c\u4e2d\u6253\u5370\u6240\u6709\u53f6\u5b50\u7684\u7d22\u5f15\u3002\u4efb\u4f55\u76f8\u90bb\u6570\u5b57\u4e4b\u95f4\u5fc5\u987b\u6b63\u597d\u6709\u4e00\u4e2a\u7a7a\u683c\uff0c\u5e76\u4e14\u5728\u884c\u5c3e\u6ca1\u6709\u591a\u4f59\u7684\u7a7a\u683c\u3002<\/p>\n
        \u6837\u672c\u8f93\u5165\uff1a<\/strong>
        \n8.
        \n1 –<\/p>\n
          \n
        • –
          \n0 –
          \n2 7<\/li>\n
        • –<\/li>\n
        • –
          \n5 –
          \n4 6<\/li>\n<\/ul>\n
          \u6837\u672c\u8f93\u51fa\uff1a<\/strong>
          \n4 1 5<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          03-\u68113 Tree Traversals Again<\/h3>\n
          An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
          \nFigure 1<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. For each case, the first line contains a positive integer\u00a0N\u00a0(\u226430) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to\u00a0N). Then\u00a02N\u00a0lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.<\/p>\n
          Sample Input:<\/strong>
          \n6
          \nPush 1
          \nPush 2
          \nPush 3
          \nPop
          \nPop
          \nPush 4
          \nPop
          \nPop
          \nPush 5
          \nPush 6
          \nPop
          \nPop<\/p>\n
          Sample Output:<\/strong>
          \n3 4 2 6 5 1<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  03-\u6811\u518d\u6b21\u8fdb\u884c3\u6b21\u6811\u904d\u5386<\/h4>\n
          \u6709\u5e8f\u4e8c\u53c9\u6811\u904d\u5386\u53ef\u4ee5\u901a\u8fc7\u5806\u6808\u4ee5\u975e\u9012\u5f52\u65b9\u5f0f\u5b9e\u73b0\u3002\u4f8b\u5982\uff0c\u5047\u8bbe\u904d\u5386\u4e00\u4e2a6\u8282\u70b9\u7684\u4e8c\u53c9\u6811\uff08\u952e\u7684\u7f16\u53f7\u4ece1\u52306\uff09\uff0c\u5806\u6808\u64cd\u4f5c\u662f\uff1apush\uff081\uff09\uff1b\u63a8\u52a8\uff082\uff09\uff1b\u63a8\u52a8\uff083\uff09\uff1bpop\uff08\uff09\uff1bpop\uff08\uff09\uff1b\u63a8\u52a8\uff084\uff09\uff1bpop\uff08\uff09\uff1bpop\uff08\uff09\uff1b\u63a8\u52a8\uff085\uff09\uff1b\u63a8\u52a8\uff086\uff09\uff1bpop\uff08\uff09\uff1bpop\uff08\uff09\u3002\u7136\u540e\uff0c\u53ef\u4ee5\u4ece\u8fd9\u4e2a\u64cd\u4f5c\u5e8f\u5217\u751f\u6210\u4e00\u4e2a\u552f\u4e00\u7684\u4e8c\u53c9\u6811\uff08\u5982\u56fe1\u6240\u793a\uff09\u3002\u60a8\u7684\u4efb\u52a1\u662f\u7ed9\u51fa\u6b64\u6811\u7684\u540e\u5e8f\u904d\u5386\u5e8f\u5217\u3002
          \n\u56fe1<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u90fd\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570N(\u226430\uff09\uff0c\u8fd9\u662f\u6811\u4e2d\u7684\u8282\u70b9\u603b\u6570\uff08\u56e0\u6b64\u8282\u70b9\u7684\u7f16\u53f7\u4ece1\u5230N\uff09\u3002\u63a5\u4e0b\u6765\u662f2N\u884c\uff0c\u6bcf\u884c\u4ee5\u201cPush X\u201d\u7684\u683c\u5f0f\u63cf\u8ff0\u5806\u6808\u64cd\u4f5c\uff0c\u5176\u4e2dX\u662f\u88ab\u63a8\u9001\u5230\u5806\u6808\u4e0a\u7684\u8282\u70b9\u7684\u7d22\u5f15\uff1b\u6216\u201cPop\u201d\uff0c\u610f\u601d\u662f\u4ece\u5806\u6808\u4e2d\u5f39\u51fa\u4e00\u4e2a\u8282\u70b9\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5728\u4e00\u884c\u4e2d\u6253\u5370\u76f8\u5e94\u6811\u7684\u540e\u5e8f\u904d\u5386\u5e8f\u5217\u3002\u4fdd\u8bc1\u5b58\u5728\u89e3\u51b3\u65b9\u6848\u3002\u6240\u6709\u6570\u5b57\u5fc5\u987b\u7528\u4e00\u4e2a\u7a7a\u683c\u5206\u9694\uff0c\u5e76\u4e14\u5728\u884c\u5c3e\u4e0d\u5f97\u6709\u989d\u5916\u7684\u7a7a\u683c\u3002<\/p>\n
          \u6837\u672c\u8f93\u5165\uff1a<\/strong>
          \n6.
          \n\u63091
          \n\u63a82
          \n\u63a83
          \n\u6d41\u884c\u97f3\u4e50
          \n\u6d41\u884c\u97f3\u4e50
          \n\u63a84
          \n\u6d41\u884c\u97f3\u4e50
          \n\u6d41\u884c\u97f3\u4e50
          \n\u63a85
          \n\u63a86
          \n\u6d41\u884c\u97f3\u4e50
          \n\u6d41\u884c\u97f3\u4e50<\/p>\n
          \u6837\u672c\u8f93\u51fa\uff1a<\/strong>
          \n3 4 2 6 5 1<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          04-\u68114 \u662f\u5426\u540c\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811<\/h3>\n
          \u7ed9\u5b9a\u4e00\u4e2a\u63d2\u5165\u5e8f\u5217\u5c31\u53ef\u4ee5\u552f\u4e00\u786e\u5b9a\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\u3002\u7136\u800c\uff0c\u4e00\u68f5\u7ed9\u5b9a\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u5374\u53ef\u4ee5\u7531\u591a\u79cd\u4e0d\u540c\u7684\u63d2\u5165\u5e8f\u5217\u5f97\u5230\u3002\u4f8b\u5982\u5206\u522b\u6309\u7167\u5e8f\u5217{2, 1, 3}\u548c{2, 3, 1}\u63d2\u5165\u521d\u59cb\u4e3a\u7a7a\u7684\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u90fd\u5f97\u5230\u4e00\u6837\u7684\u7ed3\u679c\u3002\u4e8e\u662f\u5bf9\u4e8e\u8f93\u5165\u7684\u5404\u79cd\u63d2\u5165\u5e8f\u5217\uff0c\u4f60\u9700\u8981\u5224\u65ad\u5b83\u4eec\u662f\u5426\u80fd\u751f\u6210\u4e00\u6837\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u5305\u542b\u82e5\u5e72\u7ec4\u6d4b\u8bd5\u6570\u636e\u3002\u6bcf\u7ec4\u6570\u636e\u7684\u7b2c1\u884c\u7ed9\u51fa\u4e24\u4e2a\u6b63\u6574\u6570N\u00a0(\u226410)\u548cL\uff0c\u5206\u522b\u662f\u6bcf\u4e2a\u5e8f\u5217\u63d2\u5165\u5143\u7d20\u7684\u4e2a\u6570\u548c\u9700\u8981\u68c0\u67e5\u7684\u5e8f\u5217\u4e2a\u6570\u3002\u7b2c2\u884c\u7ed9\u51faN\u4e2a\u4ee5\u7a7a\u683c\u5206\u9694\u7684\u6b63\u6574\u6570\uff0c\u4f5c\u4e3a\u521d\u59cb\u63d2\u5165\u5e8f\u5217\u3002\u968f\u540eL\u884c\uff0c\u6bcf\u884c\u7ed9\u51faN\u4e2a\u63d2\u5165\u7684\u5143\u7d20\uff0c\u5c5e\u4e8eL\u4e2a\u9700\u8981\u68c0\u67e5\u7684\u5e8f\u5217\u3002
          \n\u7b80\u5355\u8d77\u89c1\uff0c\u6211\u4eec\u4fdd\u8bc1\u6bcf\u4e2a\u63d2\u5165\u5e8f\u5217\u90fd\u662f1\u5230N\u7684\u4e00\u4e2a\u6392\u5217\u3002\u5f53\u8bfb\u5230N\u4e3a0\u65f6\uff0c\u6807\u5fd7\u8f93\u5165\u7ed3\u675f\uff0c\u8fd9\u7ec4\u6570\u636e\u4e0d\u8981\u5904\u7406\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u5bf9\u6bcf\u4e00\u7ec4\u9700\u8981\u68c0\u67e5\u7684\u5e8f\u5217\uff0c\u5982\u679c\u5176\u751f\u6210\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u8ddf\u5bf9\u5e94\u7684\u521d\u59cb\u5e8f\u5217\u751f\u6210\u7684\u4e00\u6837\uff0c\u8f93\u51fa\u201cYes\u201d\uff0c\u5426\u5219\u8f93\u51fa\u201cNo\u201d\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n4 2
          \n3 1 4 2
          \n3 4 1 2
          \n3 2 4 1
          \n2 1
          \n2 1
          \n1 2
          \n0<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \nYes
          \nNo
          \nNo
          \n\u9e23\u8c22\u9752\u5c9b\u5927\u5b66\u5468\u5f3a\u8001\u5e08\u8865\u5145\u6d4b\u8bd5\u6570\u636e\uff01<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          04-\u68115 Root of AVL Tree<\/h3>\n
          An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
          \nNow given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. For each case, the first line contains a positive integer\u00a0N\u00a0(\u226420) which is the total number of keys to be inserted. Then\u00a0N\u00a0distinct integer keys are given in the next line. All the numbers in a line are separated by a space.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, print the root of the resulting AVL tree in one line.<\/p>\n
          Sample Input 1:<\/strong>
          \n5
          \n88 70 61 96 120<\/p>\n
          Sample Output 1:<\/strong>
          \n70<\/p>\n
          Sample Input 2:<\/strong>
          \n7
          \n88 70 61 96 120 90 65<\/p>\n
          Sample Output 2:<\/strong>
          \n88<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  04-\u68115.AVL\u6811\u7684\u6839<\/h4>\n
          AVL\u6811\u662f\u81ea\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\u3002\u5728AVL\u6811\u4e2d\uff0c\u4efb\u4f55\u8282\u70b9\u7684\u4e24\u4e2a\u5b50\u6811\u7684\u9ad8\u5ea6\u6700\u591a\u76f8\u5dee\u4e00\uff1b\u5982\u679c\u5728\u4efb\u4f55\u65f6\u5019\u5b83\u4eec\u7684\u5dee\u5f02\u8d85\u8fc7\u4e00\u4e2a\uff0c\u5219\u8fdb\u884c\u91cd\u65b0\u5e73\u8861\u4ee5\u6062\u590d\u6b64\u5c5e\u6027\u3002\u56fe1-4\u8bf4\u660e\u4e86\u65cb\u8f6c\u89c4\u5219\u3002
          \n\u73b0\u5728\uff0c\u7ed9\u5b9a\u4e00\u7cfb\u5217\u63d2\u5165\uff0c\u60a8\u5e94\u8be5\u77e5\u9053\u751f\u6210\u7684AVL\u6811\u7684\u6839\u3002<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u90fd\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570N(\u226420\uff09 \u5176\u662f\u8981\u63d2\u5165\u7684\u952e\u7684\u603b\u6570\u3002\u7136\u540e\u5728\u4e0b\u4e00\u884c\u4e2d\u7ed9\u51faN\u4e2a\u4e0d\u540c\u7684\u6574\u6570\u952e\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5728\u4e00\u884c\u4e2d\u6253\u5370\u751f\u6210\u7684AVL\u6811\u7684\u6839\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n5.
          \n88 70 61 96 120<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n70<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n7.
          \n88 70 61 96 120 90 65<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n88<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          04-\u68116 Complete Binary Search Tree<\/h3>\n
          A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
          \n\u00b7  The left subtree of a node contains only nodes with keys less than the node’s key.
          \n\u00b7  The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
          \n\u00b7  Both the left and right subtrees must also be binary search trees.
          \nA Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
          \n\u00b7  Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
          \n\u00b7  Input Specification:<\/strong>
          \n\u00b7  Each input file contains one test case. For each case, the first line contains a positive integer\u00a0N\u00a0(\u22641000). Then\u00a0N\u00a0distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
          \n\u00b7  Output Specification:<\/strong>
          \n\u00b7  For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
          \n\u00b7  Sample Input:
          \n\u00b7  10
          \n1 2 3 4 5 6 7 8 9 0
          \n\u00b7  Sample Output:
          \n\u00b7  6 3 8 1 5 7 9 0 2 4
          \n\u00b7  \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  04-\u68116.\u5b8c\u5168\u4e8c\u53c9\u641c\u7d22\u6811<\/h4>\n
          \u4e8c\u53c9\u641c\u7d22\u6811\uff08BST\uff09\u9012\u5f52\u5b9a\u4e49\u4e3a\u5177\u6709\u4ee5\u4e0b\u5c5e\u6027\u7684\u4e8c\u53c9\u6811\uff1a
          \n\u00b7\u8282\u70b9\u7684\u5de6\u5b50\u6811\u4ec5\u5305\u542b\u952e\u5c0f\u4e8e\u8282\u70b9\u952e\u7684\u8282\u70b9\u3002
          \n\u00b7\u8282\u70b9\u7684\u53f3\u5b50\u6811\u4ec5\u5305\u542b\u952e\u5927\u4e8e\u6216\u7b49\u4e8e\u8282\u70b9\u952e\u7684\u8282\u70b9\u3002
          \n\u00b7\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u90fd\u5fc5\u987b\u662f\u4e8c\u53c9\u641c\u7d22\u6811\u3002
          \n\u5b8c\u5168\u4e8c\u53c9\u6811\uff08CBT\uff09\u662f\u4e00\u79cd\u5b8c\u5168\u586b\u5145\u7684\u6811\uff0c\u4f46\u5e95\u5c42\u53ef\u80fd\u4f8b\u5916\uff0c\u5e95\u5c42\u4ece\u5de6\u5230\u53f3\u586b\u5145\u3002
          \n\u00b7\u73b0\u5728\uff0c\u7ed9\u5b9a\u4e00\u7cfb\u5217\u4e0d\u540c\u7684\u975e\u8d1f\u6574\u6570\u952e\uff0c\u5982\u679c\u8981\u6c42\u6811\u4e5f\u5fc5\u987b\u662fCBT\uff0c\u5219\u53ef\u4ee5\u6784\u9020\u552f\u4e00\u7684BST\u3002\u60a8\u5e94\u8be5\u8f93\u51fa\u6b64BST\u7684\u7ea7\u522b\u987a\u5e8f\u904d\u5386\u5e8f\u5217\u3002
          \n\u00b7\u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u00b7\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u90fd\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570N(\u22641000). \u7136\u540e\u5728\u4e0b\u4e00\u884c\u4e2d\u7ed9\u51faN\u4e2a\u4e0d\u540c\u7684\u975e\u8d1f\u6574\u6570\u952e\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u7528\u7a7a\u683c\u5206\u9694\uff0c\u4e14\u4e0d\u5927\u4e8e2000\u3002
          \n\u00b7\u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u00b7\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5728\u4e00\u884c\u4e2d\u6253\u5370\u76f8\u5e94\u5b8c\u6574\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7ea7\u522b\u987a\u5e8f\u904d\u5386\u5e8f\u5217\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u5fc5\u987b\u7528\u7a7a\u683c\u5206\u9694\uff0c\u5e76\u4e14\u5728\u884c\u5c3e\u4e0d\u5f97\u6709\u989d\u5916\u7684\u7a7a\u683c\u3002
          \n\u00b7\u6837\u672c\u8f93\u5165\uff1a
          \n\u00b7 10
          \n1 2 3 4 5 6 7 8 9 0
          \n\u00b7\u6837\u672c\u8f93\u51fa\uff1a
          \n\u00b7 6 3 8 1 5 7 9 0 2 4
          \n\u00b7 \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          05-\u68117 \u5806\u4e2d\u7684\u8def\u5f84<\/h3>\n
          \u5c06\u4e00\u7cfb\u5217\u7ed9\u5b9a\u6570\u5b57\u4f9d\u6b21\u63d2\u5165\u4e00\u4e2a\u521d\u59cb\u4e3a\u7a7a\u7684\u5c0f\u9876\u5806H[]\u3002\u968f\u540e\u5bf9\u4efb\u610f\u7ed9\u5b9a\u7684\u4e0b\u6807i\uff0c\u6253\u5370\u4eceH[i]\u5230\u6839\u7ed3\u70b9\u7684\u8def\u5f84\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u6bcf\u7ec4\u6d4b\u8bd5\u7b2c1\u884c\u5305\u542b2\u4e2a\u6b63\u6574\u6570N\u548cM(\u22641000)\uff0c\u5206\u522b\u662f\u63d2\u5165\u5143\u7d20\u7684\u4e2a\u6570\u3001\u4ee5\u53ca\u9700\u8981\u6253\u5370\u7684\u8def\u5f84\u6761\u6570\u3002\u4e0b\u4e00\u884c\u7ed9\u51fa\u533a\u95f4[-10000, 10000]\u5185\u7684N\u4e2a\u8981\u88ab\u63d2\u5165\u4e00\u4e2a\u521d\u59cb\u4e3a\u7a7a\u7684\u5c0f\u9876\u5806\u7684\u6574\u6570\u3002\u6700\u540e\u4e00\u884c\u7ed9\u51faM\u4e2a\u4e0b\u6807\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u5bf9\u8f93\u5165\u4e2d\u7ed9\u51fa\u7684\u6bcf\u4e2a\u4e0b\u6807i\uff0c\u5728\u4e00\u884c\u4e2d\u8f93\u51fa\u4eceH[i]\u5230\u6839\u7ed3\u70b9\u7684\u8def\u5f84\u4e0a\u7684\u6570\u636e\u3002\u6570\u5b57\u95f4\u4ee51\u4e2a\u7a7a\u683c\u5206\u9694\uff0c\u884c\u672b\u4e0d\u5f97\u6709\u591a\u4f59\u7a7a\u683c\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n5 3
          \n46 23 26 24 10
          \n5 4 3<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n24 23 10
          \n46 23 10
          \n26 10<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          05-\u68118 File Transfer<\/h3>\n
          We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. For each test case, the first line contains\u00a0N\u00a0(2\u2264N\u2264104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and\u00a0N. Then in the following lines, the input is given in the format:
          \nI c1 c2
          \nwhere\u00a0I\u00a0stands for inputting a connection between\u00a0c1\u00a0and\u00a0c2; or
          \nC c1 c2
          \nwhere\u00a0C\u00a0stands for checking if it is possible to transfer files between\u00a0c1\u00a0and\u00a0c2; or
          \nS
          \nwhere\u00a0S\u00a0stands for stopping this case.<\/p>\n
          Output Specification:<\/strong>
          \nFor each\u00a0C\u00a0case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between\u00a0c1\u00a0and\u00a0c2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are\u00a0k\u00a0components." where\u00a0k\u00a0is the number of connected components in this network.<\/p>\n
          Sample Input 1:<\/strong>
          \n5
          \nC 3 2
          \nI 3 2
          \nC 1 5
          \nI 4 5
          \nI 2 4
          \nC 3 5
          \nS<\/p>\n
          Sample Output 1:<\/strong>
          \nno
          \nno
          \nyes
          \nThere are 2 components.<\/p>\n
          Sample Input 2:<\/strong>
          \n5
          \nC 3 2
          \nI 3 2
          \nC 1 5
          \nI 4 5
          \nI 2 4
          \nC 3 5
          \nI 1 3
          \nC 1 5
          \nS<\/p>\n
          Sample Output 2:<\/strong>
          \nno
          \nno
          \nyes
          \nyes
          \nThe network is connected.<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \nGo (go)
          \n\u65f6\u95f4\u9650\u5236<\/p>\n
          \u7ffb\u8bd1  05-\u68118\u6587\u4ef6\u4f20\u8f93<\/h4>\n
          \u6211\u4eec\u6709\u4e00\u4e2a\u8ba1\u7b97\u673a\u7f51\u7edc\u548c\u4e00\u7cfb\u5217\u53cc\u5411\u8fde\u63a5\u3002\u6bcf\u4e2a\u8fde\u63a5\u90fd\u5141\u8bb8\u4ece\u4e00\u53f0\u8ba1\u7b97\u673a\u5230\u53e6\u4e00\u53f0\u8ba1\u7b97\u673a\u7684\u6587\u4ef6\u4f20\u8f93\u3002\u53ef\u4ee5\u4ece\u7f51\u7edc\u4e0a\u7684\u4efb\u4f55\u8ba1\u7b97\u673a\u5411\u4efb\u4f55\u5176\u4ed6\u8ba1\u7b97\u673a\u53d1\u9001\u6587\u4ef6\u5417\uff1f<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u7b2c\u4e00\u884c\u5305\u542bN\uff082\u2264N\u2264104\uff09\u3001\u7f51\u7edc\u4e2d\u7684\u8ba1\u7b97\u673a\u603b\u6570\u3002\u7136\u540e\uff0c\u7f51\u7edc\u4e2d\u7684\u6bcf\u53f0\u8ba1\u7b97\u673a\u75311\u5230N\u4e4b\u95f4\u7684\u6b63\u6574\u6570\u8868\u793a\u3002\u7136\u540e\uff0c\u5728\u4ee5\u4e0b\u884c\u4e2d\uff0c\u8f93\u5165\u4ee5\u4ee5\u4e0b\u683c\u5f0f\u7ed9\u51fa\uff1a
          \nI c1\u548cc2
          \n\u5176\u4e2dI\u8868\u793a\u8f93\u5165c1\u548cc2\u4e4b\u95f4\u7684\u8fde\u63a5\uff1b\u6216
          \nc1\u548cc2
          \n\u5176\u4e2dC\u8868\u793a\u68c0\u67e5\u662f\u5426\u53ef\u4ee5\u5728c1\u548cc2\u4e4b\u95f4\u4f20\u8f93\u6587\u4ef6\uff1b\u6216
          \nS
          \n\u5176\u4e2dS\u4ee3\u8868\u505c\u6b62\u8fd9\u79cd\u60c5\u51b5\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2aC\u7c7b\uff0c\u5982\u679c\u53ef\u4ee5\u6216\u4e0d\u53ef\u80fd\u5728c1\u548cc2\u4e4b\u95f4\u5206\u522b\u4f20\u8f93\u6587\u4ef6\uff0c\u5219\u5728\u4e00\u884c\u4e2d\u6253\u5370\u201c\u662f\u201d\u6216\u201c\u5426\u201d\u3002\u5728\u6bcf\u4e2a\u6848\u4f8b\u7684\u7ed3\u5c3e\uff0c\u5982\u679c\u4efb\u4f55\u4e00\u5bf9\u8ba1\u7b97\u673a\u4e4b\u95f4\u5b58\u5728\u8def\u5f84\uff0c\u5219\u5728\u4e00\u884c\u4e2d\u6253\u5370\u201c\u7f51\u7edc\u5df2\u8fde\u63a5\u201d\uff1b\u6216\u201c\u6709k\u4e2a\u7ec4\u4ef6\u201d\u3002\u5176\u4e2dk\u662f\u8be5\u7f51\u7edc\u4e2d\u8fde\u63a5\u7ec4\u4ef6\u7684\u6570\u91cf\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n5.
          \nC 3 2
          \nI 3 2
          \nC 1 5
          \nI 4 5
          \nI 2 4
          \nC 3 5
          \nS<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n\u4e0d
          \n\u4e0d
          \n\u5bf9
          \n\u6709\u4e24\u4e2a\u7ec4\u4ef6\u3002<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n5.
          \nC 3 2
          \nI 3 2
          \nC 1 5
          \nI 4 5
          \nI 2 4
          \nC 3 5
          \nI 1 3
          \nC 1 5
          \nS<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n\u4e0d
          \n\u4e0d
          \n\u5bf9
          \n\u5bf9
          \n\u7f51\u7edc\u88ab\u8fde\u63a5\u3002<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u8d70
          \n\u65f6\u95f4\u9650\u5236<\/p>\n
          05-\u68119 Huffman Codes<\/h3>\n
          In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. For each case, the first line gives an integer\u00a0N\u00a0(2\u2264N\u226463), then followed by a line that contains all the\u00a0N\u00a0distinct characters and their frequencies in the following format:
          \nc[1] f[1] c[2] f[2] … c[N] f[N]
          \nwhere\u00a0c[i]\u00a0is a character chosen from {‘0’ – ‘9’, ‘a’ – ‘z’, ‘A’ – ‘Z’, ‘_’}, and\u00a0f[i]\u00a0is the frequency of\u00a0c[i]\u00a0and is an integer no more than 1000. The next line gives a positive integer\u00a0M\u00a0(\u22641000), then followed by\u00a0M\u00a0student submissions. Each student submission consists of\u00a0N\u00a0lines, each in the format:
          \nc[i] code[i]
          \nwhere\u00a0c[i]\u00a0is the\u00a0i-th character and\u00a0code[i]\u00a0is an non-empty string of no more than 63 ‘0’s and ‘1’s.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, print in each line either "Yes" if the student’s submission is correct, or "No" if not.
          \nNote: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.<\/p>\n
          Sample Input:<\/strong>
          \n7
          \nA 1 B 1 C 1 D 3 E 3 F 6 G 6
          \n4
          \nA 00000
          \nB 00001
          \nC 0001
          \nD 001
          \nE 01
          \nF 10
          \nG 11
          \nA 01010
          \nB 01011
          \nC 0100
          \nD 011
          \nE 10
          \nF 11
          \nG 00
          \nA 000
          \nB 001
          \nC 010
          \nD 011
          \nE 100
          \nF 101
          \nG 110
          \nA 00000
          \nB 00001
          \nC 0001
          \nD 001
          \nE 00
          \nF 10
          \nG 11<\/p>\n
          Sample Output:<\/strong>
          \nYes
          \nYes
          \nNo
          \nNo<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  05-\u68119\u54c8\u592b\u66fc\u7801<\/h4>\n
          1953\u5e74\uff0c\u5927\u536b\u00b7A\u00b7\u970d\u592b\u66fc\u53d1\u8868\u4e86\u4ed6\u7684\u8bba\u6587\u300a\u6784\u9020\u6700\u5c0f\u5197\u4f59\u7801\u7684\u65b9\u6cd5\u300b\uff0c\u5e76\u56e0\u6b64\u5728\u8ba1\u7b97\u673a\u79d1\u5b66\u53f2\u4e0a\u53d1\u8868\u4e86\u81ea\u5df1\u7684\u540d\u5b57\u3002\u4f5c\u4e3a\u4e00\u540d\u6559\u6388\uff0c\u6211\u7ed9\u51fa\u4e86\u5173\u4e8e\u54c8\u592b\u66fc\u5bc6\u7801\u7684\u671f\u672b\u8003\u8bd5\u95ee\u9898\uff0c\u6211\u9047\u5230\u4e86\u4e00\u4e2a\u5927\u95ee\u9898\uff1a\u54c8\u592b\u66fc\u4ee3\u7801\u4e0d\u662f\u552f\u4e00\u7684\u3002\u4f8b\u5982\uff0c\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32\u201caaaxuaxz\u201d\uff0c\u6211\u4eec\u53ef\u4ee5\u89c2\u5bdf\u5230\u5b57\u7b26\u201ca\u201d\u3001\u201cx\u201d\u3001\u201cu\u201d\u548c\u201cz\u201d\u7684\u9891\u7387\u5206\u522b\u4e3a4\u30012\u30011\u548c1\u3002\u6211\u4eec\u53ef\u4ee5\u5c06\u7b26\u53f7\u7f16\u7801\u4e3a{‘a’=0\uff0c’x’=10\uff0c’u’=110\uff0c’z’=111}\uff0c\u6216\u8005\u4ee5\u53e6\u4e00\u79cd\u65b9\u5f0f\u7f16\u7801\u4e3a\uff5b\u2018a’=1\uff0c’x’=01\uff0c’u’=001\uff0c’z’=000}\uff0c\u4e24\u8005\u90fd\u5c06\u5b57\u7b26\u4e32\u538b\u7f29\u4e3a14\u4f4d\u3002\u53e6\u4e00\u7ec4\u4ee3\u7801\u53ef\u4ee5\u8868\u793a\u4e3a{‘a’=0\uff0c’x’=11\uff0c’u’=100\uff0c’z’=101}\uff0c\u4f46\u662f{‘a’=0\uff0cx’=01\uff0c’u’=011\uff0c’z’=001}\u662f\u4e0d\u6b63\u786e\u7684\uff0c\u56e0\u4e3a\u201caaaxuaxz\u201d\u548c\u201caazuax\u201d\u90fd\u53ef\u4ee5\u4ece\u4ee3\u7801000010110001\u4e2d\u89e3\u7801\u3002\u5b66\u751f\u4eec\u6b63\u5728\u63d0\u4ea4\u5404\u79cd\u4ee3\u7801\uff0c\u6211\u9700\u8981\u4e00\u4e2a\u8ba1\u7b97\u673a\u7a0b\u5e8f\u6765\u5e2e\u52a9\u6211\u786e\u5b9a\u54ea\u4e9b\u4ee3\u7801\u662f\u6b63\u786e\u7684\uff0c\u54ea\u4e9b\u662f\u9519\u8bef\u7684\u3002<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u7ed9\u51fa\u6574\u6570N\uff082\u2264N\u226463\uff09\uff0c\u7136\u540e\u540e\u8ddf\u4e00\u884c\uff0c\u8be5\u884c\u5305\u542b\u4ee5\u4e0b\u683c\u5f0f\u7684\u6240\u6709N\u4e2a\u4e0d\u540c\u5b57\u7b26\u53ca\u5176\u9891\u7387\uff1a
          \nc[1]f[1]c[2]f[2]\u2026c[N]f[N]
          \n\u5176\u4e2dc[i]\u662f\u4ece{0′-‘9’\uff0ca’-‘z’\uff0ca’-‘z’\uff0c’_’}\u4e2d\u9009\u62e9\u7684\u5b57\u7b26\uff0cf[i]\u4e3ac[i’\u7684\u9891\u7387\uff0c\u662f\u4e0d\u8d85\u8fc71000\u7684\u6574\u6570\u3002\u4e0b\u4e00\u884c\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570M(\u22641000\uff09\uff0c\u7136\u540e\u662fM\u4e2a\u5b66\u751f\u63d0\u4ea4\u3002\u6bcf\u4e2a\u5b66\u751f\u63d0\u4ea4\u7684\u6750\u6599\u7531N\u884c\u7ec4\u6210\uff0c\u6bcf\u884c\u7684\u683c\u5f0f\u5982\u4e0b\uff1a
          \nc[i]\u4ee3\u7801[i]
          \n\u5176\u4e2dc[i]\u662f\u7b2ci\u4e2a\u5b57\u7b26\uff0c\u4ee3\u7801[i]\u662f\u4e0d\u8d85\u8fc763’0’\u548c’1’\u7684\u975e\u7a7a\u5b57\u7b26\u4e32\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5982\u679c\u5b66\u751f\u63d0\u4ea4\u7684\u5185\u5bb9\u6b63\u786e\uff0c\u5219\u5728\u6bcf\u884c\u6253\u5370\u201c\u662f\u201d\uff0c\u5982\u679c\u4e0d\u6b63\u786e\uff0c\u5219\u6253\u5370\u201c\u5426\u201d\u3002
          \n\u6ce8\uff1a\u6700\u4f18\u89e3\u4e0d\u4e00\u5b9a\u7531\u970d\u592b\u66fc\u7b97\u6cd5\u751f\u6210\u3002\u4efb\u4f55\u5177\u6709\u6700\u4f73\u7801\u957f\u7684\u524d\u7f00\u7801\u90fd\u88ab\u8ba4\u4e3a\u662f\u6b63\u786e\u7684\u3002<\/p>\n
          \u6837\u672c\u8f93\u5165\uff1a<\/strong>
          \n7.
          \nA 1 B 1 C 1 D 3 E 3 F 6 G 6
          \n4.
          \n\u5341\u4e07
          \nB 00001
          \nC 0001
          \nD 001
          \nE 01
          \nF10
          \nG.11
          \nA 01010
          \nB 01011
          \nC 0100
          \nD 011
          \nE10
          \nF 11
          \nG 00
          \n\u4e00\u5343
          \nB 001
          \nC 010
          \nD 011
          \nE100
          \nF 101
          \nG 110
          \n\u5341\u4e07
          \nB 00001
          \nC 0001
          \nD 001
          \nE 00
          \nF10
          \nG.11<\/p>\n
          \u6837\u672c\u8f93\u51fa\uff1a<\/strong>
          \n\u5bf9
          \n\u5bf9
          \n\u4e0d
          \n\u4e0d<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          06-\u56fe1 \u5217\u51fa\u8fde\u901a\u96c6<\/h3>\n
          \u7ed9\u5b9a\u4e00\u4e2a\u6709N\u4e2a\u9876\u70b9\u548cE\u6761\u8fb9\u7684\u65e0\u5411\u56fe\uff0c\u8bf7\u7528DFS\u548cBFS\u5206\u522b\u5217\u51fa\u5176\u6240\u6709\u7684\u8fde\u901a\u96c6\u3002\u5047\u8bbe\u9876\u70b9\u4ece0\u5230N\u22121\u7f16\u53f7\u3002\u8fdb\u884c\u641c\u7d22\u65f6\uff0c\u5047\u8bbe\u6211\u4eec\u603b\u662f\u4ece\u7f16\u53f7\u6700\u5c0f\u7684\u9876\u70b9\u51fa\u53d1\uff0c\u6309\u7f16\u53f7\u9012\u589e\u7684\u987a\u5e8f\u8bbf\u95ee\u90bb\u63a5\u70b9\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u7b2c1\u884c\u7ed9\u51fa2\u4e2a\u6574\u6570N(0<N\u226410)\u548cE\uff0c\u5206\u522b\u662f\u56fe\u7684\u9876\u70b9\u6570\u548c\u8fb9\u6570\u3002\u968f\u540eE\u884c\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e00\u6761\u8fb9\u7684\u4e24\u4e2a\u7aef\u70b9\u3002\u6bcf\u884c\u4e2d\u7684\u6570\u5b57\u4e4b\u95f4\u75281\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u6309\u7167"{\u00a0v1\u200b\u00a0v2\u200b\u00a0…\u00a0vk\u200b\u00a0}"\u7684\u683c\u5f0f\uff0c\u6bcf\u884c\u8f93\u51fa\u4e00\u4e2a\u8fde\u901a\u96c6\u3002\u5148\u8f93\u51faDFS\u7684\u7ed3\u679c\uff0c\u518d\u8f93\u51faBFS\u7684\u7ed3\u679c\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n8 6
          \n0 7
          \n0 1
          \n2 0
          \n4 1
          \n2 4
          \n3 5<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n{ 0 1 4 2 7 }
          \n{ 3 5 }
          \n{ 6 }
          \n{ 0 1 2 7 4 }
          \n{ 3 5 }
          \n{ 6 }<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          06-\u56fe2 Saving James Bond – Easy Version<\/h3>\n
          This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape — he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
          \nAssume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. Each case starts with a line containing two positive integers\u00a0N\u00a0(\u2264100), the number of crocodiles, and\u00a0D, the maximum distance that James could jump. Then\u00a0N\u00a0lines follow, each containing the\u00a0(x,y)\u00a0location of a crocodile. Note that no two crocodiles are staying at the same position.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, print in a line "Yes" if James can escape, or "No" if not.<\/p>\n
          Sample Input 1:<\/strong>
          \n14 20
          \n25 -15
          \n-25 28
          \n8 49
          \n29 15
          \n-35 -2
          \n5 28
          \n27 -29
          \n-8 -28
          \n-20 -35
          \n-25 -20
          \n-13 29
          \n-30 15
          \n-35 40
          \n12 12<\/p>\n
          Sample Output 1:<\/strong>
          \nYes<\/p>\n
          Sample Input 2:<\/strong>
          \n4 13
          \n-12 12
          \n12 12
          \n-12 -12
          \n12 -12<\/p>\n
          Sample Output 2:<\/strong>
          \nNo<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  06-\u56fe2\u62ef\u6551\u8a79\u59c6\u65af\u00b7\u90a6\u5fb7-\u7b80\u6613\u7248<\/h4>\n
          \u8fd9\u4e00\u6b21\uff0c\u8ba9\u6211\u4eec\u8003\u8651\u4e00\u4e0b\u7535\u5f71\u300a\u751f\u6b7b\u6289\u62e9\u300b\u4e2d\u7684\u60c5\u51b5\uff0c\u4e16\u754c\u4e0a\u6700\u8457\u540d\u7684\u95f4\u8c0d\u8a79\u59c6\u65af\u00b7\u90a6\u5fb7\u88ab\u4e00\u7fa4\u6bd2\u8d29\u6293\u83b7\u3002\u4ed6\u88ab\u9001\u5230\u6e56\u5fc3\u7684\u4e00\u5c0f\u5757\u571f\u5730\u4e0a\uff0c\u90a3\u91cc\u5230\u5904\u90fd\u662f\u9cc4\u9c7c\u3002\u5728\u90a3\u91cc\uff0c\u4ed6\u505a\u51fa\u4e86\u6700\u5927\u80c6\u7684\u9003\u8dd1\u52a8\u4f5c\u2014\u2014\u4ed6\u8df3\u5230\u4e86\u6700\u8fd1\u4e00\u6761\u9cc4\u9c7c\u7684\u5934\u4e0a\uff01\u5728\u52a8\u7269\u610f\u8bc6\u5230\u53d1\u751f\u4e86\u4ec0\u4e48\u4e4b\u524d\uff0c\u8a79\u59c6\u65af\u53c8\u8df3\u5230\u4e86\u4e0b\u4e00\u4e2a\u5927\u8111\u888b\u4e0a\u2026\u2026\u6700\u540e\uff0c\u4ed6\u5728\u6700\u540e\u4e00\u6761\u9cc4\u9c7c\u54ac\u4ed6\u4e4b\u524d\u5230\u8fbe\u4e86\u6cb3\u5cb8\uff08\u4e8b\u5b9e\u4e0a\uff0c\u7279\u6280\u6f14\u5458\u88ab\u5927\u5634\u5df4\u6293\u4f4f\u4e86\uff0c\u7528\u4ed6\u90a3\u8d85\u539a\u7684\u9774\u5b50\u52c9\u5f3a\u9003\u8131\uff09\u3002
          \n\u5047\u8bbe\u8fd9\u4e2a\u6e56\u662f\u4e00\u4e2a100\u4e58100\u5e73\u65b9\u7c73\u7684\u6e56\u3002\u5047\u8bbe\u6e56\u7684\u4e2d\u5fc3\u4f4d\u4e8e\uff080,0\uff09\uff0c\u4e1c\u5317\u89d2\u4f4d\u4e8e\uff0850,50\uff09\u3002\u4e2d\u592e\u5c9b\u662f\u4e00\u4e2a\u4ee5\uff080,0\uff09\u4e3a\u4e2d\u5fc3\u7684\u5706\u76d8\uff0c\u76f4\u5f84\u4e3a15\u3002\u8bb8\u591a\u9cc4\u9c7c\u5728\u6e56\u4e2d\u7684\u4e0d\u540c\u4f4d\u7f6e\u3002\u8003\u8651\u5230\u6bcf\u53ea\u9cc4\u9c7c\u7684\u5750\u6807\u548c\u8a79\u59c6\u65af\u80fd\u8df3\u7684\u8ddd\u79bb\uff0c\u4f60\u5fc5\u987b\u544a\u8bc9\u4ed6\u4ed6\u662f\u5426\u80fd\u9003\u8131\u3002<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u6bcf\u79cd\u60c5\u51b5\u90fd\u4ece\u5305\u542b\u4e24\u4e2a\u6b63\u6574\u6570N\u7684\u884c\u5f00\u59cb(\u2264100\uff09\u8868\u793a\u9cc4\u9c7c\u7684\u6570\u91cf\uff0cD\u8868\u793a\u8a79\u59c6\u65af\u80fd\u8df3\u7684\u6700\u5927\u8ddd\u79bb\u3002\u63a5\u4e0b\u6765\u662fN\u884c\uff0c\u6bcf\u884c\u5305\u542b\u9cc4\u9c7c\u7684\uff08x\uff0cy\uff09\u4f4d\u7f6e\u3002\u8bf7\u6ce8\u610f\uff0c\u6ca1\u6709\u4e24\u53ea\u9cc4\u9c7c\u505c\u7559\u5728\u540c\u4e00\u4f4d\u7f6e\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5982\u679cJames\u53ef\u4ee5\u9003\u9038\uff0c\u8bf7\u6253\u5370\u4e00\u884c\u201c\u662f\u201d\uff0c\u5982\u679c\u4e0d\u53ef\u4ee5\uff0c\u8bf7\u6253\u5370\u201c\u5426\u201d\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n14 20
          \n25 -15
          \n-25 28
          \n8 49
          \n29 15
          \n-35 -2
          \n5 28
          \n27 -29
          \n-8 -28
          \n-20 -35
          \n-25 -20
          \n-13 29
          \n-30 15
          \n-35 40
          \n12 12<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n\u5bf9<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n4 13
          \n-12 12
          \n12 12
          \n-12 -12
          \n12 -12<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n\u4e0d<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          06-\u56fe3 \u516d\u5ea6\u7a7a\u95f4<\/h3>\n
          \u201c\u516d\u5ea6\u7a7a\u95f4\u201d\u7406\u8bba\u53c8\u79f0\u4f5c\u201c\u516d\u5ea6\u5206\u9694\uff08Six Degrees of Separation\uff09\u201d\u7406\u8bba\u3002\u8fd9\u4e2a\u7406\u8bba\u53ef\u4ee5\u901a\u4fd7\u5730\u9610\u8ff0\u4e3a\uff1a\u201c\u4f60\u548c\u4efb\u4f55\u4e00\u4e2a\u964c\u751f\u4eba\u4e4b\u95f4\u6240\u95f4\u9694\u7684\u4eba\u4e0d\u4f1a\u8d85\u8fc7\u516d\u4e2a\uff0c\u4e5f\u5c31\u662f\u8bf4\uff0c\u6700\u591a\u901a\u8fc7\u4e94\u4e2a\u4eba\u4f60\u5c31\u80fd\u591f\u8ba4\u8bc6\u4efb\u4f55\u4e00\u4e2a\u964c\u751f\u4eba\u3002\u201d\u5982\u56fe1\u6240\u793a\u3002
          \n\u56fe1 \u516d\u5ea6\u7a7a\u95f4\u793a\u610f\u56fe
          \n\u201c\u516d\u5ea6\u7a7a\u95f4\u201d\u7406\u8bba\u867d\u7136\u5f97\u5230\u5e7f\u6cdb\u7684\u8ba4\u540c\uff0c\u5e76\u4e14\u6b63\u5728\u5f97\u5230\u8d8a\u6765\u8d8a\u591a\u7684\u5e94\u7528\u3002\u4f46\u662f\u6570\u5341\u5e74\u6765\uff0c\u8bd5\u56fe\u9a8c\u8bc1\u8fd9\u4e2a\u7406\u8bba\u59cb\u7ec8\u662f\u8bb8\u591a\u793e\u4f1a\u5b66\u5bb6\u52aa\u529b\u8ffd\u6c42\u7684\u76ee\u6807\u3002\u7136\u800c\u7531\u4e8e\u5386\u53f2\u7684\u539f\u56e0\uff0c\u8fd9\u6837\u7684\u7814\u7a76\u5177\u6709\u592a\u5927\u7684\u5c40\u9650\u6027\u548c\u56f0\u96be\u3002\u968f\u7740\u5f53\u4ee3\u4eba\u7684\u8054\u7edc\u4e3b\u8981\u4f9d\u8d56\u4e8e\u7535\u8bdd\u3001\u77ed\u4fe1\u3001\u5fae\u4fe1\u4ee5\u53ca\u56e0\u7279\u7f51\u4e0a\u5373\u65f6\u901a\u4fe1\u7b49\u5de5\u5177\uff0c\u80fd\u591f\u4f53\u73b0\u793e\u4ea4\u7f51\u7edc\u5173\u7cfb\u7684\u4e00\u624b\u6570\u636e\u5df2\u7ecf\u9010\u6e10\u4f7f\u5f97\u201c\u516d\u5ea6\u7a7a\u95f4\u201d\u7406\u8bba\u7684\u9a8c\u8bc1\u6210\u4e3a\u53ef\u80fd\u3002
          \n\u5047\u5982\u7ed9\u4f60\u4e00\u4e2a\u793e\u4ea4\u7f51\u7edc\u56fe\uff0c\u8bf7\u4f60\u5bf9\u6bcf\u4e2a\u8282\u70b9\u8ba1\u7b97\u7b26\u5408\u201c\u516d\u5ea6\u7a7a\u95f4\u201d\u7406\u8bba\u7684\u7ed3\u70b9\u5360\u7ed3\u70b9\u603b\u6570\u7684\u767e\u5206\u6bd4\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u7b2c1\u884c\u7ed9\u51fa\u4e24\u4e2a\u6b63\u6574\u6570\uff0c\u5206\u522b\u8868\u793a\u793e\u4ea4\u7f51\u7edc\u56fe\u7684\u7ed3\u70b9\u6570N\uff081<N\u2264103\uff0c\u8868\u793a\u4eba\u6570\uff09\u3001\u8fb9\u6570M\uff08\u226433\u00d7N\uff0c\u8868\u793a\u793e\u4ea4\u5173\u7cfb\u6570\uff09\u3002\u968f\u540e\u7684M\u884c\u5bf9\u5e94M\u6761\u8fb9\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e00\u5bf9\u6b63\u6574\u6570\uff0c\u5206\u522b\u662f\u8be5\u6761\u8fb9\u76f4\u63a5\u8fde\u901a\u7684\u4e24\u4e2a\u7ed3\u70b9\u7684\u7f16\u53f7\uff08\u8282\u70b9\u4ece1\u5230N\u7f16\u53f7\uff09\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u5bf9\u6bcf\u4e2a\u7ed3\u70b9\u8f93\u51fa\u4e0e\u8be5\u7ed3\u70b9\u8ddd\u79bb\u4e0d\u8d85\u8fc76\u7684\u7ed3\u70b9\u6570\u5360\u7ed3\u70b9\u603b\u6570\u7684\u767e\u5206\u6bd4\uff0c\u7cbe\u786e\u5230\u5c0f\u6570\u70b9\u540e2\u4f4d\u3002\u6bcf\u4e2a\u7ed3\u8282\u70b9\u8f93\u51fa\u4e00\u884c\uff0c\u683c\u5f0f\u4e3a\u201c\u7ed3\u70b9\u7f16\u53f7:\uff08\u7a7a\u683c\uff09\u767e\u5206\u6bd4%\u201d\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n10 9
          \n1 2
          \n2 3
          \n3 4
          \n4 5
          \n5 6
          \n6 7
          \n7 8
          \n8 9
          \n9 10<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n1: 70.00%
          \n2: 80.00%
          \n3: 90.00%
          \n4: 100.00%
          \n5: 100.00%
          \n6: 100.00%
          \n7: 100.00%
          \n8: 90.00%
          \n9: 80.00%
          \n10: 70.00%<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n2500 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          07-\u56fe4 \u54c8\u5229\u00b7\u6ce2\u7279\u7684\u8003\u8bd5<\/h3>\n
          \u54c8\u5229\u00b7\u6ce2\u7279\u8981\u8003\u8bd5\u4e86\uff0c\u4ed6\u9700\u8981\u4f60\u7684\u5e2e\u52a9\u3002\u8fd9\u95e8\u8bfe\u5b66\u7684\u662f\u7528\u9b54\u5492\u5c06\u4e00\u79cd\u52a8\u7269\u53d8\u6210\u53e6\u4e00\u79cd\u52a8\u7269\u7684\u672c\u4e8b\u3002\u4f8b\u5982\u5c06\u732b\u53d8\u6210\u8001\u9f20\u7684\u9b54\u5492\u662fhaha\uff0c\u5c06\u8001\u9f20\u53d8\u6210\u9c7c\u7684\u9b54\u5492\u662fhehe\u7b49\u7b49\u3002\u53cd\u65b9\u5411\u53d8\u5316\u7684\u9b54\u5492\u5c31\u662f\u7b80\u5355\u5730\u5c06\u539f\u6765\u7684\u9b54\u5492\u5012\u8fc7\u6765\u5ff5\uff0c\u4f8b\u5982ahah\u53ef\u4ee5\u5c06\u8001\u9f20\u53d8\u6210\u732b\u3002\u53e6\u5916\uff0c\u5982\u679c\u60f3\u628a\u732b\u53d8\u6210\u9c7c\uff0c\u53ef\u4ee5\u901a\u8fc7\u5ff5\u4e00\u4e2a\u76f4\u63a5\u9b54\u5492lalala\uff0c\u4e5f\u53ef\u4ee5\u5c06\u732b\u53d8\u8001\u9f20\u3001\u8001\u9f20\u53d8\u9c7c\u7684\u9b54\u5492\u8fde\u8d77\u6765\u5ff5\uff1ahahahehe\u3002
          \n\u73b0\u5728\u54c8\u5229\u00b7\u6ce2\u7279\u7684\u624b\u91cc\u6709\u4e00\u672c\u6559\u6750\uff0c\u91cc\u9762\u5217\u51fa\u4e86\u6240\u6709\u7684\u53d8\u5f62\u9b54\u5492\u548c\u80fd\u53d8\u7684\u52a8\u7269\u3002\u8001\u5e08\u5141\u8bb8\u4ed6\u81ea\u5df1\u5e26\u4e00\u53ea\u52a8\u7269\u53bb\u8003\u573a\uff0c\u8981\u8003\u5bdf\u4ed6\u628a\u8fd9\u53ea\u52a8\u7269\u53d8\u6210\u4efb\u610f\u4e00\u53ea\u6307\u5b9a\u52a8\u7269\u7684\u672c\u4e8b\u3002\u4e8e\u662f\u4ed6\u6765\u95ee\u4f60\uff1a\u5e26\u4ec0\u4e48\u52a8\u7269\u53bb\u53ef\u4ee5\u8ba9\u6700\u96be\u53d8\u7684\u90a3\u79cd\u52a8\u7269\uff08\u5373\u8be5\u52a8\u7269\u53d8\u4e3a\u54c8\u5229\u00b7\u6ce2\u7279\u81ea\u5df1\u5e26\u53bb\u7684\u52a8\u7269\u6240\u9700\u8981\u7684\u9b54\u5492\u6700\u957f\uff09\u9700\u8981\u7684\u9b54\u5492\u6700\u77ed\uff1f\u4f8b\u5982\uff1a\u5982\u679c\u53ea\u6709\u732b\u3001\u9f20\u3001\u9c7c\uff0c\u5219\u663e\u7136\u54c8\u5229\u00b7\u6ce2\u7279\u5e94\u8be5\u5e26\u9f20\u53bb\uff0c\u56e0\u4e3a\u9f20\u53d8\u6210\u53e6\u5916\u4e24\u79cd\u52a8\u7269\u90fd\u53ea\u9700\u8981\u5ff54\u4e2a\u5b57\u7b26\uff1b\u800c\u5982\u679c\u5e26\u732b\u53bb\uff0c\u5219\u81f3\u5c11\u9700\u8981\u5ff56\u4e2a\u5b57\u7b26\u624d\u80fd\u628a\u732b\u53d8\u6210\u9c7c\uff1b\u540c\u7406\uff0c\u5e26\u9c7c\u53bb\u4e5f\u4e0d\u662f\u6700\u597d\u7684\u9009\u62e9\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u8bf4\u660e\uff1a\u8f93\u5165\u7b2c1\u884c\u7ed9\u51fa\u4e24\u4e2a\u6b63\u6574\u6570N\u00a0(\u2264100)\u548cM\uff0c\u5176\u4e2dN\u662f\u8003\u8bd5\u6d89\u53ca\u7684\u52a8\u7269\u603b\u6570\uff0cM\u662f\u7528\u4e8e\u76f4\u63a5\u53d8\u5f62\u7684\u9b54\u5492\u6761\u6570\u3002\u4e3a\u7b80\u5355\u8d77\u89c1\uff0c\u6211\u4eec\u5c06\u52a8\u7269\u63091~N\u7f16\u53f7\u3002\u968f\u540eM\u884c\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e863\u4e2a\u6b63\u6574\u6570\uff0c\u5206\u522b\u662f\u4e24\u79cd\u52a8\u7269\u7684\u7f16\u53f7\u3001\u4ee5\u53ca\u5b83\u4eec\u4e4b\u95f4\u53d8\u5f62\u9700\u8981\u7684\u9b54\u5492\u7684\u957f\u5ea6(\u2264100)\uff0c\u6570\u5b57\u4e4b\u95f4\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u8f93\u51fa\u54c8\u5229\u00b7\u6ce2\u7279\u5e94\u8be5\u5e26\u53bb\u8003\u573a\u7684\u52a8\u7269\u7684\u7f16\u53f7\u3001\u4ee5\u53ca\u6700\u957f\u7684\u53d8\u5f62\u9b54\u5492\u7684\u957f\u5ea6\uff0c\u4e2d\u95f4\u4ee5\u7a7a\u683c\u5206\u9694\u3002\u5982\u679c\u53ea\u5e261\u53ea\u52a8\u7269\u662f\u4e0d\u53ef\u80fd\u5b8c\u6210\u6240\u6709\u53d8\u5f62\u8981\u6c42\u7684\uff0c\u5219\u8f93\u51fa0\u3002\u5982\u679c\u6709\u82e5\u5e72\u53ea\u52a8\u7269\u90fd\u53ef\u4ee5\u5907\u9009\uff0c\u5219\u8f93\u51fa\u7f16\u53f7\u6700\u5c0f\u7684\u90a3\u53ea\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n6 11
          \n3 4 70
          \n1 2 1
          \n5 4 50
          \n2 6 50
          \n5 6 60
          \n1 3 70
          \n4 6 60
          \n3 6 80
          \n5 1 100
          \n2 4 60
          \n5 2 80<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n4 70<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          07-\u56fe5 Saving James Bond – Hard Version<\/h3>\n
          This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape — he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
          \nAssume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. Each case starts with a line containing two positive integers\u00a0N\u00a0(\u2264100), the number of crocodiles, and\u00a0D, the maximum distance that James could jump. Then\u00a0N\u00a0lines follow, each containing the\u00a0(x,y)\u00a0location of a crocodile. Note that no two crocodiles are staying at the same position.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position\u00a0(x,y)\u00a0of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.<\/p>\n
          Sample Input 1:<\/strong>
          \n17 15
          \n10 -21
          \n10 21
          \n-40 10
          \n30 -50
          \n20 40
          \n35 10
          \n0 -10
          \n-25 22
          \n40 -40
          \n-30 30
          \n-10 22
          \n0 11
          \n25 21
          \n25 10
          \n10 10
          \n10 35
          \n-30 10<\/p>\n
          Sample Output 1:<\/strong>
          \n4
          \n0 11
          \n10 21
          \n10 35<\/p>\n
          Sample Input 2:<\/strong>
          \n4 13
          \n-12 12
          \n12 12
          \n-12 -12
          \n12 -12<\/p>\n
          Sample Output 2:<\/strong>
          \n0<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  07-\u56fe5\u62ef\u6551\u8a79\u59c6\u65af\u00b7\u90a6\u5fb7-\u786c\u7248<\/h4>\n
          \u8fd9\u4e00\u6b21\uff0c\u8ba9\u6211\u4eec\u8003\u8651\u4e00\u4e0b\u7535\u5f71\u300a\u751f\u6b7b\u6289\u62e9\u300b\u4e2d\u7684\u60c5\u51b5\uff0c\u4e16\u754c\u4e0a\u6700\u8457\u540d\u7684\u95f4\u8c0d\u8a79\u59c6\u65af\u00b7\u90a6\u5fb7\u88ab\u4e00\u7fa4\u6bd2\u8d29\u6293\u83b7\u3002\u4ed6\u88ab\u9001\u5230\u6e56\u5fc3\u7684\u4e00\u5c0f\u5757\u571f\u5730\u4e0a\uff0c\u90a3\u91cc\u5230\u5904\u90fd\u662f\u9cc4\u9c7c\u3002\u5728\u90a3\u91cc\uff0c\u4ed6\u505a\u51fa\u4e86\u6700\u5927\u80c6\u7684\u9003\u8dd1\u52a8\u4f5c\u2014\u2014\u4ed6\u8df3\u5230\u4e86\u6700\u8fd1\u4e00\u6761\u9cc4\u9c7c\u7684\u5934\u4e0a\uff01\u5728\u52a8\u7269\u610f\u8bc6\u5230\u53d1\u751f\u4e86\u4ec0\u4e48\u4e4b\u524d\uff0c\u8a79\u59c6\u65af\u53c8\u8df3\u5230\u4e86\u4e0b\u4e00\u4e2a\u5927\u8111\u888b\u4e0a\u2026\u2026\u6700\u540e\uff0c\u4ed6\u5728\u6700\u540e\u4e00\u6761\u9cc4\u9c7c\u54ac\u4ed6\u4e4b\u524d\u5230\u8fbe\u4e86\u6cb3\u5cb8\uff08\u4e8b\u5b9e\u4e0a\uff0c\u7279\u6280\u6f14\u5458\u88ab\u5927\u5634\u5df4\u6293\u4f4f\u4e86\uff0c\u7528\u4ed6\u90a3\u8d85\u539a\u7684\u9774\u5b50\u52c9\u5f3a\u9003\u8131\uff09\u3002
          \n\u5047\u8bbe\u8fd9\u4e2a\u6e56\u662f\u4e00\u4e2a100\u4e58100\u5e73\u65b9\u7c73\u7684\u6e56\u3002\u5047\u8bbe\u6e56\u7684\u4e2d\u5fc3\u4f4d\u4e8e\uff080,0\uff09\uff0c\u4e1c\u5317\u89d2\u4f4d\u4e8e\uff0850,50\uff09\u3002\u4e2d\u592e\u5c9b\u662f\u4e00\u4e2a\u4ee5\uff080,0\uff09\u4e3a\u4e2d\u5fc3\u7684\u5706\u76d8\uff0c\u76f4\u5f84\u4e3a15\u3002\u8bb8\u591a\u9cc4\u9c7c\u5728\u6e56\u4e2d\u7684\u4e0d\u540c\u4f4d\u7f6e\u3002\u8003\u8651\u5230\u6bcf\u53ea\u9cc4\u9c7c\u7684\u5750\u6807\u548c\u8a79\u59c6\u65af\u80fd\u8df3\u7684\u8ddd\u79bb\uff0c\u4f60\u5fc5\u987b\u544a\u8bc9\u4ed6\u5230\u8fbe\u5176\u4e2d\u4e00\u4e2a\u6cb3\u5cb8\u7684\u6700\u77ed\u8def\u5f84\u3002\u8def\u5f84\u7684\u957f\u5ea6\u662f\u8a79\u59c6\u65af\u5fc5\u987b\u8df3\u8dc3\u7684\u6b21\u6570\u3002<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u6bcf\u79cd\u60c5\u51b5\u90fd\u4ece\u5305\u542b\u4e24\u4e2a\u6b63\u6574\u6570N\u7684\u884c\u5f00\u59cb(\u2264100\uff09\u8868\u793a\u9cc4\u9c7c\u7684\u6570\u91cf\uff0cD\u8868\u793a\u8a79\u59c6\u65af\u80fd\u8df3\u7684\u6700\u5927\u8ddd\u79bb\u3002\u63a5\u4e0b\u6765\u662fN\u884c\uff0c\u6bcf\u884c\u5305\u542b\u9cc4\u9c7c\u7684\uff08x\uff0cy\uff09\u4f4d\u7f6e\u3002\u8bf7\u6ce8\u610f\uff0c\u6ca1\u6709\u4e24\u53ea\u9cc4\u9c7c\u505c\u7559\u5728\u540c\u4e00\u4f4d\u7f6e\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5982\u679cJames\u80fd\u591f\u9003\u8131\uff0c\u5219\u5728\u4e00\u884c\u4e2d\u8f93\u51fa\u4ed6\u5fc5\u987b\u8fdb\u884c\u7684\u6700\u5c0f\u8df3\u8dc3\u6b21\u6570\u3002\u7136\u540e\u4ece\u4e0b\u4e00\u884c\u5f00\u59cb\uff0c\u8f93\u51fa\u8def\u5f84\u4e0a\u6bcf\u53ea\u9cc4\u9c7c\u7684\u4f4d\u7f6e\uff08x\uff0cy\uff09\uff0c\u6bcf\u5bf9\u9cc4\u9c7c\u6392\u6210\u4e00\u884c\uff0c\u4ece\u5c9b\u5c7f\u5230\u6cb3\u5cb8\u3002\u5982\u679c\u8a79\u59c6\u65af\u65e0\u6cd5\u901a\u8fc7\u8fd9\u79cd\u65b9\u5f0f\u9003\u8131\uff0c\u53ea\u9700\u7ed9\u4ed60\u4f5c\u4e3a\u8df3\u8dc3\u6b21\u6570\u3002\u5982\u679c\u6709\u8bb8\u591a\u6700\u77ed\u8def\u5f84\uff0c\u53ea\u9700\u8f93\u51fa\u7b2c\u4e00\u8df3\u6700\u5c0f\u7684\u8def\u5f84\uff0c\u8fd9\u4fdd\u8bc1\u662f\u552f\u4e00\u7684\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n17 15
          \n10 -21
          \n10 21
          \n-40 10
          \n30 -50
          \n20 40
          \n35 10
          \n0 -10
          \n-25 22
          \n40 -40
          \n-30 30
          \n-10 22
          \n0 11
          \n25 21
          \n25 10
          \n10 10
          \n10 35
          \n-30 10<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n4.
          \n0 11
          \n10 21
          \n10 35<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n4 13
          \n-12 12
          \n12 12
          \n-12 -12
          \n12 -12<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n0<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          07-\u56fe6 \u65c5\u6e38\u89c4\u5212<\/h3>\n
          \u6709\u4e86\u4e00\u5f20\u81ea\u9a7e\u65c5\u6e38\u8def\u7ebf\u56fe\uff0c\u4f60\u4f1a\u77e5\u9053\u57ce\u5e02\u95f4\u7684\u9ad8\u901f\u516c\u8def\u957f\u5ea6\u3001\u4ee5\u53ca\u8be5\u516c\u8def\u8981\u6536\u53d6\u7684\u8fc7\u8def\u8d39\u3002\u73b0\u5728\u9700\u8981\u4f60\u5199\u4e00\u4e2a\u7a0b\u5e8f\uff0c\u5e2e\u52a9\u524d\u6765\u54a8\u8be2\u7684\u6e38\u5ba2\u627e\u4e00\u6761\u51fa\u53d1\u5730\u548c\u76ee\u7684\u5730\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u5f84\u3002\u5982\u679c\u6709\u82e5\u5e72\u6761\u8def\u5f84\u90fd\u662f\u6700\u77ed\u7684\uff0c\u90a3\u4e48\u9700\u8981\u8f93\u51fa\u6700\u4fbf\u5b9c\u7684\u4e00\u6761\u8def\u5f84\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u8bf4\u660e\uff1a\u8f93\u5165\u6570\u636e\u7684\u7b2c1\u884c\u7ed9\u51fa4\u4e2a\u6b63\u6574\u6570N\u3001M\u3001S\u3001D\uff0c\u5176\u4e2dN\uff082\u2264N\u2264500\uff09\u662f\u57ce\u5e02\u7684\u4e2a\u6570\uff0c\u987a\u4fbf\u5047\u8bbe\u57ce\u5e02\u7684\u7f16\u53f7\u4e3a0~(N\u22121)\uff1bM\u662f\u9ad8\u901f\u516c\u8def\u7684\u6761\u6570\uff1bS\u662f\u51fa\u53d1\u5730\u7684\u57ce\u5e02\u7f16\u53f7\uff1bD\u662f\u76ee\u7684\u5730\u7684\u57ce\u5e02\u7f16\u53f7\u3002\u968f\u540e\u7684M\u884c\u4e2d\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e00\u6761\u9ad8\u901f\u516c\u8def\u7684\u4fe1\u606f\uff0c\u5206\u522b\u662f\uff1a\u57ce\u5e021\u3001\u57ce\u5e022\u3001\u9ad8\u901f\u516c\u8def\u957f\u5ea6\u3001\u6536\u8d39\u989d\uff0c\u4e2d\u95f4\u7528\u7a7a\u683c\u5206\u5f00\uff0c\u6570\u5b57\u5747\u4e3a\u6574\u6570\u4e14\u4e0d\u8d85\u8fc7500\u3002\u8f93\u5165\u4fdd\u8bc1\u89e3\u7684\u5b58\u5728\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u5728\u4e00\u884c\u91cc\u8f93\u51fa\u8def\u5f84\u7684\u957f\u5ea6\u548c\u6536\u8d39\u603b\u989d\uff0c\u6570\u5b57\u95f4\u4ee5\u7a7a\u683c\u5206\u9694\uff0c\u8f93\u51fa\u7ed3\u5c3e\u4e0d\u80fd\u6709\u591a\u4f59\u7a7a\u683c\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n4 5 0 3
          \n0 1 1 20
          \n1 3 2 30
          \n0 3 4 10
          \n0 2 2 20
          \n2 3 1 20<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n3 40<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \nJava (javac)
          \n\u65f6\u95f4\u9650\u5236<\/p>\n
          08-\u56fe7 \u516c\u8def\u6751\u6751\u901a<\/h3>\n
          \u73b0\u6709\u6751\u843d\u95f4\u9053\u8def\u7684\u7edf\u8ba1\u6570\u636e\u8868\u4e2d\uff0c\u5217\u51fa\u4e86\u6709\u53ef\u80fd\u5efa\u8bbe\u6210\u6807\u51c6\u516c\u8def\u7684\u82e5\u5e72\u6761\u9053\u8def\u7684\u6210\u672c\uff0c\u6c42\u4f7f\u6bcf\u4e2a\u6751\u843d\u90fd\u6709\u516c\u8def\u8fde\u901a\u6240\u9700\u8981\u7684\u6700\u4f4e\u6210\u672c\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u6570\u636e\u5305\u62ec\u57ce\u9547\u6570\u76ee\u6b63\u6574\u6570N\uff08\u22641000\uff09\u548c\u5019\u9009\u9053\u8def\u6570\u76eeM\uff08\u22643N\uff09\uff1b\u968f\u540e\u7684M\u884c\u5bf9\u5e94M\u6761\u9053\u8def\uff0c\u6bcf\u884c\u7ed9\u51fa3\u4e2a\u6b63\u6574\u6570\uff0c\u5206\u522b\u662f\u8be5\u6761\u9053\u8def\u76f4\u63a5\u8fde\u901a\u7684\u4e24\u4e2a\u57ce\u9547\u7684\u7f16\u53f7\u4ee5\u53ca\u8be5\u9053\u8def\u6539\u5efa\u7684\u9884\u7b97\u6210\u672c\u3002\u4e3a\u7b80\u5355\u8d77\u89c1\uff0c\u57ce\u9547\u4ece1\u5230N\u7f16\u53f7\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u8f93\u51fa\u6751\u6751\u901a\u9700\u8981\u7684\u6700\u4f4e\u6210\u672c\u3002\u5982\u679c\u8f93\u5165\u6570\u636e\u4e0d\u8db3\u4ee5\u4fdd\u8bc1\u7545\u901a\uff0c\u5219\u8f93\u51fa\u22121\uff0c\u8868\u793a\u9700\u8981\u5efa\u8bbe\u66f4\u591a\u516c\u8def\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n6 15
          \n1 2 5
          \n1 3 3
          \n1 4 7
          \n1 5 4
          \n1 6 2
          \n2 3 4
          \n2 4 6
          \n2 5 2
          \n2 6 6
          \n3 4 6
          \n3 5 1
          \n3 6 1
          \n4 5 10
          \n4 6 8
          \n5 6 3<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n12<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          08-\u56fe8 How Long Does It Take<\/h3>\n
          Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. Each case starts with a line containing two positive integers\u00a0N\u00a0(\u2264100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to\u00a0N\u22121), and\u00a0M, the number of activities. Then\u00a0M\u00a0lines follow, each gives the description of an activity. For the\u00a0i-th activity, three non-negative numbers are given:\u00a0S[i],\u00a0E[i], and\u00a0L[i], where\u00a0S[i]\u00a0is the index of the starting check point,\u00a0E[i]\u00a0of the ending check point, and\u00a0L[i]\u00a0the lasting time of the activity. The numbers in a line are separated by a space.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".<\/p>\n
          Sample Input 1:<\/strong>
          \n9 12
          \n0 1 6
          \n0 2 4
          \n0 3 5
          \n1 4 1
          \n2 4 1
          \n3 5 2
          \n5 4 0
          \n4 6 9
          \n4 7 7
          \n5 7 4
          \n6 8 2
          \n7 8 4<\/p>\n
          Sample Output 1:<\/strong>
          \n18<\/p>\n
          Sample Input 2:<\/strong>
          \n4 5
          \n0 1 1
          \n0 2 2
          \n2 1 3
          \n1 3 4
          \n3 2 5<\/p>\n
          Sample Output 2:<\/strong>
          \nImpossible<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  08-\u56fe8.\u9700\u8981\u591a\u957f\u65f6\u95f4<\/h4>\n
          \u8003\u8651\u5230\u9879\u76ee\u6240\u6709\u6d3b\u52a8\u4e4b\u95f4\u7684\u5173\u7cfb\uff0c\u60a8\u5e94\u8be5\u627e\u5230\u9879\u76ee\u7684\u6700\u65e9\u5b8c\u6210\u65f6\u95f4\u3002<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u6bcf\u79cd\u60c5\u51b5\u90fd\u4ece\u5305\u542b\u4e24\u4e2a\u6b63\u6574\u6570N\u7684\u884c\u5f00\u59cb(\u2264100\uff09\u3001\u6d3b\u52a8\u68c0\u67e5\u70b9\u7684\u6570\u91cf\uff08\u56e0\u6b64\u5047\u8bbe\u68c0\u67e5\u70b9\u7684\u7f16\u53f7\u4ece0\u5230N\u22121\uff09 \u548cM\uff0c\u6d3b\u52a8\u7684\u6570\u91cf\u3002\u63a5\u4e0b\u6765\u662fM\u884c\uff0c\u6bcf\u884c\u90fd\u7ed9\u51fa\u4e86\u4e00\u9879\u6d3b\u52a8\u7684\u63cf\u8ff0\u3002\u5bf9\u4e8e\u7b2ci\u4e2a\u6d3b\u52a8\uff0c\u7ed9\u51fa\u4e86\u4e09\u4e2a\u975e\u8d1f\u6570\uff1aS[i]\u3001E[i]\u548cL[i]\uff0c\u5176\u4e2dS[i]\u662f\u5f00\u59cb\u68c0\u67e5\u70b9\u7684\u7d22\u5f15\uff0cE[i]\uff1a\u7ed3\u675f\u68c0\u67e5\u70b9\uff0cL[i]\u4e3a\u6d3b\u52a8\u7684\u6301\u7eed\u65f6\u95f4\u3002\u4e00\u884c\u4e2d\u7684\u6570\u5b57\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5982\u679c\u53ef\u4ee5\u5b89\u6392\uff0c\u5219\u5728\u4e00\u884c\u4e2d\u6253\u5370\u5176\u6700\u65e9\u5b8c\u6210\u65f6\u95f4\uff1b\u6216\u8005\u7b80\u5355\u5730\u8f93\u51fa\u201c\u4e0d\u53ef\u80fd\u201d\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n9 12
          \n0 1 6
          \n0 2 4
          \n0 3 5
          \n1 4 1
          \n2 4 1
          \n3 5 2
          \n5 4 0
          \n4 6 9
          \n4 7 7
          \n5 7 4
          \n6 8 2
          \n7 8 4<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n18<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n4 5
          \n0 1 1
          \n0 2 2
          \n2 1 3
          \n1 3 4
          \n3 2 5<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n\u4e0d\u53ef\u80fd\u7684<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          08-\u56fe9 \u5173\u952e\u6d3b\u52a8<\/h3>\n
          \u5047\u5b9a\u4e00\u4e2a\u5de5\u7a0b\u9879\u76ee\u7531\u4e00\u7ec4\u5b50\u4efb\u52a1\u6784\u6210\uff0c\u5b50\u4efb\u52a1\u4e4b\u95f4\u6709\u7684\u53ef\u4ee5\u5e76\u884c\u6267\u884c\uff0c\u6709\u7684\u5fc5\u987b\u5728\u5b8c\u6210\u4e86\u5176\u5b83\u4e00\u4e9b\u5b50\u4efb\u52a1\u540e\u624d\u80fd\u6267\u884c\u3002\u201c\u4efb\u52a1\u8c03\u5ea6\u201d\u5305\u62ec\u4e00\u7ec4\u5b50\u4efb\u52a1\u3001\u4ee5\u53ca\u6bcf\u4e2a\u5b50\u4efb\u52a1\u53ef\u4ee5\u6267\u884c\u6240\u4f9d\u8d56\u7684\u5b50\u4efb\u52a1\u96c6\u3002
          \n\u6bd4\u5982\u5b8c\u6210\u4e00\u4e2a\u4e13\u4e1a\u7684\u6240\u6709\u8bfe\u7a0b\u5b66\u4e60\u548c\u6bd5\u4e1a\u8bbe\u8ba1\u53ef\u4ee5\u770b\u6210\u4e00\u4e2a\u672c\u79d1\u751f\u8981\u5b8c\u6210\u7684\u4e00\u9879\u5de5\u7a0b\uff0c\u5404\u95e8\u8bfe\u7a0b\u53ef\u4ee5\u770b\u6210\u662f\u5b50\u4efb\u52a1\u3002\u6709\u4e9b\u8bfe\u7a0b\u53ef\u4ee5\u540c\u65f6\u5f00\u8bbe\uff0c\u6bd4\u5982\u82f1\u8bed\u548cC\u7a0b\u5e8f\u8bbe\u8ba1\uff0c\u5b83\u4eec\u6ca1\u6709\u5fc5\u987b\u5148\u4fee\u54ea\u95e8\u7684\u7ea6\u675f\uff1b\u6709\u4e9b\u8bfe\u7a0b\u5219\u4e0d\u53ef\u4ee5\u540c\u65f6\u5f00\u8bbe\uff0c\u56e0\u4e3a\u5b83\u4eec\u6709\u5148\u540e\u7684\u4f9d\u8d56\u5173\u7cfb\uff0c\u6bd4\u5982C\u7a0b\u5e8f\u8bbe\u8ba1\u548c\u6570\u636e\u7ed3\u6784\u4e24\u95e8\u8bfe\uff0c\u5fc5\u987b\u5148\u5b66\u4e60\u524d\u8005\u3002
          \n\u4f46\u662f\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u5bf9\u4e00\u7ec4\u5b50\u4efb\u52a1\uff0c\u5e76\u4e0d\u662f\u4efb\u610f\u7684\u4efb\u52a1\u8c03\u5ea6\u90fd\u662f\u4e00\u4e2a\u53ef\u884c\u7684\u65b9\u6848\u3002\u6bd4\u5982\u65b9\u6848\u4e2d\u5b58\u5728\u201c\u5b50\u4efb\u52a1A\u4f9d\u8d56\u4e8e\u5b50\u4efb\u52a1B\uff0c\u5b50\u4efb\u52a1B\u4f9d\u8d56\u4e8e\u5b50\u4efb\u52a1C\uff0c\u5b50\u4efb\u52a1C\u53c8\u4f9d\u8d56\u4e8e\u5b50\u4efb\u52a1A\u201d\uff0c\u90a3\u4e48\u8fd9\u4e09\u4e2a\u4efb\u52a1\u54ea\u4e2a\u90fd\u4e0d\u80fd\u5148\u6267\u884c\uff0c\u8fd9\u5c31\u662f\u4e00\u4e2a\u4e0d\u53ef\u884c\u7684\u65b9\u6848\u3002
          \n\u4efb\u52a1\u8c03\u5ea6\u95ee\u9898\u4e2d\uff0c\u5982\u679c\u8fd8\u7ed9\u51fa\u4e86\u5b8c\u6210\u6bcf\u4e2a\u5b50\u4efb\u52a1\u9700\u8981\u7684\u65f6\u95f4\uff0c\u5219\u6211\u4eec\u53ef\u4ee5\u7b97\u51fa\u5b8c\u6210\u6574\u4e2a\u5de5\u7a0b\u9700\u8981\u7684\u6700\u77ed\u65f6\u95f4\u3002\u5728\u8fd9\u4e9b\u5b50\u4efb\u52a1\u4e2d\uff0c\u6709\u4e9b\u4efb\u52a1\u5373\u4f7f\u63a8\u8fdf\u51e0\u5929\u5b8c\u6210\uff0c\u4e5f\u4e0d\u4f1a\u5f71\u54cd\u5168\u5c40\u7684\u5de5\u671f\uff1b\u4f46\u662f\u6709\u4e9b\u4efb\u52a1\u5fc5\u987b\u51c6\u65f6\u5b8c\u6210\uff0c\u5426\u5219\u6574\u4e2a\u9879\u76ee\u7684\u5de5\u671f\u5c31\u8981\u56e0\u6b64\u5ef6\u8bef\uff0c\u8fd9\u79cd\u4efb\u52a1\u5c31\u53eb\u201c\u5173\u952e\u6d3b\u52a8\u201d\u3002
          \n\u8bf7\u7f16\u5199\u7a0b\u5e8f\u5224\u5b9a\u4e00\u4e2a\u7ed9\u5b9a\u7684\u5de5\u7a0b\u9879\u76ee\u7684\u4efb\u52a1\u8c03\u5ea6\u662f\u5426\u53ef\u884c\uff1b\u5982\u679c\u8be5\u8c03\u5ea6\u65b9\u6848\u53ef\u884c\uff0c\u5219\u8ba1\u7b97\u5b8c\u6210\u6574\u4e2a\u5de5\u7a0b\u9879\u76ee\u9700\u8981\u7684\u6700\u77ed\u65f6\u95f4\uff0c\u5e76\u8f93\u51fa\u6240\u6709\u7684\u5173\u952e\u6d3b\u52a8\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u8f93\u5165\u7b2c1\u884c\u7ed9\u51fa\u4e24\u4e2a\u6b63\u6574\u6570N(\u2264100)\u548cM\uff0c\u5176\u4e2dN\u662f\u4efb\u52a1\u4ea4\u63a5\u70b9\uff08\u5373\u8854\u63a5\u76f8\u4e92\u4f9d\u8d56\u7684\u4e24\u4e2a\u5b50\u4efb\u52a1\u7684\u8282\u70b9\uff0c\u4f8b\u5982\uff1a\u82e5\u4efb\u52a12\u8981\u5728\u4efb\u52a11\u5b8c\u6210\u540e\u624d\u5f00\u59cb\uff0c\u5219\u4e24\u4efb\u52a1\u4e4b\u95f4\u5fc5\u6709\u4e00\u4e2a\u4ea4\u63a5\u70b9\uff09\u7684\u6570\u91cf\u3002\u4ea4\u63a5\u70b9\u63091~N\u7f16\u53f7\uff0cM\u662f\u5b50\u4efb\u52a1\u7684\u6570\u91cf\uff0c\u4f9d\u6b21\u7f16\u53f7\u4e3a1~M\u3002\u968f\u540eM\u884c\uff0c\u6bcf\u884c\u7ed9\u51fa\u4e863\u4e2a\u6b63\u6574\u6570\uff0c\u5206\u522b\u662f\u8be5\u4efb\u52a1\u5f00\u59cb\u548c\u5b8c\u6210\u6d89\u53ca\u7684\u4ea4\u63a5\u70b9\u7f16\u53f7\u4ee5\u53ca\u8be5\u4efb\u52a1\u6240\u9700\u7684\u65f6\u95f4\uff0c\u6574\u6570\u95f4\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u5982\u679c\u4efb\u52a1\u8c03\u5ea6\u4e0d\u53ef\u884c\uff0c\u5219\u8f93\u51fa0\uff1b\u5426\u5219\u7b2c1\u884c\u8f93\u51fa\u5b8c\u6210\u6574\u4e2a\u5de5\u7a0b\u9879\u76ee\u9700\u8981\u7684\u65f6\u95f4\uff0c\u7b2c2\u884c\u5f00\u59cb\u8f93\u51fa\u6240\u6709\u5173\u952e\u6d3b\u52a8\uff0c\u6bcf\u4e2a\u5173\u952e\u6d3b\u52a8\u5360\u4e00\u884c\uff0c\u6309\u683c\u5f0f\u201cV->W\u201d\u8f93\u51fa\uff0c\u5176\u4e2dV\u548cW\u4e3a\u8be5\u4efb\u52a1\u5f00\u59cb\u548c\u5b8c\u6210\u6d89\u53ca\u7684\u4ea4\u63a5\u70b9\u7f16\u53f7\u3002\u5173\u952e\u6d3b\u52a8\u8f93\u51fa\u7684\u987a\u5e8f\u89c4\u5219\u662f\uff1a\u4efb\u52a1\u5f00\u59cb\u7684\u4ea4\u63a5\u70b9\u7f16\u53f7\u5c0f\u8005\u4f18\u5148\uff0c\u8d77\u70b9\u7f16\u53f7\u76f8\u540c\u65f6\uff0c\u4e0e\u8f93\u5165\u65f6\u4efb\u52a1\u7684\u987a\u5e8f\u76f8\u53cd\u3002<\/p>\n
          \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n7 8
          \n1 2 4
          \n1 3 3
          \n2 4 5
          \n3 4 3
          \n4 5 1
          \n4 6 6
          \n5 7 5
          \n6 7 2<\/p>\n
          \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n17
          \n1->2
          \n2->4
          \n4->6
          \n6->7<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          09-\u6392\u5e8f1 \u6392\u5e8f<\/h3>\n
          \u7ed9\u5b9aN\u4e2a\uff08\u957f\u6574\u578b\u8303\u56f4\u5185\u7684\uff09\u6574\u6570\uff0c\u8981\u6c42\u8f93\u51fa\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\u540e\u7684\u7ed3\u679c\u3002
          \n\u672c\u9898\u65e8\u5728\u6d4b\u8bd5\u5404\u79cd\u4e0d\u540c\u7684\u6392\u5e8f\u7b97\u6cd5\u5728\u5404\u79cd\u6570\u636e\u60c5\u51b5\u4e0b\u7684\u8868\u73b0\u3002\u5404\u7ec4\u6d4b\u8bd5\u6570\u636e\u7279\u70b9\u5982\u4e0b\uff1a
          \n\u00b7  \u6570\u636e1\uff1a\u53ea\u67091\u4e2a\u5143\u7d20\uff1b
          \n\u00b7  \u6570\u636e2\uff1a11\u4e2a\u4e0d\u76f8\u540c\u7684\u6574\u6570\uff0c\u6d4b\u8bd5\u57fa\u672c\u6b63\u786e\u6027\uff1b
          \n\u00b7  \u6570\u636e3\uff1a103\u4e2a\u968f\u673a\u6574\u6570\uff1b
          \n\u00b7  \u6570\u636e4\uff1a104\u4e2a\u968f\u673a\u6574\u6570\uff1b
          \n\u00b7  \u6570\u636e5\uff1a105\u4e2a\u968f\u673a\u6574\u6570\uff1b
          \n\u00b7  \u6570\u636e6\uff1a105\u4e2a\u987a\u5e8f\u6574\u6570\uff1b
          \n\u00b7  \u6570\u636e7\uff1a105\u4e2a\u9006\u5e8f\u6574\u6570\uff1b
          \n\u00b7  \u6570\u636e8\uff1a105\u4e2a\u57fa\u672c\u6709\u5e8f\u7684\u6574\u6570\uff1b
          \n\u00b7  \u6570\u636e9\uff1a105\u4e2a\u968f\u673a\u6b63\u6574\u6570\uff0c\u6bcf\u4e2a\u6570\u5b57\u4e0d\u8d85\u8fc71000\u3002<\/p>\n
          \u8f93\u5165\u683c\u5f0f:<\/strong>
          \n\u00b7  \u8f93\u5165\u7b2c\u4e00\u884c\u7ed9\u51fa\u6b63\u6574\u6570N\uff08\u2264105\uff09\uff0c\u968f\u540e\u4e00\u884c\u7ed9\u51faN\u4e2a\uff08\u957f\u6574\u578b\u8303\u56f4\u5185\u7684\uff09\u6574\u6570\uff0c\u5176\u95f4\u4ee5\u7a7a\u683c\u5206\u9694\u3002
          \n\u00b7  \u8f93\u51fa\u683c\u5f0f:<\/strong>
          \n\u00b7  \u5728\u4e00\u884c\u4e2d\u8f93\u51fa\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\u540e\u7684\u7ed3\u679c\uff0c\u6570\u5b57\u95f4\u4ee51\u4e2a\u7a7a\u683c\u5206\u9694\uff0c\u884c\u672b\u4e0d\u5f97\u6709\u591a\u4f59\u7a7a\u683c\u3002
          \n\u00b7  \u8f93\u5165\u6837\u4f8b:<\/strong>
          \n\u00b7  11
          \n4 981 10 -17 0 -20 29 50 8 43 -5
          \n\u00b7  \u8f93\u51fa\u6837\u4f8b:<\/strong>
          \n\u00b7  -20 -17 -5 0 4 8 10 29 43 50 981
          \n\u00b7  \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n10000 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          09-\u6392\u5e8f2 Insert or Merge<\/h3>\n
          According to Wikipedia:
          \nInsertion sort\u00a0iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
          \nMerge sort\u00a0works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.
          \nNow given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. For each case, the first line gives a positive integer\u00a0N\u00a0(\u2264100). Then in the next line,\u00a0N\u00a0integers are given as the initial sequence. The last line contains the partially sorted sequence of the\u00a0N\u00a0numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, print in the first line either "Insertion Sort" or "Merge Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.<\/p>\n
          Sample Input 1:<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 6 0
          \n1 2 3 7 8 5 9 4 6 0<\/p>\n
          Sample Output 1:<\/strong>
          \nInsertion Sort
          \n1 2 3 5 7 8 9 4 6 0<\/p>\n
          Sample Input 2:<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 0 6
          \n1 3 2 8 5 7 4 9 0 6<\/p>\n
          Sample Output 2:<\/strong>
          \nMerge Sort
          \n1 2 3 8 4 5 7 9 0 6<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  09-\u6392\u5e8f2.\u63d2\u5165\u6216\u5408\u5e76<\/h4>\n
          \u6839\u636e\u7ef4\u57fa\u767e\u79d1\uff1a
          \n\u63d2\u5165\u6392\u5e8f\u8fed\u4ee3\uff0c\u6bcf\u6b21\u91cd\u590d\u4f7f\u7528\u4e00\u4e2a\u8f93\u5165\u5143\u7d20\uff0c\u5e76\u589e\u957f\u6392\u5e8f\u8f93\u51fa\u5217\u8868\u3002\u5728\u6bcf\u6b21\u8fed\u4ee3\u4e2d\uff0c\u63d2\u5165\u6392\u5e8f\u4ece\u8f93\u5165\u6570\u636e\u4e2d\u5220\u9664\u4e00\u4e2a\u5143\u7d20\uff0c\u5728\u6392\u5e8f\u5217\u8868\u4e2d\u627e\u5230\u5b83\u6240\u5c5e\u7684\u4f4d\u7f6e\uff0c\u5e76\u5c06\u5176\u63d2\u5165\u5176\u4e2d\u3002\u5b83\u4f1a\u91cd\u590d\uff0c\u76f4\u5230\u6ca1\u6709\u8f93\u5165\u5143\u7d20\u4fdd\u7559\u3002
          \n\u5408\u5e76\u6392\u5e8f\u7684\u5de5\u4f5c\u539f\u7406\u5982\u4e0b\uff1a\u5c06\u672a\u6392\u5e8f\u7684\u5217\u8868\u5212\u5206\u4e3aN\u4e2a\u5b50\u5217\u8868\uff0c\u6bcf\u4e2a\u5b50\u5217\u8868\u5305\u542b1\u4e2a\u5143\u7d20\uff081\u4e2a\u5143\u7d20\u7684\u5217\u8868\u88ab\u89c6\u4e3a\u5df2\u6392\u5e8f\uff09\u3002\u7136\u540e\u91cd\u590d\u5408\u5e76\u4e24\u4e2a\u76f8\u90bb\u7684\u5b50\u5217\u8868\u4ee5\u4ea7\u751f\u65b0\u7684\u6392\u5e8f\u5b50\u5217\u8868\uff0c\u76f4\u5230\u53ea\u5269\u4e0b1\u4e2a\u5b50\u5217\u8868\u3002
          \n\u73b0\u5728\uff0c\u7ed9\u5b9a\u6574\u6570\u7684\u521d\u59cb\u5e8f\u5217\uff0c\u518d\u52a0\u4e0a\u4e00\u4e2a\u5e8f\u5217\uff0c\u5b83\u662f\u67d0\u79cd\u6392\u5e8f\u65b9\u6cd5\u591a\u6b21\u8fed\u4ee3\u7684\u7ed3\u679c\uff0c\u4f60\u80fd\u544a\u8bc9\u6211\u4eec\u4f7f\u7528\u7684\u662f\u54ea\u79cd\u6392\u5e8f\u65b9\u6cd5\u5417\uff1f<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570N(\u2264100). \u7136\u540e\u5728\u4e0b\u4e00\u884c\u4e2d\uff0c\u7ed9\u51faN\u4e2a\u6574\u6570\u4f5c\u4e3a\u521d\u59cb\u5e8f\u5217\u3002\u6700\u540e\u4e00\u884c\u5305\u542bN\u4e2a\u6570\u5b57\u7684\u90e8\u5206\u6392\u5e8f\u5e8f\u5217\u3002\u5047\u8bbe\u76ee\u6807\u5e8f\u5217\u603b\u662f\u4e0a\u5347\u7684\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5728\u7b2c\u4e00\u884c\u4e2d\u6253\u5370\u201c\u63d2\u5165\u6392\u5e8f\u201d\u6216\u201c\u5408\u5e76\u6392\u5e8f\u201d\uff0c\u4ee5\u6307\u793a\u7528\u4e8e\u83b7\u5f97\u90e8\u5206\u7ed3\u679c\u7684\u65b9\u6cd5\u3002\u7136\u540e\u518d\u8fd0\u884c\u6b64\u65b9\u6cd5\u8fdb\u884c\u4e00\u6b21\u8fed\u4ee3\uff0c\u5e76\u5728\u7b2c\u4e8c\u884c\u4e2d\u8f93\u51fa\u7ed3\u679c\u5e8f\u5217\u3002\u4fdd\u8bc1\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u7684\u7b54\u6848\u90fd\u662f\u552f\u4e00\u7684\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u5fc5\u987b\u7528\u7a7a\u683c\u5206\u9694\uff0c\u5e76\u4e14\u5728\u884c\u5c3e\u4e0d\u5f97\u6709\u989d\u5916\u7684\u7a7a\u683c\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 6 0
          \n1 2 3 7 8 5 9 4 6 0<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n\u63d2\u5165\u6392\u5e8f
          \n1 2 3 5 7 8 9 4 6 0<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 0 6
          \n1 3 2 8 5 7 4 9 0 6<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n\u5408\u5e76\u6392\u5e8f
          \n1 2 3 8 4 5 7 9 0 6<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          09-\u6392\u5e8f3 Insertion or Heap Sort<\/h3>\n
          According to Wikipedia:
          \nInsertion sort\u00a0iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
          \nHeap sort\u00a0divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.
          \nNow given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?<\/p>\n
          Input Specification:<\/strong>
          \nEach input file contains one test case. For each case, the first line gives a positive integer\u00a0N\u00a0(\u2264100). Then in the next line,\u00a0N\u00a0integers are given as the initial sequence. The last line contains the partially sorted sequence of the\u00a0N\u00a0numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.<\/p>\n
          Output Specification:<\/strong>
          \nFor each test case, print in the first line either "Insertion Sort" or "Heap Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.<\/p>\n
          Sample Input 1:<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 6 0
          \n1 2 3 7 8 5 9 4 6 0<\/p>\n
          Sample Output 1:<\/strong>
          \nInsertion Sort
          \n1 2 3 5 7 8 9 4 6 0<\/p>\n
          Sample Input 2:<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 6 0
          \n6 4 5 1 0 3 2 7 8 9<\/p>\n
          Sample Output 2:<\/strong>
          \nHeap Sort
          \n5 4 3 1 0 2 6 7 8 9<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16 KB
          \n\u65f6\u95f4\u9650\u5236
          \n400 ms
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n
          \u7ffb\u8bd1  09-\u6392\u5e8f3.\u63d2\u5165\u6216\u5806\u6392\u5e8f<\/h4>\n
          \u6839\u636e\u7ef4\u57fa\u767e\u79d1\uff1a
          \n\u63d2\u5165\u6392\u5e8f\u8fed\u4ee3\uff0c\u6bcf\u6b21\u91cd\u590d\u4f7f\u7528\u4e00\u4e2a\u8f93\u5165\u5143\u7d20\uff0c\u5e76\u589e\u957f\u6392\u5e8f\u8f93\u51fa\u5217\u8868\u3002\u5728\u6bcf\u6b21\u8fed\u4ee3\u4e2d\uff0c\u63d2\u5165\u6392\u5e8f\u4ece\u8f93\u5165\u6570\u636e\u4e2d\u5220\u9664\u4e00\u4e2a\u5143\u7d20\uff0c\u5728\u6392\u5e8f\u5217\u8868\u4e2d\u627e\u5230\u5b83\u6240\u5c5e\u7684\u4f4d\u7f6e\uff0c\u5e76\u5c06\u5176\u63d2\u5165\u5176\u4e2d\u3002\u5b83\u4f1a\u91cd\u590d\uff0c\u76f4\u5230\u6ca1\u6709\u8f93\u5165\u5143\u7d20\u4fdd\u7559\u3002
          \n\u5806\u6392\u5e8f\u5c06\u5176\u8f93\u5165\u5206\u4e3a\u5df2\u6392\u5e8f\u533a\u57df\u548c\u672a\u6392\u5e8f\u533a\u57df\uff0c\u5b83\u901a\u8fc7\u63d0\u53d6\u6700\u5927\u5143\u7d20\u5e76\u5c06\u5176\u79fb\u52a8\u5230\u5df2\u6392\u5e8f\u533a\u57df\u6765\u8fed\u4ee3\u6536\u7f29\u672a\u6392\u5e8f\u533a\u57df\u3002\u5b83\u6d89\u53ca\u4f7f\u7528\u5806\u6570\u636e\u7ed3\u6784\u800c\u4e0d\u662f\u7ebf\u6027\u65f6\u95f4\u641c\u7d22\u6765\u67e5\u627e\u6700\u5927\u503c\u3002
          \n\u73b0\u5728\uff0c\u7ed9\u5b9a\u6574\u6570\u7684\u521d\u59cb\u5e8f\u5217\uff0c\u518d\u52a0\u4e0a\u4e00\u4e2a\u5e8f\u5217\uff0c\u5b83\u662f\u67d0\u79cd\u6392\u5e8f\u65b9\u6cd5\u591a\u6b21\u8fed\u4ee3\u7684\u7ed3\u679c\uff0c\u4f60\u80fd\u544a\u8bc9\u6211\u4eec\u4f7f\u7528\u7684\u662f\u54ea\u79cd\u6392\u5e8f\u65b9\u6cd5\u5417\uff1f<\/p>\n
          \u8f93\u5165\u89c4\u683c\uff1a<\/strong>
          \n\u6bcf\u4e2a\u8f93\u5165\u6587\u4ef6\u5305\u542b\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u3002\u5bf9\u4e8e\u6bcf\u79cd\u60c5\u51b5\uff0c\u7b2c\u4e00\u884c\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570N(\u2264100). \u7136\u540e\u5728\u4e0b\u4e00\u884c\u4e2d\uff0c\u7ed9\u51faN\u4e2a\u6574\u6570\u4f5c\u4e3a\u521d\u59cb\u5e8f\u5217\u3002\u6700\u540e\u4e00\u884c\u5305\u542bN\u4e2a\u6570\u5b57\u7684\u90e8\u5206\u6392\u5e8f\u5e8f\u5217\u3002\u5047\u8bbe\u76ee\u6807\u5e8f\u5217\u603b\u662f\u4e0a\u5347\u7684\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u7528\u7a7a\u683c\u5206\u9694\u3002<\/p>\n
          \u8f93\u51fa\u89c4\u683c\uff1a<\/strong>
          \n\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5728\u7b2c\u4e00\u884c\u4e2d\u6253\u5370\u201c\u63d2\u5165\u6392\u5e8f\u201d\u6216\u201c\u5806\u6392\u5e8f\u201d\uff0c\u4ee5\u6307\u793a\u7528\u4e8e\u83b7\u5f97\u90e8\u5206\u7ed3\u679c\u7684\u65b9\u6cd5\u3002\u7136\u540e\u518d\u8fd0\u884c\u6b64\u65b9\u6cd5\u8fdb\u884c\u4e00\u6b21\u8fed\u4ee3\uff0c\u5e76\u5728\u7b2c\u4e8c\u884c\u4e2d\u8f93\u51fa\u7ed3\u679c\u5e8f\u5217\u3002\u4fdd\u8bc1\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u7684\u7b54\u6848\u90fd\u662f\u552f\u4e00\u7684\u3002\u4e00\u884c\u4e2d\u7684\u6240\u6709\u6570\u5b57\u90fd\u5fc5\u987b\u7528\u7a7a\u683c\u5206\u9694\uff0c\u5e76\u4e14\u5728\u884c\u5c3e\u4e0d\u5f97\u6709\u989d\u5916\u7684\u7a7a\u683c\u3002<\/p>\n
          \u6837\u672c\u8f93\u51651\uff1a<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 6 0
          \n1 2 3 7 8 5 9 4 6 0<\/p>\n
          \u6837\u672c\u8f93\u51fa1\uff1a<\/strong>
          \n\u63d2\u5165\u6392\u5e8f
          \n1 2 3 5 7 8 9 4 6 0<\/p>\n
          \u6837\u672c\u8f93\u51652\uff1a<\/strong>
          \n10
          \n3 1 2 8 7 5 9 4 6 0
          \n6 4 5 1 0 3 2 7 8 9<\/p>\n
          \u6837\u672c\u8f93\u51fa2\uff1a<\/strong>
          \n\u5806\u6392\u5e8f
          \n5 4 3 1 0 2 6 7 8 9<\/p>\n
          \u4ee3\u7801\u957f\u5ea6\u9650\u5236
          \n16kb
          \n\u65f6\u95f4\u9650\u5236
          \n400\u6beb\u79d2
          \n\u5185\u5b58\u9650\u5236
          \n64MB<\/p>\n","protected":false},"excerpt":{"rendered":"
          \u4e2d\u56fd\u5927\u5b66MOOC-\u9648\u8d8a\u3001\u4f55\u94a6\u94ed-\u6570\u636e\u7ed3\u6784-2022 …<\/p>\n","protected":false},"author":1,"featured_media":616,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,11],"tags":[17,27],"class_list":["post-598","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-4","category-11","tag-c","tag-27"],"_links":{"self":[{"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=\/wp\/v2\/posts\/598","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=598"}],"version-history":[{"count":0,"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=\/wp\/v2\/posts\/598\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=598"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.xuanchenbin.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}