2017广东工业大学程序设计竞赛决赛 题解源码(A,数学解方程，B,贪心博弈，C,递归，D,水，E,贪心，面试题，F,贪心，枚举，LCA，G,dp，记忆化搜索，H,思维题)...
心得：
這比賽真的是不要不要的，pending了一下午，也不知道對錯，直接做過去就是了，也沒有管太多！
Problem A: 兩只老虎
Description
?
來，我們先來放松下，聽聽兒歌，一起“唱”。
兩只老虎兩只老虎，跑得快跑得快。
一只沒有耳朵，一只沒有尾巴。
真奇怪，真奇怪。
Tmk也覺得很奇怪，因為在他面前突然出現了一群這樣的老虎，有的沒耳朵，有的沒尾巴，不過也有正常的。
現在Tmk告訴你這群老虎的耳朵個數，尾巴條數，以及老虎的腿的數目，問你有多少只是正常的。
其中只有三種老虎：
第一種（正常的）：有2個耳朵、1條尾巴、4條腿
第二種（沒耳朵）：有0個耳朵、1條尾巴、4條腿
第三種（沒尾巴）：有2個耳朵、0條尾巴、4條腿
Input
?
?
?
第一行一個整數T表示有多少組樣例。
接下來每一行一個樣例：
包含三個整數a，b，c表示總共有a個耳朵，b條尾巴，c(<=4000)條腿，數據保證有解。
Output
?
對于每組樣例輸出一行，表示有多少只正常的老虎。
Sample Input
1 12 7 40Sample Output
3HINT
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=0
分析：解方程咯，設以上三種情況分別為x，y，z，則有下列三個方程組：
2*x+2*z=a/2;
x+y=b;
4*x+4*y+4*z=c;
解得x=a/2+b-c/4;即為答案！
下面給出AC代碼：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int T; 6 int a,b,c; 7 while(cin>>T) 8 { 9 while(T--) 10 { 11 cin>>a>>b>>c; 12 c/=4; 13 a/=2; 14 int x=a+b-c; 15 printf("%d\n",x); 16 } 17 } 18 return 0; 19 }Problem B: 占點游戲
Description
?
?
?
?
?
眾所周知的是，TMK特別容易遲到，終于在TMK某次又遲到了之后，Maple怒了，Maple大喊一聲：“我要跟你決一死戰！”然后Maple就跟TMK玩起了一個關于占點的游戲。
Maple在一個無限展開的只有整數點的二維平面上找到兩個點，由TMK和Maple分別操控這兩個點，兩人輪流操作，每一次操作中TMK或Maple可以把他的點移動一格到上、下、左、右四個方向，當TMK操作時，移動到的這個點會被染成紅色，而當Maple操作時，移動到的這個點會被染成藍色，需要注意的是，兩個起始時的兩個點也都會被染上相應的顏色，而當任一人走到已經染了不同顏色的點，這個顏色會被覆蓋掉，當兩個點覆蓋在一起時，這個點會被后來的點染色。當游戲結束時染著自己顏色的點就代表被自己占領了。
TMK一下就明白了，這個游戲的目標是讓自己占領的點比對方占領的點多，而且要讓差值最大。
為了公平一些，Maple決定讓TMK來選擇先手或后手和讓TMK來選擇點，相應的Maple就會選擇另一個點。
現在給出游戲的總輪數N，Maple選擇的兩個點的坐標（x1，y1），（x2，y2），要TMK來選擇先后手和起始點，假設Maple一定按最優策略來走，問TMK能不能選擇先后手和起始點使得自己占領的點比Maple占領的多，如果能，那么同時要求出占領的點數的最大差值。
?
?
?
Input
?
?
?
第一行一個T，代表接下來有T組數據(1<=T<=2000)。
每組數據有五個整數N,x1,y1,x2,y2，代表了操作的總輪數N以及選擇的兩個起始點(x1,y1),(x2,y2)，其中1<=N<=10^8，-10^8<=x1,y1,x2,y2<=10^8，數據保證兩個點不相同。
?
Output
對于每一組數據，如果TMK占領的點不能比Maple占領的多，那么輸出-1，否則輸出兩個占領點數的最大差值。
Sample Input
4 1 0 0 1 0 2 0 0 1 0 1 0 0 2 0 2 0 0 2 0Sample Output
2 -1 1 -1HINT
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=1
分析：令 d = abs(x1-x2)+abs(y1-y2)
首先判斷(n+1)/2 >= d，先手可不可以從一個點走到另一個點 :
如果不可以，則先手可以多得 n&1 分（因為劣勢者可以選擇逃離）
如果可以，考慮 d 的奇偶性：
如果 d 為奇數（先手可以先踩到后手覆蓋過的點）：
如果 n 為奇數，先手可以多得 2 分，否則平。
否則（d 為偶數）:
如果 n 為奇數，先手可以多得 1 分，否則后手可以多得 1 分。
下面給出AC代碼：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n,x1,x2,y1,y2; 6 int T; 7 while(scanf("%d",&T)!=EOF) 8 { 9 while(T--) 10 { 11 scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2); 12 int d=abs(x1-x2)+abs(y1-y2); 13 int ans=-1; 14 if((n+1)/2>=d) 15 { 16 if(d%2!=0) 17 { 18 if(n%2!=0) 19 { 20 ans=2; 21 } 22 } 23 else 24 { 25 ans=1; 26 } 27 } 28 else if(n%2!=0) 29 { 30 ans=1; 31 } 32 printf("%d\n",ans); 33 } 34 } 35 return 0; 36 }?
Problem C: 爬樓梯
Description
?
小時候，我只能一階一階得爬樓梯，
后來，我除了能一次爬一階，還可以一次爬兩階，
到現在，我最多一次可以爬三階。
那么現在問題來了，我想爬上n層樓，相鄰樓層之間有一段樓梯，雖然我一次可以爬1個臺階、2個臺階和3個臺階，但是我在i與i+1層之間的樓梯上時，我不能跨越到i+1與i+2層之間的樓梯。現在有個n層的樓，知道每一段樓梯的階數，我想知道，如果我只會往上走，并且忽略其他不在樓梯上的其他移動，共有多少種方案可以到達第n層。
Input
?
第一行一個整數T（0<T<=50）表示有多少組樣例。
對于每一組樣例：
第一行一個n（1<n<=50）表示有多少層樓。
接下來一行，包括n-1個整數xi（0<xi<=20），由下到上依次表示每段樓梯的長度。
?
Output
?
對于每組數據，輸出一行表示共有多少種方案。由于答案較大，所以輸出答案請對10007取模。
?
Sample Input
2 2 3 4 4 5 6Sample Output
4 2184HINT
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=2
分析：遞歸求解,
C[0]=C[1]=1;C[2]=2;
C[i]=C[i-1]+C[i-2]+C[i-3];
此題給出的范圍剛好合適，大了應該會TL
1 #include <bits/stdc++.h> 2 using namespace std; 3 int b[55]; 4 int gcd(int n) 5 { 6 b[0]=1; 7 b[1]=1; 8 b[2]=2; 9 for(int i=3;i<=n;i++) 10 b[i]=b[i-1]+b[i-2]+b[i-3]; 11 return b[n]; 12 } 13 int main() 14 { 15 int T; 16 int n,t; 17 int a[55]; 18 while(cin>>T) 19 { 20 while(T--) 21 { 22 cin>>n; 23 int s=1; 24 for(int i=0;i<n-1;i++) 25 cin>>a[i]; 26 for(int i=0;i<n-1;i++) 27 { 28 int t=gcd(a[i]); 29 s*=t; 30 s%=10007; 31 } 32 printf("%d\n",s); 33 } 34 } 35 return 0; 36 }Problem D: 只有通過毀滅才能揭示真理
Description
?
“只有通過毀滅才能揭示真理。” —— 虛空之眼
維克茲是一個有觸手的虛空來客，他帶著非凡的意圖探索著符文之地：吸收掉所有知識。憑借著他不斷地注視，維克茲可以發射瓦解光線來滅除并分析他途中的一切東西，并為他供給數量龐大的信息。沒人知道他為什么需要如此多的材料，盡管有人推測他設法了解符文之地，是為了加速它的毀滅。
另外，維克茲本身也是一個極其強大的魔法師，他的技能會對命中的敵人施加有機體解構效果。如果累積到3層效果，敵人就會受到爆發性的真實傷害。
現在，維克茲正準備施展他的絕招 —— 生命形態瓦解射線，來對付被永久眩暈且沒有攜帶任何魔抗裝備的約德爾人。另外，他的絕招每10秒就可以對敵人累積一層有機體解構效果。
維克茲希望找到能夠跟他一起遨游大陸的伙伴，所以他準備考考你，如果已知生命形態瓦解射線持續的時間和每一秒的傷害，以及有機體解構效果每累積到3層所爆發的傷害（傷害爆發后層數歸零），你是否能算出約德爾人受到的總傷害是多少呢？
請注意，如果你回答不出來，維克茲絕對很樂意將你一起分解掉。
?
Input
?
輸入包括T組數據，每組數據包括生命形態瓦解射線的持續時間A，每一秒的傷害B，以及有機體解構效果每累積到3層所爆發的傷害C。
（T <= 10000, 0 <= A, B, C <= 10000, 所有數據皆為整數）
Output
?
輸出一個數代表約德爾人受到的總傷害。
?
Sample Input
2 10 10 10 30 10 10Sample Output
100 310HINT
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=3 分析：每三十次進一，類似于30進制，每十次傷害加c！ 下面給出AC代碼： 1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int T; 6 int a,b,c; 7 while(cin>>T) 8 { 9 while(T--) 10 { 11 cin>>a>>b>>c; 12 int ans=a*b; 13 int t=a/30; 14 while(t) 15 { 16 t--; 17 ans+=c; 18 } 19 cout<<ans<<endl; 20 } 21 } 22 return 0; 23 }Problem E: 倒水(Water)
Description
?
一天，CC買了N個容量可以認為是無限大的瓶子，開始時每個瓶子里有1升水。接著~~CC發現瓶子實在太多了，于是他決定保留不超過K個瓶子。每次他選擇兩個當前含水量相同的瓶子，把一個瓶子的水全部倒進另一個里，然后把空瓶丟棄。(不能丟棄有水的瓶子)
顯然在某些情況下CC無法達到目標，比如N=3,K=1。此時CC會重新買一些新的瓶子(新瓶子容量無限，開始時有1升水)，以到達目標。
現在CC想知道，最少需要買多少新瓶子才能達到目標呢？
Input
?
第一行一個整數T，表示有T組數據。
接著T行，每行兩個正整數， N,K(1<=N<=10^9，K<=1000)。
?
Output
?
一個非負整數，表示最少需要買多少新瓶子。
Sample Input
3 3 1 13 2 1000000 5Sample Output
1 3 15808HINT
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=4 分析：此題貪心求解，好像是一道面試題，其實就是考驗思維能力，因為每個瓶子的水都一定是2的倍數，所以最少的瓶子數就是總數的二進制表示中1的個數。每次加上最低位的1直到滿足要求，來一波位運算。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 int cnt(LL x) 5 { 6 int ret=0; 7 while(x) 8 { 9 if(x&1) ret++; 10 x>>=1; 11 } 12 return ret; 13 } 14 int main() 15 { 16 int i,j,k,n; 17 LL m,ans,x,y,z; 18 int T; 19 while(cin>>T) 20 { 21 while(T--) 22 { 23 scanf("%lld%d",&m,&n); 24 ans=0; 25 while(cnt(m)>n) 26 { 27 for (x=1;;x<<=1) 28 if(m&x) 29 break; 30 ans+=x; 31 m+=x; 32 } 33 printf("%lld\n",ans); 34 } 35 } 36 return 0; 37 }下面給出官方的題解：
對于 n 瓶一升的水，把他們合并后，最少需要的瓶子數為 n 的二進制中 1 的個數。假
設 n 的二進制中 1 的個數大于 k，那么我們要找到 1 個大于 n 的數，且二進制中 1 的個數等
于 k 的最小的數 m，那么答案為 m-n。
假設 n 二進制中，最右邊的 1 在第 i 位（這里的第幾位是從右往左數的，最右邊為第 0
位），那么假設你加上一個小于 2^i 的數，結果二進制中 1 的個數只會增加，如果加上一個
2^i，則結果二進制中 1 的個數必定不會增加。所以只需要一直加上一個 2^i（這里的 i 表示
的是當前水的總體積的二進制中最右邊的 1 所在的位置）直到結果中 1 的個數等于 k 即可。
?
Problem F: tmk找三角
Description
?
有一棵樹，樹上有只tmk。他在這棵樹上生活了很久，對他的構造了如指掌。所以他在樹上從來都是走最短路，不會繞路。他還還特別喜歡三角形，所以當他在樹上爬來爬去的時候總會在想，如果把剛才爬過的那幾根樹枝/樹干鋸下來，能不能從中選三根出來拼成一個三角形呢？
?
Input
?
第一行輸入一個T，表示有多少組樣例。
對于每組數據：第一行包含一個整數 N，表示樹上節點的個數（從 1 到 N 標號）。
接下來的 N-1 行包含三個整數 a, b, len，表示有一根長度為 len 的樹枝/樹干在節點 a 和節點 b 之間。
接下來一行包含一個整數 M，表示詢問數。
接下來M行每行兩個整數 S, T，表示毛毛蟲從 S 爬行到了 T，詢問這段路程中的樹枝/樹干是否能拼成三角形。
?
Output
?
對于每組數據,每個詢問輸出一行，包含"Yes"或“No”，表示是否可以拼成三角形。
?
Sample Input
2 5 1 2 5 1 3 20 2 4 30 4 5 15 2 3 4 3 5 5 1 4 32 2 3 100 3 5 45 4 5 60 2 1 4 1 3Sample Output
No Yes No YesHINT
對于20%數據 1 ≤ N, M ≤ 1000
對于所有數據1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
?
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=5?
分析：這道題如果直接按照題意去寫，那么可以利用廣度優先搜索得到最短路徑（因為這是一顆樹，而不是圖，所以不必使用最短路算法），然后判斷路徑上的邊是否能組成一個三角形（先對路徑排序，然后用兩邊之和大于第三邊進行判斷）。不過搜索的時間復雜度是 O(N)，判斷三角形的時間復雜度為 O(llgl)（其中 l 是最短路徑的長度），小數據沒問題，但大數據肯定會掛。?
LCA可是可以寫，不過估計會TL，目前還沒想到什么好辦法！ 先給出一種LCA寫法吧，我也沒敢提交，估計會TL，課后補了下重掛賽，AC了，竟然不會超時，只能說數據太水！ 1 #include <stdio.h> 2 #include <cmath> 3 #include <algorithm> 4 #include <list> 5 #include <string.h> 6 using namespace std; 7 // 樹的節點 8 struct Node { 9 int next, len; 10 Node (int n, int l):next(n), len(l) {} 11 }; 12 int pow2[20]; 13 list<Node> nodes[100010]; 14 bool visit[100010]; 15 int ns[200010]; 16 int nIdx; 17 int length[100010]; 18 int parent[100010]; 19 int depth[200010]; 20 int first[100010]; 21 int mmin[20][200010]; 22 int edges[100010]; 23 // DFS 對樹進行預處理 24 void dfs(int u, int dep) 25 { 26 ns[++nIdx] = u; depth[nIdx] = dep; 27 visit[u] = true; 28 if (first[u] == -1) first[u] = nIdx; 29 list<Node>::iterator it = nodes[u].begin(), end = nodes[u].end(); 30 for (;it != end; it++) 31 { 32 int v = it->next; 33 if(!visit[v]) 34 { 35 length[v] = it->len; 36 parent[v] = u; 37 dfs(v, dep + 1); 38 ns[++nIdx] = u; 39 depth[nIdx] = dep; 40 } 41 } 42 } 43 // 初始化 RMQ 44 void init_rmq() 45 { 46 nIdx = 0; 47 memset(visit, 0, sizeof(visit)); 48 memset(first, -1, sizeof(first)); 49 depth[0] = 0; 50 length[1] = parent[1] = 0; 51 dfs(1, 1); 52 memset(mmin, 0, sizeof(mmin)); 53 for(int i = 1; i <= nIdx; i++) { 54 mmin[0][i] = i; 55 } 56 int t1 = (int)(log((double)nIdx) / log(2.0)); 57 for(int i = 1; i <= t1; i++) { 58 for(int j = 1; j + pow2[i] - 1 <= nIdx; j++) { 59 int a = mmin[i-1][j], b = mmin[i-1][j+pow2[i-1]]; 60 if(depth[a] <= depth[b]) { 61 mmin[i][j] = a; 62 } else { 63 mmin[i][j] = b; 64 } 65 } 66 } 67 } 68 // RMQ 詢問 69 int rmq(int u, int v) 70 { 71 int i = first[u], j = first[v]; 72 if(i > j) swap(i, j); 73 int t1 = (int)(log((double)j - i + 1) / log(2.0)); 74 int a = mmin[t1][i], b = mmin[t1][j - pow2[t1] + 1]; 75 if(depth[a] <= depth[b]) { 76 return ns[a]; 77 } else { 78 return ns[b]; 79 } 80 } 81 82 int main() { 83 for(int i = 0; i < 20; i++) { 84 pow2[i] = 1 << i; 85 } 86 int T, n, m, a, b, len; 87 scanf("%d ", &T); 88 for (int caseIdx = 1;caseIdx <= T;caseIdx++) { 89 scanf("%d", &n); 90 for (int i = 0;i <= n;i++) { 91 nodes[i].clear(); 92 } 93 for (int i = 1;i < n;i++) { 94 scanf("%d%d%d", &a, &b, &len); 95 nodes[a].push_back(Node(b, len)); 96 nodes[b].push_back(Node(a, len)); 97 } 98 init_rmq(); 99 scanf("%d", &m); 100 //printf("Case #%d: ", caseIdx); 101 for (int i = 0;i < m;i++) { 102 scanf("%d%d", &a, &b); 103 // 利用 RMQ 得到 LCA 104 int root = rmq(a, b); 105 bool success = false; 106 int l = 0; 107 while (a != root) { 108 edges[l++] = length[a]; 109 a = parent[a]; 110 } 111 while (b != root) { 112 edges[l++] = length[b]; 113 b = parent[b]; 114 } 115 if (l >= 3) { 116 sort(edges, edges + l); 117 for (int j = 2;j < l;j++) { 118 if (edges[j - 2] + edges[j - 1] > edges[j]) { 119 success = true; 120 break; 121 } 122 } 123 } 124 if (success) { 125 puts("Yes"); 126 } else { 127 puts("No"); 128 } 129 } 130 } 131 return 0; 132 }官方題解來了：
假設現在有 n 條線段，假設 n 條邊從小到達排序，如果這 n 條邊中沒有三條可以構成
三角形，那么這 n 條邊必須滿足關系：A[i] >= A[i-2]+A[i-1]，這里的 A[i]表示第 i 條邊的大小。
假設 A[i]盡量取最小 A[i]=A[i-2]+A[i-1]，且 A[1]=A[2]=1，是不是就是一個斐波那契，也就
是對于一個 n 條邊的集合，如果不存在三條邊能構成一個三角形，那么最長的邊至少為 f[n]，
表示斐波那契第 n 項。而題目中 A[i]<1e9，也就是只要 n>50，就必定存在三條邊可以構成一
個三角形，所以我們只需要暴力加入兩點路徑上的邊（如果大于 50，直接 Yes），然后對這
些邊進行排序，枚舉第 i 條邊為最長邊，貪心判斷 A[i]是否小于 A[i-1]+A[i-2]即可。
?
Problem G: 等凹數字
Description
定義一種數字稱為等凹數字，即從高位到地位，每一位的數字先非遞增再非遞減，不能全部數字一樣，且該數是一個回文數，即從左讀到右與從右讀到左是一樣的，僅形成一個等凹峰，如543212345，5544334455是合法的等凹數字，543212346，123321，111111不是等凹數字。現在問你[L,R]中有多少等凹數字呢？
?
Input
第一行一個整數T，表示數據的組數。
接下來T行每行倆個數字L和R，(1<=L<=R<=1e18)
Output
?輸出一個整數，代表[L,R]中有多少等凹數字
Sample Input
2 1 100 101 200Sample Output
0 1HINT
?
?小于等于2位的數字無凹峰
?
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=6
?
分析：dp[i][len][pre][up][down][ispa]代表當前第 i 位，長度為 len，上一位是什么，前面是否遞
增過，前面是否遞減過，當前是否符合回文串的性質，然后記憶化搜索。
?
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <time.h> 8 #include <set> 9 #include <map> 10 #include <string> 11 #include <math.h> 12 #include <stdlib.h> 13 using namespace std; 14 long long dp[20][20][10][2][2][2]; 15 int num[20]; 16 int s[20]; 17 long long rec(int i,int pre,int up,int down,int flag,int q,int len,int ispa) 18 { 19 if(i<0)return up&&down&&ispa; 20 if(~dp[i][len][pre][up][down][ispa]&&!flag&&!q)return dp[i][len][pre][up][down][ispa]; 21 long long res=0; 22 int o=s[i]; 23 for(int j=0;j<10;j++) 24 { 25 num[i]=j; 26 if(j>o&&flag)break; 27 if(q)res+=rec(i-1,j,0,0,j<o?0:flag,q&&j==0,len-(q&&j==0),ispa); 28 else if(j==pre) 29 { 30 if(ispa&&i<len/2) 31 res+=rec(i-1,j,up,down,j<o?0:flag,q&&j==0,len,j==num[len-i-1]); 32 else res+=rec(i-1,j,up,down,j<o?0:flag,q&&j==0,len,ispa); 33 } 34 else if(j>pre) 35 { 36 if(!down)continue; 37 if(ispa&&i<len/2) 38 res+=rec(i-1,j,1,down,j<o?0:flag,q&&j==0,len,j==num[len-i-1]); 39 else res+=rec(i-1,j,1,down,j<o?0:flag,q&&j==0,len,ispa); 40 } 41 else if(j<pre) 42 { 43 if(up)continue; 44 if(ispa&&i<len/2) 45 res+=rec(i-1,j,up,1,j<o?0:flag,q&&j==0,len,j==num[len-i-1]); 46 else res+=rec(i-1,j,up,1,j<o?0:flag,q&&j==0,len,ispa); 47 } 48 } 49 if(!flag&&!q)dp[i][len][pre][up][down][ispa]=res; 50 return res; 51 } 52 long long cal(long long x) 53 { 54 int len=0; 55 while(x) 56 { 57 s[len++]=x%10; 58 x/=10; 59 } 60 return rec(len-1,0,0,0,1,1,len,1); 61 } 62 int main() 63 { 64 memset(dp,-1,sizeof(dp)); 65 long long l,r; 66 int t; 67 scanf("%d",&t); 68 while(t--){ 69 scanf("%lld%lld",&l,&r); 70 printf("%lld\n",cal(r)-cal(l-1)); 71 } 72 return 0; 73 }?
Problem H: tmk買禮物
?
Description
?
?
今天是校賽的日子，為了慶祝這么喜慶的日子，TMK打算買些禮物給女票LSH慶祝一下。
TMK進入了雪梨超市，然后剛踏入的一瞬間，店主就對TMK說：“恭喜你成為了本店第2147483647位顧客，本店在搞一個活動，對本店第2147483647位顧客進行贈送活動。你先看看你有多少錢？”
TMK一摸口袋，發現只有n個硬幣，每個硬幣的價值為a[i]。
然后店主繼續說：“現在你用你的錢湊一些數，如果你的錢能湊成[0,x]里面所有的數，那么你將會免費獲得該店價值x元的代金券，假設你有四個硬幣面值分別為1,2,4，100，你就可以湊成[0,7]里面所有的數，我們將會送你7元的代金券。現在就用你的硬幣來試試吧。Enjoy yourself！”
在TMK努力湊錢的時候，店主想知道他要送多少代金券給TMK。
?
?
Input
?
?
第一行一個整數T，表示數據組數。
對于每組數據，首先讀入一個整數n（n<=100000），然后接下來的一行有n個整數，表示a[i]（0<a[i]<=1e9）
?
Output
?
?
對于每個數據，輸出一個整數x，表示店主要送x元的代金券給TMK
?
?
Sample Input
?
1 3 1 2 3?
Sample Output
?
6?
HINT
題目鏈接：http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=7
?還是給下正解的思路吧，可能是因為數據太水就過了！
思路：先將所有的數排序，先特判一下第一個數是不是1，如果不是的話，那么肯定不可能有x，否則就找到第一個a[i]使得 a[i]>a[i-1]+...a[0]+1,這個a[i]就是一定不能組成的1 #include<bits/stdc++.h> 2 using namespace std; 3 int t; 4 int n; 5 long long a[100005]; 6 long long res; 7 void init(){ 8 res=0; 9 } 10 int main(){ 11 // freopen("in.txt","r",stdin); 12 scanf("%d",&t); 13 while(t--){ 14 init(); 15 scanf("%d",&n); 16 for(int i=1;i<=n;i++){ 17 scanf("%lld",&a[i]); 18 } 19 sort(a+1,a+n+1); 20 int f=0; 21 for(int i=1;i<=n;i++){ 22 if(a[i]>res+1){ 23 f=1; 24 printf("%lld\n",res); 25 break; 26 } 27 res+=a[i]; 28 } 29 if(f==0){ 30 printf("%lld\n",res); 31 } 32 } 33 return 0; 34 } 另外一種解法：
首先，先對 a[i]從小到大排序，假設對于前 i 個硬幣，我們可以組合成 0~y：
①如果 a[i+1]>y+1，那么從 i+1~n 中任意取硬幣，構成的和都>y+1，所以必定構造不出
y+1，于是答案等于 y。
②如果 a[i+1]<=y+1，那么前 i+1 位可以組合成 0~y+a[i+1]。
所以只需要對硬幣從小到大排序，然后從第一個硬幣枚舉到最后一個硬幣，或者中途有
某個數夠不出來即可得到答案。
要注意，輸出要用long long型，否則會溢出！
下面給出AC代碼： 1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int T; 6 int n; 7 int a[100005]; 8 while(cin>>T) 9 { 10 while(T--) 11 { 12 cin>>n; 13 for(int i=0;i<n;i++) 14 cin>>a[i]; 15 sort(a,a+n); 16 long long ans=0; 17 for(int i=0;i<n&&ans+1>=a[i];i++) 18 ans+=a[i]; 19 printf("%lld\n",ans); 20 } 21 } 22 return 0; 23 }
?
?
?
?
?
轉載于:https://www.cnblogs.com/ECJTUACM-873284962/p/6623582.html
總結
以上是生活随笔為你收集整理的2017广东工业大学程序设计竞赛决赛 题解源码(A,数学解方程，B,贪心博弈，C,递归，D,水，E,贪心，面试题，F,贪心，枚举，LCA，G,dp，记忆化搜索，H,思维题)...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： VMware虚拟机打开后不兼容
- 下一篇： Cannot place PIO com