AtCoder Beginner Contest 259

A - Growth Record

主人公 \(N\) 岁的时候身高是 \(T\) , 已知他 \([1,X]\) 期间每年长 \(D\) ，后面不长个子，问 \(M\) 岁的时候身高多少

\(0\) 岁的身高是 \(T−X\times D\) ，然后分情况讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int main() {
    int n = rd(), m = rd(), x = rd(), t = rd(), d = rd();
    int st = t - x * d;
    if (m > x) printf("%d\n", t);
    else printf("%d\n", st + m * d);
    return 0;
}

B - Counterclockwise Rotation

给定坐标 \((x,y)\) 问绕原点逆时针旋转 \(d\) 角度后的坐标。

坐标为 \(x^{\prime}=x * \cos d-y * \sin d, y^{\prime}=x * \sin d+y * \cos d\)，可以用各种方法(诱导公式/旋转矩阵)推。

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;
using ll = long long;
using ld = long double;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

const ld PI = 3.1415926535;
struct vec {
    ld x, y;
    vec turn (ld ang) { // 逆时针旋转 ang 角度
        ld cosa = cos(ang), sina = sin(ang);
        return (vec){x * cosa - y * sina, x * sina + y * cosa};
    }
};


int main() {
    vec a;
    a.x = rd(); a.y = rd();
    ld d = rd() / 180.0 * PI;
    a = a.turn(d);
    printf("%.10Lf %.10Lf\n", a.x, a.y);
    return 0;
}

C - XX to XXX

给定两个串 \(S\) 和 \(T\), 每次可以向 \(S\) 中相邻且相同的两个字符中间塞一个相同的字符。问若干次操作后 \(S\) 是否能变成 \(T\) 。

考虑双指针 \(\left(p t r_s, p t r_t\right)\), 从头对齐往后扫描，每次先不考虑扩张, 能不能匹配上。

如果不能匹配上，即 \(S\left[p t r_s\right] \neq T\left[p t r_t\right]\), 那么 \(T\left[p t r_t\right]\) 只能往回看，尝试用 \(S\left[p t r_s-1\right]\) 和 \(S\left[p t r_s-2\right]\) 来扩张, 否则无解。

记得最后要判断一下两个串的指针是否都走到了结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

#define N 200007

char s[N], t[N];

int main() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    int ptr = 1;
    for (int i = 1; i <= m; ++i) {
        if (s[ptr] == t[i]) {++ptr; continue;}
        if (s[ptr - 1] != t[i]) {puts("No"); return 0;}
        if (ptr <= 1 || s[ptr - 1] != s[ptr - 2]) {
            puts("No"); return 0;
        }
    }
    puts(ptr == n + 1 ? "Yes" : "No");
    return 0;
}

D - Circumferences

给定二维平面上的 \(n\) 个圆, 以及某个圆上的起点和某个圆上的终点。

只能走圆的边界 (可以通 过两圆交点更换所在的圆），问能否从起点走到终点?

并查集判连通性, 数据范围只需要 \(n^2\) 暴力枚举判断是否有交点即可。

判断两圆有交点：不相离也不包含。

  • 相离：圆心距大于两圆半径之和。
  • 包含：圆心距小于两圆半径之差的绝对值。
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 3007

ll x[N], y[N], r[N];

int f[N];

int find(int x) {
    return x == f[x] ? x : (f[x] = find(f[x]));
}

inline ll sqr(ll x) {return x * x;}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) f[i] = i;
    int sx = rd(), sy = rd();
    int tx = rd(), ty = rd();
    for (int i = 1; i <= n; ++i) {
        x[i] = rd(); y[i] = rd(); r[i] = rd();
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (sqr(x[i] - x[j]) + sqr(y[i] - y[j]) > sqr(r[i] + r[j])) continue;
            if (sqr(x[i] - x[j]) + sqr(y[i] - y[j]) < sqr(r[i] - r[j])) continue;
            int u = find(i), v = find(j);
            f[u] = v;
        }
    int px, py;
    for (int i = 1; i <= n; ++i) {
        if (sqr(sx - x[i]) + sqr(sy - y[i]) == sqr(r[i])) px = i;
        if (sqr(tx - x[i]) + sqr(ty - y[i]) == sqr(r[i])) py = i;
    }
    puts(find(px) == find(py) ? "Yes" : "No");
    return 0;
}

E - LCM on Whiteboard

给定 \(n\) 个数字的标准分解, 将其中的某一个变成 \(1\) , 问操作后所有数字的最小公倍数有多少种不同的可能性?

结论是所有数字的最小公倍数等于 每个质因数的指数 取 所有数字对应质因数指数的 \(\max\)。

一个数字变成 \(1\) 相当于对于 LCM 什么都不提供, 那么什么时候会导致 LCM 变化呢?

首先他的某一个质因数指数要和 LCM 对应的相同, 其次这个最大值在所有数字中是唯一的。

两个 unordered_map 实现： mx[i] 记录质因数 \(i\) 出现过的最大指数是多少, cnt[i] 记录有多少个数字对应这个最大指数。

那么一个数字有贡献也就对应于 e[i]==mx[i] && cnt[i]==1 。

此外没有影响的所有数字总体会对答案产生一个贡献, 即原本所有数的 LCM 。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

unordered_map<int, int> mx, cnt;

vector<pii> s[N];

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int m = rd();
        for (int j = 1; j <= m; ++j) {
            int a = rd(), b = rd();
            s[i].pb(mp(a, b));
            if (mx[a] < b) {mx[a] = b; cnt[a] = 1;}
            else if (mx[a] == b) ++cnt[a];
        }
    }
    bool fl = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        bool tag = 0;
        for (auto [a, b] : s[i]) {
            if (mx[a] == b && cnt[a] == 1) {tag = 1; break;}
        }
        if (tag) ++ans;
        else fl = 1;
    }
    ans += fl;
    printf("%d\n", ans);
    return 0;
}

F - Select Edges

给定一棵树, 每条边有一个边权 \(w\), 每个点有一个限制 \(d_i\) 。

选一个边集, 使得每个点相邻的边在这个集合里的个数不超过 \(d_i\), 并且最大化集合里边的 \(\sum w\) 。

设 \(f[i][0 / 1]\) 表示节点 \(i\) 及其子树内, 是否要选 \(i\) 到父亲的边 \((0/1)\) ， 能得到的最大价值。

  • 不选到父亲的边: 就是最多把 \(d_i\) 个儿子的贡献从 \(f [son] [0]\) 改为 \(f[s o n] [1] +w[u][son]\) ，挑能贡献最多的选（修改后较修改前差值最大的 \(d_i\) 个)
  • 选到父亲的边： 就是最多把 \(d_i-1\) 个儿子的贡献从 \(f [son] [0]\) 改为 \(f[s o n] [1] +w[u][son]\) ; 特殊的如果 \(d_i=0\) 则 \(f[i][1]=-\mathrm{inf}\)

直接 DP 就好了, 复杂度是 \(O(n \log n)\) 的（因为涉及到儿子贡献的排序）。

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
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 300007
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

vector<pii> e[N];
vector<ll> tmp;

int d[N];

ll f[N][2];

void dfs(int u, int fa) {
    ll sum = 0;
    for (auto [v, w] : e[u])
        if (v != fa) dfs(v, u);
    tmp.clear();
    for (auto [v, w] : e[u]) 
        if (v != fa) {
            sum += f[v][0];
            tmp.push_back(f[v][1] + w - f[v][0]);
        }
    sort(tmp.begin(), tmp.end());
    reverse(tmp.begin(), tmp.end());
    if (d[u] == 0) {
        f[u][0] = sum;
        f[u][1] = -1e18; 
    } else {
        f[u][0] = f[u][1] = sum;
        int len = tmp.size();
        for (int i = 0; i < len; ++i) {
            if (tmp[i] < 0) break;
            if (i < d[u]) f[u][0] += tmp[i];
            if (i < d[u] - 1) f[u][1] += tmp[i];
        }
    }
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) d[i] = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(), w = max(0, rd());
        e[u].pb(mp(v, w)); e[v].pb(mp(u, w));
    }
    dfs(1, 1);
    printf("%lld\n", max(f[1][0], f[1][1]));
    return 0;
}

G - Grid Card Game

给定一个数字矩阵 \((1\le H,W\le 100)\) ，选定一些行一些列，使得：

  • 负数的位置所在行列不能同时选中。
  • 定义一个位置被覆盖当且仅当所在行/列被覆盖，最大化被覆盖的位置权值和。

假设把所有非负数都选了，考虑最小割表示选择需要产生的代价，两排点左边表示行右边表示列。

假如选第 \(i\) 行，代价就是该行的负值的和 \((S, R_i,-\sum_j\left[A_{i, j}<0\right] A_{i j})\)

假如选第 \(i\) 列，代价就是该列的负值的和 \((C_i, T,-\sum_j\left[A_{j, i}<0\right] A_{j i})\)

接下来两排点之间的边表示对应格子的状态，割掉表示选择了对应行列都未选

  • 若 \(A_{x,y}\ge 0\) ，则行列都未选的代价就是扣掉这个位置的贡献 \((R_i, C_j,A_{i j})\)
  • 若 \(A_{x,y}<0\) ，则所在行列不能同时选，即不允许左右都被割掉，那么限制的方法就是强制中间的边被割，即

Ex - Yet Another Path Counting

给定一个矩阵 \(A_{n \times n}(1 \leq n \leq 400)\), 从某个格子出发, 每次可以向右或向下走。问起点终点的数字相同的路径有多少条?

首先枚举数字是多少，然后考虑计算这个数字对应的所有点之间的贡献。根据每种数字出现次数讨论:

  • 如果出现次数不超过 \(n\), 那么直接暴力枚举任意两个位置算贡献, 答案是 \(\left(\begin{array}{c}\Delta x+\Delta y \\ \Delta x\end{array}\right)\) 。 复杂度是 \(O\left(\sum_{\sum c n t_i=n^2, c n t_i \leq n} c n t_i^2\right) \leq O\left(n \times n^2\right)=O\left(n^3\right)\) ，用 \(a^2+b^2 \leq(a+b)^2\) 放缩一下。

  • 如果出现次数超过 \(n\), 那么种类数不会超过 \(n\) 个, 对每种颜色跑一个 \(O\left(n^2\right)\) 的 DP：

    这个 DP 和 AGC001E 的方法是一样的，设 f[i][j] 表示所有可能的起点走到 \((i,j)\) 的总方案数。

    f[i][j] = f[i - 1][j] + f[i][j - 1] ，此外如果这个点是我们要的颜色还要 f[i][j]++ 。

因此总复杂度也是 \(O(n^3)\) 的。

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
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1007
#define NN 407
#define M 160007
#define mod 998244353
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

int n, c[N][N], a[NN][NN], f[NN][NN], ans;

vector<pii> pos[M];

inline void calc(int col) {
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % mod;
            if (a[i][j] == col) {
                f[i][j] = (f[i][j] + 1) % mod;
                ans = (ans + f[i][j]) % mod;
            }
        }
}

int main() {
    c[0][0] = 1;
    for (int i = 1; i < N; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) 
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
    n = rd();
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) {
            a[i][j] = rd();
            pos[a[i][j]].push_back(mp(i, j));
        }
    for (int i = n * n; i; --i) {
        if (pos[i].size() > n) calc(i);
        else {
            int sz = pos[i].size();
            for (int j = 0; j < sz; ++j)
                for (int k = 0; k < sz; ++k) {
                    auto [sx, sy] = pos[i][j];
                    auto [tx, ty] = pos[i][k];
                    if (tx < sx || ty < sy) continue;
                    ans = (ans + c[tx - sx + ty - sy][tx - sx]) % mod;
                }
        }
    }
    printf("%d\n", ans);
    return 0;
}