https://wiki.cvbbacm.com/ 2026-04-30T02:46:02+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-09-05T13:37:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&rev=1599284238&do=diff 动态规划 CF808E 题意 01背包，$n$个物品，重量只有$1,2,3$三种。$(n \le 10^5)$ 题解 枚举拿几个重量为$3$的，然后按照性价比给$1,2$的物品进行排序，拿最高的那一些，最后讨论一下进行微调即可（可以证明需要调整的数量不大）。$n$$(n \le 1000)$$\leq$$O(n^2)$$f_{i,0/1,0/1}$$i$$a$$k$$k \le \min(n, 20), n \le 10^5, 1 \le a_i \le n$$dp_{i,j}$$1 \sim i$$j$$dp$$dp_{i,j} = \min(dp_{k,j - 1} + w_{k + 1, i})$$w_{i, j}$$i \sim j$$dp$$dp$$w_{i,j}$$O(nk\log(n))$$n$$(1 \le n \le 15)$$f_{i,j,k}$$i$$j$$k$$O(2^n)$$O(n^23^n)$… text/html 2020-09-04T20:19:14+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E5%9B%BE%E8%AE%BA&rev=1599221954&do=diff 图论 CF1391E 题意 给出一张$n$个点$m$条边的无向联通图，现在要求在这张图中要么找到一个至少有$\lceil \frac{n}{2} \rceil$个点的路径，要么找到一个至少包含$\lceil \frac{n}{2} \rceil$个点集合，要求点的个数为偶数，每两个节点分为一组，每个节点只在一组，且任意两组一共四个点所生成的子图中边数不超过两条。$(2 \le n \le 5\cdot 10^5, 1 \le m \le 10^6)$$\ge \lceil \frac{n}{2} \rceil$$\lceil \frac{n}{2} \rceil$$\lfloor\frac{n}{2} \rfloor$$n$$m$$k$$w_i$$c_i$$U$$S$$1,2, \ldots , n$$\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$$(2 \le n \le 3 \cdot 10^5, n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2}), 1 \… text/html 2020-09-04T10:20:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E5%85%B6%E5%AE%83&rev=1599186044&do=diff 其它 CF837F 题意 给出一个长度为$n$的序列，问多少次前缀和操作后序列最大值可以超过$k$，保证序列至少有两个数为正。$(2 \le n \le 2 \times 10^5, 1 \le k \le 10^{18})$ 题解 由F题可知，前缀和操作的增长速度是$O(x^{n-1})$的，在$k=10^{18}$的数据范围下，只有$n=2,3$时暴力模拟复杂度过高，其它情况都可以直接暴力模拟。$n=2$$n=3$$0$$n$$0$ text/html 2020-09-04T09:20:22+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E5%A4%9A%E9%A1%B9%E5%BC%8F&rev=1599182422&do=diff 多项式 text/html 2020-09-04T20:55:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E5%AD%97%E7%AC%A6%E4%B8%B2&rev=1599224139&do=diff 字符串 CF802H 题意 构造两个字符串$s,p$，满足$s$有恰好$n$个子序列等于$p$，要求两者长度均不超过$200$。$(n \le 10^6)$ 题解 当$n=1$时，$s=a,p=a$满足条件，当$n=2$时，$s=abb,p=ab$满足条件。 我们设$t$为形如$abcd \cdots$的字符串，并保证任何时刻两字符串均满足$s=tu,p=t$$u$$n=1,2$$t$$x$$n\rightarrow2n+1$$s=txuxx,p=tx$$tx$$tu$$n$$t$$tuxx$$2n$$n\rightarrow2n+2$$s=txxuxx,p=tx$$n=1$$n=2$$O(\log n)$$n$$10^9+7$$(1 \le n \le 10^5, \sum|s_i| \le 10^6)$$L$$O(L)$$i$$s_i$$nxt_i$$nxt_i=z$$l=1,r=L$$s_i>nxt_i$$i$$l$$l++$$i$$r$$r--$$s_i>nxt_i$$O(L \log L)$… text/html 2020-12-24T20:07:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E6%95%B0%E5%AD%A6&rev=1608811628&do=diff 数学 CF803C 题意 请你构造一个长度为$k$的严格上升正整数序列，使得所有数的和恰好为$n$，并且所有数的最大公约数最大。输出这个序列。如果没有合法的序列输出$-1$。如果有多个合法的序列，可以输出任意一个。$(n,k \le 10^{10})$$\gcd$$\gcd \cdot \frac{k(k+1)}{2} \le n$$n$$\gcd=1$$10^9+7$$(n \le 10^5)$$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}1$$$$cnt_i=\sum_{j=1}^n[i|a_j]$$$$f_i=\sum_{j=1}^{cnt_i}\binom{cnt_i}{j}-\sum_{j=1}^Nf_j[i|j]$$$$=2^{cnt_i}-1-\sum_{j=1}^Nf_j[i|j]$$$i$$O(n \log n)$$n$$a_i$$$\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \ne 1}k \cdot \gcd(a_{p_{1}},a_… text/html 2020-09-05T11:23:45+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&rev=1599276225&do=diff 数据结构 CF803G 题意 将一个长度为$n$的序列复制$k$次，要求维护数据结构支持区间赋值与区间最小值查询，$q$次操作。$(n,q \le 10^5,k \le 10^4)$ 题解 线段树动态开点，对于没有开点的部分$[l,r]$，可以将原序列复制一遍到$2n$长度，将其对应到$[(l-1)\mod n+1,(l-1)\mod n+1+l-r]$$O(1)$$n$$q$$[l,r]$$k$$(n,q,k \le 10^5)$$a_i$$i$$k$$n+1$$[l,r]$$a_i>r$$n$$L_1$$L_2$$E(L_1)$$\frac{(L_1 - 1)E(L_1)}{L_1}$$a_i$$\frac{\sum_{i \in L_2} a_i}{L_2} = \frac{E(L_2)}{L_2}$$\frac{E(L_2)}{L_2 L_1}$$2^n$$k$$i \ge 1$$[(i-1) \cdot 2^k+1, i \cdot 2^k]$$k$$i \ge 1$$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$$[(2i-1) \… text/html 2020-09-05T11:54:09+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E6%A0%91%E4%B8%8A%E9%97%AE%E9%A2%98&rev=1599278049&do=diff 树上问题 CF802K 题意 给定一棵节点数为$n$的树，每一条边有一个权值。现在要求从$1$号点出发，在不经过一个点超过$k$次的情况下经过的边的权值和最大。 题解 设$f_{i,0/1}$为以$i$为根的子树中进去后回溯/不回溯的边权最大值，合并时将子树对应值排序即可，如果回溯的话只能从回溯的值里选，如果不回溯的话只能选一个不回溯的子树其它都要回溯，最后答案为$f_{1,1}$$n$$m$$i$$s_i$$G$$G$$m$$G$$u$$v$$u$$v$$G$$q$$u,v$$u,v$$-1$$(n,q\le 10^5)$$u$$mx[u]$$DP$$len$$u,v$$mx[u]+mx[v]+1$$\max(len[u],len[v])$$v$$u$$map$$O(n\sqrt{n}\log{n})$$n$$n$$1$$k$$(n \le 10^5, k \le n^2)$$x$$n-x$$x$$\min(x,n-x)$$a$$(x \mod 2 )\le a \le \min(x, n - x)$$\min(x,n-x)=x$$\sum (siz_i\mod 2) \l… text/html 2020-09-04T10:17:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E7%BD%91%E7%BB%9C%E6%B5%81&rev=1599185837&do=diff 网络流 CF808F 题意 $n$张卡，每张卡有数值$a$，价值$b$，等级$c$三个值，你可以更改自己的等级，你需要选一些卡，满足这些卡两两之间的数值和都不是质数，所有卡的等级不超过你的等级，且所有卡的价值之和不小于$k$$(n \le 100, a \le 10^5)$$2$$1$$2$$1$$1$ text/html 2020-09-04T09:21:51+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E6%9A%91%E5%81%87%E7%B2%BE%E9%80%89%E9%A2%98%E7%9B%AE:%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95&rev=1599182511&do=diff 计算几何