當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

百度之星初赛（1）解题报告

發(fā)布時間：2025/3/20 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了百度之星初赛（1）解题报告小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

? ? ? ? ? ? ? ? ? ? ? ? ?超級賽亞ACMer

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1536????Accepted Submission(s): 437

Problem Description 百小度是一個ACMer，也是一個超級賽亞人，每個ACMer都有一個戰(zhàn)斗力，包括百小度。 所謂超級賽亞人的定義，是說如果在對抗中剛好接近極限狀態(tài)，那就會激發(fā)斗志，實(shí)力提升.

具體來說，就是百小度現(xiàn)在要接受一些ACMer的挑戰(zhàn)了，這些ACMer有n個人，第i個人的戰(zhàn)斗力是a[i]。

 百小度接下來可以自主安排與這n個ACMer的PK順序，他要想在PK賽中贏過另外一個ACMer，就必須使得自己的戰(zhàn)斗力不小于對方（平局情況他會按照百小度字典上的規(guī)則把自己排在第一).

如果百小度的戰(zhàn)斗力大于對方，那么百小度就會輕易獲勝，得不到鍛煉并且驕傲起來，他以后的戰(zhàn)斗力將保持在這個值，再也不會發(fā)生改變。 如果百小度的戰(zhàn)斗力等于對方，那么百小度在獲勝的同時也會感到很吃力，但是這會激發(fā)百小度的斗志，使得他刻苦刷題，在下場PK賽之前，戰(zhàn)斗力最多提升k點(diǎn)（即可以提升0~k點(diǎn)任意值）.

k是百小度的潛力提升上限，會被給定一個初始值，這個潛力提升上限k在后面的比賽中會下降.

每戰(zhàn)勝一個ACMer，這個潛力上限k將減少1（因?yàn)槌壻悂喨税傩《纫矔械嚼?#xff09;，但k最低只會減少到0，即不會出現(xiàn)戰(zhàn)斗力下降的情況 。也就是第一次比賽如果激發(fā)了百小度的斗志，他能把戰(zhàn)斗力提升0~k的任一值，如果第二次比賽繼續(xù)被激發(fā)斗志，他能在第一次提升后的基礎(chǔ)上，把戰(zhàn)斗力再提升

Input 輸入包含多組數(shù)據(jù)（數(shù)據(jù)不超過500組)

第一行一個整數(shù)T，表示T組數(shù)據(jù)

對于每組數(shù)據(jù)，第一行包括三個整數(shù)

Output 對于每組數(shù)據(jù)，先輸出一行Case #i:

Sample Input 2 5 11 3 15 13 10 9 8 5 11 3 8 9 10 13 16

Sample Output Case #1: why am I so diao? Case #2: madan! Hint 第一組樣例解釋 5個ACMer，初始戰(zhàn)斗力選擇范圍是[0,11],接下來每場戰(zhàn)斗力提升上限是3,2,1,0,0,...,0 百小度首先使得自己的初始戰(zhàn)斗力為10，打敗戰(zhàn)斗力為10的第一個ACMer，然后選擇戰(zhàn)斗力提升3，變成13，打敗戰(zhàn)斗力為13的第二個ACMer，然后選擇戰(zhàn)斗力提升2，變成15，打敗戰(zhàn)斗力為15的第三個ACMer，之后再以任意順序打敗剩下的ACMer

Source 2015年百度之星程序設(shè)計(jì)大賽 - 初賽(1)? 題意： ? 就好比上臺階，每次自己跳躍的高度有限，怎么樣跳到頂點(diǎn)是一個思路。思路： ? ?對于給定的那些戰(zhàn)斗力的進(jìn)行升序排序，然后采取貪心策略，每次盡可能的往上走。代碼： 1 #include <stdio.h> 2 #include<algorithm> 3 #define maxn 10005 4 long long aa[maxn]; 5 int main() 6 { 7 int cnt=1,cas,i; 8 long long nn,mm,kk,res; 9 scanf("%d",&cas); 10 while(cas--){ 11 scanf("%lld %lld %lld ",&nn,&mm,&kk); 12 for(i=0 ; i<nn ; i++) 13 scanf("%lld",aa+i); 14 std::sort(aa,aa+nn); 15 printf("Case #%d:\n",cnt++); 16 for(res=mm,i=0 ; i<nn ; i++ ) 17 if(aa[i]<=mm) res=aa[i]; 18 else break; 19 20 while(i!=0&&i<nn){ 21 int j=i; 22 while(j<nn&&res+kk>=aa[j]) j++; 23 if(j==i)break; 24 else res=aa[j-1]; 25 if(kk>0) kk--; 26 i=j; 27 } 28 if(res>=aa[nn-1]) 29 puts("why am I so diao?"); 30 else 31 puts("madan!"); 32 } 33 return 0; 34 }

? ? ? ? ? 找連續(xù)數(shù)

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 801????Accepted Submission(s): 294

Problem Description 小度熊拿到了一個無序的數(shù)組，對于這個數(shù)組，小度熊想知道是否能找到一個k 的區(qū)間，里面的 k 個數(shù)字排完序后是連續(xù)的。

現(xiàn)在小度熊增加題目難度，他不想知道是否有這樣的 k 的區(qū)間，而是想知道有幾個這樣的 k 的區(qū)間。

Input 輸入包含一組測試數(shù)據(jù)。

第一行包含兩個整數(shù)n，m，n代表數(shù)組中有多少個數(shù)字，m 代表針對于此數(shù)組的詢問次數(shù)，n不會超過10的4次方，m 不會超過1000。第二行包含n個正整數(shù)，第 I 個數(shù)字代表無序數(shù)組的第 I 位上的數(shù)字，數(shù)字大小不會超過2的31次方。接下來 m 行，每行一個正整數(shù) k，含義詳見題目描述，k 的大小不會超過1000。

Output 第一行輸"Case #i:"。(由于只有一組樣例，只輸出”Case #1:”即可)

然后對于每個詢問的 k，輸出一行包含一個整數(shù)，代表數(shù)組中滿足條件的 k 的大小的區(qū)間的數(shù)量。

Sample Input 6 2 3 2 1 4 3 5 3 4

Sample Output Case #1: 2 2

Source 2015年百度之星程序設(shè)計(jì)大賽 - 初賽(1)? 思路： ?對于一個集合{a1,a2,a3,a4, .... an }map，我們?nèi)绾沃览锩娴臄?shù)是連續(xù)，其實(shí)只需要滿足這樣的特征：集合中最大值和集合中最小值的差+1 = 集合中元素的個數(shù) 。 ?我們就可以去說，這個集合是連續(xù)的。 1 #include<iostream> 2 #include<map> 3 #include<stdio.h> 4 #include<string.h> 5 6 const int maxn= 10005; 7 int n,m,k; 8 int aa[maxn]; 9 int res[1005]; 10 int main() 11 { 12 int T,cas=1; 13 int max_a ,min_a ; 14 std::map<int ,bool>tmp ; 15 while(~scanf("%d%d",&n,&m)){ 16 17 for(int i=0;i<n;i++) 18 scanf("%d",aa+i); 19 //采用離線的方法 20 memset(res, 0,sizeof(res)); 21 for(int i=0;i<n ;i++){ 22 max_a = aa[i]; 23 min_a = aa[i]; 24 tmp.clear(); 25 for(int j=i ; j<n&&j<1000+i;j++){ 26 if(max_a < aa[j] ) max_a = aa[j]; 27 if(min_a > aa[j] ) min_a = aa[j]; 28 tmp[aa[j]]=true; 29 if(max_a -min_a==j-i&&max_a -min_a+1==tmp.size()) 30 res[max_a -min_a+1]++; 31 } 32 } 33 printf("Case #%d:\n",cas++); 34 for(int i=0; i<m;i++) 35 { 36 scanf("%d",&k); 37 printf("%d\n",res[k]); 38 } 39 } 40 return 0; 41 }

? ? ?很危險(xiǎn)的滑了過去...920ms ?

序列變換

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 581????Accepted Submission(s): 287

Problem Description 給定序列

Input 第一行為測試的組數(shù)

Output 對于每一個測試樣例，輸出兩行：

第一行輸出："Case #i:"。i代表第 i 組測試數(shù)據(jù)。

第二行輸出一個正整數(shù)，代表滿足條件的最小代價。

Sample Input 2 2 1 10 3 2 5 4

Sample Output Case #1: 0 Case #2: 1

Source 2015年百度之星程序設(shè)計(jì)大賽 - 初賽(1)?

題意： ?其實(shí)求的最小代價res，就是對于任意集合A{},使得里面的元素+—res，成為一個單調(diào)數(shù)列.... 剛開始搞不懂題目究竟是什么意思！ ╮(╯▽╰)╭ 簡單的二分代碼：
?? 1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #define maxn 100005 5 int aa[maxn]; 6 7 bool solve(int var ,int n){ 8 //對于a[i]+|- var 變成單調(diào)數(shù)列 9 int tmp = var +aa[n-1]; 10 for(int i=n-2; i>=0 ;i-- ){ 11 if (abs(tmp - 1 - aa[i]) <= var) 12 tmp = tmp - 1; 13 else if (tmp - 1 >= aa[i]) 14 tmp = aa[i] + var; 15 else 16 return 0; 17 } 18 return 1; 19 } 20 int main() 21 { 22 int t,n; 23 scanf("%d",&t); 24 for(int cas=1;cas<=t;cas++){ 25 scanf("%d",&n); 26 for(int i=0; i<n ;i++) 27 scanf("%d",aa+i); 28 29 printf("Case #%d:\n",cas); 30 int mid ,ri=1000005,le=0; 31 while(le<ri){ 32 mid = le +((ri-le)>>1L); 33 //判斷是否為單調(diào)數(shù)列 34 if(solve(mid,n)) 35 ri=mid ; 36 else 37 le = mid+1; 38 } 39 printf("%d\n",le); 40 } 41 return 0; 42 }

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? KPI

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 639????Accepted Submission(s): 267

Problem Description 你工作以后, KPI 就是你的全部了. 我開發(fā)了一個服務(wù)，取得了很大的知名度。數(shù)十億的請求被推到一個大管道后同時服務(wù)從管頭拉取請求。讓我們來定義每個請求都有一個重要值。我的KPI是由當(dāng)前管道內(nèi)請求的重要值的中間值來計(jì)算。現(xiàn)在給你服務(wù)記錄，有時我想知道當(dāng)前管道內(nèi)請求的重要值得中間值。

Input 有大約100組數(shù)據(jù)。

每組數(shù)據(jù)第一行有一個

Output 對于每組數(shù)據(jù)，先輸出一行

Case #i:
然后每一次"query"，輸出當(dāng)前管道內(nèi)重要值的中間值。

Sample Input 6 in 874 query out in 24622 in 12194 query

Sample Output Case #1: 874 24622

Source 2015年百度之星程序設(shè)計(jì)大賽 - 初賽(1)? 這道題剛開始用堆來處理，發(fā)現(xiàn)總是出錯！后來在看了下別人的解題報(bào)告，發(fā)現(xiàn)了一種新的思路，運(yùn)用兩個set集合，利用紅黑樹的特性。分段來進(jìn)行排序但是要總是保持這兩顆樹的元素個數(shù)之差保持在小于2的狀態(tài)。而且要滿足上層集合的個數(shù)始終大于或者等于下層集合個數(shù)。 1 #include<stdio.h> 2 #include<string.h> 3 #include<set> 4 #include<queue> 5 #include<stdlib.h> 6 #include<iostream> 7 8 int tt ,x,tmp,cnt=1; 9 char cmd[8]; 10 int main( void ) 11 { 12 std::set<int> low,hig; 13 14 while(scanf("%d",&tt)!=EOF){ 15 std::queue<int>aa; 16 printf("Case #%d:\n",cnt++); 17 low.clear(); 18 hig.clear(); 19 20 while(tt--){ 21 scanf("%s",cmd); 22 if(cmd[0]=='i'){ 23 24 scanf("%d",&x); 25 aa.push(x); 26 if(hig.empty()|| x > *hig.begin()) 27 hig.insert(x); 28 else 29 low.insert(x); 30 31 } 32 else if(cmd[0]=='o'){ 33 34 tmp=aa.front(); 35 aa.pop(); 36 if(low.count(tmp)) 37 low.erase(tmp); 38 else 39 hig.erase(tmp); 40 41 }else if(cmd[0]=='q') 42 printf("%d\n",*hig.begin()); 43 44 if(low.size()+1<hig.size()){ 45 low.insert(*hig.begin()); 46 hig.erase(*hig.begin()); 47 } 48 else if(low.size()>hig.size()){ 49 hig.insert(*low.rbegin()); 50 low.erase(*low.rbegin()); 51 } 52 } 53 } 54 return 0; 55 }

? ?方法二 ?利用線段樹處理，類似于一個單點(diǎn)更新和離散化處理...

? ? ?

1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<queue> 5 #include<iostream> 6 #include<algorithm> 7 8 9 using namespace std; 10 const int maxn=10005; 11 12 int Hash[maxn],sum[maxn<<2]; 13 int cnt; 14 15 typedef struct node{ 16 17 int var ; 18 char cmd[6]; 19 20 }Node; 21 22 void Push(int pos ){ 23 sum[pos]=sum[pos<<1]+sum[pos<<1|1]; 24 } 25 26 void Build(int st ,int en ,int pos){ 27 if(st==en){ 28 sum[st]=0; 29 return ; 30 } 31 int mid=st+((en-st)>>1L); 32 Build(st,mid,pos<<1); 33 Build(mid+1,en,pos<<1|1); 34 Push(pos); 35 } 36 37 void Update(int st ,int en ,int value ,int pos ,int find_p){ 38 39 if(st==en) { //單點(diǎn)更新，說明增加或者減少一個點(diǎn) 40 sum[pos]=value; 41 return ; 42 } 43 int mid =st+((en-st)>>1L); 44 if(find_p<=mid) 45 Update(st , mid , value , pos<<1 , find_p); 46 else 47 Update(mid+1 , en , value , pos<<1|1 ,find_p); 48 Push(pos); 49 } 50 51 int query(int st ,int en ,int pos ,int num){ 52 if(st==en) 53 return st; 54 int mid = st + ((en -st)>>1L); 55 if(sum[pos<<1]>=num) 56 return query(st,mid,pos<<1 , num); 57 else 58 return query(mid+1,en,pos<<1|1,num-sum[pos<<1]); //相對起點(diǎn)為0 59 } 60 61 //學(xué)習(xí)了某位大牛的STL用法 62 int HASH(int x ){ 63 64 return lower_bound(Hash ,Hash+cnt,x)-Hash; 65 } 66 67 Node tem[maxn]; 68 int main() 69 { 70 int nn,cas=1,pos; 71 while(~scanf("%d",&nn)){ 72 queue<int>aa; 73 cnt=0; 74 memset(sum,0,sizeof(sum)); 75 printf("Case #%d:\n",cas++); 76 77 for(int i=0;i<nn;i++){ 78 scanf("%s",tem[i].cmd); 79 if(tem[i].cmd[0]=='i'){ 80 scanf("%d",&tem[i].var); 81 Hash[cnt++]=tem[i].var; 82 } 83 } 84 sort(Hash,Hash+cnt); 85 86 for(int i=0;i<nn;i++){ 87 if(tem[i].cmd[0]=='i') 88 { 89 pos = HASH(tem[i].var); 90 Update(1,cnt+1,1,1,pos+1); 91 aa.push(pos); 92 93 } 94 else if(tem[i].cmd[0]=='o') 95 { 96 pos =aa.front(); 97 aa.pop(); 98 Update(1,cnt+1,0,1,pos+1); 99 100 } 101 else{ 102 103 pos = sum[1]/2 +1; 104 pos=query(1,cnt+1,1,pos); 105 printf("%d\n",Hash[pos-1]); 106 107 } 108 } 109 } 110 return 0; 111 }

速度499ms飄然而過！?

總結(jié)

以上是生活随笔為你收集整理的百度之星初赛（1）解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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

上一篇： mysql服务器（二）
下一篇：移动web开发都会遇到的坑（会持续更新）