百度之星Astar2012程序設計大賽初賽試題及參考答案

1、-作者xxxx-日期xxxx百度之星Astar2012程序設計大賽初賽試題及參考答案【精品文檔】百度之星Astar2012程序設計大賽初賽試題（第一場）及B題答案比賽說明百度之星初賽：2012年6月2日、6月3日10：00Am12：00Pm本次大賽的初賽的初賽采取在線答題、編譯，離線判題的形式，選手報名后，可以在6月2日、6月3日任選一天參加比賽，也可選擇兩場都參加。針對每題，交題后，系統(tǒng)將給出程序編譯是否正確的結果，但不會給出程序是否通過全部測試數(shù)據(jù)的評價；當場比賽結束后，所有選手的針對每題所寫的程序將被離線評判，每題根據(jù)程序通過測試數(shù)據(jù)的數(shù)目計算得分。每場初賽根據(jù)單場所有題目總分計算成績，

2、選出當場成績在前400名的選手進入復賽（第一場已經進入復賽的選手參加第二場比賽如果再次晉級，將被不在第二場參與排名）。2012年6月2日，2012百度之星Astar2012程序設計大賽初賽打開大幕。這里提供了初賽第一場的題目，供有未進初賽和其它有興趣的朋友研究。初賽第一場共4題。分別是度度熊就是要第一個出場、小小度刷禮品、集合的交與并、輪子上的度度熊。目錄比賽說明···················

3、83;··· 1·A：度度熊就是要第一個出場·············· 2·B：小小度刷禮品··················· 5·C：集合的交與并····

4、3;···············6·D：輪子上的度度熊···················6·A：度度熊就是要第一個出場題目描述Baidu年會安排了一場時裝秀節(jié)目。N名員工將依次身穿盛裝上臺表演。表演的順序是通過一種“畫線”抽簽的方式決

5、定的。首先，員工們在一張白紙上畫下N條平行的豎線。在豎線的上方從左到右依次寫下1至N代表員工的編號；在豎線的下方也從左到右依次寫下1至N代表出場表演的次序。接著，員工們隨意在兩條相鄰的豎線間添加垂直于豎線的橫線段。最后，每位員工的出場順序是按如下規(guī)則決定的：每位員工從自己的編號開始用手指沿豎線向下劃，每當遇到橫線就沿橫線移動到相鄰的豎線上去，直到手指到達豎線下方的出場次序編號。這時手指指向的編號就是該員工的出場次序。例如在下圖的例子中，度度熊將第二名出場，第一名出場的是員工4。員工在畫橫線時，會避免在同一位置重復畫線，并且避免兩條相鄰的橫線連在一起。即下圖所示的情況是不會出現(xiàn)的：給定一種畫線的

6、方案，員工編號為K的度度熊想知道自己是不是第一位出場表演的。如果不是，度度熊想知道自己能不能通過增加一條橫線段來使得自己變成第一位出場表演。輸入為了描述方便，我們規(guī)定寫有員工編號的方向是y軸正方向（即上文中的豎線上方），寫有出場次序的方向是y軸負方向（即上文中的豎線下方）。豎線沿x軸方向（即上文中從左到右）依次編號1至N。于是，每條橫線的位置都可以由一個三元組<xl, xr, y>確定，其中xl, xr是橫線左右兩個端點所在豎線的編號，y是橫線的高度。輸入第一行是一個整數(shù)T(T <= 50)，代表測試數(shù)據(jù)的組數(shù)。每組數(shù)據(jù)的第一行包含三個整數(shù)N, M,K( 1<=N<

7、;=100, 0<=M<=1000, 1<=K<=N)，分別代表參與表演的員工人數(shù)、畫下的橫線數(shù)目以及度度熊的員工編號。每組數(shù)據(jù)的第2M+1行每行包含3個整數(shù), xl, xr, y, (1 <= xl < N, xr = xl + 1, 0 <= y <= 1,000,000)，描述了一條橫線的位置。輸出對于每組數(shù)據(jù)輸出一行Yes或者No，表示度度熊能否通過增加一條橫線段來使得自己變成第一位出場表演。如果度度熊已經是第一位出場表演，也輸出Yes。注意，盡管輸入數(shù)據(jù)中員工畫的橫線高度都是整數(shù)，但是度度熊可以在任意實數(shù)高度畫橫線。此外，度度熊和員工一

8、樣，在畫橫線時需要避免在同一位置重復畫線，也要避免兩條相鄰的橫線連在一起。樣例輸入24 6 31 2 11 2 41 2 62 3 22 3 53 4 44 0 3樣例輸出YesNo#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;struct nodeint l,r,y;line1010;struct node1int t,b,pos;a1010,b1010;bool cmp(node a,node b)

9、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;i<m;i+)scanf("%d%d%d",&linei.l,&linei.r,&linei.y);sort(line,li

10、ne+m,cmp);pos = k;afi=0;h = aafi.t = 1000000;while(true)flag = false;for(i=0;i<m;i+)if(linei.l=pos&&linei.y<h)h = aafi.b = aafi+1.t = linei.y;aafi.pos = pos;pos = linei.r;afi+;flag = true;else if(linei.r=pos&&linei.y<h)h = aafi.b = aafi+1.t = linei.y;aafi.pos = pos;pos = lin

11、ei.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;i<m;i+)if(linei.l=pos&&linei.y>h)h = bbfi.t = bbfi+1.b = linei.y;bbfi.pos = pos;po

12、s = linei.r;bfi+;flag = true;else if(linei.r=pos&&linei.y>h)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 =

13、 true;break;ha = ai.b;hb = bj.b;if(ha>hb&&i!=afi)i+;else if(hb>ha&&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：小小度刷禮品題目描述

14、一年一度的百度之星又開始了，這次參賽人數(shù)創(chuàng)下了吉尼斯世界紀錄，于是百度之星決定獎勵一部分人：所有資格賽提交ID以x結尾的參賽選手將得到精美禮品一份。小小度同學非常想得到這份禮品，于是他就連續(xù)狂交了很多次，提交ID從a連續(xù)到b，他想問問你他能得到多少份禮品，你能幫幫他嗎？輸入第一行一個正整數(shù)T表示數(shù)據(jù)組數(shù)；接下去T行，每行三個正整數(shù)x，a，b (0 <=x <= 1018， 1 <= a，b <= 1018，a <= b)輸出T行，每行為對應的數(shù)據(jù)情況下，小小度得到的禮品數(shù)樣例輸入188888 88888 88888樣例輸出1#include <stdio.h

15、>#include <iostream>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=si

16、zeof(a)/sizeof(int);int len_b=sizeof(b)/sizeof(int);for (long long i=a; i<=b; +i)int len_i=sizeof(i)/sizeof(int);if (0=(a-x)%fun(len_i-len_x)cnt+;i+=x;printf ("%lldn",cnt);return 0;C：集合的交與并對于一個閉區(qū)間集合A1,A2AK(K>1，AiAjij)，我們定義其權值其中|X|表示X區(qū)間的長度；如果X為空集|X|=0。當然，如果這些閉區(qū)間沒有交集則權值為0。給定N個各不相同的閉區(qū)間，

17、請你從中找出若干個(至少2個)區(qū)間使其權值最大。輸入第一行一個整數(shù)N (2 <= N <= 105)接下來N行每行兩個整數(shù) l r(1<=l<=r<=106)，表示閉區(qū)間的兩個端點。輸出最大權值樣例輸入41 64 82 73 5樣例輸出24D：輪子上的度度熊百度樓下有一塊很大很大的廣場。廣場上有很多輪滑愛好者，每天輪滑愛好者們都會在廣場上做一種叫做平地花式輪滑的表演。度度熊也想像他們一樣在輪上飛舞，所以也天天和他們練習。因為度度熊的天賦，一下就學會了好多動作。但他覺得只是單獨的做動作很沒意思，動作的組合才更有欣賞性。平地花式輪滑（簡稱平花），是穿輪滑鞋在固定數(shù)量的

18、標準樁距間做無跳起動作的各式連續(xù)滑行。度度熊表演的舞臺上總共有N個樁，而他也從自己會的動作中挑出M最好看的。但事情并沒有這么簡單。首先每個動作因為復雜度不同，所以經過的樁的個數(shù)也不盡相同。然后，為了保持連貫性，有些動作是接不起來的，所以每個動作都有他前面能接的一個動作的列表。更有甚者，有的動作要考慮前兩個動作才能確定是否能做出來。因此動作被分為三類：0型動作，無論前面是什么動作都能做出來，所以這種動作也能作為起始動作；1型動作，要考慮前面那個動作才能確定是否能接上；2型動作，要考慮前面兩個動作才能確定是否能接上。最后，評分也很復雜。每個動作有個單獨得分，只要在表演過程中做了這個動作就能獲得這個

19、分數(shù)。有些動作的組合也非常好看，也會有相應的得分。不過要獲得某個組合的得分就要在過程中完成這組組合中所有的動作，但是，這些動作既不要求按順序完成也不要求連續(xù)完成。當然，大家不喜歡重復的動作，所以同一個動作和同一個組合不會獲得兩次得分。舉個例子，總共有10個樁，有以下幾個動作：動作1：0型，需要3個樁，得分5。動作2：0型，需要4個樁，得分4。動作3：1型，能接在動作1或者動作2后面，需要6個樁，得分10。動作4：2型，要接在動作2+動作1后面，需要4個樁，得分30。組合1：（動作1，動作2，動作4），得分15。組合2：（動作1，動作3），得分10。組合3：（動作2，動作3），得分5。能配成的方案不少，但有這么幾種方案是不行的：1、動作2+動作1+動作4，雖然，動作4分數(shù)很多，而且1,2,4的組合還能額外獲得15分。但是，這個方案總共要用4+3+4=11個樁，超過了總樁數(shù)，所以不行。2、動作1+動作3，同樣也完成了一個組合，也滿足各個動作要求的限定條件。但是做完后，只過了9個樁，沒有完成整個表演。這樣度度熊會很尷尬的。所以這樣的方案也不行。最優(yōu)方案應該是動作2+動作3，滿足樁數(shù)要求，也滿足各個動作前置限定條件。最后得分：單項動作14分+組合加