當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

天梯赛2016-L2

發布時間：2023/12/13 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了天梯赛2016-L2 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

L2-001. 緊急救援

作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖。在地圖上顯示有多個分散的城市和一些連接城市的快速道路。每個城市的救援隊數量和每一條連接兩個城市的快速道路長度都標在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊盡快趕往事發地，同時，一路上召集盡可能多的救援隊。

輸入格式：

輸入第一行給出4個正整數N、M、S、D，其中N（2<=N<=500）是城市的個數，順便假設城市的編號為0~(N-1)；M是快速道路的條數；S是出發地的城市編號；D是目的地的城市編號。第二行給出N個正整數，其中第i個數是第i個城市的救援隊的數目，數字間以空格分隔。隨后的M行中，每行給出一條快速道路的信息，分別是：城市1、城市2、快速道路的長度，中間用空格分開，數字均為整數且不超過500。輸入保證救援可行且最優解唯一。

輸出格式：

第一行輸出不同的最短路徑的條數和能夠召集的最多的救援隊數量。第二行輸出從S到D的路徑中經過的城市編號。數字間以空格分隔，輸出首尾不能有多余空格。

輸入樣例： 4 5 0 3 20 30 40 10 0 1 1 1 3 2 0 3 3 0 2 2 2 3 2 輸出樣例： 2 60 0 1 3

1 //2017-03-17 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 #include <stack> 7 8 using namespace std; 9 10 const int N = 510; 11 const int inf = 0x3f3f3f3f; 12 int n, m, G[N][N], dis[N], vis[N], pre[N], way[N], maxpeo[N]; 13 14 int dijkstra(int s, int d) 15 { 16 for(int i = 0; i < n; i++) 17 { 18 dis[i] = G[s][i]; 19 if(G[s][i] != inf){ 20 pre[i] = s; 21 way[i]++; 22 } 23 } 24 pre[s] = -1; 25 dis[s] = 0; 26 vis[s] = 1; 27 way[s] = 1; 28 int mindis, u; 29 maxpeo[s] = G[s][s]; 30 for(int i = 0; i < n; i++) 31 { 32 mindis = inf; 33 for(int j = 0; j < n; j++) 34 if(!vis[j] && dis[j] < mindis) 35 { 36 mindis = dis[j]; 37 u = j; 38 } 39 vis[u] = 1; 40 for(int v = 0; v < n; v++) 41 { 42 if(vis[v] || G[u][v]==inf)continue; 43 if(dis[v] > dis[u]+G[u][v]){ 44 dis[v] = dis[u]+G[u][v]; 45 pre[v] = u; 46 maxpeo[v] = maxpeo[u] + G[v][v]; 47 way[v] = way[u]; 48 }else if(dis[v] == dis[u]+G[u][v]){ 49 way[v] += way[u]; 50 if(maxpeo[v] < maxpeo[u]+G[v][v]){ 51 maxpeo[v] = maxpeo[u] + G[v][v]; 52 pre[v] = u; 53 } 54 } 55 } 56 } 57 return maxpeo[d]+maxpeo[s]; 58 } 59 60 int main() 61 { 62 int s, d, u, v, w; 63 while(cin>>n>>m>>s>>d) 64 { 65 for(int i = 0; i < n; i++) 66 { 67 for(int j = 0; j < n; j++) 68 G[i][j] = inf; 69 vis[i] = 0; 70 dis[i] = inf; 71 pre[i] = -1; 72 way[i] = 0; 73 maxpeo[i] = 0; 74 cin>>G[i][i]; 75 maxpeo[i] = G[i][i]; 76 } 77 for(int i = 0; i < m; i++) 78 { 79 cin>>u>>v>>w; 80 G[u][v] = G[v][u] = w; 81 } 82 int peo = dijkstra(s, d); 83 int pr = d; 84 stack<int> sk; 85 while(pr != s) 86 { 87 sk.push(pr); 88 pr = pre[pr]; 89 } 90 cout<<way[d]<<" "<<peo<<endl; 91 cout<<s; 92 int o; 93 while(!sk.empty()) 94 { 95 o = sk.top(); 96 cout<<" "<<o; 97 sk.pop(); 98 } 99 cout<<endl; 100 } 101 102 return 0; 103 } View Code

L2-002. 鏈表去重

給定一個帶整數鍵值的單鏈表L，本題要求你編寫程序，刪除那些鍵值的絕對值有重復的結點。即對任意鍵值K，只有鍵值或其絕對值等于K的第一個結點可以被保留。同時，所有被刪除的結點必須被保存在另外一個鏈表中。例如：另L為21→-15→-15→-7→15，則你必須輸出去重后的鏈表21→-15→-7、以及被刪除的鏈表-15→15。

輸入格式：

輸入第一行包含鏈表第一個結點的地址、以及結點個數N（<= 10⁵?的正整數）。結點地址是一個非負的5位整數，NULL指針用-1表示。

隨后N行，每行按下列格式給出一個結點的信息：

Address Key Next

其中Address是結點的地址，Key是絕對值不超過10⁴的整數，Next是下一個結點的地址。

輸出格式：

首先輸出去重后的鏈表，然后輸出被刪除結點組成的鏈表。每個結點占一行，按輸入的格式輸出。

輸入樣例： 00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854 輸出樣例： 00100 21 23854 23854 -15 99999 99999 -7 -1 00000 -15 87654 87654 15 -1

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <list> 6 7 using namespace std; 8 9 const int N = 1e6+10; 10 int ne[N], ke[N], book[10005]; 11 struct node 12 { 13 int add, key, next; 14 void setNode(int a, int k, int n){ 15 this->add = a; 16 this->key = k; 17 this->next = n; 18 } 19 }; 20 21 int main() 22 { 23 int s, n, pos; 24 while(cin>>s>>n) 25 { 26 int ad; 27 for(int i = 0; i < n; i++) 28 { 29 cin>>ad; 30 cin>>ke[ad]>>ne[ad]; 31 } 32 list<node> l1, l2; 33 list<node>::iterator it; 34 node tmp; 35 memset(book, 0, sizeof(book)); 36 pos = s; 37 book[abs(s)] = 1; 38 tmp.setNode(pos, ke[pos], ne[pos]); 39 l1.push_back(tmp); 40 pos = ne[pos]; 41 while(pos != -1) 42 { 43 if(book[abs(ke[pos])]){ 44 if(!l2.empty()){ 45 tmp = l2.back(); 46 tmp.next = pos; 47 l2.pop_back(); 48 l2.push_back(tmp); 49 } 50 tmp.setNode(pos, ke[pos], ne[pos]); 51 l2.push_back(tmp); 52 }else{ 53 book[abs(ke[pos])] = 1; 54 if(!l1.empty()){ 55 tmp = l1.back(); 56 tmp.next = pos; 57 l1.pop_back(); 58 l1.push_back(tmp); 59 } 60 tmp.setNode(pos, ke[pos], ne[pos]); 61 l1.push_back(tmp); 62 } 63 pos = ne[pos]; 64 } 65 tmp = l1.back(); tmp.next = -1; 66 l1.pop_back();l1.push_back(tmp); 67 for(it = l1.begin(); it != l1.end(); it++){ 68 if(it->next == -1)printf("%05d %d %d\n", it->add, it->key, it->next); 69 else printf("%05d %d %05d\n", it->add, it->key, it->next); 70 } 71 if(!l2.empty()){ 72 tmp = l2.back(); tmp.next = -1; 73 l2.pop_back();l2.push_back(tmp); 74 } 75 for(it = l2.begin(); it != l2.end(); it++){ 76 if(it->next == -1)printf("%05d %d %d\n", it->add, it->key, it->next); 77 else printf("%05d %d %05d\n", it->add, it->key, it->next); 78 } 79 } 80 81 return 0; 82 } View Code

L2-003. 月餅

月餅是中國人在中秋佳節時吃的一種傳統食品，不同地區有許多不同風味的月餅。現給定所有種類月餅的庫存量、總售價、以及市場的最大需求量，請你計算可以獲得的最大收益是多少。

注意：銷售時允許取出一部分庫存。樣例給出的情形是這樣的：假如我們有3種月餅，其庫存量分別為18、15、10萬噸，總售價分別為75、72、45億元。如果市場的最大需求量只有20萬噸，那么我們最大收益策略應該是賣出全部15萬噸第2種月餅、以及5萬噸第3種月餅，獲得 72 + 45/2 = 94.5（億元）。

輸入格式：

每個輸入包含1個測試用例。每個測試用例先給出一個不超過1000的正整數N表示月餅的種類數、以及不超過500（以萬噸為單位）的正整數D表示市場最大需求量。隨后一行給出N個正數表示每種月餅的庫存量（以萬噸為單位）；最后一行給出N個正數表示每種月餅的總售價（以億元為單位）。數字間以空格分隔。

輸出格式：

對每組測試用例，在一行中輸出最大收益，以億元為單位并精確到小數點后2位。

輸入樣例： 3 20 18 15 10 75 72 45 輸出樣例： 94.50 1 //2017-03-18 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 1005; 10 struct node{ 11 double a, b; 12 double c; 13 bool operator < (const node& x){ 14 return c > x.c; 15 } 16 }moom[N]; 17 18 int main() 19 { 20 int n, need; 21 while(cin>>n>>need) 22 { 23 for(int i = 0; i < n; i++) 24 cin>>moom[i].a; 25 for(int i = 0; i < n; i++) 26 cin>>moom[i].b; 27 for(int i = 0; i < n; i++) 28 moom[i].c = moom[i].b*1.0/moom[i].a; 29 sort(moom, moom+n); 30 double ans = 0; 31 for(int i = 0; i < n; i++) 32 { 33 if(need < moom[i].a){ 34 ans += moom[i].c*need; 35 break; 36 }else{ 37 ans += moom[i].b; 38 need -= moom[i].a; 39 } 40 } 41 printf("%.2lf\n", ans); 42 } 43 44 return 0; 45 } View Code

L2-004. 這是二叉搜索樹嗎？

一棵二叉搜索樹可被遞歸地定義為具有下列性質的二叉樹：對于任一結點，

其左子樹中所有結點的鍵值小于該結點的鍵值；
其右子樹中所有結點的鍵值大于等于該結點的鍵值；
其左右子樹都是二叉搜索樹。

所謂二叉搜索樹的“鏡像”，即將所有結點的左右子樹對換位置后所得到的樹。

給定一個整數鍵值序列，現請你編寫程序，判斷這是否是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果。

輸入格式：

輸入的第一行給出正整數N（<=1000）。隨后一行給出N個整數鍵值，其間以空格分隔。

輸出格式：

如果輸入序列是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果，則首先在一行中輸出“YES”，然后在下一行輸出該樹后序遍歷的結果。數字間有1個空格，一行的首尾不得有多余空格。若答案是否，則輸出“NO”。

輸入樣例1： 7 8 6 5 7 10 8 11 輸出樣例1： YES 5 7 6 8 11 10 8 輸入樣例2： 7 8 10 11 8 6 7 5 輸出樣例2： YES 11 8 10 7 5 6 8 輸入樣例3： 7 8 6 8 5 10 9 11 輸出樣例3： NO 1 //2017-03-19 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 6 using namespace std; 7 8 const int N = 1005; 9 int bt[N], bst1[N], bst2[N], ANS[N], n, cnt; 10 struct node{ 11 int data; 12 node *lson, *rson; 13 node(int d):data(d), lson(NULL), rson(NULL){} 14 }; 15 16 class BST 17 { 18 public: 19 node *rt; 20 BST():rt(NULL){} 21 void insert(int a) 22 { 23 node* nd = new node(a); 24 if(rt == NULL){ 25 rt = nd; 26 }else{ 27 node *p = rt, *q = NULL; 28 while(p != NULL){ 29 q = p; 30 if(a < p->data){ 31 p = p->lson; 32 }else{ 33 p = p->rson; 34 } 35 } 36 if(a < q->data)q->lson = nd; 37 else q->rson = nd; 38 } 39 } 40 }; 41 42 void preOrder1(node* id) 43 { 44 if(id != NULL) 45 { 46 bst1[cnt] = id->data; 47 cnt++; 48 preOrder1(id->lson); 49 preOrder1(id->rson); 50 } 51 } 52 53 void preOrder2(node* id) 54 { 55 if(id != NULL) 56 { 57 bst2[cnt] = id->data; 58 cnt++; 59 preOrder2(id->rson); 60 preOrder2(id->lson); 61 } 62 } 63 64 void postOrder1(node* id) 65 { 66 if(id != NULL){ 67 postOrder1(id->lson); 68 postOrder1(id->rson); 69 ANS[cnt] = id->data; 70 cnt++; 71 } 72 } 73 74 void postOrder2(node* id) 75 { 76 if(id != NULL){ 77 postOrder2(id->rson); 78 postOrder2(id->lson); 79 ANS[cnt] = id->data; 80 cnt++; 81 } 82 } 83 84 int main() 85 { 86 while(cin>>n) 87 { 88 BST bst; 89 for(int i = 0; i < n; i++) 90 { 91 cin>>bt[i]; 92 bst.insert(bt[i]); 93 } 94 cnt = 0; 95 preOrder1(bst.rt); 96 cnt = 0; 97 preOrder2(bst.rt); 98 bool fg1 = true, fg2 = true; 99 for(int i = 0; i < n; i++){ 100 if(bt[i] != bst1[i])fg1 = false; 101 if(bt[i] != bst2[i])fg2 = false; 102 } 103 if(fg1){ 104 cout<<"YES"<<endl; 105 cnt = 0; 106 postOrder1(bst.rt); 107 for(int i = 0; i < n; i++) 108 if(i == n-1)cout<<ANS[i]<<endl; 109 else cout<<ANS[i]<<" "; 110 }else if(fg2){ 111 cout<<"YES"<<endl; 112 cnt = 0; 113 postOrder2(bst.rt); 114 for(int i = 0; i < n; i++) 115 if(i == n-1)cout<<ANS[i]<<endl; 116 else cout<<ANS[i]<<" "; 117 }else cout<<"NO"<<endl; 118 } 119 120 return 0; 121 } View Code

L2-005. 集合相似度

給定兩個整數集合，它們的相似度定義為：N_c/N_t*100%。其中N_c是兩個集合都有的不相等整數的個數，N_t是兩個集合一共有的不相等整數的個數。你的任務就是計算任意一對給定集合的相似度。

輸入格式：

輸入第一行給出一個正整數N（<=50），是集合的個數。隨后N行，每行對應一個集合。每個集合首先給出一個正整數M（<=10⁴），是集合中元素的個數；然后跟M個[0, 10⁹]區間內的整數。

之后一行給出一個正整數K（<=2000），隨后K行，每行對應一對需要計算相似度的集合的編號（集合從1到N編號）。數字間以空格分隔。

輸出格式：

對每一對需要計算的集合，在一行中輸出它們的相似度，為保留小數點后2位的百分比數字。

輸入樣例： 3 3 99 87 101 4 87 101 5 87 7 99 101 18 5 135 18 99 2 1 2 1 3 輸出樣例： 50.00% 33.33% 1 //2017-03-19 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <set> 7 8 using namespace std; 9 10 int se[55][1005], cnt[55]; 11 12 double merge(int a, int b) 13 { 14 int nt = 0, nc = 0; 15 int cnt1 = 0, cnt2 = 0; 16 while(cnt1 < cnt[a] && cnt2 < cnt[b]) 17 { 18 if(se[a][cnt1] < se[b][cnt2]){ 19 nt++; 20 cnt1++; 21 }else if(se[a][cnt1] > se[b][cnt2]){ 22 nt++; 23 cnt2++; 24 }else{ 25 nt++; 26 nc++; 27 cnt1++; 28 cnt2++; 29 } 30 } 31 if(cnt1<cnt[a])nt += cnt[a]-cnt1; 32 if(cnt2<cnt[b])nt += cnt[b]-cnt2; 33 return nc*1.0/nt; 34 } 35 36 int main() 37 { 38 int n, m, a; 39 while(cin>>n) 40 { 41 memset(cnt, 0, sizeof(cnt)); 42 for(int i = 1; i <= n; i++) 43 { 44 cin>>m; 45 set<int> S; 46 set<int>::iterator it; 47 for(int j = 0; j < m; j++) 48 { 49 cin>>a; 50 it = S.find(a); 51 if(it == S.end()){ 52 S.insert(a); 53 se[i][cnt[i]] = a; 54 cnt[i]++; 55 } 56 } 57 sort(se[i], se[i]+cnt[i]); 58 } 59 cin>>m; 60 int s1, s2; 61 while(m--) 62 { 63 cin>>s1>>s2; 64 double ans = merge(s1, s2)*100; 65 printf("%.2lf%\n", ans); 66 } 67 } 68 69 return 0; 70 } View Code

L2-006. 樹的遍歷

給定一棵二叉樹的后序遍歷和中序遍歷，請你輸出其層序遍歷的序列。這里假設鍵值都是互不相等的正整數。

輸入格式：

輸入第一行給出一個正整數N（<=30），是二叉樹中結點的個數。第二行給出其后序遍歷序列。第三行給出其中序遍歷序列。數字間以空格分隔。

輸出格式：

在一行中輸出該樹的層序遍歷的序列。數字間以1個空格分隔，行首尾不得有多余空格。

輸入樣例： 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 輸出樣例： 4 1 6 3 5 7 2 1 //2017-03-20 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 7 using namespace std; 8 9 int post[35], in[35], ANS[35]; 10 struct node{ 11 int data; 12 node *lson, *rson; 13 node(int d):data(d), lson(NULL), rson(NULL){} 14 }; 15 16 struct BT{ 17 node *root; 18 void rebuild(int n) 19 { 20 root = buildTree(post, in, n); 21 } 22 node* buildTree(int *post, int *in, int n) 23 { 24 if(n < 1)return NULL; 25 node *rt = new node(post[n-1]); 26 if(n == 1)return rt; 27 int R; 28 for(int i = 0; i < n; i++) 29 { 30 if(in[i] == post[n-1]){ 31 R = i; 32 break; 33 } 34 } 35 rt->lson = buildTree(post, in, R); 36 rt->rson = buildTree(post+R, in+R+1, n-R-1); 37 return rt; 38 } 39 void levelOrder() 40 { 41 queue<node*> q; 42 q.push(root); 43 node *h; 44 int cnt = 0; 45 while(!q.empty()){ 46 h = q.front(); 47 q.pop(); 48 ANS[cnt++] = h->data; 49 if(h->lson)q.push(h->lson); 50 if(h->rson)q.push(h->rson); 51 } 52 for(int i = 0; i < cnt; i++) 53 if(i == cnt-1)cout<<ANS[i]<<endl; 54 else cout<<ANS[i]<<" "; 55 } 56 }; 57 58 int main() 59 { 60 int n; 61 while(cin>>n) 62 { 63 for(int i = 0; i < n; i++) 64 cin>>post[i]; 65 for(int i = 0; i < n; i++) 66 cin>>in[i]; 67 BT bt; 68 bt.rebuild(n); 69 bt.levelOrder(); 70 } 71 72 return 0; 73 } View Code

L2-008. 最長對稱子串

對給定的字符串，本題要求你輸出最長對稱子串的長度。例如，給定"Is PAT&TAP symmetric?"，最長對稱子串為"s PAT&TAP s"，于是你應該輸出11。

輸入格式：

輸入在一行中給出長度不超過1000的非空字符串。

輸出格式：

在一行中輸出最長對稱子串的長度。

輸入樣例： Is PAT&TAP symmetric? 輸出樣例： 11 1 //2017-03-19 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 6 using namespace std; 7 8 string str; 9 int len; 10 11 int search(int pos) 12 { 13 int l, r, ans = 1; 14 l = pos-1; 15 r = pos+1; 16 while(l >= 0 && r < len) 17 { 18 if(str[l] == str[r]) 19 { 20 ans+=2; 21 l--; 22 r++; 23 }else break; 24 } 25 return ans; 26 } 27 28 int search2(int pos) 29 { 30 int l, r, ans = 0; 31 l = pos; 32 r = pos+1; 33 while(l >= 0 && r < len) 34 { 35 if(str[l] == str[r]) 36 { 37 ans+=2; 38 l--; 39 r++; 40 }else break; 41 } 42 return ans; 43 } 44 45 int main() 46 { 47 while(getline(cin, str)) 48 { 49 len = str.length(); 50 int ans = 0, tmp; 51 for(int i = 0; i < len; i++) 52 { 53 tmp = search(i); 54 if(tmp>ans)ans = tmp; 55 tmp = search2(i); 56 if(tmp>ans)ans = tmp; 57 } 58 cout<<ans<<endl; 59 } 60 61 return 0; 62 } View Code

L2-009. 搶紅包

沒有人沒搶過紅包吧…… 這里給出N個人之間互相發紅包、搶紅包的記錄，請你統計一下他們搶紅包的收獲。

輸入格式：

輸入第一行給出一個正整數N（<= 10⁴），即參與發紅包和搶紅包的總人數，則這些人從1到N編號。隨后N行，第i行給出編號為i的人發紅包的記錄，格式如下：

K N₁?P₁?... N_K?P_K

其中K（0 <= K <= 20）是發出去的紅包個數，N_i是搶到紅包的人的編號，P_i（> 0）是其搶到的紅包金額（以分為單位）。注意：對于同一個人發出的紅包，每人最多只能搶1次，不能重復搶。

輸出格式：

按照收入金額從高到低的遞減順序輸出每個人的編號和收入金額（以元為單位，輸出小數點后2位）。每個人的信息占一行，兩數字間有1個空格。如果收入金額有并列，則按搶到紅包的個數遞減輸出；如果還有并列，則按個人編號遞增輸出。

輸入樣例： 10 3 2 22 10 58 8 125 5 1 345 3 211 5 233 7 13 8 101 1 7 8800 2 1 1000 2 1000 2 4 250 10 320 6 5 11 9 22 8 33 7 44 10 55 4 2 1 3 8800 2 1 23 2 123 1 8 250 4 2 121 4 516 7 112 9 10 輸出樣例： 1 11.63 2 3.63 8 3.63 3 2.11 7 1.69 6 -1.67 9 -2.18 10 -3.26 5 -3.26 4 -12.32

1 //2017-03-19 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 10010; 10 struct node{ 11 int id, cnt; 12 double out, in; 13 double fin; 14 bool operator <(node x) 15 { 16 if(fin == x.fin)return cnt > x.cnt; 17 return fin > x.fin; 18 } 19 }man[N]; 20 21 int main() 22 { 23 int n, k; 24 while(cin>>n) 25 { 26 for(int i = 1; i <= n; i++) 27 { 28 man[i].in = 0; 29 man[i].out = 0; 30 man[i].cnt = 0; 31 } 32 for(int i = 1; i <= n; i++) 33 { 34 man[i].id = i; 35 cin>>k; 36 int id, monky; 37 while(k--) 38 { 39 cin>>id>>monky; 40 man[id].in += monky; 41 man[i].out += monky; 42 man[id].cnt++; 43 } 44 } 45 for(int i = 1; i <= n; i++) 46 man[i].fin = (man[i].in-man[i].out)/100; 47 sort(man+1, man+n+1); 48 for(int i = 1; i <= n; i++) 49 printf("%d %.2lf\n", man[i].id, man[i].fin); 50 } 51 52 return 0; 53 } View Code

L2-010. 排座位

布置宴席最微妙的事情，就是給前來參宴的各位賓客安排座位。無論如何，總不能把兩個死對頭排到同一張宴會桌旁！這個艱巨任務現在就交給你，對任何一對客人，請編寫程序告訴主人他們是否能被安排同席。

輸入格式：

輸入第一行給出3個正整數：N（<= 100），即前來參宴的賓客總人數，則這些人從1到N編號；M為已知兩兩賓客之間的關系數；K為查詢的條數。隨后M行，每行給出一對賓客之間的關系，格式為：“賓客1 賓客2 關系”，其中“關系”為1表示是朋友，-1表示是死對頭。注意兩個人不可能既是朋友又是敵人。最后K行，每行給出一對需要查詢的賓客編號。

這里假設朋友的朋友也是朋友。但敵人的敵人并不一定就是朋友，朋友的敵人也不一定是敵人。只有單純直接的敵對關系才是絕對不能同席的。

輸出格式：

對每個查詢輸出一行結果：如果兩位賓客之間是朋友，且沒有敵對關系，則輸出“No problem”；如果他們之間并不是朋友，但也不敵對，則輸出“OK”；如果他們之間有敵對，然而也有共同的朋友，則輸出“OK but...”；如果他們之間只有敵對關系，則輸出“No way”。

輸入樣例： 7 8 4 5 6 1 2 7 -1 1 3 1 3 4 1 6 7 -1 1 2 1 1 4 1 2 3 -1 3 4 5 7 2 3 7 2 輸出樣例： No problem OK OK but... No way 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int G[105][105]; 8 int n; 9 10 void query(int a, int b) 11 { 12 if(G[a][b] == 0){ 13 for(int i = 1; i <= n; i++) 14 if(G[a][i] == 1 && G[b][i] == 1){ 15 cout<<"No problem"<<endl; 16 return; 17 } 18 cout<<"OK"<<endl; 19 }else if(G[a][b] == 1){ 20 for(int i = 1; i <= n; i++) 21 if(G[a][i] == -1 && G[b][i] == -1) 22 return; 23 cout<<"No problem"<<endl; 24 }else if(G[a][b] == -1){ 25 for(int i = 1; i <= n; i++) 26 if(G[a][i] == 1 && G[b][i] == 1){ 27 cout<<"OK but..."<<endl; 28 return; 29 } 30 cout<<"No way"<<endl; 31 } 32 } 33 34 int main() 35 { 36 int m, q, u, v, re; 37 while(cin>>n>>m>>q) 38 { 39 memset(G, 0, sizeof(G)); 40 for(int i = 0; i < m; i++) 41 { 42 cin>>u>>v>>re; 43 G[u][v] = G[v][u] = re; 44 } 45 while(q--) 46 { 47 cin>>u>>v; 48 query(u, v); 49 } 50 } 51 52 return 0; 53 } View Code

L2-011. 玩轉二叉樹

給定一棵二叉樹的中序遍歷和前序遍歷，請你先將樹做個鏡面反轉，再輸出反轉后的層序遍歷的序列。所謂鏡面反轉，是指將所有非葉結點的左右孩子對換。這里假設鍵值都是互不相等的正整數。

輸入格式：

輸入第一行給出一個正整數N（<=30），是二叉樹中結點的個數。第二行給出其中序遍歷序列。第三行給出其前序遍歷序列。數字間以空格分隔。

輸出格式：

在一行中輸出該樹反轉后的層序遍歷的序列。數字間以1個空格分隔，行首尾不得有多余空格。

輸入樣例： 7 1 2 3 4 5 6 7 4 1 3 2 6 5 7 輸出樣例： 4 6 1 7 5 3 2 1 //2017-03-20 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 7 using namespace std; 8 9 int pre[35], in[35], ANS[35]; 10 struct node{ 11 int data; 12 node *lson, *rson; 13 node(int d):data(d), lson(NULL), rson(NULL){} 14 }; 15 16 struct BT{ 17 node *root; 18 void rebuild(int n) 19 { 20 root = buildTree(pre, in, n); 21 } 22 node* buildTree(int *pre, int *in, int n) 23 { 24 if(n < 1)return NULL; 25 node *rt = new node(pre[0]); 26 if(n == 1)return rt; 27 int R; 28 for(int i = 0; i < n; i++) 29 { 30 if(in[i] == pre[0]){ 31 R = i; 32 break; 33 } 34 } 35 rt->lson = buildTree(pre+1, in, R); 36 rt->rson = buildTree(pre+1+R, in+R+1, n-R-1); 37 return rt; 38 } 39 void levelOrder() 40 { 41 queue<node*> q; 42 q.push(root); 43 node *h; 44 int cnt = 0; 45 while(!q.empty()){ 46 h = q.front(); 47 q.pop(); 48 ANS[cnt++] = h->data; 49 if(h->rson)q.push(h->rson); 50 if(h->lson)q.push(h->lson); 51 } 52 for(int i = 0; i < cnt; i++) 53 if(i == cnt-1)cout<<ANS[i]<<endl; 54 else cout<<ANS[i]<<" "; 55 } 56 }; 57 58 int main() 59 { 60 int n; 61 while(cin>>n) 62 { 63 for(int i = 0; i < n; i++) 64 cin>>in[i]; 65 for(int i = 0; i < n; i++) 66 cin>>pre[i]; 67 BT bt; 68 bt.rebuild(n); 69 bt.levelOrder(); 70 } 71 72 return 0; 73 } View Code

L2-012. 關于堆的判斷

將一系列給定數字順序插入一個初始為空的小頂堆H[]。隨后判斷一系列相關命題是否為真。命題分下列幾種：

“x is the root”：x是根結點；
“x and y are siblings”：x和y是兄弟結點；
“x is the parent of y”：x是y的父結點；
“x is a child of y”：x是y的一個子結點。

輸入格式：

每組測試第1行包含2個正整數N（<= 1000）和M（<= 20），分別是插入元素的個數、以及需要判斷的命題數。下一行給出區間[-10000, 10000]內的N個要被插入一個初始為空的小頂堆的整數。之后M行，每行給出一個命題。題目保證命題中的結點鍵值都是存在的。

輸出格式：

對輸入的每個命題，如果其為真，則在一行中輸出“T”，否則輸出“F”。

輸入樣例： 5 4 46 23 26 24 10 24 is the root 26 and 23 are siblings 46 is the parent of 23 23 is a child of 10 輸出樣例： F T F T 1 //2017-03-20 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 6 using namespace std; 7 8 struct Heap{ 9 int h[1010]; 10 int n; 11 void init() 12 { 13 n = 0; 14 } 15 void shiftup(int pos) 16 { 17 int fa, tmp; 18 while(pos >= 0){ 19 fa = (pos-1)/2; 20 if(h[fa]>h[pos]){ 21 tmp = h[pos]; 22 h[pos] = h[fa]; 23 h[fa] = tmp; 24 pos = fa; 25 }else break; 26 } 27 } 28 void addNode(int x) 29 { 30 h[n++] = x; 31 shiftup(n-1); 32 } 33 void show(){ 34 for(int i = 0; i < n; i++) 35 cout<<h[i]<<" "; 36 cout<<endl; 37 } 38 }; 39 40 int main() 41 { 42 int n,m; 43 while(cin>>n>>m) 44 { 45 Heap heap; 46 heap.init(); 47 int a; 48 for(int i = 0; i < n; i++) 49 { 50 cin>>a; 51 heap.addNode(a); 52 } 53 int x, y; 54 string s1, s2, s3, s4; 55 while(m--) 56 { 57 cin>>x; 58 cin>>s1; 59 if(s1[0] == 'a'){ 60 cin>>y>>s2>>s3; 61 int p1, p2; 62 for(int i = 0; i < heap.n; i++) 63 { 64 if(heap.h[i] == x)p1 = i; 65 if(heap.h[i] == y)p2 = i; 66 } 67 if((p1-1)/2 == (p2-1)/2)cout<<"T"<<endl; 68 else cout<<"F"<<endl; 69 }else{ 70 cin>>s2; 71 if(s2[0] == 'a'){ 72 cin>>s3>>s4>>y; 73 int p1, p2; 74 for(int i = 0; i < heap.n; i++) 75 { 76 if(heap.h[i] == x)p1 = i; 77 if(heap.h[i] == y)p2 = i; 78 } 79 if((p1-1)/2 == p2)cout<<"T"<<endl; 80 else cout<<"F"<<endl; 81 }else{ 82 cin>>s3; 83 if(s3[0] == 'r'){ 84 if(heap.h[0] == x)cout<<"T"<<endl; 85 else cout<<"F"<<endl; 86 }else{ 87 cin>>s4>>y; 88 int p1, p2; 89 for(int i = 0; i < heap.n; i++){ 90 if(heap.h[i] == x)p1 = i; 91 if(heap.h[i] == y)p2 = i; 92 } 93 if((p2-1)/2 == p1)cout<<"T"<<endl; 94 else cout<<"F"<<endl; 95 } 96 } 97 } 98 } 99 } 100 101 return 0; 102 } View Code

L2-017. 人以群分

社交網絡中我們給每個人定義了一個“活躍度”，現希望根據這個指標把人群分為兩大類，即外向型（outgoing，即活躍度高的）和內向型（introverted，即活躍度低的）。要求兩類人群的規模盡可能接近，而他們的總活躍度差距盡可能拉開。

輸入格式：

輸入第一行給出一個正整數N（2 <= N <= 10⁵）。隨后一行給出N個正整數，分別是每個人的活躍度，其間以空格分隔。題目保證這些數字以及它們的和都不會超過2³¹。

輸出格式：

按下列格式輸出：

Outgoing #: N1 Introverted #: N2 Diff = N3

其中 N1 是外向型人的個數；N2 是內向型人的個數；N3 是兩群人總活躍度之差的絕對值。

輸入樣例1： 10 23 8 10 99 46 2333 46 1 666 555 輸出樣例1： Outgoing #: 5 Introverted #: 5 Diff = 3611 輸入樣例2： 13 110 79 218 69 3721 100 29 135 2 6 13 5188 85 輸出樣例2： Outgoing #: 7 Introverted #: 6 Diff = 9359 1 //2018-03-14 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 100005; 10 int arr[N]; 11 12 int main() 13 { 14 int n; 15 while(~scanf("%d", &n)){ 16 for(int i = 0; i < n; i++) 17 scanf("%d", &arr[i]); 18 sort(arr, arr+n); 19 int in = n/2; 20 int sumIn = 0, sumOut = 0; 21 for(int i= 0; i < n; i++){ 22 if(i < in) sumIn += arr[i]; 23 else sumOut += arr[i]; 24 } 25 printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d\n", n-in, in, sumOut-sumIn); 26 } 27 28 return 0; 29 } View Code

L2-019. 悄悄關注

新浪微博上有個“悄悄關注”，一個用戶悄悄關注的人，不出現在這個用戶的關注列表上，但系統會推送其悄悄關注的人發表的微博給該用戶。現在我們來做一回網絡偵探，根據某人的關注列表和其對其他用戶的點贊情況，扒出有可能被其悄悄關注的人。

輸入格式：

輸入首先在第一行給出某用戶的關注列表，格式如下：

人數N 用戶1 用戶2 …… 用戶N

其中N是不超過5000的正整數，每個“用戶i”（i=1, ..., N）是被其關注的用戶的ID，是長度為4位的由數字和英文字母組成的字符串，各項間以空格分隔。

之后給出該用戶點贊的信息：首先給出一個不超過10000的正整數M，隨后M行，每行給出一個被其點贊的用戶ID和對該用戶的點贊次數（不超過1000），以空格分隔。注意：用戶ID是一個用戶的唯一身份標識。題目保證在關注列表中沒有重復用戶，在點贊信息中也沒有重復用戶。

輸出格式：

我們認為被該用戶點贊次數大于其點贊平均數、且不在其關注列表上的人，很可能是其悄悄關注的人。根據這個假設，請你按用戶ID字母序的升序輸出可能是其悄悄關注的人，每行1個ID。如果其實并沒有這樣的人，則輸出“Bing Mei You”。

輸入樣例1： 10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao 8 Magi 50 Pota 30 LLao 3 Ammy 48 Dave 15 GAO3 31 Zoro 1 Cath 60 輸出樣例1： Ammy Cath Pota 輸入樣例2： 11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota 7 Magi 50 Pota 30 LLao 48 Ammy 3 Dave 15 GAO3 31 Zoro 29 輸出樣例2： Bing Mei You 1 //2018-03-14 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #include <set> 7 8 using namespace std; 9 10 const int N = 5005; 11 12 string strs[2*N]; 13 int arr[2*N]; 14 set<string> st, ans_st; 15 16 int main() 17 { 18 int n, m; 19 while(cin>>n){ 20 string str; 21 st.clear(); 22 for(int i = 0; i < n; i++){ 23 cin>>str; 24 st.insert(str); 25 } 26 cin>>m; 27 int sum = 0; 28 for(int i = 0; i < m; i++){ 29 cin>>strs[i]>>arr[i]; 30 sum += arr[i]; 31 } 32 double avg = 1.0*sum/m; 33 set<string>::iterator iter; 34 ans_st.clear(); 35 for(int i = 0; i < m; i++){ 36 if((iter = st.find(strs[i])) == st.end() && arr[i] > avg){ 37 ans_st.insert(strs[i]); 38 } 39 } 40 if(ans_st.empty()){ 41 cout<<"Bing Mei You"<<endl; 42 }else{ 43 for(auto x: ans_st){ 44 cout<<x<<endl; 45 } 46 } 47 } 48 49 return 0; 50 } View Code

L2-020. 功夫傳人

一門武功能否傳承久遠并被發揚光大，是要看緣分的。一般來說，師傅傳授給徒弟的武功總要打個折扣，于是越往后傳，弟子們的功夫就越弱…… 直到某一支的某一代突然出現一個天分特別高的弟子（或者是吃到了靈丹、挖到了特別的秘笈），會將功夫的威力一下子放大N倍 —— 我們稱這種弟子為“得道者”。

這里我們來考察某一位祖師爺門下的徒子徒孫家譜：假設家譜中的每個人只有1位師傅（除了祖師爺沒有師傅）；每位師傅可以帶很多徒弟；并且假設輩分嚴格有序，即祖師爺這門武功的每個第i代傳人只能在第i-1代傳人中拜1個師傅。我們假設已知祖師爺的功力值為Z，每向下傳承一代，就會減弱r%，除非某一代弟子得道。現給出師門譜系關系，要求你算出所有得道者的功力總值。

輸入格式：

輸入在第一行給出3個正整數，分別是：N（<=10⁵）——整個師門的總人數（于是每個人從0到N-1編號，祖師爺的編號為0）；Z——祖師爺的功力值（不一定是整數，但起碼是正數）；r ——每傳一代功夫所打的折扣百分比值（不超過100的正數）。接下來有N行，第i行（i=0, ..., N-1）描述編號為i的人所傳的徒弟，格式為：

K_i?ID[1] ID[2] ... ID[K_i]

其中K_i是徒弟的個數，后面跟的是各位徒弟的編號，數字間以空格間隔。K_i為零表示這是一位得道者，這時后面跟的一個數字表示其武功被放大的倍數。

輸出格式：

在一行中輸出所有得道者的功力總值，只保留其整數部分。題目保證輸入和正確的輸出都不超過10¹⁰。

輸入樣例： 10 18.0 1.00 3 2 3 5 1 9 1 4 1 7 0 7 2 6 1 1 8 0 9 0 4 0 3 輸出樣例： 404 1 //2018-03-15 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #include <cmath> 7 8 using namespace std; 9 10 const int N = 100005; 11 int fa[N], dd_id[N], dd_bs[N], depth[N]; 12 13 int getDepth(int x){ 14 if(fa[x] == x)return 0; 15 if(depth[x])return depth[x]; 16 return depth[x] = getDepth(fa[x])+1; 17 } 18 19 int main() 20 { 21 int n, k; 22 double Z, r; 23 while(cin>>n>>Z>>r){ 24 r = (100-r)/100; 25 int cnt = 0, tmp; 26 memset(depth, 0, sizeof(depth)); 27 for(int i = 0; i < n; i++) 28 fa[i] = i; 29 for(int i = 0; i < n; i++){ 30 cin >> k; 31 if(!k){ 32 cin>>tmp; 33 dd_id[cnt] = i; 34 dd_bs[cnt++] = tmp; 35 }else{ 36 while(k--){ 37 cin>>tmp; 38 fa[tmp] = i; 39 } 40 } 41 } 42 double sum = 0; 43 for(int i = 0; i < cnt; i++){ 44 double dsum = Z*dd_bs[i]; 45 int dp = getDepth(dd_id[i]); 46 dsum *= pow(r, dp); 47 sum += dsum; 48 } 49 cout<<(int)sum<<endl; 50 } 51 52 return 0; 53 } View Code

L2-021. 點贊狂魔

微博上有個“點贊”功能，你可以為你喜歡的博文點個贊表示支持。每篇博文都有一些刻畫其特性的標簽，而你點贊的博文的類型，也間接刻畫了你的特性。然而有這么一種人，他們會通過給自己看到的一切內容點贊來狂刷存在感，這種人就被稱為“點贊狂魔”。他們點贊的標簽非常分散，無法體現出明顯的特性。本題就要求你寫個程序，通過統計每個人點贊的不同標簽的數量，找出前3名點贊狂魔。

輸入格式：

輸入在第一行給出一個正整數N（<=100），是待統計的用戶數。隨后N行，每行列出一位用戶的點贊標簽。格式為“Name K F₁?... F_K”，其中 Name 是不超過8個英文小寫字母的非空用戶名，1<=K<=1000，F_i（i=1, ..., K）是特性標簽的編號，我們將所有特性標簽從1到10⁷編號。數字間以空格分隔。

輸出格式：

統計每個人點贊的不同標簽的數量，找出數量最大的前3名，在一行中順序輸出他們的用戶名,其間以1個空格分隔,且行末不得有多余空格。如果有并列，則輸出標簽出現次數平均值最小的那個，題目保證這樣的用戶沒有并列。若不足3人，則用“-”補齊缺失，例如“mike jenny -”就表示只有2人。

輸入樣例： 5 bob 11 101 102 103 104 105 106 107 108 108 107 107 peter 8 1 2 3 4 3 2 5 1 chris 12 1 2 3 4 5 6 7 8 9 1 2 3 john 10 8 7 6 5 4 3 2 1 7 5 jack 9 6 7 8 9 10 11 12 13 14 輸出樣例： jack chris john

1 //2018-03-15 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 110; 10 11 struct Node{ 12 string name; 13 int len, uniLen; 14 15 bool operator<(Node node){ 16 if(uniLen == node.uniLen) 17 return len < node.len; 18 return uniLen > node.uniLen; 19 } 20 }person[N]; 21 22 int arr[1010]; 23 24 int main() 25 { 26 int n; 27 while(cin >> n){ 28 string str; 29 for(int i = 0; i < n; i++){ 30 cin>>person[i].name>>person[i].len; 31 for(int j = 0; j < person[i].len; j++) 32 scanf("%d", &arr[j]); 33 sort(arr, arr+person[i].len); 34 int cnt = unique(arr, arr+person[i].len) - arr; 35 person[i].uniLen = cnt; 36 } 37 sort(person, person+n); 38 if(n == 0)cout<<"- - -"<<endl; 39 else if(n == 1)cout<<person[0].name<<" - -"<<endl; 40 else if(n == 2)cout<<person[0].name<<" "<<person[1].name<<" -"<<endl; 41 else cout<<person[0].name<<" "<<person[1].name<<" "<<person[2].name<<endl; 42 } 43 44 return 0; 45 } View Code

L3-001. 湊零錢

韓梅梅喜歡滿宇宙到處逛街。現在她逛到了一家火星店里，發現這家店有個特別的規矩：你可以用任何星球的硬幣付錢，但是絕不找零，當然也不能欠債。韓梅梅手邊有10⁴枚來自各個星球的硬幣，需要請你幫她盤算一下，是否可能精確湊出要付的款額。

輸入格式：

輸入第一行給出兩個正整數：N（<=10⁴）是硬幣的總個數，M（<=10²）是韓梅梅要付的款額。第二行給出N枚硬幣的正整數面值。數字間以空格分隔。

輸出格式：

在一行中輸出硬幣的面值 V₁?<= V₂?<= ... <= V_k，滿足條件 V₁?+ V₂?+ ... + V_k?= M。數字間以1個空格分隔，行首尾不得有多余空格。若解不唯一，則輸出最小序列。若無解，則輸出“No Solution”。

注：我們說序列{A[1], A[2], ...}比{B[1], B[2], ...}“小”，是指存在 k >= 1 使得 A[i]=B[i] 對所有 i < k 成立，并且 A[k] < B[k]。

輸入樣例1： 8 9 5 9 8 7 2 3 4 1 輸出樣例1： 1 3 5 輸入樣例2： 4 8 7 2 4 3 輸出樣例2： No Solution 1 //2018-03-15 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 10010; 10 int arr[N], book[N], suffix_sum[N];//后綴和 11 int n, m; 12 bool ok; 13 14 void dfs(int step, int money){ 15 //剪枝 16 if(step > n || ok || money > m || money+suffix_sum[step] < m)return; 17 if(money == m){ 18 ok = true; 19 bool first = true; 20 for(int i = 0; i < n; i++){ 21 if(book[i]){ 22 if(first){ 23 printf("%d", arr[i]); 24 first = false; 25 }else{ 26 printf(" %d", arr[i]); 27 } 28 } 29 } 30 printf("\n"); 31 } 32 book[step] = 1; 33 dfs(step+1, money+arr[step]); 34 book[step] = 0; 35 dfs(step+1, money); 36 } 37 38 int main() 39 { 40 while(~scanf("%d%d", &n, &m)) 41 { 42 for(int i = 0; i < n; i++) 43 scanf("%d", &arr[i]); 44 sort(arr, arr+n); 45 suffix_sum[n] = 0; 46 for(int i = n-1; i >= 0; i--) 47 suffix_sum[i] = suffix_sum[i+1]+arr[i]; 48 ok = false; 49 memset(book, 0, sizeof(book)); 50 dfs(0, 0); 51 if(!ok)printf("No Solution\n"); 52 } 53 54 return 0; 55 } View Code

轉載于:https://www.cnblogs.com/Penn000/p/6568905.html

總結

以上是生活随笔為你收集整理的天梯赛2016-L2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

天梯

上一篇：网申高额信用卡的套路你知道吗？这三种需当
下一篇：交通银行账单查询方法盘点教你轻松查账单