- A
- #include <iostream>
- using namespace std;
- int main()
- {
- int a, b;
- cin>> a>> b;
- cout <<(b % a ? b - a : b + a) << endl;
- return 0;
- }
- B
- #include <bits/stdc++.h>
- using namespace std;
- int main()
- {
- int N, M;
- cin>> N>> M;
- vector<int> cnt(M);
- for (int i = 0; i <N; i++)
- {
- int K;
- cin>> K;
- for (int j = 0; j <K; j++)
- {
- int A;
- cin>> A;
- A--;
- cnt[A]++;
- }
- }
- int ans = 0;
- for (int i = 0; i <M; i++)
- {
- if (cnt[i] == N)
- {
- ans += 1;
- }
- }
- cout << ans << endl;
- }
- C
分析:
逐个求最大公约数就行.
代码:
- #include<bits/stdc++.h>
- using namespace std;
- int gcd(int a,int b)
- {
- return (0 == b) ? a : gcd(b, a % b);
- }
- int main()
- {
- int N;
- cin>> N;
- int A[N];
- for(int i=0;i<N;i++)
- {
- cin>>A[i];
- }
- int ans = A[0];
- for(int i=1;i<N;i++)
- {
- ans = gcd(ans,A[i]);
- }
- cout <<ans << endl;
- return 0;
- }
- D
分析:
本题可以使用动态规划来解决. 以样例 1 为例 来分析.
20 4
3 7 8 4
(1)可先对 Ai 按从大到小的顺序进行排序: 8 7 4 3
(2)数据的对应关系为
- 0
- 2
- 5
- 5
- 4
- 5
- 6
- 3
- 7
- 6
所以, 样例 1 中数据的对应关系为
- 8 7
- 7 3
- 4 4
- 3 5
所以, 映射前的数组 A[] = {8, 7, 4, 3}, 映射后的数组 map[] = {7, 3, 4, 5}
(3)考虑到 string 重载了 "+" 运算符, 可以很方便地将数字 (字符) 连接起来.
比如 "7"+"7"="77", 或 "77777" + "3" = "777773".
可以声明 vector<string> dp, 刚开始时, dp[i]都为 "".dp 中存放的是结果.
样例 1 中 N=20, 则最终要求的是 dp[20].
(4)
根据样例 1 中数据的对应关系, dp[7]="8", dp[3]="7", dp[4] = "4", dp[5] = "3".
接着从 1 开始枚举 dp.
N = 1 时, dp[1] = "", 也就是说,{8,7,4,3}无法组成各位数之和为 1 的数.
N = 2 时, dp[1] = "", 也就是说,{8,7,4,3}无法组成各位数之和为 2 的数.
N = 3 时, dp[3] = "7".
N = 4 时, dp[4] = "4".
N = 5 时, dp[5] = "3".
N = 6 时, 6 = 3 + 3.3 对应的数是 7, 所以 dp[6] = "7" + "7" = "77".
N = 7 时, dp[7] = "7". 另外 7 = 3 + 4 = 4 + 3,3 对应的是 7,4 对应的是 4. 所以 dp[7] = "74" 或 dp[7] = "47". 取最大值 dp[7] = "74".
N = 8 时, dp[8] = 3 + 5 = 4 + 4 = 5 + 3.3 对应着 7,4 对应着 4,5 对应着 3, 则 dp[8] = "73" 或 "44" 或 "37", 取最大值 dp[8] = "73".
N = 9 时, dp[9] = dp[6] + 3 = "777".
......
最终, dp[20]即为所求.
代码:
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<int> m = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
- string getMax(string a, string b)
- {
- if(a.length()> b.length())
- {
- return a;
- }
- else if(a.length() <b.length())
- {
- return b;
- }
- else // 如果长度相等, 返回字典序较大的字符串
- {
- return a> b ? a : b;
- }
- }
- int main()
- {
- int N, M;
- cin>> N>> M;
- vector<int> A(M, 0);
- for(int i = 0; i <M; i++)
- {
- cin>> A[i];
- }
- sort(A.begin(), A.end(), greater<int>());
- vector<string> dp(max(N+1,10), "");
- for(int i = 0; i <M; i++)
- {
- dp[m[A[i]]] = getMax(dp[m[A[i]]], to_string(A[i]));
- }
- for(int j = 0; j <= N; j++)
- {
- for(int i = 0; i < M; i++)
- {
- if(j - m[A[i]]>= 0 && dp[j-m[A[i]]] != "")
- {
- dp[j] = getMax(dp[j], dp[j-m[A[i]]] + to_string(A[i]));
- }
- }
- }
- cout << dp[N] << endl;
- return 0;
- }
TopCoder & Codeforces & AtCoder 交流 QQ 群: 648202993
来源: http://www.jianshu.com/p/4bd12af280c8