- A - B +/- A
- #include <bits/stdc++.h>
- int main() {
- int a, b; std::cin>> a>> b;
- b % a ? std::cout <<b - a : std::cout << a + b;
- }
- B - Foods Loved by Everyone
- #include <bits/stdc++.h>
- int cnt[31], ans;
- int main() {
- int n, m; std::cin>> n>> m;
- for(int i = 1; i <= n; ++i) {
- int k, x; std::cin>> k;
- while(k--) std::cin>> x, ++cnt[x];
- }
- for(int i = 1; i <= m; ++i) if(cnt[i] == n) ++ans;
- std::cout <<ans << std::endl;
- }
- C - Monsters Battle Royale
答案即为所有数的 \(\gcd\).
考虑 \(\gcd(n,n-x)=\gcd(n,x)\).
实际上每次减法就是在重复这个过程.
- #include <bits/stdc++.h>
- int main() {
- int n, a, x; std::cin>> n>> a; --n;
- while(n--) std::cin>> x, a = std::__gcd(a, x);
- printf("%d\n",a);
- }
- D - Match Matching
设 \(f[i]\) 表示用了 \(i\) 根火柴, 能拼出的数的个数, 输出答案对每个 dp 值维护一个 vector 即可.
\[ f[i]=max\{f[i-a[j]]+1\} \]
每次转移都将原数组的 vector 也转过去, push 个 a[j] 进去即可.
注意排序, 按数字大小倒序排序, 最后倒序输出出去.
复杂度 \(O(nmlen+mlogm)\), 因为是 dp, 所以这个 len 随机数据下实际不会跑很满, 总时间才用了 104ms
- #include <bits/stdc++.h>
- const int N = 10010;
- const int s[10] = {0,2,5,5,4,5,6,3,7,6};
- struct Node {int id, cnt;} a[20];
- int f[N], n, m;
- std::vector<int>v[N];
- bool operator <(Node a, Node b) { return a.id> b.id; }
- int main() {
- std::cin>> n>> m;
- for(int i = 1; i <= m; ++i) std::cin>> a[i].id, a[i].cnt = s[a[i].id];
- std::sort(a + 1, a + m + 1); std::memset(f, -0x3f, sizeof(f)); f[0] = 0;
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= m; ++j)
- if(i - a[j].cnt>= 0 && f[i - a[j].cnt] + 1> f[i])
- v[i] = v[i - a[j].cnt], v[i].push_back(a[j].id), f[i] = f[i - a[j].cnt] + 1;
- for(int i = v[n].size() - 1; i>= 0; --i) std::cout << v[n][i];
- }
来源: https://www.cnblogs.com/henry-1202/p/10389574.html