题解codeforces round 879

# 思路 任意两个序列都有至少一个相同的元素，但相同的元素不必在相同的位置。 保证每两个之间都要有相同的元素？ 我们先考虑一下 $n=k\times 2$ 的情况，此时如果你左边取一半,右边取一半,这时两边的元素才可能不一样。 那么当 $n using namespace std; typedef ......

一道贪心题。 根据题意，我们需要在原序列中找出一条从 $1$ 到 $n$ 的路径，这条路径能被分成几个长度为 $k$ 且颜色相等的连续段。我们可以将这个问题简单化，那么这个问题就能被转化为从 $1$ 开始向后找一个颜色连续段，从 $n$ 开始向前找一个颜色相同的连续段，只要这两个连续段不相交即可，代 ......

我们首先可以观察到这道题的 $m$ 很大，所以要考虑这么多列里面是否存在一个性质，让我们求出前 $n$ 列之后快速求出后 $m$ 列的答案。观察一下可以发现第 $i,j$ 两列的答案等价时满足 $i \equiv j \pmod n$。这样的话我们只需要求出前 $n$ 列的答案即可。记 $s_i$ ......

这道题显然是一道 dp。转移方程式也很好推，我们记 $f_{i,j}$ 为前 $i$ 位且第 $i$ 位为 $j$ 的 DNA 序列数量。而对于输入的字符串，我们用 $vis_{i,j}=0$ 表示第 $i$ 个字母后面不能放第 $j$ 个字母。那么转移方程式即为： $$f_{i,j}= \sum ......

# CF1178F1题解 根据题意，每次选择一个区间染色，我们可以发现这道题满足了区间 dp 的一些性质，即区间答案可以合并，大区间的答案可以由小区间的答案更新而来。那么我们就可以设 $f_{i,j}$ 表示区间 $i$ 到 $j$ 的答案，那么接下来就考虑如何转移。然后考虑到题目要求从 $1$ 到 ......

这是一道比较板子的数位 dp 。 首先观察到 $k$ 很大，肯定不能用枚举的方法求，然后就考虑用数位 dp 。对于这道题来说，我们可以在用记忆化搜索做数位 dp 的时候存一个当前各数位之和对 $d$ 取余的余数，当把数填完之后判断余数是否为 $0$ 就能判断这个数是否符合条件。 ```cpp #in ......

这是一道~~比较简单~~的博弈论。 我们假设 $x \ge y$，那么此时可以分两种情况讨论： - $x using namespace std; #define int long long inline int read(){ int f=1,w=0; char c=getchar(); whil ......

简要题意： 对于一张$n$条边的无向完全图，每条边有两个权值$a_i,b_i$,求一棵最小生成树使其$\frac{\sum{a_i}}{\sum{b_i}}$最小。 这道题如果没见过这种技巧可能不好想，但我们也可以考虑一个朴素的想法，那就是猜！ 我们猜这个答案是$ mid$,然后就可以推一下柿子。 ......

显然，我们可以先忽略两个串已经一样的部分，只考虑剩下不一样的部分，然后我们就可以将它抽象成一个链上游走问题。我们记 $g_i$ 为从第 $i-1$ 个到第 $i$ 个点的期望步数，此时 $g_1=1$。且 $g$ 满足： $$g_i=\frac{n}{n-i}+\frac{i \cdot g_{i- ......

## A.Ekiden Race ### 题目描述： 有 $n$ 个人参加了往返赛跑，每个人有一个编号 $1$ 到 $n$。已知以下信息： - 如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第 $i$ 个人在往路中排名第 $i$。 - 如果按照往返的成绩排序，那么任何两个人的成绩都不相同 ......

## B. The Corridor or There and Back Again > # ......

## $A. Two Vessels$ 一开始我以为那个 $c$ 桶只能装满，看了好久。 范围内的任意容量都可以取的话，那么只要看需要转移多少量，然后看需要多少次。 ```cpp void solve(){ int n=read(),m=read(),k=read(); double nd=abs( ......

## Description 奶牛旅馆可以被看作一个 $N$ 个节点 $M$ 条边的无向简单图，其中每个房间有一个颜色 $C_i$，以及一个钥匙，颜色为 $S_i$， FJ 最初在 $1$ 号节点，手上一把钥匙都没有。 FJ 可以进行无数次以下操作： - 捡起当前房间的钥匙。（FJ 可以同时手持多个 ......

## $A. Cowardly Rooks$ 我模拟了一遍，因为我没看到题目中*给出的矩阵已经合法*， $a$ 题第一次写这么多。 实验室同事跟我说只要判断 $n$ 和 $m$ 的大小关系就行了。 ```cpp int x[N],y[N],m,n; bool check(){ for(int i=1 ......

双倍经验 [CF559C](https://www.luogu.com.cn/problem/CF559C) 前置知识：网格图内任意两点间的路径数量。这个我们可以通过组合数的方法计算出来。假设我们从点 $(1,1)$ 走到点 $(i,j)$，在这个过程中我们的移动步数是 $|i-1+j-1|=|i+ ......

[C. Infected Tree](https://codeforces.com/problemset/problem/1689/C "C. Infected Tree") > 题意：给定一棵树, 钦定 $ 1 $ 号点为根节点, 一开始根节点中毒了, 接下来的 $ n $ 个时刻, 每一时刻可以 ......

被 C 卡了。 最后被 E 的各种分讨劝退，但是同时也学习到了一种换根 dp 的简单写法。 评价：It's educational for me. ## A.Typical Interview Problem ### 题目描述： 有一个包含 F 和 B 的字符串，最开始是空的。我们开始从 $1$ 向 ......

## 前置知识： ### 1. [P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376) ### 2.[P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P489 ......

某网站的题解标点符号的要求真是a piece of bloody shit. 在这里会自由一些. ## 0. 题目大意 题目的大意是模拟黑白棋游戏。简单而言有如下的要求： - 列出可能的移动。合法移动的规则是：新下的棋子必须 "夹住" 原来的。所谓夹住，其实就是一段横向、竖向、斜向的棋子之间的两段必 ......

链接：[https://codeforces.com/gym/104025](https://codeforces.com/gym/104025) ## A. Gifts in box ```cpp #include "bits/stdc++.h" using namespace std; usin ......

# AtCoder Beginner Contest 308 A~G ## A. New Scheme ```cpp void Main() { vector a(8); for (auto &x : a) cin >> x; if (!is_sorted(a.begin(), a.end()) & ......

# CF1374E2 Reading Books(hard version) 这道题是在 [CF1374E1 Reading Books(easy version)](https://www.luogu.com.cn/problem/CF1374E1) 的基础上出的，而且仅仅增加了一个 $m$ 的限 ......

~~被这个题折磨了好久，决定写一篇题解~~ 先考虑没有这个$k$的限制的情况，等价于对原来的$a_i$序列的差分数组$b_i$,每次找到两个位置$1\le x 0$的位置进行$-1$的操作，后面对应的$+1$可以放在$b_ic[i]$,那么$c[i]$减去$k$对答案的贡献就是$0$,因为$d[i] ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF960G "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/960/G "CF 传送门") 发现设排列最大值位置为 $i$，那么 $[1, i] ......

[题目链接](https://www.luogu.com.cn/problem/P5021) 挺综合的一道题目。 询问最小值最大，考虑二分最小值，二分上下界是 $[最小边权,树的直径]$，但是为了方便我们直接设为 $[1,5\times 10^8]$ 即可。 考虑如何 $check$，可以采用类似树 ......

# CF1328E Tree Queries ## 题意 给定一棵以 $1$ 为根节点的有根树。 现在有 $q$ 次询问，每次询问给定 $m$ 个节点，问是否存在一条从根节点开始的链，使得每个节点到这条链的距离不超过 $1$ 。 ## 思路 我们首先可以给出一个结论：如果节点 $v$ 与一条链的距离 ......

题目链接：[https://hydro.ac/d/bzoj/p/3732](https://hydro.ac/d/bzoj/p/3732) 题目大意： 给定一个图，每次询问两个点 $u$ 和 $v$，在 $u$ 到 $v$ 的所有路径中找一条路径，且这条路径上的所有边的边权最大值最小。 解题思路： ......

[C. k-Tree](https://codeforces.com/contest/431/problem/C "C. k-Tree") > 题意：给定一颗 \$ k \$ 叉树, 每个节点和其子节点的连边的权值分别为 \$ 1, 2, \cdot\cdot\cdot, k \$, 问从根节点开始 ......

# CF1835 题解 ### A 考虑到 $a,b,c > 3$ 的最多只有 $5$ 个，可以直接循环枚举 $A$ 。首先将 $B$ 取到最小值，然后判断 $C$ 是否达到了最小值，如果没有就将 $B$ 和 $C$ 同时补齐。此时特判如果 $C$ 大于上限（就是 $\geq 10^{c}$ ），就 ......

# 9.6 CF1830 题解 ## A. Copil Copac Draws Trees [链接](https://www.luogu.com.cn/problem/CF1830A) 真弱智题不用讲 ## B. The BOSS Can Count Pairs ### 题意 每组数据给你一个 $n ......