AtCoder Beginner Contest 182

发表于2020-11-13更新于2023-09-15字数统计1.7k阅读时长16分

比赛链接

D Wandering

Description

题目链接

Solution

设当前是第 ii 次行动，第 i−1i-1 次行动后完成后位置为 pp, 那么第 ii 次行动中能抵达的最大位置是 p+max⁡1≤j≤i∑k=1ja[k]p+\max\limits_{1 \le j \le i}{\sum\limits_{k=1}^{j}a[k]}，因此记录前缀和和前缀最大值即可。时间复杂度 O(n)O(n)。

Code

Wandering
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
LL n, m, a[MAXN], sum[MAXN], last, mx[MAXN];

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

signed main() {
    read(n);
    LL ans = 0;
    for (int i = 1; i <= n; i++) mx[i] = -1e18;
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        sum[i] = sum[i - 1] + a[i];
        mx[i] = max(mx[i - 1], sum[i]);
        ans = max(ans, mx[i] + last);
        last = last + sum[i];
    }
    cout << ans;
    return 0;
}

E Akari

Description

题目链接

Solution

对于 NN 个 bulbbulb，如果仅向四个方向搜索，直到遇到边界或 blockblock 为止，最后统计被照亮的区域，那么由于每次最多访问 (H+W)(H + W) 个格子，时间复杂度为 N∗(H+W)N * (H + W)。

上述操作过程中 bulbbulb 之间的区域会被访问多次。如果搜索时遇到其它 bulbbulb 即停止，两个 bulbbulb 之间的区域只会被访问 2 次。时间复杂度 O(HW)O(HW)。

Code

Akari
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
#include <bits/stdc++.h>
 
using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e3 + 3, MOD = 1e9 + 7;

int h, w, a, b, g[MAXN][MAXN], bulb[MAXN][MAXN], block[MAXN][MAXN], ans;
bool vis[MAXN][MAXN], light[MAXN][MAXN];

void dfs(int x, int y, int dx, int dy) {
    if (block[x][y]) return;
    if (x < 1 || x > h || y < 1 || y > w) return;
    light[x][y] = true;
    if (bulb[x + dx][y + dy]) return;
    dfs(x + dx, y + dy, dx, dy);
}
 
int main() {
    boost;
    cin >> h >> w;
    cin >> a >> b;
    for (int i = 1; i <= a; i++) {
        int u, v;
        cin >> u >> v;
        bulb[u][v] = 1;
    }
    for (int i = 1; i <= b; i++) {
        int u, v;
        cin >> u >> v;
        block[u][v] = 1;
    }
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            if (bulb[i][j]) {
                dfs(i, j, 0, 1);
                dfs(i, j, 0, -1);
                dfs(i, j, -1, 0);
                dfs(i, j, 1, 0);
            }
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            if (light[i][j]) ans++;
    cout << ans << endl;
    return 0;
}

F Valid payments

Description

题目链接

Solution

首先，由于收付款过程中使用货币种类最少，因此任意金额都可以通过尽可能先支付面值大的货币来唯一表示。同时，对于货币 ii, 有 cnti<ai+1aicnt_i < \frac{a_{i+1}}{a_i}，否则产生进位，用 1 个 ai+1a_{i+1} 面值的货币比用 ai+1ai\frac{a_{i+1}}{a_i} 个 aia_i 面值的货币更优。

题目问付款的方案数，等价于求找零的方案数。将 XX 按上述方法唯一分解后，设第 ii 种货币用了 gig_i 个，同时第 ii 种货币使用次数得上限为 limi=ai+1ai−1lim_i = \frac{a_{i+1}}{a_i} - 1。由于找零和支付不能使用同一种货币，因此对于某一种货币 ii, 要么不找，要么找 limi−gilim_i-g_i （gi≠0g_i \neq 0）个产生进位将这种货币消去使得支付时不会用这种货币。于是，容易想到设 dp[i][0]dp[i][0] 表示在第 ii 到第 n−1n-1 位中至少选了 1 位，第 ii 位没有得到来自上一位 (第 i−1i-1 位) 进位的方案数，dp[i][0]dp[i][0] 表示获得了上一位进位的方案数。接下来分三种情况讨论：

  • gi=0g_i = 0 : 如果上一位没有进位，此时一定不选第 ii 位，下一位也不会有进位，有 dp[i][0]=dp[i+1][0]dp[i][0] = dp[i+1][0]; 否则，有三种选择：

    • 不选第 ii 位，下一位不产生进位，有 dp[i+1][0]dp[i+1][0] 种方案。
    • 只选第 ii 位，有 1 种方案。
    • 选了第 ii 位，下一位产生进位，在第 i+1i+1 到 n−1n-1 位至少选一位，有 dp[i+1][1]dp[i+1][1] 种方案。

  • gi=limi−1g_i = lim_i - 1 ：若上一位产生进位，则这一位直接被消去，在下一位产生进位，此时有 dp[i][1]=dp[i+1][1]dp[i][1] = dp[i+1][1]。否则，有三种选择：

    • 不选第 ii 位，有 dp[i+1][0]dp[i+1][0] 种方案。
    • 只选第 ii 位，有 1 种方案。
    • 选了第 ii 位，下一位产生进位，在第 i+1i+1 到 n−1n-1 位至少选一位，有 dp[i+1][1]dp[i+1][1] 种方案。

  • 1<gi<limi−11 < g_i < lim_i - 1：不论上一位有没有进位，都有三种选择：

    • 不选第 ii 位，有 dp[i+1][0]dp[i+1][0] 种方案。
    • 只选第 ii 位，有 1 种方案。
    • 选了第 ii 位，下一位产生进位，在第 i+1i+1 到 n−1n-1 位至少选一位，有 dp[i+1][1]dp[i+1][1] 种方案。

最后答案为 dp[1][0]+1dp[1][0]+1，即至少选一位加上直接支付 XX 元不找零的方案数。时间复杂度 O(n)O(n)。

Code

Valid payments
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 55;
const int MOD = 1E9 + 7;
LL n, x, a[MAXN], g[MAXN], dp[MAXN][2];

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

signed main() {
    read(n, x);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = n; i >= 1; i--) {
        if (!x) break;
        g[i] = x / a[i], x %= a[i];
    }
    for (int i = n - 1; i >= 1; i--) {
        LL lim = a[i + 1] / a[i];
        if (g[i] == 0) {
            dp[i][0] = dp[i + 1][0];
            dp[i][1] = dp[i + 1][1] + dp[i + 1][0] + 1;
        } else if (g[i] == lim - 1) {
            dp[i][0] = dp[i + 1][0] + dp[i + 1][1] + 1;
            dp[i][1] = dp[i + 1][1];
        } else {
            dp[i][1] = dp[i + 1][1] + dp[i + 1][0] + 1;
            dp[i][0] = dp[i + 1][0] + dp[i + 1][1] + 1;
        }
    }
    cout << dp[1][0] + 1;
    return 0;
}