心得：
这比赛真的是不要不要的，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
Sample Output
HINT
题目链接：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
Sample Output
HINT
题目链接：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
Sample Output
HINT
题目链接：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
Sample Output
HINT
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
Sample Output
HINT
因为每个瓶子的水都一定是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 即可。
1 #include <iostream> 2 using namespace std; 3 int cal(int n) 4 { 5 int ans = 0; 6 while(n) 7 { 8 ans ++; 9 n &= n-1; 10 } 11 return ans; 12 } 13 int lowbit(int n) 14 { 15 return n&-n; 16 } 17 int main() 18 { 19 int T; 20 scanf("%d",&T); 21 while(T--) 22 { 23 int n, k; 24 scanf("%d%d", &n, &k); 25 int ans = 0; 26 while(cal(n) > k) 27 { 28 ans += lowbit(n); 29 n += lowbit(n); 30 } 31 printf("%d\n", ans); 32 } 33 return 0; 34 }
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
Sample Output
HINT
对于20%数据 1 ≤ N, M ≤ 1000
对于所有数据1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
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]即可。
1 #include <cstdio> 2 #include <set> 3 #include <cstring> 4 #include <iostream> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 9 const int N = 1e5+10; 10 int n; 11 int tot, head[N], to[N<<1], nex[N<<1], len[N<<1]; 12 int f[N], dis[N], dep[N]; 13 14 void init() 15 { 16 tot = 0; 17 for(int i = 0; i <= n; ++ i) 18 { 19 head[i] = -1; 20 } 21 } 22 23 void addEdge(int x, int y, int l) 24 { 25 to[tot] = y; 26 len[tot] = l; 27 nex[tot] = head[x]; 28 head[x] = tot++; 29 } 30 31 void dfs(int u, int d) 32 { 33 dep[u] = d; 34 for(int i = head[u]; ~i; i = nex[i]) 35 { 36 int v = to[i]; 37 if(v == f[u]) continue; 38 dis[v] = len[i]; 39 f[v] = u; 40 dfs(v, d+1); 41 } 42 } 43 44 bool solve(int x, int y) 45 { 46 vector<int> vec; 47 while(vec.size() < 50 && x != y) 48 { 49 if(dep[x] < dep[y]) 50 { 51 vec.push_back(dis[y]); 52 y = f[y]; 53 } 54 else 55 { 56 vec.push_back(dis[x]); 57 x = f[x]; 58 } 59 } 60 if(vec.size()>=50) return true; 61 sort(vec.begin(), vec.end()); 62 for(int i = 0; i + 2 < vec.size(); ++ i) 63 { 64 if(vec[i] + vec[i+1] > vec[i+2]) return true; 65 } 66 return false; 67 } 68 69 int main() 70 { 71 int T; 72 scanf("%d", &T); 73 while(T--) 74 { 75 scanf("%d", &n); 76 init(); 77 for(int i = 1; i < n; ++ i) 78 { 79 int x, y, l; 80 scanf("%d%d%d", &x, &y, &l); 81 addEdge(x, y, l); 82 addEdge(y, x, l); 83 } 84 dfs(1, 0); 85 int m; 86 scanf("%d", &m); 87 for(int i = 0; i < m; ++ i) 88 { 89 int x, y; 90 scanf("%d%d", &x, &y); 91 puts(solve(x, y) ? "Yes" : "No"); 92 } 93 } 94 return 0; 95 }
Problem G: 等凹数字
Description
定义一种数字称为等凹数字，即从高位到地位，每一位的数字先非递增再非递减，不能全部数字一样，且该数是一个回文数，即从左读到右与从右读到左是一样的，仅形成一个等凹峰，如543212345，5544334455是合法的等凹数字，543212346，123321，111111不是等凹数字。现在问你[L,R]中有多少等凹数字呢？
Input
第一行一个整数T，表示数据的组数。
接下来T行每行俩个数字L和R，(1<=L<=R<=1e18)
Output
输出一个整数，代表[L,R]中有多少等凹数字
Sample Input
Sample Output
HINT
小于等于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
Sample Output
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 }
