一只小菜鸡的Blog

https://img.dodolalorc.cn/i/2024/09/21/66ee459d33192.png

2024牛客暑假多校训练营Day5||补题

DODOLA 发布于 2024-07-31 更新于 2024-10-01, 收录于类别在学算法的日子里和系列题解记录

2024牛客暑假多校训练营Day4||补题

DODOLA 发布于 2024-07-31 更新于 2024-10-01, 收录于类别在学算法的日子里和系列题解记录

A-LCT

题意

给定一棵有根树，每次询问前$i$条边组成的森林中，第$c_i$个点为根的树的深度。

数据范围

$2\leq n\leq 10^6$
$1\leq a_i,b_i,c_i\leq n,a_i\neq b_i$

思路

带权并查集，维护每个节点在当前所属树的层数，维护所有以该节点为根节点的树的深度。

代码

 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
int deep[maxn], fa[maxn], dis[maxn];
int findfa(int x) {
    if (x == fa[x])return x;
    int fx = findfa(fa[x]);
    // 更新deep,旧根:fa[x],新根:fx
    deep[x] += deep[fa[x]];
    return fa[x] = fx;
}

void merge(int u, int v) {
    int fu = findfa(u);
    fa[v] = fu;
    deep[v] = deep[u] + 1;
    dis[fu] = max(dis[fu], dis[v] + deep[v]);
}

void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        fa[i] = i;
        deep[i] = 0;
        dis[i] = 0;
    }
    for (int i = 1;i <= n - 1;i++) {
        int u, v, c;cin >> u >> v >> c;
        merge(u, v);
        cout << dis[c] << " ";
    }
    cout << "\n";
}

C-Sort4

题意

给出一个排列，每次选择四个位置交换其中的元素，求将该排列排序成上升序列的最小操作次数。

2024牛客暑假多校训练营Day3||补题

DODOLA 发布于 2024-07-23 更新于 2024-10-01, 收录于类别在学算法的日子里和系列题解记录

A-Bridging the Gap 2

题意

在河岸的一侧有$n$个人，每个人有一个体力值$h_i$，有一艘船可以将人从一侧载到另一侧，每次航行需要至少$L$个人掌舵，每次掌舵会花费每个掌舵人的一点体力，当体力不足一点时，这个人不能再掌舵，船的容量最大是$R$，提问是否能够将这些人都运送到对岸。

数据范围

$1\leq L\lt R\leq n\leq 5\times 10^5$
$1\leq h_i\leq 5\times 10^5$

思路

贪心的运输，从左岸运输的最小次数是$k=\lceil \frac{n-R}{R-L} \rceil$，计算每个人最多的来回次数$a_i$，假如满足$\sum_{i-1}^{n} min(k,a_i)\geq k\times L$，则可以将所有人都运输到对岸。

2024杭电钉耙编程联赛Day1||补题

DODOLA 发布于 2024-07-19 更新于 2024-10-01, 收录于类别在学算法的日子里和系列题解记录

1001-循环位移

$(709/3775)$

题意

将字符串$S=S_0+S_1+S_2+…+S_{n-1}$循环位移$k$次后得到$S(k)=S_{k\bmod n }+…+S_{n-1}+S+0+…+S_{(k-1)\bmod n}$。

定义$[A]={A(k),k\in N}$。给出$T$组串$A,B$，询问$B$有多少个子串在$[A]$中。

数据范围

$|A|\leq |B|$
$\sum|B|\leq 1048576$

思路

思路1：字符串哈希

记字符串$A$的长度是$n$，将字符串$A$转变为首尾相连的样子（$A=A+A.substr(1,n-1)$），并计算其中每个长度为$n$的哈希值，用map存值，再对字符串$B$进行哈希，同样也对长度为$n$的子串计算哈希值，若有符合的则计数。

代码

代码1：字符串哈希

 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
ll ha[maxn], hb[maxn];
ll pwr[maxn];

void solve() {
    string a, b;cin >> a >> b;
    ll n = a.size();
    a = a.substr(1, n - 1) + a;
    ll la = a.size(), lb = b.size();
    a = " " + a, b = " " + b;
    pwr[0] = 1;
    map<ll, bool>mp;
    for (ll i = 1;i <= la;i++) {
        ha[i] = ha[i - 1] * bas1 + a[i];
        pwr[i] = pwr[i - 1] * bas1;
        if (i - n >= 0) {
            ll x = ha[i] - ha[i - n] * pwr[n];
            mp[x] = true;
        }
    }
    ll ans = 0;
    for (ll i = 1;i <= lb;i++) {
        hb[i] = hb[i - 1] * bas1 + b[i];
        if (i - n >= 0) {
            ll x = hb[i] - hb[i - n] * pwr[n];
            if (mp.count(x)) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

1002-星星

$(991/1659)$

2024牛客暑假多校训练营Day2||补题

DODOLA 发布于 2024-07-19 更新于 2024-10-01, 收录于类别在学算法的日子里和系列题解记录

A-Floor Tiles

题意

存在如下A型、B型两种砖：

https://img.dodolalorc.cn/i/2024/08/20/66c45194a139e.png

现用这两种砖拼成$N\times M$的矩形，提问是否有恰好存在$K$条曲线的平铺方式，曲线如下：

https://img.dodolalorc.cn/i/2024/08/20/66c451fa98412.png

数据范围

$1\leq T\leq 10^5$
$1\leq N,M\leq 800$
$1\leq K \leq 2\times N\times M$

思路

边缘一圈的点所在的线一定不是一个环，所以最少的线数相当于都是A型或B型时的线数，也就是$N\times M$个，若要比$N\times M$个多，则多的部分只能是图形中环的数目，贪心的让所有的环最小，则能构造出最多的环，最小的环如例图中一样，当平铺的方式是 $$ AB\\BA $$ 时，形成的环是最小的。

2024牛客暑假多校训练营Day1||补题

DODOLA 发布于 2024-07-16 更新于 2024-10-01, 收录于类别在学算法的日子里和系列题解记录

A-Bit Common

题意

计算满足长度为$n$，每个元素小于$2^m$，且存在至少一个子序列满足按位$AND$后是$1$的序列的数量。

答案对正整数$q$取模。

数据范围

$1\leq n,m\leq 5000$
$1\leq q\leq 10^9$

思路

https://img.dodolalorc.cn/i/2024/07/17/66978bf423ad6.png

如图按位分析，对于一个长度为$n$的序列，序列中的数分为$k$个末尾是$1$的数和$n-k$个末尾是$0$的数。