Znzryb's Blog
0%

Posted on Edited on

题目大意

巴巴拉有一个花园。这个花园可以表示为一个n×mn \times m的网格。她在花园里放置了kk块石板，这样她每天可以享受从一块石板跳到另一块石板。这些石板的索引从11到kk。每块石板完全占据花园中的某个单元格，并且没有两块石板放置在同一个单元格上。

然而，一个邪恶的人，巴巴拉，打算放置一个特殊设备，它将占据花园中的一个矩形区域。如果任何石板与设备重叠，它将爆炸并摧毁整个花园！

为了避免爆炸，巴巴拉想通过在花园内移动石板来重新排列石板。在重新排列石板期间，石板应保持不重叠。花费的能量等于所有已移动的石板中最大的索引。现在，巴巴拉想知道重新排列石板所需的最小能量，这样她就可以为“其他目的”节省能量。

例如，假设设备将放置在蓝色矩形区域。然后，巴巴拉可以按以下方式重新排列石板。请注意，在整个过程中，石板不会重叠，不仅在重新排列之后。所有已移动的石板的索引最多为44，因此花费的能量为44。

image

思路讲解

判定 E 是否可行（check(E)）

  1. 如果矩形里存在编号 > E 的石板：它动不了，又在矩形里 ⇒ 直接不可行。

  2. 在整张网格上，把所有“编号 > E 的石板格子”删掉（当墙），对剩余格子做 BFS/DFS 求连通块。

  3. 对每个连通块 CC 统计：

  • t(C)t(C)：这个块里 编号 <= E 的石板数量（可移动棋子数）

  • s(C)s(C)：这个块里 不在矩形内 的格子数量（最终可安置容量）
    必须满足对所有块：t(C)≤s(C)t(C) \le s(C)
    否则该连通块里有“多出来的棋子”无论怎么挪也得有人留在矩形里 ⇒ 不可行。

  1. 单调性：E 越大，你能动的石板越多（墙越少），只会更容易可行 ⇒ 可以对 E 在 [0,k][0,k] 二分最小可行值。

对于一连通块，这个合法，其实就是在炸弹区的石块数量≤炸弹区外空白数量在炸弹区的石块数量≤炸弹区外空白数量。

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
auto bfs=[&](ll threshold,ll x,ll y) -> bool  {
    queue<pair<ll,ll>> q;
    vis[x][y]=tim;
    q.push({x,y});
    ll block_in_cnt=0,space_cnt=0;
    while (!q.empty()) {
        auto [px,py]=q.front();
        q.pop();
        if (is_in(px,py)) {
            if (maze[px][py]>0) {
                block_in_cnt++;
            }
        }else {
            if (maze[px][py]==0) {
                space_cnt++;
            }
        }
        for (int i=0;i<4;++i) {
            ll tox=px+dx[i],toy=py+dy[i];
            if (is_valid(threshold,tox,toy)) {
                vis[tox][toy]=tim;
                q.push({tox,toy});
            }
        }
    }
    if (space_cnt>=block_in_cnt) {
        return true;
    }
    return false;
};

AC代码

AC
https://codeforces.com/gym/106084/submission/361123071

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

Mitty是一位勇敢的冒险者，正在探索一个被称为深渊的神秘地下洞穴系统。深渊由nn个平行垂直井和mm个水平隧道组成。每条隧道恰好连接两个相同深度的井。所有mm个隧道的深度各不相同，令人惊讶的是，每条隧道的中间都藏有一宝藏！

Mitty可以选择任意一个井开始。他从所选井的顶部向下移动，遵守以下规则：

  • 他只能向下移动，不允许向上移动。

  • 每当他遇到水平隧道时，必须立即进入，并将到达连接的井。

  • 一旦他进入水平隧道，就不能回头。

这些隧道中的宝藏有各种价值。Mitty想要尽可能多地收集宝藏。请帮助他计算从一个井开始时他可以收集到的最大总宝藏价值。

最大样例的示例图：

image

思路讲解

可以把两个值绑在一起，当然三个，四个也是可以的。

注意，由于必须移动，因此不能够去 max。

1
2
3
4
5
6
7
8
9
10
11
12
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> dp(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v,w;
        cin>>u>>v>>w;
        tie(dp[u],dp[v])=(pair<ll,ll>){dp[v]+w,dp[u]+w};
    }
    ll ans=*max_element(all(dp));
    cout<<ans<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106084/submission/361088193

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

两个字符串uu和vv之间的编辑距离是将uu转换为vv的最小编辑操作次数。可以对字符串应用三种编辑操作：插入字符，删除字符，用不同字符替换某个字符。

例如，我们可以用四次替换将hello转换为world，因此编辑距离最多为44。您可以用两次替换和一次插入将wally转换为walter，因此编辑距离最多为33。计算两个字符串之间的编辑距离是一个众所周知的问题，有许多应用。

当前任务是计算一个字符串到最接近的回文串的编辑距离。回文串是从后往前读和从前往后读相同的字符串，例如madam。

hello到最接近回文串的编辑距离仅为22：我们可以用两次编辑操作将hello转换为ollo，或hllh，或elle。

编写一个程序，可以找到一个单词到最接近回文串的距离。

思路讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
auto dfs=[&](auto && self,ll l,ll r) -> ll {
    if (r==l) {
        return 0;
    }
    if (r-l==1) {
        return s[l]!=s[r];
    }
    if (dp[l][r]!=INF) {
        return dp[l][r];
    }
    dp[l][r]=min({self(self,l+1,r-1)+(s[l]!=s[r]),      // 替换
        self(self,l,r-1)+1,     // 删除右侧（等价于左侧插入一个相同的抵消）
        self(self,l+1,r)+1,     // 删除左侧（等价于在右侧插入一个相同的）
    });
    return dp[l][r];
};

AC代码

AC
https://codeforces.com/gym/106084/submission/361098919

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

Jerry和Tom正在一个有nn个顶点的有向图GG上玩一个游戏，顶点编号从11到nn。对于每个顶点1≤u<n1 \le u < n，从uu到u+1u+1有一条有向边。此外，还有mm条额外的有向边。第ii条额外边从uiu_i到viv_i。

图GG具有以下特殊性质：不存在两条有向边(ui→vi)(u_i\to v_i)和(uj→vj)(u_j\to v_j)使得ui<uj<vi<vju_i < u_j < v_i < v_j。

在游戏开始时，Jerry和Tom分别站在顶点xx和yy上，其中x≠yx \ne y。游戏按照轮次进行。在每个轮次中，玩家根据以下规则行动，Jerry先行，然后是Tom：

  • Jerry 必须选择从他当前顶点出发的一条出边****并沿着它移动到终点。如果他当前顶点没有出边，则他保持原地。

  • Tom 可以选择从他当前顶点出发的一条出边并沿着它移动到终点，或者选择不移动并保持原地。

如果在任何轮次结束时，Jerry和Tom在同一个顶点上（包括在顶点nn处），游戏立即结束且Tom获胜。否则，如果Jerry最初在顶点nn，或在任何轮次结束时到达顶点nn，Jerry获胜。

注意，如果在一轮之后，Jerry和Tom都在顶点nn，则Tom获胜。

在整个游戏过程中，两个玩家都知道对方的位置。

可以证明游戏会在有限轮次内结束。

对于一对整数1≤x,y≤n1 \le x,y \le n，x≠yx \ne y，定义f(x,y)f(x,y)如下：

  • Jerry和Tom将进行一个游戏，其中Jerry从顶点xx开始，Tom从顶点yy开始。Tom想赢，但他也想最小化他实际移动的次数（即，他改变顶点的轮次数；原地不算移动）。假设双方都以最佳方式行动，如果Tom不能赢则令f(x,y)=0f(x,y)=0；否则，令f(x,y)f(x,y)为Tom强迫赢所需的最小移动次数。如果Tom在最佳游戏中获胜，Jerry仍会尽力最大化Tom必须移动的次数。

计算

∑1≤x,y≤n,x≠yf(x,y). \sum\limits_{1 \le x,y \le n, x \ne y}f(x,y).

思路讲解

我们梳理一下题意，并进行一下样例解释

image

题目不允许这样子的两条边存在。

image

在样例 2 中，贡献为 1 的两种情况。

如果说没有额外的边，那么答案就是 00。因为 Tom 在 Jerry 前面，反正肯定赢不了。Tom 在 Jerry 后面，守株待兔即可。可以发现，无论什么情况，根据定义，都是 00。

我们现在这个问题还是回来，什么时候肯定不会有这个追及，有这个贡献？其实就是如果把额外边当作区间加法的话，Tom 在没有被任何区间覆盖的地方，肯定是不会有答案贡献的。

不过我们发现，这样子一种一种情况看，实在是太慢了。既然是博弈题目，那么Tom 和 Jerry 的最优策略是什么呢？就是每步都走最远的边。

因此，我们不妨把 Tom 走的路径，以及 Jerry 走的路径绘画在一张图上（按照上面说的最优策略），这张图，其实是一颗树。

或者，换句话说，我们只保留每个点的最长出边（这样子就可以形成一颗树），较短的出边，我们直接删除（因为不符合）。

接着就是来处理这个贡献与计算问题了。

我们想要计算的就是，当我们已经知道 一个点 uu，在其他所有树上，比他的深度浅或者同样深度的所有点，记作 VV 集合，贡献为：

∑v∈Vdep(u)−dep(lca(u,v))\sum_{v\in V}\text{dep}(u)-\text{dep}(\text{lca}(u,v))

这个问题，有许多解决方法，不过，我们这里选择使用启发式合并。

启发式合并的关键就是，合并过程复杂度，必须要依赖于轻儿子的这个子树的参数（如节点数量，深度等），不能够依赖于遍历重儿子。

不过，这个要求并不难，使用前缀和，搞一搞，就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 计算答案，把轻儿子节点合并进主集合中。
for (auto [dep_son,cnt]:node_dep_cnt_mtx[to]) {
    // cnt 是深度为 dep_son，较大的节点的数量（Jerry），get_presum_val 拿到的
    // 是所有比 dep_son 小的点的 dep(v)-dep(lca(u,v)) 的这个和
    ans+=cnt*get_presum_val(dep_son);
    // 深度相同的节点可以反复贡献（可以理解为上面也可以贡献，下面也可以贡献）
    ans+=cnt*node_dep_cnt_mtx[u][dep_son]*(dep_son-dep);
    // 这个是深度比 dep_son 大的节点的数量
    ll num_gt_dep=sum_node-get_presum_num(dep_son);
    // 深度比 dep 深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
    // 合并进来的时候还没有这样一个节点，贡献的就是 dep_son-dep(lca)
    ans+=num_gt_dep*cnt*(dep_son-dep);
    // 这里是顺手进行一个更新
    node_dep_cnt_mtx[u][dep_son]+=cnt;
}

注意这个有可能出现重儿子比轻儿子的这个链长短的这个情况（当然可以变为分长儿子/短儿子）。这个时候直接取这个前缀和，因为我们用 map 实现，就会取到 00。这个时候可以用一个匿名 get 函数特判一下这个情况。

这种情况的一个 hack 数据：

1
2
3
4
5
6
1
7 2
3 7
4 6

ans:20

AC代码

AC
https://codeforces.com/contest/2188/submission/361002651

心路历程（WA，TLE，MLE……）