差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:mian:cf_mashup:20200730 [2020/07/30 22:05]
grapelemonade [解法]
+++ 2020-2021:teams:mian:cf_mashup:20200730 [2020/08/04 19:19] (当前版本)
grapelemonade [解法]
@@ 行 245: / 行 245: @@
 ===== A - Writing Code (543A) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Gary//**
 ==== 题意 ====
+n个人，每个人填一行需要a_i的代价，问n个人按顺序填满m行(每个人可以填任意行)代价不超过b的方案数
 ==== 解法 ====
+简单的dp
+<code>
+while(n--){
+    int x=read();
+    for(int i=1;i<=m;i++){
+        for(int j=x;j<=b;j++){
+            (f[i][j]+=f[i-1][j-x])%=mod;
+        }
+    }
+}
+</code>
 ===== B - Destroying Roads (543B) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Gary//**
 ==== 题意 ====
+连通图问最多删除多少遍可以仍使得$distance(s1,t1)\le l1,distance(s2,t2)\le l2$
+$1\le n,m \le 5\times 10^3$
 ==== 解法 ====
+bfs求出所有点对的最短路，两种情况即$s1 \to t1$和$s2\to t2$是否有重合的路径
+  - 没有则删除最短路以外所有点
+  - 有则$n^2$枚举重合的道路，删去路径以外所有边
+所有情况取最大值即可
 ===== C - Remembering Strings (543C) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Gary//**
 ==== 题意 ====
+n个长m的串，$(1\le n,m \le 20)$修改每一个位置的串需要$v_{i,j}$的代价，问最小的代价使得每个串只要有一位满足它与其余串的该位都不相同
 ==== 解法 ====
+状压表示已经处理过的串，枚举状态每次只更改最小的没有被处理的串，对于该串，枚举每一位，要么更改这一位的字母，要么更改所有串这一位上与它字母相同的串并且保留更改代价最小的，这样的贪心可以使总代价最小
 ===== D - Road Improvement (543D) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Withinlover//**
 ==== 题意 ====
+给定一颗无根树，树边可以黑白染色。对于选定的中心节点 $x$，一个优秀的染色方案应当满足树上任意一点到中心节点的路径上黑色的树边至多只有一个。
+对于每个节点 $n$，求出以该节点作为中心节点时的染色方案数。
+$n \leq 2e5$
 ==== 解法 ====
+考虑换根dp
+当中心节点确定时，显然可以通过简单的树形DP解决。
+方程为 $dp[x] = \prod(dp[son[x]] + 1)$
+不难发现，当根节点移动时，仅会影响一条边上的两个节点的 $dp$ 数组，而这个可以 $O(1)$ 的进行转移。再模意义下 $dp[son[x]] + 1$ 的值可能为 $0$，此时逆元不存在，用前缀和后缀计算一下就可以了。
+总复杂度 $O(n)$
 ===== E - Paths and Trees (545E) =====
@@ 行 280: / 行 325: @@
 ==== 题意 ====
 ==== 解法 ====
@@ 行 293: / 行 340: @@
 ===== G - Mike and Frog (547A) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Gary//** & **//Pantw//**
 ==== 题意 ====
+$h1=(h1*x1+y1)%m,h2=(h2*x2+y2)%m$,问多少轮后恰好$h1=a1，h2=a2$;
+$1\le m le 2\times 10^6$
 ==== 解法 ====
+找到第一次出现a1，a2的位置，再找出运算出现循环的长度，可以保证这些值如果存在会在m次内找到
+枚举h1循环了多少次后，判断时候恰好都相同(感觉会在m次循环内重合，不太会证)
+有一个细节是a1或a2有可能在循环节出现前出现，也就是不在循环中，需要特判一下
 ===== H - Mike and Feet (547B) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Gary//**
 ==== 题意 ====
+一个长n的序列a，问长度为i的所有子串串内最小值的最大值，$(1\le i \le n)$
+$1\le n \le 2\times 10^5$
 ==== 解法 ====
+对每个数维护其两侧第一个比它小的数的位置l和r,可以发现长度r-l-1以内的子串的答案都会被$a_i$更新一遍
+所以只需要两次单调栈维护出l和r，在线段树上更新区间最大值，最后在线段树上查询n次
 ===== I - Mike and Foam (547C) =====
@@ 行 333: / 行 397: @@
 ===== L - Regular Bridge (550D) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Withinlover//**
 ==== 题意 ====
+给定 $k$，构造一个每个节点的度数都是 $k$，且包含至少一条割边的图。
 ==== 解法 ====
+尝试了半天，宣判 $k = 2 * s$ 的情况无解
+对于 $k = 2 * s - 1$ 的情况，可以构造 4 个包含 $s$ 个点的完全图，然后添加两个点作为割边的两端。剩下的凭感觉对称的构造上去就可以了
 ===== M - Brackets in Implications (550E) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Withinlover//**
 ==== 题意 ====
+给定一个仅包含 $\{0, 1, \to \}$ 的离散公式，询问是否可以添加若干个括号使得这个公式的计算结果为 $0$。
 ==== 解法 ====
+末尾为 $1$，不管怎么加括号答案都是 $1$ ，无解
+末尾为 $0$，考虑构造 $1 \to 0$，倒数第二位是 $1$ 就直接做完了。如果不是 $1$ 的话考虑构造 $(0\to 0) \to 0$，第二个 $0$ 可以迭代的拆成 $1\to 0$，即 $(0\to (1 \to 0))\to 0$，然后就做完了
+$n = 1$ 和 $n = 2$ 的情况特殊一点，特判一下
 ===== N - GukiZ hates Boxes (551C) =====
@@ 行 446: / 行 524: @@
 亦即我们可以仅对与 $m$ 数量级相当（或比其小）的砝码搜索。
-当 $n=5$ 时，只需搜索到 $5^13=1,220,703,125$ 即可。
+当 $n=5$ 时，只需搜索到 $5^{13}=1,220,703,125$ 即可。
 可见 $n>5$ 时，需要考虑的元素数量不超过 $13$。
@@ 行 482: / 行 560: @@
 <del>不会吧不会吧不会真的有人不会判三点不共线吧</del>
+题解说枚举直线然后把直线拿个 map 存下来，记录出现次数。
+这样的话是 $\Theta(n^2\log n)$ 的。
 ===== S - Vanya and Brackets (552E) =====
@@ 行 503: / 行 585: @@
 Code as follows:
-<hidden><code>
+<hidden><code python>
 S = input()
 N = len(S)
@@ 行 541: / 行 623: @@
 ===== W - Case of Fugitive (555B) =====
-  * Solved by **//QwQ//**
+  * Solved by **//Withinlover//**
 ==== 题意 ====
+无限长的河流上有 $n$ 块石头，每一块用一个区间 $[l, r]$ 表示，你有 $m$ 块木板，每块的长度固定。
+你需要依次将着 $m$ 块石头用木板连起来，即1连2，2连3，3连4……
+询问是否存在摆放木板的方案，如果有，输出方案。
 ==== 解法 ====
+$n$ 块石头之间需要 $n - 1$ 块木板，对木板长度的要求可以转换成 $n - 1$ 条形如 $[l, r]$ 的限制条件。木板的长度视为单点，就转换成了一个经典的贪心。
 ===== X - Case of Chocolate (555C) =====
@@ 行 591: / 行 680: @@
 一些关键代码如下。
-<hidden><code>
+<hidden><code cpp>
 tuple<Interval, Interval, int> Split (int pos, Direction dir) const {
   if(dir == UP)

CVBB ACM Team

用户工具

站点工具

差别

页面工具