百度之星Astar2012程序設(shè)計(jì)大賽初賽試題13 / 13百度之星Astar2012程序設(shè)計(jì)大賽初賽試題（第一場(chǎng)）及B題答案比賽說明百度之星初賽：2012年6月2日、6月3日10：00Am12：00Pm本次大賽的初賽的初賽采取在線答題、編譯，離線判題的形式，選手報(bào)名后，可以在6月2日、6月3日任選一天參加比賽，也可選擇兩場(chǎng)都參加。針對(duì)每題，交題后，系統(tǒng)將給出程序編譯是否正確的結(jié)果，但不會(huì)給出程序是否通過全部測(cè)試數(shù)據(jù)的評(píng)價(jià)；當(dāng)場(chǎng)比賽結(jié)束后，所有選手的針對(duì)每題所寫的程序?qū)⒈浑x線評(píng)判，每題根據(jù)程序通過測(cè)試數(shù)據(jù)的數(shù)目計(jì)算得分。每場(chǎng)初賽根據(jù)單場(chǎng)所有題目總分計(jì)算成績(jī)，選出當(dāng)場(chǎng)成績(jī)?cè)谇?00名的選手進(jìn)入復(fù)賽（第一場(chǎng)已經(jīng)進(jìn)入復(fù)賽的選手參加第二場(chǎng)比賽如果再次晉級(jí)，將被不在第二場(chǎng)參與排名）。2012年6月2日，2012百度之星Astar2012程序設(shè)計(jì)大賽初賽打開大幕。這里提供了初賽第一場(chǎng)的題目，供有未進(jìn)初賽和其它有興趣的朋友研究。初賽第一場(chǎng)共4題。分別是度度熊就是要第一個(gè)出場(chǎng)、小小度刷禮品、集合的交與并、輪子上的度度熊。目錄比賽說明 1A：度度熊就是要第一個(gè)出場(chǎng) 2B：小小度刷禮品 5C：集合的交與并6D：輪子上的度度熊6A：度度熊就是要第一個(gè)出場(chǎng)題目描述Baidu年會(huì)安排了一場(chǎng)時(shí)裝秀節(jié)目。N名員工將依次身穿盛裝上臺(tái)表演。表演的順序是通過一種“畫線”抽簽的方式?jīng)Q定的。首先，員工們?cè)谝粡埌准埳袭嬒翹條平行的豎線。在豎線的上方從左到右依次寫下1至N代表員工的編號(hào)；在豎線的下方也從左到右依次寫下1至N代表出場(chǎng)表演的次序。接著，員工們隨意在兩條相鄰的豎線間添加垂直于豎線的橫線段。最后，每位員工的出場(chǎng)順序是按如下規(guī)則決定的：每位員工從自己的編號(hào)開始用手指沿豎線向下劃，每當(dāng)遇到橫線就沿橫線移動(dòng)到相鄰的豎線上去，直到手指到達(dá)豎線下方的出場(chǎng)次序編號(hào)。這時(shí)手指指向的編號(hào)就是該員工的出場(chǎng)次序。例如在下圖的例子中，度度熊將第二名出場(chǎng)，第一名出場(chǎng)的是員工4。員工在畫橫線時(shí)，會(huì)避免在同一位置重復(fù)畫線，并且避免兩條相鄰的橫線連在一起。即下圖所示的情況是不會(huì)出現(xiàn)的：給定一種畫線的方案，員工編號(hào)為K的度度熊想知道自己是不是第一位出場(chǎng)表演的。如果不是，度度熊想知道自己能不能通過增加一條橫線段來使得自己變成第一位出場(chǎng)表演。輸入為了描述方便，我們規(guī)定寫有員工編號(hào)的方向是y軸正方向（即上文中的豎線上方），寫有出場(chǎng)次序的方向是y軸負(fù)方向（即上文中的豎線下方）。豎線沿x軸方向（即上文中從左到右）依次編號(hào)1至N。于是，每條橫線的位置都可以由一個(gè)三元組確定，其中xl, xr是橫線左右兩個(gè)端點(diǎn)所在豎線的編號(hào)，y是橫線的高度。輸入第一行是一個(gè)整數(shù)T(T = 50)，代表測(cè)試數(shù)據(jù)的組數(shù)。每組數(shù)據(jù)的第一行包含三個(gè)整數(shù)N, M,K( 1=N=100, 0=M=1000, 1=K=N)，分別代表參與表演的員工人數(shù)、畫下的橫線數(shù)目以及度度熊的員工編號(hào)。每組數(shù)據(jù)的第2M+1行每行包含3個(gè)整數(shù), xl, xr, y, (1 = xl N, xr = xl + 1, 0 = y = 1,000,000)，描述了一條橫線的位置。輸出對(duì)于每組數(shù)據(jù)輸出一行Yes或者No，表示度度熊能否通過增加一條橫線段來使得自己變成第一位出場(chǎng)表演。如果度度熊已經(jīng)是第一位出場(chǎng)表演，也輸出Yes。注意，盡管輸入數(shù)據(jù)中員工畫的橫線高度都是整數(shù)，但是度度熊可以在任意實(shí)數(shù)高度畫橫線。此外，度度熊和員工一樣，在畫橫線時(shí)需要避免在同一位置重復(fù)畫線，也要避免兩條相鄰的橫線連在一起。樣例輸入24 6 31 2 11 2 41 2 62 3 22 3 53 4 44 0 3樣例輸出YesNo#include #include #include #include using namespace std;struct nodeint l,r,y;line1010;struct node1int t,b,pos;a1010,b1010;bool cmp(node a,node b)return a.y b.y;bool cmp1(node a,node b)return a.y b.y;int main()int t,n,m,k,i,j,pos,afi,bfi,h,ha,hb;bool flag;scanf(%d,&t);while(t-)scanf(%d%d%d,&n,&m,&k);for(i=0;im;i+)scanf(%d%d%d,&linei.l,&linei.r,&linei.y);sort(line,line+m,cmp);pos = k;afi=0;h = aafi.t = 1000000;while(true)flag = false;for(i=0;im;i+)if(linei.l=pos&linei.yh)h = aafi.b = aafi+1.t = linei.y;aafi.pos = pos;pos = linei.r;afi+;flag = true;else if(linei.r=pos&linei.yh)h = aafi.b = aafi+1.t = linei.y;aafi.pos = pos;pos = linei.l;afi+;flag = true;if(flag)break;if(!flag)break;aafi.b = 0;aafi.pos = pos;if(pos=1)printf(Yesn);continue;sort(line,line+m,cmp1);pos = 1;bfi=0;h = bbfi.b = 0;while(true)flag = false;for(i=0;ih)h = bbfi.t = bbfi+1.b = linei.y;bbfi.pos = pos;pos = linei.r;bfi+;flag = true;else if(linei.r=pos&linei.yh)h = bbfi.t = bbfi+1.b = linei.y;bbfi.pos = pos;pos = linei.l;bfi+;flag = true;if(flag)break;if(!flag)break;bbfi.t = 1000000;bbfi.pos = pos;flag = false;for(i=0,j=bfi;i!=afi&j!=0;)if(ai.pos+1=bj.pos|ai.pos-1=bj.pos)flag = true;break;ha = ai.b;hb = bj.b;if(hahb&i!=afi)i+;else if(hbha&j!=0)j-;elseif(i!=afi)i+;if(j!=0)j-;if(afi=0&bfi=0)if(k=1)printf(Yesn);elseprintf(Non);continue;if(flag)printf(Yesn);elseprintf(Non);return 0;B：小小度刷禮品題目描述一年一度的百度之星又開始了，這次參賽人數(shù)創(chuàng)下了吉尼斯世界紀(jì)錄，于是百度之星決定獎(jiǎng)勵(lì)一部分人：所有資格賽提交ID以x結(jié)尾的參賽選手將得到精美禮品一份。小小度同學(xué)非常想得到這份禮品，于是他就連續(xù)狂交了很多次，提交ID從a連續(xù)到b，他想問問你他能得到多少份禮品，你能幫幫他嗎？輸入第一行一個(gè)正整數(shù)T表示數(shù)據(jù)組數(shù)；接下去T行，每行三個(gè)正整數(shù)x，a，b (0 =x = 1018， 1 = a，b = 1018，a = b)輸出T行，每行為對(duì)應(yīng)的數(shù)據(jù)情況下，小小度得到的禮品數(shù)樣例輸入188888 88888 88888樣例輸出1#include #include using namespace std;long long fun(int n)long long sum=1;while (n-)sum*=10;return sum;int main()int t;long long x,a,b;scanf(%d,&t);while (t-)scanf(%lld %lld %lld,&x,&a,&b);long long cnt=0;int len_x=sizeof(x)/sizeof(int);int len_a=sizeof(a)/sizeof(int);int len_b=sizeof(b)/sizeof(int);for (long long i=a; i1，AiAjij)，我們定義其權(quán)值其中|X|表示X區(qū)間的長(zhǎng)度；如果X為空集|X|=0。當(dāng)然，如果這些閉區(qū)間沒有交集則權(quán)值為0。給定N個(gè)各不相同的閉區(qū)間，請(qǐng)你從中找出若干個(gè)(至少2個(gè))區(qū)間使其權(quán)值最大。輸入第一行一個(gè)整數(shù)N (2 = N = 105)接下來N行每行兩個(gè)整數(shù) l r(1=l=r=106)，表示閉區(qū)間的兩個(gè)端點(diǎn)。輸出最大權(quán)值樣例輸入41 64 82 73 5樣例輸出24D：輪子上的度度熊百度樓下有一塊很大很大的廣場(chǎng)。廣場(chǎng)上有很多輪滑愛好者，每天輪滑愛好者們都會(huì)在廣場(chǎng)上做一種叫做平地花式輪滑的表演。度度熊也想像他們一樣在輪上飛舞，所以也天天和他們練習(xí)。因?yàn)槎榷刃艿奶熨x，一下就學(xué)會(huì)了好多動(dòng)作。但他覺得只是單獨(dú)的做動(dòng)作很沒意思，動(dòng)作的組合才更有欣賞性。平地花式輪滑（簡(jiǎn)稱平花），是穿輪滑鞋在固定數(shù)量的標(biāo)準(zhǔn)樁距間做無跳起動(dòng)作的各式連續(xù)滑行。度度熊表演的舞臺(tái)上總共有N個(gè)樁，而他也從自己會(huì)的動(dòng)作中挑出M最好看的。但事情并沒有這么簡(jiǎn)單。首先每個(gè)動(dòng)作因?yàn)閺?fù)雜度不同，所以經(jīng)過的樁的個(gè)數(shù)也不盡相同。然后，為了保持連貫性，有些動(dòng)作是接不起來的，所以每個(gè)動(dòng)作都有他前面能接的一個(gè)動(dòng)作的列表。更有甚者，有的動(dòng)作要考慮前兩個(gè)動(dòng)作才能確定是否能做出來。因此動(dòng)作被分為三類：0型動(dòng)作，無論前面是什么動(dòng)作都能做出來，所以這種動(dòng)作也能作為起始動(dòng)作；1型動(dòng)作，要考慮前面那個(gè)動(dòng)作才能確定是否能接上；2型動(dòng)作，要考慮前面兩個(gè)動(dòng)作才能確定是否能接上。最后，評(píng)分也很復(fù)雜。每個(gè)動(dòng)作有個(gè)單獨(dú)得分，只要在表演過程中做了這個(gè)動(dòng)作就能獲得這個(gè)分?jǐn)?shù)。有些動(dòng)作的組合也非常好看，也會(huì)有相應(yīng)的得分。不過要獲得某個(gè)組合的得分就要在過程中完成這組組合中所有的動(dòng)作，但是，這些動(dòng)作既不要求按順序完成也不要求連續(xù)完成。當(dāng)然，大家不喜歡重復(fù)的動(dòng)作，所以同一個(gè)動(dòng)作和同一個(gè)組合不會(huì)獲得兩次得分。舉個(gè)例子，總共有10個(gè)樁，有以下幾個(gè)動(dòng)作：動(dòng)作1：0型，需要3個(gè)樁，得分5。動(dòng)作2：0型，需要4個(gè)樁，得分4。動(dòng)作3：1型，能接在動(dòng)作1或者動(dòng)作2后面，需要6個(gè)樁，得分10。動(dòng)作4：2型，要接在動(dòng)作2+動(dòng)作1后面，需要4個(gè)樁，得分30。組合1：（動(dòng)作1，動(dòng)作2，動(dòng)作4），得分15。組合2：（動(dòng)作1，動(dòng)作3），得分10。組合3：（動(dòng)作2，動(dòng)作3），得分5。能配成的方案不少，但有這么幾種方案是不行的：1、動(dòng)作2+動(dòng)作1+動(dòng)作4，雖然，動(dòng)作4分?jǐn)?shù)很多，而且1,2,4的組合還能額外獲得15分。但是，這個(gè)方案總共要用4+3+4=11個(gè)樁，超過了總樁數(shù)，所以不行。2、動(dòng)作1+動(dòng)作3，同樣也完成了一個(gè)組合，也滿足各個(gè)動(dòng)作要求的限定條件。但是做完后，只過了9個(gè)樁，沒有完成整個(gè)表演。這樣度度熊會(huì)很尷尬的。所以這樣的方案也不行。最優(yōu)方案應(yīng)該是動(dòng)作2+動(dòng)作3，滿足樁數(shù)要求，也滿足各個(gè)動(dòng)作前置限定條件。最后得分：?jiǎn)雾?xiàng)動(dòng)作14分+組合加分5分=19分。雖然，度度熊一下就算出來自己應(yīng)該怎么表演了。但是他還是想考考精通編程的你。輸入一開始一個(gè)整數(shù)T(1 = T = 5)，表示有T組數(shù)據(jù)，每個(gè)數(shù)據(jù)如下格式：第一行有三個(gè)整數(shù)，N，M，P。分別表示樁數(shù)、動(dòng)作數(shù)和組合數(shù)。第二行M個(gè)02的整數(shù)，表示每個(gè)動(dòng)作的類型。第三行M個(gè)整數(shù)，表示每個(gè)動(dòng)作需要使用的樁數(shù)。第四行M個(gè)整數(shù)，表示每個(gè)動(dòng)作單項(xiàng)的分?jǐn)?shù)。接下來P（P=1024）行，每行描述一個(gè)組合。每行的前兩個(gè)數(shù)X，Y，X表示組合中總共有X個(gè)動(dòng)作，Y表示組合能獲得的分?jǐn)?shù)。后面接X個(gè)數(shù)，表示組合中包含的X個(gè)動(dòng)作的編號(hào)。再接下來分為M塊，第i塊描述第i個(gè)動(dòng)作的前置條件。若第i個(gè)動(dòng)作是0型的，那么它沒有前置條件。所以對(duì)應(yīng)的塊是一個(gè)空行。若第i個(gè)動(dòng)作是1型的，對(duì)應(yīng)的塊是一個(gè)M的01序列。若這個(gè)序列是Aj的話，Aj=1表示動(dòng)作i可以接在動(dòng)作j后面。若第i