A

题目说明

总共能关注的人是 $2 \times A + 100$ ，现在已经关注了 $B$ 位用户，那么还能关注 $2 \times A +100 - B$ 位用户。

时间复杂度为 $O(1)$

参考代码

#include <stdio.h>
int main() {
   int a, b;
   scanf("%d%d", &a, &b);
   printf("%d\n", 2 * a + 100 - b);
   return 0;
}

B

题目说明

注意到 $A$ 的大小不会超过 $1000$ 因此直接暴力枚举即可。

时间复杂度为 $O(nV)$，$V$ 表示值域。

另外，借助埃氏筛的思想，可以优化到 $O(V \log V + n)$ ，请读者自行探索 。

参考代码

#include <stdio.h>
int main() {
	int n;
	scanf("%d", &n);
	int a[n];
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	int max = 0;
	int res = -1;
	for (int i = 2; i <= 1000; i++) {
		int cnt = 0;
		for (int j = 0; j < n; j++) if (a[j] % i == 0) cnt++;
		if (max <= cnt) max = cnt, res = i;
	}
	printf("%d\n", res);
	return 0;
}

C

题目说明

注意到，被 $3$ 整除的数一定满足各位数字之和是 $3$ 的倍数。因此原问题等价于，给定一个序列，删除其中若干个数，要求剩下的数之和是 $3$ 的倍数，问至少删除几个数。

根据模运算的基本常识，我们只需要枚举一下可能的几种情况就好。各位数字之和模 $3$ 为 $1$ ，我们可以删除一个模为 $1$ 的数，或者删除两个模为 $2$ 的数；各位数字之和模 $3$ 为 $2$ ，我们可以删除一个模为 $2$ 的数，或者删除两个模为 $1$ 的数。

时间复杂度为 $O(\log N)$

参考代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    string s;
    cin >> s;
    vector<int> a(3);
    int sum = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        int num = (s[i] - '0') % 3;
        a[num]++;
        sum = (sum + num) % 3;
    }
    if (sum == 0)
    {
        cout << 0 << '\n';
        return;
    }
    if (sum == 1)
    {
        if (s.size() > 1 && a[1] >= 1)
        {
            cout << 1 << '\n';
        }
        else if (s.size() > 2 && a[2] >= 2)
        {
            cout << 2 << '\n';
        }
        else
        {
            cout << -1 << '\n';
        }
        return;
    }
    if (sum == 2)
    {
        if (s.size() > 1 && a[2] >= 1)
        {
            cout << 1 << '\n';
        }
        else if (s.size() > 2 && a[1] >= 2)
        {
            cout << 2 << '\n';
        }
        else
        {
            cout << -1 << '\n';
        }
        return;
    }
}
/*

*/
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t; cin >> t; while(t--)
    solve();
    return 0;
}

D

题目说明

朴素的写法，我们去模拟每一步的过程，时间复杂度为 $O(N^2)$ ，无法通过此题。

我们考虑怎么去优化这个过程。注意到，每轮执行的操作中，前面的部分是完全一致的。每一轮都是在上一轮基础上额外向正方向走了 $A_i$ 的距离。因此，我们可以记录前 $i$ 个操作中，相对于一开始的位置偏移的大小 $p_i$ ，以及这个过程中相对于一开始的位置所能到达的最大位置 $q_i$ 。

初始 $p = 0, x = 0, r = 0, q = 0$

每一轮，$r \leftarrow \max(r, x + q_i)$ 并且 $x \leftarrow x + p_i$ 。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
    int n;
    cin >> n;
    ll r = 0, x = 0, p = 0, q = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll a;
        cin >> a;
        p += a;
        q = max(q, p);
        r = max(r, x + q);
        x = x + p;
	}
    cout << r;
}
/*

*/
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

E

题目说明

朴素的想法为，对于每一个灯泡，都考虑它上下左右能够照亮的方块，时间复杂度为 $O(N \times (H + W))$ 。

这个复杂度无法被接受，但是可以发现我们将光束拆成上下和左右分开考虑，彼此之间是互不影响的。

接下来我们先单独考虑左右的情况，如果一行中第二个灯泡想要增加照亮的区域，那么当前这个灯泡必须处于未被照亮的地方。通过以上结论，每一个灯泡是有效的灯泡当且仅当处于未被照亮的区域，单独检验并左右标记，至多只需标记 $O(H \times W)$ 次，那么总共只需要 $O(H \times W + N + M)$ 的复杂度。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int h, w;
    cin >> h >> w;
    vector<vector<int>> mp1(h + 1, vector<int>(w + 1)),
        mp2(h + 1, vector<int>(w + 1));
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> rs(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> rs[i].first >> rs[i].second;
    }
    for (int j = 1; j <= m; ++j)
    {
        int x, y;
        cin >> x >> y;
        mp1[x][y] = -1;
        mp2[x][y] = -1;
    }
    for (int i = 1; i <= n; ++i)
    {
        int x = rs[i].first, y = rs[i].second;
        if (mp1[x][y] == 0)
        {
            for (int j = y; j <= w; ++j)
            {
                if (mp1[x][j] == 0)
                    mp1[x][j] = 1;
                else
                    break;
            }
            for (int j = y - 1; j >= 1; --j)
            {
                if (mp1[x][j] == 0)
                    mp1[x][j] = 1;
                else
                    break;
            }
        }
        if (mp2[x][y] == 0)
        {
            for (int j = x; j <= h; ++j)
            {
                if (mp2[j][y] == 0)
                    mp2[j][y] = 1;
                else
                    break;
            }
            for (int j = x - 1; j >= 1; --j)
            {
                if (mp2[j][y] == 0)
                    mp2[j][y] = 1;
                else
                    break;
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= h; ++i)
    {
        for (int j = 1; j <= w; ++j)
        {
            if (mp1[i][j] == 1 || mp2[i][j] == 1)
            {
                cnt++;
            }
        }
    }
    cout << cnt << '\n';
}
/*

*/
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t; cin >> t; while(t--)
    solve();
    return 0;
}

F

题目说明

我们不妨将这些金额用硬币的面值表示出来。

$X = \sum_{i=1}^{n} x_i \times A_i$

$Y = \sum_{i=1}^{n} y_i \times A_i$

$Z = Y - X = \sum_{i=1}^{n} z_i \times A_i$

那么原题目等价于已知 $X$ ， 求 满足 $X + Z = Y$ 的 $Y$ 的数量有多少，并且 $y_i, z_i$ 不同时大于 $0$ 。

容易发现若考虑 $y_i = 0$ ，并且 $x_i != 0$ 那么一定有 $z_i = \frac{A_{i+1}}{A_{i}} - x_i$ ，此时就会产生进位。

那么我们考虑前 $i$ 位数， 是否产生进位来进行计算。

后面递推式请读者参考实现的代码自行完成推导。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin >> n;
    ll x;
    cin >> x;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    vector<ll> X(n + 1);
    for (int i = n; i >= 1; --i)
    {
        X[i] = x / a[i];
        x %= a[i];
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(2));
    dp[1][0] = 1;
    if (X[1]) dp[1][1] = 1;
    for (int i = 1; i < n; ++i)
    {
        if (X[i + 1])
        {
            dp[i + 1][1] = dp[i][0] + dp[i][1];
            dp[i + 1][0] = dp[i][0];
            if (X[i + 1] + 1 != a[i + 2] / a[i + 1])
            {
                dp[i + 1][0] += dp[i][1];
            }
        }
        else
        {
            dp[i + 1][1] = dp[i][1];
            dp[i + 1][0] = dp[i][0] + dp[i][1];
        }
    }
    cout << dp[n][0] << '\n';
}
/*

*/
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t; cin >> t; while(t--)
    solve();
    return 0;
}