AtCoder Beginner Contest 118 解题报告

henry-1202 2019-02-16 原文

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];
}