AtCoder Beginner Contest 045 题解

A - Trapezoids

题目大意：
告诉你题型的上底、下底、高，求面积。

解题思路：
(S = frac{(a+b) cdot h}{2})

示例程序：

#include <bits/stdc++.h>
using namespace std;
int a, b, h;
int main() {
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
    return 0;
}

B - Card Game for Three (ABC Edit)

题目大意：
三个人轮流曲牌，按照对应规则。问最后谁的排最先没有（没有牌出）。

解题思路：
开三个字符串，三个坐标，以及一个变量表示当前在哪个字符串，然后模拟。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
char a[maxn], b[maxn], c[maxn];
int ia, ib, ic, p = 1;
int main() {
    cin >> a >> b >> c;
    while (true) {
        if (p == 1) {
            char x = a[ia++];
            if (!x) { puts("A"); return 0; }
            if (x == 'a') p = 1;
            else if (x == 'b') p = 2;
            else p = 3;
        }
        else if (p == 2) {
            char x = b[ib++];
            if (!x) { puts("B"); return 0; }
            if (x == 'a') p = 1;
            else if (x == 'b') p = 2;
            else p = 3;
        }
        else {
            char x = c[ic++];
            if (!x) { puts("C"); return 0; }
            if (x == 'a') p = 1;
            else if (x == 'b') p = 2;
            else p = 3;
        }
    }
    return 0;
}

C - Many Formulas

题目大意：
把一个数字用 '+' 号拆分，求所有能够合法拆分出的公式的和。

解题思路：
因为 (|S| le 10)，所以可以暴搜，时间复杂度为 (O(2^{|S|}))。

示例程序：

#include <bits/stdc++.h>
using namespace std;
char s[11];
int n;
long long ans;
void dfs(int p, long long tmp, long long sum)
{
    if (p == n) {
        ans += tmp + sum;
        return;
    }
    dfs(p+1, tmp*10+s[p]-'0', sum);
    if (p) // 第一次避免重复
        dfs(p+1, s[p]-'0', sum+tmp);
}
int main() {
    cin >> s;
    n = strlen(s);
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

D - Snuke's Coloring

题目大意：
在一个 (H imes W(H,W le 10^9)) 的格子中给 (N(le 10^5)) 个格子染色，问所有的 (3 imes 3) 的小格子中有多少染了 (0,1,2,3,4,5,6,7,8,9) 个的。

解题思路：
只需要考虑有染色的格子，没染色的格子用总方案数减去一下就可以了。而有染色的格子数量较少，可以枚举，我是讲离散的点hash一下之后处理的。这题也算作一道模拟题。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
long long H, W, N, a, b, cnt;
long long ha[maxn*17];
long long ans[10];

set<long long> st;

long long h(long long a, long long b) {
    return (long long) (a - 1) * W + b - 1;
}

int check(long long hv) {
    int a = hv / W + 1, b = hv % W + 1;
    if (a+2 > H || b+2 > W) return 0;
    int cc = 0;
    for (int i = 0; i < 3; i ++) {
        for (int j = 0; j < 3; j ++) {
            long long hh = h(a+i, b+j);
            if (st.count(hh)) cc ++;
        }
    }
    return cc;
}

int main() {
    scanf("%lld%lld%lld", &H, &W, &N);
    for (int i = 0; i < N; i ++) {
        scanf("%lld%lld", &a, &b);
        long long hh = h(a, b);
        st.insert(hh);
        for (int i = 0; i < 3; i ++) {
            for (int j = 0; j < 3; j ++) {
                if (a-i >= 1 && b-j >= 1) ha[cnt++] = h(a-i, b-j);
                if (i || j) {
                    if (a+i <= H && b+j <= W) ha[cnt++] = h(a+i, b+j);
                }
            }
        }
    }
    sort(ha, ha+cnt);
    cnt = unique(ha, ha+cnt) - ha;
    for (int i = 0; i < cnt; i ++)
        ans[check(ha[i])] ++;
    ans[0] = (H - 2) * (W - 2);
    for (int i = 1; i < 10; i ++) ans[0] -= ans[i];
    for (int i = 0; i < 10; i ++)
        printf("%lld
", ans[i]);
    return 0;
}