{"rsdb":{"rid":"155909","subhead":"","postdate":"0","aid":"117032","fid":"45","uid":"1","topic":"1","content":"
\n
\n

Problem A: \u6c42\u96c6\u5408\u7684\u4ea4\u5e76\u8865\u96c6<\/h2> Time Limit: 1 SecMemory Limit: 4 MB\n
Submit: 6817Solved: 1972\n
[Submit][Status][Web Board]\n <\/center> \n

Description<\/h2> \n

\u4efb\u610f\u7ed9\u5b9a\u4e24\u4e2a\u5305\u542b1-30000\u4e2a\u5143\u7d20\u7684\u96c6\u5408A,B\uff08\u96c6\u5408\u4e2d\u5143\u7d20\u7c7b\u578b\u4e3a\u4efb\u610f\u6574\u578b\u6570\uff0c\u4e14\u4e25\u683c\u9012\u589e\u6392\u5217\uff09\uff0c\u6c42A\u4ea4B\u3001A\u5e76B\u3001A-B\u548cB-A\u96c6\u5408\u3002 <\/p>\n

Input<\/h2> \n

\u8f93\u5165\u7b2c\u4e00\u884c\u4e3a\u6d4b\u8bd5\u6570\u636e\u7ec4\u6570\u3002\u6bcf\u7ec4\u6d4b\u8bd5\u6570\u636e\u4e24\u884c\uff0c\u5206\u522b\u4e3a\u96c6\u5408A\u3001B\u3002\u6bcf\u884c\u7b2c\u4e00\u4e2a\u6570n\uff081<=n<=30000\uff09\u4e3a\u5143\u7d20\u6570\u91cf\uff0c\u540e\u9762\u6709n\u4e2a\u4e25\u683c\u9012\u589e\u7684\u7edd\u5bf9\u503c\u5c0f\u4e8e2^31\u4ee3\u8868\u96c6\u5408\u4e2d\u5305\u542b\u7684\u6570\u3002 <\/p>\n

Output<\/h2> \n

\u5bf9\u6bcf\u7ec4\u6d4b\u8bd5\u6570\u636e\u8f93\u51fa5\u884c\uff0c\u7b2c1\u884c\u4e3a\u6570\u636e\u7ec4\u6570\uff0c\u540e4\u884c\u5206\u522b\u4e3a\u6309\u5347\u5e8f\u8f93\u51fa\u4e24\u4e2a\u96c6\u5408\u7684A\u4ea4B\u3001A\u5e76B\u3001A-B\u548cB-A\u96c6\u5408\u3002\u683c\u5f0f\u89c1\u6837\u4f8b\u3002 <\/p>\n

Sample Input<\/h2> \n
\r\n1\r\n3 1 2 5\r\n4 2 3 5 8\r\n<\/pre> \n 

Sample Output<\/h2> \n
\r\nCase #1:\r\n2 5\r\n1 2 3 5 8\r\n1\r\n3 8\r\n<\/pre> \n 

HINT<\/h2> \n

\u8003\u5bdf\u77e5\u8bc6\u70b9\uff1a\u6709\u5e8f\u8868\u5408\u5e76\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6O(n)<\/p> \n

\u89e3\u9898\u601d\u8def\uff1a1\uff09\u5206\u6790 \u6570\u636e\/\u5143\u7d20 \u9700\u8981\u7528\u4ec0\u4e48\u7ed3\u6784\u50a8\u5b58 2\uff09\u8bbe\u8ba1\u7b97\u6cd5\u5b9e\u73b0<\/p> \n

\r\n#include      \r\n#include      \r\n#include      \r\n#include      \r\n#define LIST_INIT_SIZE 100     \r\n#define LISTINCREMENT 10     \r\n#define OK 1     \r\n#define OVERFLOW -1     \r\n#define ERROR 0     \r\n    \r\n        \r\ntypedef int Status;     \r\n        \r\ntypedef int ElemType;     \r\n        \r\ntypedef struct SqList{     \r\n    ElemType * elem;   \/\/\u6570\u7ec4\u9996\u5730\u5740     \r\n    int listSize;  \/\/\u8868\u5bb9\u91cf\uff1b\u5f53\u524d\u8868\u7684\u5bb9\u91cf     \r\n    int length;  \/\/\u8868\u957f\uff0c\u4ee3\u8868\u5f53\u524d\u6570\u7ec4\u4e2d\u6709\u6548\u5143\u7d20\u7684\u4e2a\u6570     \r\n}SqList;     \r\n        \r\n\/\/ \u4e0b\u9762\u5b9e\u73b0nitList\u64cd\u4f5c\uff0c\u5373\u521d\u59cb\u5316\u4e00\u4e2a\u7a7a\u7684\u7ebf\u6027\u8868     \r\nStatus InitList_Sq(SqList &L)     \r\n{     \r\n    L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));     \r\n    \/\/malloc\u7684\u8fd4\u56de\u503c\u7c7b\u578b\u662fvoid *;     \r\n    \/\/\u4f7f\u7528\u65f6\u8981\u53ca\u65f6\u8fdb\u884c\u5f3a\u5236\u7c7b\u578b\u8f6c\u6362     \r\n    if(!L.elem)     \r\n        exit(OVERFLOW);     \r\n    L.listSize=LIST_INIT_SIZE;     \r\n    L.length=0;     \r\n    return OK;     \r\n}     \r\n      \r\n    \r\n          \r\nStatus CreateList(SqList &La,int na){      \r\n    for(int i = 1;i<=na;++i){      \r\n        ElemType e;      \r\n\/\/      printf(\"\u8bf7\u8f93\u5165\u7b2c%d\u4e2a\u5143\u7d20\",i);      \r\n        scanf(\"%d\",&e);      \r\n   if(La.length >= La.listSize)   {      \r\n        La.elem=(ElemType *)realloc(La.elem,(La.listSize+LISTINCREMENT)*sizeof(ElemType));      \r\n        La.listSize += LISTINCREMENT;      \r\n    }      \r\n        La.elem[i-1]=e;      \r\n        La.length++;      \r\n    }      \r\n    return OK;      \r\n}        \r\n  \r\n        \r\nvoid MergeList_Sq(SqList La,SqList Lb,SqList &Ld,SqList &Le)     \r\n{  \/\/Ld\u662f\u4ea4\uff0cLe\u662f\u8865   \r\n    ElemType* pa = La.elem;     \r\n    ElemType* pb = Lb.elem;     \r\n  \r\n    Ld.length = 0;     \r\n    Ld.listSize = La.length + Lb.length;     \r\n    Ld.elem = (ElemType*)malloc(Ld.listSize*sizeof(ElemType));     \r\n    ElemType* pd = Ld.elem;     \r\n    if(!Ld.elem)     \r\n        exit(OVERFLOW);     \r\n        \r\n    Le.length = 0;     \r\n    Le.listSize = La.length + Lb.length;     \r\n    Le.elem = (ElemType*)malloc(Ld.listSize*sizeof(ElemType));     \r\n    ElemType* pe = Le.elem;      \r\n    if(!Le.elem)     \r\n        exit(OVERFLOW);     \r\n        \r\n        \r\n    ElemType* pa_last = La.elem + La.length -1;     \r\n    ElemType* pb_last = Lb.elem + Lb.length -1;     \r\n    while(pa <= pa_last && pb <= pb_last)     \r\n    {     \r\n        if(*pa <= *pb)     \r\n        {     \r\n            if(*pa == *pb)     \r\n            {     \r\n                *pd++ = *pa;     \r\n                Ld.length++;     \r\n            }     \r\n            else  \r\n            {     \r\n                *pe++ = *pa;      \r\n                Le.length++;     \r\n            }     \r\n           \/\/ *pc++ = *pa++;     \r\n            pa++;   \r\n        }     \r\n        else  \r\n        {     \r\n            *pe++ = *pb;     \r\n            Le.length++;     \r\n          \/\/  *pc++ = *pb++;     \r\n            pb++;   \r\n        }     \r\n    }     \r\n    while(pa <= pa_last)     \r\n    {     \r\n        *pe++ = *pa;     \r\n        Le.length++;     \r\n        \/\/*pc++ = *pa++;     \r\n        pa++;   \r\n    }     \r\n        \r\n    while(pb <= pb_last){     \r\n        *pe++ = *pb;     \r\n        Le.length++;     \r\n       \/\/ *pc++ = *pb++;    \r\n        pb++;   \r\n    }     \r\n}     \r\n        \r\nvoid MergeList_Sq2(SqList La,SqList Lb,SqList &Lc)     \r\n{     \r\n    int i,j;     \r\n    Lc.length = 0;     \r\n    Lc.listSize = La.length + Lb.length;     \r\n    Lc.elem = (ElemType*)malloc(Lc.listSize*sizeof(ElemType));     \r\n    int n = 0;     \r\n    for(i = 0;i < La.length;i++){     \r\n        j = 0;     \r\n        while((j < Lb.length)&&(La.elem[i] != Lb.elem[j])){     \r\n            j++;     \r\n        }     \r\n        if(j == Lb.length){     \r\n            Lc.elem[n] = La.elem[i];     \r\n            ++Lc.length; ++n;    \r\n        }     \r\n    }     \r\n          \r\n}     \r\n        \r\n        \r\nvoid ListPrint_Sq(SqList L){      \r\n    if(L.length==0) {      \r\n        printf(\"\\n\");      \r\n    }      \r\n    else  \r\n    {      \r\n        for(int i=0;i \n<\/dd>","orderid":"0","title":"\u6570\u636e\u7ed3\u6784\uff08\u7ebf\u6027\u7ed3\u6784\u4e60\u9898\uff09Problem A: \u6c42\u96c6\u5408\u7684\u4ea4\u5e76\u8865\u96c6","smalltitle":"","mid":"0","fname":"c\u8bed\u8a00\u7f16\u7a0b","special_id":"0","bak_id":"0","info":"0","hits":"186","pages":"1","comments":"0","posttime":"2016-12-31 08:14:40","list":"1483143280","username":"admin","author":"","copyfrom":"","copyfromurl":"","titlecolor":"","fonttype":"0","titleicon":"0","picurl":"http:\/\/www.cppentry.com\/upload_files\/","ispic":"0","yz":"1","yzer":"","yztime":"0","levels":"0","levelstime":"0","keywords":"\u6570\u636e\u7ed3\u6784<\/A> \u7ebf\u6027<\/A> \u7ed3\u6784<\/A> \u4e60\u9898<\/A> Problem<\/A> \u96c6\u5408<\/A>","jumpurl":"","iframeurl":"","style":"","template":"a:3:{s:4:\"head\";s:0:\"\";s:4:\"foot\";s:0:\"\";s:8:\"bencandy\";s:0:\"\";}","target":"0","ip":"14.17.22.31","lastfid":"0","money":"0","buyuser":"","passwd":"","allowdown":"","allowview":"","editer":"","edittime":"0","begintime":"0","endtime":"0","description":"\u6570\u636e\u7ed3\u6784\uff08\u7ebf\u6027\u7ed3\u6784\u4e60\u9898\uff09Problem A: \u6c42\u96c6\u5408\u7684\u4ea4\u5e76\u8865\u96c6","lastview":"1493206009","digg_num":"0","digg_time":"0","forbidcomment":"0","ifvote":"0","heart":"","htmlname":"","city_id":"0"},"page":"1"}