描述：Baidu年會(huì)安排了一場(chǎng)時(shí)裝秀節(jié)目。N名員工將依次身穿盛裝上臺(tái)表演。表演的順序是通過(guò)一種“畫(huà)線”抽簽的方式?jīng)Q定的。

首先，員工們?cè)谝粡埌准埳袭?huà)下N條平行的豎線。在豎線的上方從左到右依次寫(xiě)下1至N代表員工的編號(hào)；在豎線的下方也從左到右依次寫(xiě)下1至N代表出場(chǎng)表演的次序。

接著，員工們隨意在兩條相鄰的豎線間添加垂直于豎線的橫線段。

最后，每位員工的出場(chǎng)順序是按如下規(guī)則決定的：每位員工從自己的編號(hào)開(kāi)始用手指沿豎線向下劃，每當(dāng)遇到橫線就沿橫線移動(dòng)到相鄰的豎線上去，直到手指到達(dá)豎線下方的出場(chǎng)次序編號(hào)。這時(shí)手指指向的編號(hào)就是該員工的出場(chǎng)次序。例如在下圖的例子中，度度熊將第二名出場(chǎng)，第一名出場(chǎng)的是員工4。

員工在畫(huà)橫線時(shí)，會(huì)避免在同一位置重復(fù)畫(huà)線，并且避免兩條相鄰的橫線連在一起。即下圖所示的情況是不會(huì)出現(xiàn)的：

給定一種畫(huà)線的方案，員工編號(hào)為K的度度熊想知道自己是不是第一位出場(chǎng)表演的。如果不是，度度熊想知道自己能不能通過(guò)增加一條橫線段來(lái)使得自己變成第一位出場(chǎng)表演。

輸入

為了描述方便，我們規(guī)定寫(xiě)有員工編號(hào)的方向是y軸正方向（即上文中的豎線上方），寫(xiě)有出場(chǎng)次序的方向是y軸負(fù)方向（即上文中的豎線下方）。豎線沿x軸方向（即上文中從左到右）依次編號(hào)1至N。于是，每條橫線的位置都可以由一個(gè)三元組<xl, xr, y>確定，其中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ù)、畫(huà)下的橫線數(shù)目以及度度熊的員工編號(hào)。

每組數(shù)據(jù)的第2~M+1行每行包含3個(gè)整數(shù), xl, xr, y, (1 <= xl < N, xr = xl + 1, 0 <= y <= 1,000,000)，描述了一條橫線的位置。

輸出

對(duì)于每組數(shù)據(jù)輸出一行Yes或者No，表示度度熊能否通過(guò)增加一條橫線段來(lái)使得自己變成第一位出場(chǎng)表演。如果度度熊已經(jīng)是第一位出場(chǎng)表演，也輸出Yes。注意，盡管輸入數(shù)據(jù)中員工畫(huà)的橫線高度都是整數(shù)，但是度度熊可以在任意實(shí)數(shù)高度畫(huà)橫線。此外，度度熊和員工一樣，在畫(huà)橫線時(shí)需要避免在同一位置重復(fù)畫(huà)線，也要避免兩條相鄰的橫線連在一起。

樣例輸入

2

4 6 3

1 2 1

1 2 4

1 2 6

2 3 2

2 3 5

3 4 4

4 0 3

樣例輸出

Yes

No

代碼1：
/* 度度熊就是要第一個(gè)出場(chǎng) * 程序未檢測(cè)輸入數(shù)據(jù)的合法性 */ #include<iostream> #include<map> #include<vector> #include<climits> #include<string> #include<set> using namespace std;int ComputeRank(map<int, map<double, int> > &line_map, int k) {// 判定是否已經(jīng)是第一個(gè)出場(chǎng)int num = k;map<int, map<double, int> >::iterator iter = line_map.find(num);if(iter==line_map.end()){return num;}double y = INT_MAX;while(true){map<double, int>::iterator iter2 = iter->second.begin();for(; iter2!=iter->second.end(); ++iter2){if(iter2->first < y){break;}}if(iter2!=iter->second.end()){y = iter2->first;num = iter2->second;}else{return num;}iter = line_map.find(num);}return num; }bool CanBeFirst(map<int, map<double, int> > &line_map, int k, int n, set<double, greater<int> > &allY) {// 判定是否已經(jīng)是第一個(gè)出場(chǎng)int rank = ComputeRank(line_map, k);if(rank == 1){return true;}// 如果不是，則添加橫線，再判斷能否第一個(gè)出場(chǎng)set<double, greater<int> >::iterator iterY = allY.begin();double test = *iterY + 1;do{if(k>1){map<int, map<double, int> > tMap = line_map;map<int, map<double, int> >::iterator tmpIter = tMap.find(k);if(tmpIter == tMap.end()){map<double, int> tMap1;tMap1.insert(make_pair(test, k-1) );tMap.insert(make_pair(k, tMap1) );}else{tmpIter->second.insert(make_pair(test, k-1));}rank = ComputeRank(line_map, k);if(rank == 1){return true;}}if(k<n){map<int, map<double, int> > tMap = line_map;map<int, map<double, int> >::iterator tmpIter = tMap.find(k);if(tmpIter == tMap.end()){map<double, int> tMap1;tMap1.insert(make_pair(test, k+1) );tMap.insert(make_pair(k, tMap1) );}else{tmpIter->second.insert(make_pair(test, k+1));}rank = ComputeRank(line_map, k);if(rank == 1){return true;}}if(iterY == allY.end()){break;}test = *iterY;++iterY;if(iterY == allY.end()){test -= 1;}else{test += *iterY;test /=2;}}while(true);return false; }int main(void) {int i , t , xl, xr, y , n , m , k;cin>>t;for(i = 0 ; i < t ; ++i){// line_map存放(xl, (y,xr)) 和 (xr, (y,xl))map<int, map<double, int> > line_map;// allY存放各種可能的高度set<double, greater<int> > allY;cin>>n>>m>>k;if(!m){puts("No");continue;}while(m--){cin>>xl>>xr>>y;allY.insert(y);map<int, map<double, int> >::iterator iter;iter=line_map.find(xl);if(iter!=line_map.end()){iter->second.insert(make_pair(y, xr));}else{map<double, int> tmp;tmp.insert(make_pair(y, xr));line_map.insert(make_pair(xl, tmp) );}iter=line_map.find(xr);if(iter!=line_map.end()){iter->second.insert(make_pair(y, xl));}else{map<double, int> tmp;tmp.insert(make_pair(y, xl));line_map.insert(make_pair(xr, tmp) );}}if(CanBeFirst(line_map, k, m, allY) )puts("Yes");elseputs("No");}return 0; } 代碼2：
/* 1、從下向上，找第一名的路徑,把橫線段做標(biāo)記1，沒(méi)有橫線段的地方添加橫線段出來(lái)，標(biāo)記2 2、從上向下，找第k名(即度度熊的位置)的路徑，遇到有標(biāo)記的即表示本身就是第一(標(biāo)記1)，或加線段后可以是第一(標(biāo)記2) */ #include<iostream> #include<vector> #include<algorithm> using namespace std;typedef struct line {int xl;int xr;int y;int path; }line;//升序排序,是"<",降序排列是">"號(hào) bool cmp(line a,line b) {return a.y<b.y; }int main(void) {int t , i , j , tag , n , m , k , max3 , noline;cin>>t;while (t--){tag = max3 = noline = 0;//員工數(shù),線段樹(shù),度度熊的位置cin>>n>>m>>k;int tmpK = k;vector<line> array;??? //M條線段line lin;for(i = 0 ; i < m ; ++i){cin>>lin.xl>>lin.xr>>lin.y;lin.path = 0;array.push_back(lin);}//按線段高低降序排列按線段高低降序排列sort(array.begin(),array.end(),cmp);//從下向上,找第一名的路線,線段path標(biāo)記為1int firstpath = 1;int preelem3;preelem3 = 0;for(i = 0 ; i < m ; ++i){max3 = max3 > array[i].y ? max3 : array[i].y;if (array[i].xl==firstpath || array[i].xr==firstpath){++noline;//與上一個(gè)高度差if(array[i].y > preelem3+1){for (j = array[i].y-1 ; j > preelem3 ; --j){lin.xl = firstpath;lin.xr = firstpath+1;lin.y = j;lin.path = 2;array.push_back(lin);?????? //往右添加橫線lin.xl = firstpath-1;lin.xr = firstpath;array.push_back(lin);??? //往左添加橫線}}//主軸移動(dòng)到旁邊一個(gè)軸上firstpath = array[i].xl==firstpath ? array[i].xr : array[i].xl;array[i].path = 1;preelem3 = array[i].y;}}if(noline==0){for(j = 0 ; j < max3 + 1 ; ++j){lin.xl = 1;lin.xr = 2;lin.y = j;lin.path = 2;array.push_back(lin);????? //往右添加橫線}}//在主軸最大值上向左右加橫線for(i = preelem3 + 1 ; i <= max3+1 ; ++i){lin.xl = firstpath;lin.xr = firstpath+1;lin.y = i;lin.path = 2;array.push_back(lin);????? //往右添加橫線lin.xl = firstpath-1;lin.xr = firstpath;array.push_back(lin);????? //往左添加橫線}//穩(wěn)定排序,使固有線段在后加線段之前stable_sort(array.begin(),array.end(),cmp);//從上向下,找度度熊的路線,看能否遇到有標(biāo)記的線段preelem3 = 1000000;for (i = array.size()-1 ; i >= 0 ; --i){if ( (array[i].xr!=preelem3) && (array[i].xl==tmpK || array[i].xr==tmpK) ){if (array[i].path>0)//線段標(biāo)有1,表示度度熊本身就是第一; 是2表示可以通過(guò)加一個(gè)線段變?yōu)榈谝粄tag++;}tmpK = array[i].xl == tmpK ? array[i].xr : array[i].xl;preelem3 = array[i].y;}}if(tag>0) //tag>0表示可以通過(guò)加線段改為第一,tag的值表示可添加線段的位置的個(gè)數(shù)puts("Yes");elseputs("No");}return 0; }/* 2 4 7 3 1 2 12 1 2 2 2 3 11 2 3 9 3 4 10 3 4 8 3 4 7 Yes 4 0 3 No */


與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【2012百度之星/初赛上】A:度度熊就是要第一个出场的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。