🎉2024牛客寒假营2||补题

A-Tokitsukaze and Bracelet

题意

根据手环的三个属性值判断手环的等级。

对攻击百分比来说，+0为100%，+1为150%，+2为200%
对体力和精神来说，+0在 $\{29,30,31,32\}$ 里选择，+1在 $\{34,36,38,40\}$ 里选择，+2固定为45

数据范围

$n(1≤n≤100)$

$a_i,b_i,c_i(a_i∈\{100,150,200\};b_i,ci∈\{29,30,31,32,34,36,38,40,45\})$

思路

模拟即可

参考代码

1
void solve() {
2
    int lv1[3] = { 100,150,200 };
3
    int lv2[9] = { 29,30,31,32,34,36,38,40,45 };
4
    int a, b, c;cin >> a >> b >> c;
5
    int ans = 0;
6
    for (int i = 0;i < 3;i++) {
7
        if (a == lv1[i]) { ans += i; break; }
8
    }
9
    for (int i = 0;i < 9;i++) {
10
        if (b == lv2[i]) {
11
            if (i < 4)ans += 0;
12
            else if (i < 8)ans += 1;
13
            else ans += 2;
14
            break;
15
        }
16
    }
17
    for (int i = 0;i < 9;i++) {
18
        if (c == lv2[i]) {
19
            if (i < 4)ans += 0;
20
            else if (i < 8)ans += 1;
21
            else ans += 2;
22
            break;
23
        }
24
    }
25
    cout << ans << endl;
26
}

B-Tokitsukaze and Cats

题意

关猫，每个猫被限制在一个单元格内就算被关住了，如图：

给猫的坐标，询问至少需要多少片防猫网能把他们全都关住。

数据范围

$n, m, k (1≤n,m≤300;1≤k≤n⋅m)$

$x_i, y_i (1≤xi≤n; 1≤yi≤m)$

思路

遍历坐标点判断它上下左右是否有隔板，如果没有则补充。

参考代码

1
void solve() {
2
    int n, m, k;cin >> n >> m >> k;
3
    map<pair<int, int>, bool>cats;
4
    int ans = 0;
5
    while (k--) {
6
        int x, y;cin >> x >> y;
7
        cats[{ x, y }] = true;
8
        pair<int, int>pu = { x - 1,y }, pd = { x + 1,y }, pl = { x,y - 1 }, pr = { x,y + 1 };
9
        int cnt = 4;
10
        if (cats.count(pu) != 0)cnt -= 1;
11
        if (cats.count(pd) != 0)cnt -= 1;
12
        if (cats.count(pl) != 0)cnt -= 1;
13
        if (cats.count(pr) != 0)cnt -= 1;
14
        ans += cnt;
15
    }
16
    cout << ans << endl;
17
}

E&F-Tokitsukaze and Eliminate

题意

有一排n个宝石，第i个的颜色是 $col_i$ ，可以进行如下的操作：

选一种颜色x，将颜色为x的最右边的那颗宝石及其右边的所有宝石全部消除。

数据范围

$T(1\leq T\leq 2 * 10^5)$

$n(1\leq n\leq 2 * 10^5)$

easy： $1\leq col_i\leq min(n,2)$

hard： $1\leq col_i\leq n$

思路

贪心，从右边枚举，当找到最后一种达到两次出现的颜色后，进行一次对该颜色的操作，直到所有宝石都被消除。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<int>col(n + 1);
4
    set<int>cls;
5
    for (int i = 1;i <= n;i++) {
6
        cin >> col[i];
7
        cls.insert(col[i]);
8
    }
9
    int tn = cls.size();    // 颜色种数
10
    map<int, int>clrs;
11
    map<int, int>colors;
12
    int ans = 0;
13
    int cnt = 0;
14
    int pi = n;
15
    while (tn != 0) {
16
        for (int i = n;i > 0;i--) {
17
            colors[col[i]]++;
18
            if (colors[col[i]] == 1) {
19
                cnt++;  // 达到两次及以上的颜色数
20
                if (cnt == tn) {
21
                    ans++;
22
                    cnt = 0;
23
                    colors = clrs;
24
                    pi = i - 1;
25
                }
26
            }
27
        }
28
        tn = colors.size();
29
        colors = clrs;
30
        n = pi;cnt = 0;
31
    }
32
    cout << ans << endl;
33
}

I-Tokitsukaze and Short Path (plus)

题意

有一个 $n$ 个顶点的完全图 $G$ ，顶点编号是 $1$ 到 $n$ ，编号为 $i$ 的顶点值是 $a_i$ ，边权的计算方式如下：

w_{u,v}= \begin{cases} 0& \text{u=v}\\ |a_u+a_v|+|a_u-a_v|& \text{u ≠ v} \end{cases}

$dist(i,j)$ 定义为以 $i$ 为起点到 $j$ 的最短路。

求：

\sum_{i=1}^{n}\sum_{j=1}^{n}dist(i,j)

数据范围

$T(1\leq T\leq 2\times 10^5)$

$n(1\leq n\leq 2\times 10^5)$

$a_i(1\leq a_i\leq 2\times 10^5)$

思路

|a_i+a_j|+|a_i-a_j|= \begin{cases} &a_i+a_j+a_i-a_j&=2\times a_i&\quad a_i\ge a_j \\ &a_i+a_j+a_j-a_i&=2\times a_j&\quad a_i\lt a_j \end{cases}

对 $a$ 进行排序，计算每个数对总和的贡献，也就是比某数小的数的个数。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<ll>a(n);
4
    for (int i = 0;i < n;i++) {
5
        cin >> a[i];
6
    }
7
    sort(a.begin(), a.end());
8
    ll ans = 0;
9
    for (int i = 0;i < n;i++) {
10
        ans += a[i] * i;
11
    }
12
    cout << 4 * ans << '\n';
13
}

J-Tokitsukaze and Short Path (minus)

题意

有一个 $n$ 个顶点的完全图 $G$ ，顶点编号是 $1$ 到 $n$ ，编号为 $i$ 的顶点值是 $a_i$ ，边权的计算方式如下：

w_{u,v}= \begin{cases} 0& \text{u=v}\\ |a_u+a_v|-|a_u-a_v|& \text{u ≠ v} \end{cases}

$dist(i,j)$ 定义为以 $i$ 为起点到 $j$ 的最短路。

求：

\sum_{i=1}^{n}\sum_{j=1}^{n}dist(i,j)

数据范围

$T(1\leq T\leq 2\times 10^5)$

$n(1\leq n\leq 2\times 10^5)$

$a_i(1\leq a_i\leq 2\times 10^5)$

思路

|a_i+a_j|-|a_i-a_j|= \begin{cases} &a_i+a_j-a_i+a_j&=2\times a_j&\quad a_i\ge a_j \\ &a_i+a_j-a_j+a_i&=2\times a_i&\quad a_i\lt a_j \end{cases}

如果 $u$ 到 $v$ 的直接路径的长度大于 $dist(u,w)+dist(v,w)$ ，则取后者，假设 $dist(u,v)=2\times a_v$ ，则有 $dist(u,w)+dist(v,w)=2\times a_v+2\times a_v=4\times a_v$ ，则只有当 $2\times a_w$ 的值小于 $a_v$ 时取后者找到数组中的最小值。

对 $a$ 进行排序，计算每个数对总和的贡献次数，也就是比某数或2×最小 $a_i$ 大的数的个数。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<ll>a(n);
4
    ll mn = 1e18;
5
    for (int i = 0;i < n;i++) {
6
        cin >> a[i];
7
        mn = min(mn, a[i]);
8
    }
9
    sort(a.begin(), a.end());
10
    ll ans = 0;
11
    for (int i = 0;i < n;i++) {
12
        ans += min(mn * 2, a[i]) * (n - i - 1);
13
    }
14
    cout << 4 * ans << '\n';
15
}