Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

AtCoder Beginner Contest 118 解题报告

henry_y 2019-02-16 22:36:00 阅读数:191 评论数:0 点赞数:0 收藏数:0

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];
}
版权声明
本文为[henry_y]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/henry-1202/p/10389574.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领