AtCoder Beginner Contest 330

• AtCoder Beginner Contest 330

A

思路

满足 \(x \ge l\) 的 \(x\) 的个数即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, l;
    cin >> n >> l;

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (x >= l)
            ans++;
    }

    cout << ans;

    return 0;
}

B

思路

如果满足 \(L \le A_i \le R\) 输出 \(A_i\)

如果满足 \(A_i \lt L\) 输出 \(L\)

如果满足 \(A_i \gt R\) 输出 \(R\)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, l, r;
    cin >> n >> l >> r;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (x < l)
            cout << l << ' ';
        else if (x > r)
            cout << r << ' ';
        else
            cout << x << ' ';
    }

    return 0;
}

C

思路

令 \(x\) 从 \(0\) 遍历到 \(\lceil \sqrt{D}\rceil\) ，如果 \(x\) 大于 \(\lceil \sqrt{D}\rceil\) ，那么设置 \(y=0\) 是最优的，但这里的 \(|x^2+y^2-D|\) 明显大于 \(x=\lceil \sqrt{D}\rceil\) 和 \(y=0\) 时。

对一个 \(x\) 最佳的 \(y\) 为 \(y=\lfloor \sqrt{-C}\rfloor\) 或 \(y=\lceil\sqrt{-C}\rceil\) ，可以直接算出这时候的值，更新 \(ans\) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll d;
    cin >> d;

    ll ans = 0x7fffffff;
    for (int i = 0; i * i <= d; i++)
    {
        ll x = 1LL * i * i;
        if (x > d)
            break;
        ll y1 = sqrt(d - x);
        ll y2 = y1 + 1;

        ans = min({ans, abs((x + y1 * y1) - d), abs((x + y2 * y2) - d)});
    }
    cout << ans;

    return 0;
}

D

思路

记录每一行每一列有多少 \(o\) ，最后遍历每个 \(o\) 看这行这列还有多少其余的 \(o\) ，算出方案数累加即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 2e3 + 10;
const int M = 1e5 + 10;

char mp[N][N];
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> mp[i][j];
            if (mp[i][j] == 'o')
                a[i]++;
        }
    }

    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if (mp[i][j] == 'o')
                b[j]++;
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mp[i][j] == 'o')
                ans += 1LL * (a[i] - 1) * (b[j] - 1);
        }
    }
    cout << ans;

    return 0;
}

E

思路

使用 set 的自动排序和去重来计算 \(mex\) ，即存储有哪些数不在序列中。

由于序列长度仅为 \(n\) 故超过 \(n\) 的数我们不对 set 进行操作。

使用一个数组存储当前的序列每个数有多少个，当出现 \(0\rightarrow 1\) 和 \(1 \rightarrow 0\) 的变化时，更新 set 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n + 10), cnt(n + 10);
    set<int> st;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] <= n)
            cnt[a[i]]++;
    }

    for (int i = 0; i <= n; i++)
    {
        if (!cnt[i])
            st.insert(i);
    }

    while (q--)
    {
        int i, x;
        cin >> i >> x;
        if (a[i] <= n)
        {
            cnt[a[i]]--;
            if (cnt[a[i]] == 0)
                st.insert(a[i]);
        }
        if (x <= n)
        {
            cnt[x]++;
            if (cnt[x] == 1)
                st.erase(x);
        }
        a[i] = x;
        cout << *st.begin() << endl;
    }

    return 0;
}