A-Cake

题意

Oscar和Grammy玩游戏，第一阶段两人轮流在有根树上走，走到叶子停止，经过的边有两种，标0边或者标1边，记录走下的01串。设01串的长度是$m$，第二阶段Oscar将蛋糕切成$m$份，有些蛋糕可以是空的，按照第一阶段的01串顺序依次拿蛋糕（1代表Grammy拿，0代表Oscar拿），两人都想获得最多的蛋糕，求最后Grammy获得的蛋糕比例。

数据范围

• $1\leq n\leq 2\times 10^5$

思路

在第二阶段，Oscar分蛋糕的时候，是对当前串寻找一个0占比最大的前缀，然后拿走占比一致的蛋糕。

于是，在第一阶段时，首先树上每个节点即代表一个前缀，预处理出每个节点为前缀时0的占比，在之后两人轮流取数时，Oscar会取选择下一个节点轮流选择后0占比最大的节点，Grammy会选择0占比最小的节点。

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

题意

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

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$，则可以将所有人都运输到对岸。

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)$

A-Floor Tiles

题意

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

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

数据范围

• $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 $$ 时，形成的环是最小的。