心得:
这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多!
来,我们先来放松下,听听儿歌,一起“唱”。
两只老虎两只老虎,跑得快跑得快。
一只没有耳朵,一只没有尾巴。
真奇怪,真奇怪。
Tmk也觉得很奇怪,因为在他面前突然出现了一群这样的老虎,有的没耳朵,有的没尾巴,不过也有正常的。
现在Tmk告诉你这群老虎的耳朵个数,尾巴条数,以及老虎的腿的数目,问你有多少只是正常的。
其中只有三种老虎:
第一种(正常的):有2个耳朵、1条尾巴、4条腿
第二种(没耳朵):有0个耳朵、1条尾巴、4条腿
第三种(没尾巴):有2个耳朵、0条尾巴、4条腿
第一行一个整数T表示有多少组样例。
接下来每一行一个样例:
包含三个整数a,b,c表示总共有a个耳朵,b条尾巴,c(<=4000)条腿,数据保证有解。
对于每组样例输出一行,表示有多少只正常的老虎。
1
12 7 40
3
题目链接: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 }
众所周知的是,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占领的多,如果能,那么同时要求出占领的点数的最大差值。
第一行一个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,数据保证两个点不相同。
对于每一组数据,如果TMK占领的点不能比Maple占领的多,那么输出-1,否则输出两个占领点数的最大差值。
4
1 0 0 1 0
2 0 0 1 0
1 0 0 2 0
2 0 0 2 0
2
-1
1
-1
题目链接: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 }
小时候,我只能一阶一阶得爬楼梯,
后来,我除了能一次爬一阶,还可以一次爬两阶,
到现在,我最多一次可以爬三阶。
那么现在问题来了,我想爬上n层楼,相邻楼层之间有一段楼梯,虽然我一次可以爬1个台阶、2个台阶和3个台阶,但是我在i与i+1层之间的楼梯上时,我不能跨越到i+1与i+2层之间的楼梯。现在有个n层的楼,知道每一段楼梯的阶数,我想知道,如果我只会往上走,并且忽略其他不在楼梯上的其他移动,共有多少种方案可以到达第n层。
第一行一个整数T(0<T<=50)表示有多少组样例。
对于每一组样例:
第一行一个n(1<n<=50)表示有多少层楼。
接下来一行,包括n-1个整数xi(0<xi<=20),由下到上依次表示每段楼梯的长度。
对于每组数据,输出一行表示共有多少种方案。由于答案较大,所以输出答案请对10007取模。
2
2
3
4
4 5 6
4
2184
题目链接: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 }
“只有通过毁灭才能揭示真理。” —— 虚空之眼
维克兹是一个有触手的虚空来客,他带着非凡的意图探索着符文之地:吸收掉所有知识。凭借着他不断地注视,维克兹可以发射瓦解光线来灭除并分析他途中的一切东西,并为他供给数量庞大的信息。没人知道他为什么需要如此多的材料,尽管有人推测他设法了解符文之地,是为了加速它的毁灭。
另外,维克兹本身也是一个极其强大的魔法师,他的技能会对命中的敌人施加有机体解构效果。如果累积到3层效果,敌人就会受到爆发性的真实伤害。
现在,维克兹正准备施展他的绝招 —— 生命形态瓦解射线,来对付被永久眩晕且没有携带任何魔抗装备的约德尔人。另外,他的绝招每10秒就可以对敌人累积一层有机体解构效果。
维克兹希望找到能够跟他一起遨游大陆的伙伴,所以他准备考考你,如果已知生命形态瓦解射线持续的时间和每一秒的伤害,以及有机体解构效果每累积到3层所爆发的伤害(伤害爆发后层数归零),你是否能算出约德尔人受到的总伤害是多少呢?
请注意,如果你回答不出来,维克兹绝对很乐意将你一起分解掉。
输入包括T组数据,每组数据包括生命形态瓦解射线的持续时间A,每一秒的伤害B,以及有机体解构效果每累积到3层所爆发的伤害C。
(T <= 10000, 0 <= A, B, C <= 10000, 所有数据皆为整数)
输出一个数代表约德尔人受到的总伤害。
2
10 10 10
30 10 10
100
310
题目链接: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 }
一天,CC买了N个容量可以认为是无限大的瓶子,开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了,于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子,把一个瓶子的水全部倒进另一个里,然后把空瓶丢弃。(不能丢弃有水的瓶子)
显然在某些情况下CC无法达到目标,比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限,开始时有1升水),以到达目标。
现在CC想知道,最少需要买多少新瓶子才能达到目标呢?
第一行一个整数T,表示有T组数据。
接着T行,每行两个正整数, N,K(1<=N<=10^9,K<=1000)。
一个非负整数,表示最少需要买多少新瓶子。
3
3 1
13 2
1000000 5
1
3
15808
题目链接: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 即可。
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 }
有一棵树,树上有只tmk。他在这棵树上生活了很久,对他的构造了如指掌。所以他在树上从来都是走最短路,不会绕路。他还还特别喜欢三角形,所以当他在树上爬来爬去的时候总会在想,如果把刚才爬过的那几根树枝/树干锯下来,能不能从中选三根出来拼成一个三角形呢?
第一行输入一个T,表示有多少组样例。
对于每组数据:第一行包含一个整数 N,表示树上节点的个数(从 1 到 N 标号)。
接下来的 N-1 行包含三个整数 a, b, len,表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。
接下来一行包含一个整数 M,表示询问数。
接下来M行每行两个整数 S, T,表示毛毛虫从 S 爬行到了 T,询问这段路程中的树枝/树干是否能拼成三角形。
对于每组数据,每个询问输出一行,包含"Yes"或“No”,表示是否可以拼成三角形。
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 3
No
Yes
No
Yes
对于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]即可。
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 }
定义一种数字称为等凹数字,即从高位到地位,每一位的数字先非递增再非递减,不能全部数字一样,且该数是一个回文数,即从左读到右与从右读到左是一样的,仅形成一个等凹峰,如543212345,5544334455是合法的等凹数字,543212346,123321,111111不是等凹数字。现在问你[L,R]中有多少等凹数字呢?
第一行一个整数T,表示数据的组数。
接下来T行每行俩个数字L和R,(1<=L<=R<=1e18)
输出一个整数,代表[L,R]中有多少等凹数字
2
1 100
101 200
0
1
小于等于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 }
今天是校赛的日子,为了庆祝这么喜庆的日子,TMK打算买些礼物给女票LSH庆祝一下。
TMK进入了雪梨超市,然后刚踏入的一瞬间,店主就对TMK说:“恭喜你成为了本店第2147483647位顾客,本店在搞一个活动,对本店第2147483647位顾客进行赠送活动。你先看看你有多少钱?”
TMK一摸口袋,发现只有n个硬币,每个硬币的价值为a[i]。
然后店主继续说:“现在你用你的钱凑一些数,如果你的钱能凑成[0,x]里面所有的数,那么你将会免费获得该店价值x元的代金券,假设你有四个硬币面值分别为1,2,4,100,你就可以凑成[0,7]里面所有的数,我们将会送你7元的代金券。现在就用你的硬币来试试吧。Enjoy yourself!”
在TMK努力凑钱的时候,店主想知道他要送多少代金券给TMK。
第一行一个整数T,表示数据组数。
对于每组数据,首先读入一个整数n(n<=100000),然后接下来的一行有n个整数,表示a[i](0<a[i]<=1e9)
对于每个数据,输出一个整数x,表示店主要送x元的代金券给TMK
1
3
1 2 3
6
题目链接: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 }