abc253_a

题目翻译

给定 $a,b,c$，问 $b$ 是不是中位数。

题目思路

排序，判断。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c;
    d = b;
    if (a > b)
    {
        swap (a, b);
    }
    if (b > c)
    {
        swap (b, c);
    }
    if (a > c)
    {
        swap (a, c);
    }
    if (a > b)
    {
        swap (a, b);
    }
    if (b > c)
    {
        swap (b, c);
    }
    if (a > c)
    {
        swap (a, c);
    }
    if (b == d)
    {
        puts ("Yes");
    }
    else
    {
        puts ("No");
    }
    return 0;
}

abc253_b

题目翻译

给定一个 $n\times m$ 的矩阵，找两个 o 之间的哈夫曼距离。

题目思路

按题意做即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, i1, i2, j1, j2;
    i1 = i2 = j1 = j2 = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == 'o')
            {
                if (i1 == 0)
                {
                    i1 = i;
                    j1 = j;
                }
                else
                {
                    i2 = i;
                    j2 = j;
                }
            }
        }
    }
    cout << abs (i1 - i2) + abs (j1 - j2) << endl;
    return 0;
}

abc253_c

题目翻译

有 $q$ 个询问。

1 x 表示插入一个 $x$。

2 x c 表示删去 $c$ 个 $x$，如果 $x$ 数量不够，删完。

3 输出目前最大值减去最小值。

题目思路

用一个 map 存当前哪个数出现几次，当然，第二种操作需要 erase。

AC 代码

#include<bits/stdc++.h>
using namespace std;
map<int, int>m;
int main()
{
    int q;
    cin >> q;
    while (q--)
    {
        int o;
        cin >> o;
        if (o == 1)
        {
            int x;
            cin >> x;
            m[x]++;
        }
        if (o == 2)
        {
            int x, c;
            cin >> x >> c;
            m[x] = max (m[x] - c, 0);
            if (m[x] == 0)
            {
                auto it = m.find (x);
                m.erase (it);
            }
        }
        if (o == 3)
        {
            cout << (--m.end())->first - m.begin()->first << endl;
        }
    }
    return 0;
}

abc253_d

题目翻译

问 $[1,n]$ 中不是 $a$ 的倍数或 $b$ 的倍数的数之和。

题目思路

容斥原理，答案就是 总和-a的倍数和-b的倍数和+a和b最大公因数的倍数和。

可以用等差数列。

以 $a$ 的倍数为例：

项数=n/a
和=（首项+末项）*项数/2

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    ll lcm = a / __gcd (a, b) * b;
    ll sum = (lcm + (lcm + ( (n / lcm) - 1) * lcm)) * (n / lcm) / 2;
    ll asum = (a + (a + ( (n / a) - 1) * a)) * (n / a) / 2;
    ll bsum = (b + (b + ( (n / b) - 1) * b)) * (n / b) / 2;
    cout << (1 + n) *n / 2 - asum - bsum + sum << endl;
    return 0;
}