AtCoder Beginner Contest 043

AtCoder Beginner Contest 045

A

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{

    int a,b,h;
    cin>>a>>b>>h;
    cout<<(a+b)*h/2;
    return 0;
}

B

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

直接用栈就ok啦

// LUOGU_RID: 173158948
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
stack<char> a[4];
int main()
{
    int n = 3;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = s[i].length() - 1; j >= 0; j--)
        {
            a[i].push(s[i][j]);
        }
    }
    int i = 1;
    while (!a[i].empty())
    {
        char c = a[i].top();
        a[i].pop();
        if (c == 'a')
        {
            i = 1;
        }
        else if (c == 'b')
        {
            i = 2;
        }
        else
        {
            i = 3;
        }
    }
    cout << char('A' + i - 1) << '\n';
    return 0;
}

C

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

数据这么小，直接暴搜。

// LUOGU_RID: 173161224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int a[11];
ll ans = 0;
int n;
void dfs(ll cnt, ll sum, ll num)
{
    if (cnt == n + 1)
    {
        ans += num + sum;
        return;
    }
    num = num * 10 + a[cnt];
    dfs(cnt + 1, sum + num, 0);
    dfs(cnt + 1, sum, num);
}
int main()
{
    string s;
    cin >> s;
    n = s.length();
    for (int i = 0; i < s.length(); i++)
    {
        a[i + 1] = s[i] - '0';
    }
    dfs(1, 0, 0);
    cout << (ans >> 1);
    return 0;
}

D

题意：

给定一个 \(H\) 行 \(W\) 列的矩形，再给定矩形上 \(N\) 个黑格子的坐标。对于每个 \(0\le j\le9\) ，求出有多少个 \(3\times3\) 的子矩阵包含有恰好 \(j\) 个黑格子。

哈希一下，改算黑色格子的贡献。

// LUOGU_RID: 173162995
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
map<pair<int, int>, ll> mp;
int main()
{
    ll h, w;
    cin >> h >> w;
    vector<ll> ans(11);
    int n;
    cin >> n;
    ans[0] = (h - 2) * (w - 2);
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        for (int j = -1; j <= 1; j++)
        {
            for (int k = -1; k <= 1; k++)
            {
                int x = a + j;
                int y = b + k;
                if (x > 1 && x < h && y > 1 && y < w)
                {
                    int now;
                    now = ++mp[{x, y}];
                    ans[now]++;
                    ans[now - 1]--;
                }
            }
        }
    }
    for (int i = 0; i < 10; i++)
    {
        cout << ans[i] << '\n';
    }
    return 0;
}