https://wiki.cvbbacm.com/ 2026-04-29T23:57:04+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-09-30T14:37:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E4%BB%BB%E5%8A%A1%E5%AE%89%E6%8E%92&rev=1601447837&do=diff 2020国庆 MJX：把最近CF补了，把剩余模板补了 CSK：补CF $5\leq$ ，按照cls的总结把几何模板摸出来，顺便练练构造题（<https://www.luogu.com.cn/training/14#problems>） ZYF：先把atcoder最近几场补了，然后每日亿题，冲！ text/html 2020-05-08T21:04:56+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%8E%8B%E4%BD%8D%E4%B8%93%E9%A2%98&rev=1588943096&do=diff 压位专题 团队Vjudge压位专题 总结 text/html 2020-08-11T22:24:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%8F%AF%E8%83%BD%E4%BC%9A%E6%9C%89%E7%9A%84%E4%BC%9A%E8%AE%AE%E8%AE%B0%E5%BD%95&rev=1597155856&do=diff 2020.08.11会议记录 text/html 2020-09-20T17:26:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%8F%AF%E8%83%BD%E4%BC%9A%E6%9C%89%E7%9A%84%E6%B3%A8%E6%84%8F%E4%BA%8B%E9%A1%B9&rev=1600593981&do=diff * 不要被旧题或类似题干扰，所有题都要当新题做。 * 不要盲目跟榜然后卡题，最好先把题过一遍（带模拟等长题面例外） * 记得换题，博弈根据情况决定做题顺序 text/html 2020-07-26T11:09:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%8F%AF%E8%83%BD%E4%BC%9A%E6%9C%89%E7%9A%84%E7%BB%8F%E9%AA%8C%E8%AE%B0%E5%BD%95&rev=1595732952&do=diff 1.不要被旧题或类似题干扰，所有题都要当新题做。 text/html 2020-08-07T16:47:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%9B%BE%E7%89%87&rev=1596790045&do=diff text/html 2020-09-05T15:42:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%A5%87%E6%8A%80%E6%B7%AB%E5%B7%A7&rev=1599291728&do=diff 感觉可以把巧妙的思路扔进来(?) 莫比乌斯反演技巧总结 裴蜀定理证明 text/html 2020-05-26T22:02:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%93%E9%A2%98&rev=1590501768&do=diff A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解: G * 题意: * 题解: H * 题意: * 题解: I * 题意: * text/html 2020-05-31T18:51:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E5%B7%AE%E5%88%86%E7%BA%A6%E6%9D%9F&rev=1590922299&do=diff 差分约束系统 概念 差分约束系统是关于 $n$ 个未知量的 $m$ 个形如 $x_i-x_j\le k$ 不等式组。一般来求解的存在性问题、最优值问题以及方程组的解。 经典模型 * 线性约束： * 一般是在一维空间里，给出一些变量，之后告诉你这些变量的大小约束关系，求某个变量的最大值/最小值$n$$d[i]$$i$$n$$i$$c_i$$d[i]$$[0,i]$$[a_i,b_i]$$d[b_i]-d[a_i-1]$$c_i$$d[i]$$0\leq d[i+1]-d[i]\leq 1$$dis$$k$$x$$y$$ dis_y \le dis_x + k $$ dis_y - dis_x \le k $$ x_i - x_j\le k $$ x_i - x_j\le k $$x_j$$x_i$$k$$dis$$x_i - x_j \le k$$x_j$$x_i$$k$$x_i - x_j \ge k$$x_j - x_i \le -k$$x_i$$x_j$$-k$$x_i = x_j$$x_i - x_j \le 0$$x_i - x_j \ge 0$$x_i$$… text/html 2020-09-29T23:13:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E6%9D%82%E9%A1%B9&rev=1601392398&do=diff 可能会有的会议记录 可能会有的注意事项 可能会有的队内日常 任务安排 text/html 2020-08-11T20:10:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E6%96%B0%E7%89%88min_25&rev=1597147833&do=diff 知乎传送门 text/html 2020-08-07T15:09:06+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E6%AF%8F%E6%97%A5%E4%BA%BF%E9%A2%98%E6%A8%A1%E6%9D%BF&rev=1596784146&do=diff 比赛链接 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 CF 题意 题解 text/html 2020-05-08T21:12:45+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E7%89%9B%E5%AE%A2%E5%81%87%E6%97%A5%E5%9B%A2%E9%98%9F%E8%B5%9B40&rev=1588943565&do=diff 牛客假日团队赛40 总结 text/html 2020-08-21T17:35:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E8%8E%AB%E6%AF%94%E4%B9%8C%E6%96%AF%E5%8F%8D%E6%BC%94%E6%8A%80%E5%B7%A7%E6%80%BB%E7%BB%93&rev=1598002532&do=diff 莫比乌斯反演技巧总结 常用狄利克雷卷积 * $\epsilon = \mu * 1$，证明：二项式定理$(1 - 1)^2 = 0$。 * $\operatorname{id} = \varphi * 1$，证明：真分数约分。 * $\varphi= \mu * \operatorname{id}$，证明：上面式子左右卷$\mu$。 常用套路 经典老番 求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$$ 先枚举$d = \gcd(i,j)$，再套用$\epsilon = \mu * 1$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]$$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\… text/html 2020-09-05T15:42:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86%E8%AF%81%E6%98%8E&rev=1599291764&do=diff 裴蜀定理：若ax+by = z，则 gcd（a，b）| z 再顺手证明一下裴蜀定理： 设k = gcd（a，b），则 k | a， k | b，根据整除的性质，有 k | （ax+by） 设 s为ax+by的最小正数值 再设 q = [a / s]（a整除s的值）；r = a mod s = a-q（ax+by） = a（1 - qx）+b（-qy）； text/html 2020-08-07T17:32:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:%E8%AE%AD%E7%BB%83%E6%A8%A1%E6%9D%BF&rev=1596792722&do=diff 比赛名称 比赛链接 A. upsolved by 题意 题解 B. upsolved by 题意 题解 C. upsolved by 题意 题解 D. upsolved by 题意 题解 E. upsolved by 题意 题解 F. upsolved by 题意 题解 G. upsolved by 题意 题解 H. text/html 2020-10-06T09:55:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2sozx&rev=1601949332&do=diff Todo List 学习笔记 * 字符串 * 数学 比赛 比赛模板 * 2020.05.06 Codeforces Round #639(Div. 1) * 2020.05.09 Educational Codeforces Round 83 (Rated for Div 2) * 2020.05.13 Codeforces Round #641(Div. 1) * 2020.05.17 Codeforces Round #643(Div. 2) * 2020.05.30 Educational Codeforces Round 87 (Rated for Div 2) * 2020.05.31 北交校赛 * 2020.05.31 Codeforces Round #646(Div. 2) * 2020.06.04 Codeforces Round #647(Div. 1) * 2020.06.22 Codeforces Round #645(Div. 2) * 2020.06.22 Educational Codeforces… text/html 2020-05-28T11:17:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2009-2010_acm-icpc_neerc_western_subregional_contest&rev=1590635822&do=diff 2009-2010 ACM-ICPC, NEERC, Western Subregional Contest 比赛链接 A solved by 2sozx * 题意：给定 $3\times N(N\le25)$ 个数，将其分为三个长度为 $N$ 的序列 $A,B,C$ ,使得 $\sum_{i=1}^{N}(A_i-B_i)\times C_i$ 最大。 * 题解：首先我们有两个很显然的结论：$B$ 一定是由最小的 $N$ 个数构成，$A_i\ge C_i$$(A_i-B_i)\times C_i +(A_j-B_j) \times C_j \ge (A_j-B_i)\times C_i + (A_i-B_j)\times C_j$$(A_i-A_j)\times (C_i-C_j) \ge 0$$(A_i-B_i)\times C_i +(A_j-B_j) \times C_j \ge (A_i-B_i)\times C_j + (A_j-B_j)\times C_i$$(A_i-B_i-A_j+B_j)\times (C_i-C_j) \ge 0$$(A_i-B_i… text/html 2020-10-15T18:09:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2016-2017_acm-icpc_neerc_southern_subregional_contest&rev=1602756572&do=diff 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest 比赛链接 A. solved by 2sozx 题意 给 $n$ 个数 $(2 \le n \le 100)$，每次可以选择 $2 \sim 5$ 个数将值减一，值不会小于零，最后要求所有数相等。求一种操作方案使得最后的数最大。 题解 $n$$n$$\lceil \frac{3 * n}{2} \rceil - 2$ text/html 2020-10-13T22:34:14+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2016_ccpc_%E5%90%88%E8%82%A5%E7%AB%99&rev=1602599654&do=diff 2016 CCPC 合肥站 比赛链接 A. solved by 2sozx 题意 给定一个竞赛图，将其拆成两个子图 $P,Q$。 定义一个图有传递性为 $a\to b,b\to c$ 有 $a\to c$，问 $P,Q$ 是否具有传递性。$n\le 2016$ 题解 $bitset$ 直接搞，$O(\frac{n^3}{w})$。 写题解时突然发现这不是必然 $Tle$ 了么，比赛时候复杂度算错了，少算个 $n$$n,n\le 40000$$0, 1$$1$$q$$x$$0$$1$$0$$1$$0$$1$$1$$map$$m$$f(i + j, j) = f(i, j)$$c$$\frac{ij + kj^2}{f(i,j)}$$c$$O(m^2c)$$O(m^2)$$10^8 + 7$… text/html 2020-10-15T17:55:40+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2016_ccpc_%E9%95%BF%E6%98%A5%E7%AB%99&rev=1602755740&do=diff 2016 CCPC 长春站 比赛链接 A. upsolved by 题意 题解 B. solved by 2sozx 题意 签到题 题解 签到题 C. upsolved by 题意 题解 D. solved by 2sozx Bazoka13 JJLeo 题意 长度为 $1\sim n$ 的棍子各一个，问最少拿走几个使得剩下的棍子构不成三角形。 $n\le 20$$x$$\lceil \frac{x}{2} \rceil$$1$$n$$1$$1$$1$$0$$1$$1$$1$$1$ text/html 2020-10-17T16:09:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2016_icpc_%E6%B2%88%E9%98%B3%E7%AB%99&rev=1602922142&do=diff 比赛名称 比赛链接 A. solved by 2sozx 题意 签到题 题解 签到题 B. solved by 2sozx 题意 签到题 题解 签到题 C. solved by 2sozx 题意 $f(1) = a, f(2) = b, f(i) = 2f(i - 2) + f(i - 1) + i^4$ 求 $f(n)$。$n,a,b < 2^{31}$ 题解 矩阵快速幂模板题，注意爆 $int$ D. upsolved by 题意 题解 $1$$2$$d$$l$$l++$$l$$r$$r+1$$n$$q$$x$$d$$x$$d$$(n, q \le 10^5, d \le 2)$$d=2$$O(n)$ text/html 2020-05-22T22:20:54+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2017-2018_acm-icpc_neerc_moscow_subregional_contest&rev=1590157254&do=diff 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest 比赛链接 A solved by 2sozx * 题意：每天可以投入 $x_i$ 元使得 $a_{i+1}=a_i+x_i+\min(a_i+x_i,\lfloor\frac{n-a_i-x_i}{2}\rfloor),\sum x_i \le k$ 问最少几天可以使得 $a_{las}=n(n\le10^{18})$ * 题解：显然是只在第一天和最后一天花钱是最优解（具体是怎么个显然法有待思考。。），然后枚举第一天花多少钱然后模拟即可。$n(n\le10^5)$$1000000\times20$$y$$y+1$$\log{n}$$n \le 26$$m \le 1000$$n \times m(n, m \le 500)$$m$$1$$T$$n$$k$$a$$a+vi$$2$$k$$n$$0$$X1xorX2xor,,,xorXn=1$$+bitset$$ing$$w\times h(w,h\le 10^4)$$n(n\le 10^5)$… text/html 2020-09-04T09:50:24+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&rev=1599184224&do=diff 2020暑假精选题目 图论 网络流 树上问题 字符串 多项式 数学 动态规划 数据结构 计算几何 其它 text/html 2020-08-07T17:41:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%B8%80%E5%9C%BA&rev=1596793270&do=diff 2020牛客暑期多校第一场 比赛链接 A. upsolved by 2sozx JJLeo Bazoka13 题意 设函数 $B(t_1t_2 \cdots t_k)=b_1b_2\cdots b_k$ 其中 $b_i = \min(j-i)(b_i == b_j)(j<i)$，如果不存在则 $b_i=0$ 。现在给定字符串 $S$ ，求 $S$ 的每个后缀的 $B$ 函数的排序 题解 令 $c_i = \min(j-i)(c_i == c_j)(j>i)$，如果不存在则令 $c_i=n+i$ ,对 $c$ 用后缀数组排序，反向输出即可。$5000$$100000$$1!,2!, \cdots ,n!$$\text{LCA}$$\text{LCA}$$(i-1)!$$i$$O(\log n)$$i!$$\text{LCA}$$O(n \log ^2 n)$$\log$$1$$m$$10^6$$10^5$$(n \log ^ 2n + m \log n)$$n\times n$$A$$1\times n$$B$$(x_1,x_2,\cdots,x_n)$$X^T A X \… text/html 2020-10-07T21:24:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%B8%83%E5%9C%BA&rev=1602077065&do=diff 2020牛客暑期多校第七场 比赛链接 A. upsolved by 题意 题解 B. solved by 2sozx JJLeo 题意 $t$ 个询问，每个询问包含两个数 $n,m$，问将 $n\times m$ 个数分成最少多少个数使得这些数能够组合成 $n$ 个 $m$ 和 $m$ 个 $n$。$n,m\le 10^4$ 题解 如果 $n=m$$n$$m$$n<m$$n$$n$$(n,m-n)$$n$$x$$w$$w-dis(i,x)$$x$$x$$0$$\min$$x$$n,q\le5\cdot10^4$$root$$x$$root$$x$$w-dis(root,i)-dis(root,x)$$x$$x$$x$$x$$2$$1e6$$1e5$$n$$1-n$$\frac{n(n+1)(2n+1)}{6}$$6$$2、3$$1、6$$\sum_{i=1}^{k}\sum_{j=1}^{n}{[i \mod j \le 1]} \pmod{10^9+7}$$(n,k \le 10^{12})$$n$$T$$(n,T \le 5000)$$n$$h_i$$i$$O… text/html 2020-07-24T17:06:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%B8%89%E5%9C%BA&rev=1595581570&do=diff 2020牛客暑期多校第三场 比赛链接 A. solved by JJLeo 题意 一共有$n$天，每天可能会有鱼或没鱼，可能会有蛤或没蛤，如果有鱼就可以抓鱼，如果有蛤就可以抓蛤做诱饵，如果之前有做好的诱饵就可以用诱饵抓鱼（不需要有鱼），每天至多进行一种操作，问最后最多能抓多少鱼。$S,|S|\le2\times10^6$$S$$x$$S$$S$$x$$S$$S$$x$$S$$S$$t$$20$$20$$9$$n$$|x_1-x_2|+|y_1-y_2|=1$$m$$n\le 50,m\le 200$$m$$m>4*n$$m$$n$$m$$L$$L$$m$$m+2$$x$$4*x$$x^2-x$$m$$4$$4*x+2$$x$$m$$a,b(a,b\le2\cdot10^6)$$c,d,e,f$$d<b,f<b,c,e\le10^{12},\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$$-1 -1 -1 -1$$gcd(a,b)$$1$$1$$c=\frac{a}{gcd(a,b)}+1,d=\frac{b}{gcd(a,b)},e=1,f=\frac… text/html 2020-10-07T21:25:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%B9%9D%E5%9C%BA&rev=1602077126&do=diff 2020牛客暑期多校第九场 比赛链接 A. solved by Bazoka13 题意 给一个$2$进制表达式，求出十进制结果 题解 使用$python$的$eval+replace$，一行$AC$ B. upsolved by JJLeo 题意 给出一棵以$1$为根的有根树，节点数为$n$，你需要做一次dfs，每一次经过一条边都要减少权值，第一次到每个点可以增加权值，要求任意时刻权值不为负，你可以在任意点花费任意秒增加对应的权值，经过边不耗费时间，问最少需要耗费多少秒。$(n \le 10^5)$$0$$a_i$$b_i$$b_i>0$$b_i<0$$a_i$$b_i+a_i$$a_1$$n$$[l_i, r_i]$$\frac{1}{2}$$998244353$$(1 \le n \le 5 \times 10^5, 0 \le l_i,r_i \le 10^9)$$x$$y$$y(2^{x}-1)$$2^n$$${(x+y+z)}^2=x(x+y+z)+y(x+y+z)+z(x+y+z)$$$i$$x$$y$$i$$$y_i\sum_jy_j(2^{x_j}… text/html 2020-07-18T18:22:43+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%BA%8C%E5%9C%BA&rev=1595067763&do=diff 2020牛客暑期多校第二场 比赛链接 A. upsolved by JJLeo 题意 给定$n$个字符串，设$x$是最大的使$s_i$长度为$x$的前缀和$s_j$长度为$x$的后缀相等的数，有$f(s_i,s_j)=x$，求$\sum_{i=1}^n \sum_{j=1}^n {f^2(s_i,s_j)} \pmod {998244353}$。$(1 \le n \le 10^5, 1 \le \sum |s_i| \le 10^6)$ 题解 考虑每个前缀有多少个后缀和它相等，可以用广义后缀自动机，也可以把哈希开到$\text{long long}$$\text{unordered_map}$$\operatorname{next}$$\operatorname{cnt}[\operatorname{next}[i]]$$\operatorname{cnt}[i]$$n$$n \le 2000$$(x_1,y_1),(x_2,y_2)$$$(\frac{y_1y_2^2-y_2y_1^2+y_1x_2^2-y_2x_1^2}{2(x_2y_1-x_1y_2)},\fra… text/html 2020-10-07T21:24:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%BA%94%E5%9C%BA&rev=1602077042&do=diff 2020牛客暑期多校第五场 比赛链接 A. upsolved by JJLeo 题意 给出一个$n$个点$m$条边的图，从$1$号点出发，依次经过$2k$个点，途中经过一点时可以在这点放传送门，任意时刻只能存在最多两个传送门，两个传送门可以瞬间互达，求途径的最短距离。$(n, k \le 300, m \le 40000)$$f_{i,j}$$i$$j$$j$$j$$O(n^2k)$$n$$0$$(n \le 100000)$$k$$a$$b$$N$$M$$a$$b$$\prod_{i=1}^k\min(a_i,b_i)$$(1 \le N,M \le 10^6,1\ \le k \le \min(N,M))$$f(x,y)=\sum{\min(n,m)x^ny^m}$$f^k(x,y)$$x^Ny^M$$f(x,y)$$\dfrac{xy}{(1-x)(1-y)(1-xy)}$$\dfrac{1}{{(1-x)}^k{(1-y)}^k{(1-xy)}^k}$$x^{(N-k)}y^{(M-k)}$$\dfrac{1}{{(1-xy)}^k}$$\dfrac{1}{{(1-x… text/html 2020-10-07T21:28:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E5%8D%81%E5%9C%BA&rev=1602077333&do=diff 2020牛客暑期多校第十场 比赛链接 A. solved by 2sozx 题意 给定一个质数 $p$ 问是否存在一个排列使得每一位满足 $a_{i+1}=2a_i(mod p)$ 或 $a_{i+1}=3a_i(mod p)$ 其中一个条件。 题解 令 $a_1=1$ ，之后能用 $2$ 就用 $2$ ，否则就用一个 $3$ ，之后再用 $2$ 。完全不会证明。$1/1$$1/10^9$$dp[i][j]$$i$$j$$dp[rt_0][rt_1]$ text/html 2020-07-24T17:09:55+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E5%9B%9B%E5%9C%BA&rev=1595581795&do=diff 2020牛客暑期多校第四场 比赛链接 A. upsolved by 2sozx 题意 给定一颗 $n(n\le 2\cdot 10^5)$ 个节点， $1$ 为根节点的树，设置 $k$ 个关键点，定义一个点的值为这个点与根节点的路径中与这个点距离最近的关键点的距离，如果没有关键点则距离为 $+\infty$$k$$k\in [1,n]$$k=1\cdots n$$ans$$ans$$ans$$O(n\log n)$$f_c(x)=\max c\cdot f_c(gcd(i,x)) (i=1\cdots n-1,x>1),f_c(1)=1$$T(T\le 10^6)$$n,c$$f_c(n)$$n$$c$$s$$10$$a$$a$$(|s| \le 10^5)$$x$$t$$n\le10^5$$\le9$$\le1$$1$$10\cdots0a$$9\cdots9b$$A,B$$C,D$$AC,AD,BC,BD$$C,D$$A$$1$$n$$3$$x$$2x$$2$$n$$\dfrac{1}{S}$$1$$i,j$$n$… text/html 2020-10-07T21:25:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E5%85%AB%E5%9C%BA&rev=1602077118&do=diff 2020牛客暑期多校第八场 比赛链接 A. solved by JJLeo 题意 简化后题意：给出一张二分图，每次操作加一条边或删一条边，每次操作后，如果左侧有点度数为$0$，输出$-1$，否则输出连通块数量减去右侧度数为$0$$21$$SET$$O(32n^2)$$n$$n$$-1$$(\sum|s_i| \le 3 \times 10^5)$$x$$len$$(len-x)|len$$len-x$$len$$n$$n$$O(n)$$2-sat$$bfs$$n$$10^{19}$ text/html 2020-10-07T21:24:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020%E7%89%9B%E5%AE%A2%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E5%85%AD%E5%9C%BA&rev=1602077048&do=diff 2020牛客暑期多校第六场 比赛链接 A. solved by 2sozx 题意 给定一个长度为 $n$ 的排列，每次可以选择长度为 $s$ 的子序列进行随机重排，代价为 $s$ ，问将此排列重排为 $1,2\cdots n$ 的最小代价是多少。 题解 这题正解题解出锅了$n,k$$1$$n$$1,2, \cdots , n$$n$$k$$(n \le 5000)$$n$$k$$\dfrac{n}{2}$$k$$0$$n, n-1,1,n-2,2,\cdots$$n, \dfrac{n}{2},n-1,1,n-2,2,\cdots$$(A,B)$$0 \le A \le B \le N$$A$$(1 \le N \le 10^{100})$$f_{i,j,k,l}$$i$$j$$N$$1,2, \cdots , n$$m$$x$$k-$$(nm \le 10^6)$$k-$$k$$x \mod n$$n$$1$$k$$(n \le 5 \times 10^5, k \le 10^9)$$k$$k$$k$$k$$k$$n+1$… text/html 2020-08-07T17:34:04+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_01&rev=1596792844&do=diff 2020-2021 BUAA ICPC Team Supplementary Training 01 比赛链接 A. upsolved by JJLeo 题意 $n$个物品，每个物品权值不超过$30$，将所有物品分为三组，求权值最大组和权值最小组差值的最小值，输出方案。$(n \le 400)$ 题解 如果只需要求最小差值直接用bitset就可以解决，但是因为不会输出方案爆搜2小时结果无限TLE on 91。$4030$$400 \times 4030 \times 4030$$100 \times 4030 \times 4030$$4$$4$$4$$A$$a~b$$n$$(a_i,b_i)$$m$$(c_i,d_i)$$n$$a_ic_j+b_id_j$$(n, m \le 5 \times 10^5)$$(c_i,d_i),(c_j,d_j)$$\ge -\dfrac{a}{b}$$i+1$$x-1$$k$… text/html 2020-10-07T21:25:41+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_02&rev=1602077141&do=diff 2020-2021 BUAA ICPC Team Supplementary Training 02 比赛链接 A. solved by JJLeo 题意 给定一个长度为奇数的序列，每次对一个区间进行升序排序或降序排序，问最后中间的数是啥。 题解 二分答案，然后将其它数字与他的大小关系变成$0$$1$$01$$n$$n$$n$$(n \le 10^5)$$u,v$$u$$v$$v$$v$$u$$1$$d$$\dfrac{1}{d+1}$$0$$0$$O(n\log n)$$O(n\log^2 n)$$hack$$k$$n\le10^5$$1,2$$3,4$$01$$k$$0$$1$$0$$01$$sum_0,sum_1$$0,1$$\min(sum_0[n],sum_0[i]-sum_0[j]+k-(sum_1[i]-sum_1[j])$$sum_1[i]-sum_1[j] \le k$… text/html 2020-10-15T18:01:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_03&rev=1602756078&do=diff 2020-2021 BUAA ICPC Team Supplementary Training 03 比赛链接 A. solved by JJLeo 题意 暴力 题解 暴力 B. solved by 2sozx 题意 签到题 题解 签到题 C. upsolved by 题意 题解 D. solved by 2sozx 题意 在坐标原点有一个发射器，$(x,0)$$0 \sim x$$n(n \le 10)$$h_i$$\vec{v} = v_x + v_y$$b(b \le 15)$$g = 1.0$$b$$L$$v_x v_y = \frac{gL}{2}$$v_y$$\sqrt{\frac{gL}{2}}$$v_x^2 + v_y^2 \ge gL$$v_y$$\vec{v}$ text/html 2020-10-13T22:41:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_04&rev=1602600076&do=diff 2020-2021 BUAA ICPC Team Supplementary Training 04 比赛链接 P. solved by 2sozx Bazoka13 JJLeo 题意 题解 Q. solved by 2sozx 题意 开始是空串，每次操作给出一个字母或者 $-$ 。若为字母则向末尾添加这个字母，否则删除最后一个字符，求每次操作后的回文子串个数。$q\le10000$$q^2$$1,2$ text/html 2020-10-15T18:06:20+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_05&rev=1602756380&do=diff 2020-2021 BUAA ICPC Team Supplementary Training 05 比赛链接 A. upsolved by 题意 题解 B. upsolved by 题意 题解 C. upsolved by 题意 题解 D. upsolved by 题意 题解 E. upsolved by 题意 题解 F. upsolved by 题意 题解 text/html 2020-08-11T22:33:40+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020.08.11%E4%BC%9A%E8%AE%AE%E8%AE%B0%E5%BD%95&rev=1597156420&do=diff 2020年8月11日，三方首脑进行了秘密会谈，达成了以下共识： 周六：ATC每日亿题 周日：CF每日亿题 周一：加训 周二：补题 周三：CF 每日亿题 周四：加训 周五：周报+补题+模板测速 第一周：图论，网络流 text/html 2020-08-02T15:46:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020.7.27&rev=1596354377&do=diff 比赛链接 CF Heidi and Library (easy) (medium) 题意 图书馆买书，库存一开始为空，且容量有限，按顺序依次要求库存有某种书，每次买书后如果库存超出容量要扔掉一本书，问最少要买几次书。 题解 如果需要扔掉一本书，贪心地扔掉往后第一次出现最晚的那本即可（不出现可以认为在第$n+1$$250$$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)$… text/html 2020-08-07T17:09:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020.7.30&rev=1596791340&do=diff 比赛链接 CF Expected diameter of a tree 题意 给定一片森林，$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$$\leq$ text/html 2020-08-07T21:10:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020.8.2&rev=1596805805&do=diff 比赛链接 CF Karen and Test 题意 题解 CF Karen and Supermarket 题意 题解 CF Choosing The Commander 题意 题解 CF MEX Queries 题意 题解 CF Sofa Thief 题意 题解 CF Level Generation 题意 $q$ 次询问，每次给出一个 $n$，问 $n$$q\le10^5,n\le2\cdot10^9$$n$$n-1$$n$$x$$1\sim x$$x+1$$x$$x$$$sum=C(x,2)+n-x,n-x\ge \frac{ans}{2}$$$x^2+x\le2n$$O(1)$$s$$s\ge0$$s=s-3$$s=s-1$$s\ge3$$s-2$$O(1)$ text/html 2020-08-07T15:10:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020.8.7&rev=1596784232&do=diff 比赛链接 CF Liar 题意 题解 CF Madness 题意 题解 CF Minimal Labels 题意 题解 CF String Compression 题意 题解 CF Tree Queries 题意 题解 CF DNA Evolution 题意 题解 CF Bamboo Partition 题意 题解 CF Strange Radiation text/html 2020-08-20T12:30:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020.8.18&rev=1597897800&do=diff 比赛链接 CF Prefix Sums 题意 给出一个长度为$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$$n$$a_i$$$\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \ne 1}k \cdot \gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \pmod{10^9+7}$$$1 \le k \le n, p_1<p_2< \cdots < p_k$$(n \le 2 \times 10^5, a_i \le 10^6)$$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}… text/html 2020-10-07T21:52:41+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020_ccpc_%E7%BD%91%E7%BB%9C%E8%B5%9B&rev=1602078761&do=diff 2020 CCPC 网络赛 比赛链接 A. upsolved by 2sozx 题意 给定一个开始全白的二维平面，每次操作选择一个矩形将其涂黑，矩形下面紧贴 $x$ 轴，问每次操作过后黑色区域的周长为多少。操作次数 $n \le 2 \times 10^5$ 题解 由于矩形紧贴 $x$$\max$$\sum_{i = 1}^{n - 1}|a_i - a_{i + 1}|$$a_i,a_{i + 1}$$\max$$t$$n$$x$$x = p \times q$$p \not = 1$$x$$p$$q$$1$$t \le 10^4, x\le 10^9, n\le 10$$p^i$$p^j$$i \not = j$$p \not = 2$$Nim$$A,K$$C$$C_{x,y}=\sum_{i=1}^{min(n-x+1,3)}\sum_{j=1}^{min(n-y+1,3)}A_{x+i-1,y+j-1}K_{i,j}$$C^{m}(A,K)=C(C^{m-1}(A,K),K)$$K$$1$$\lim\limits_{m \to \infty} C$$K$$3\ti… text/html 2020-10-07T21:23:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020hdu%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%B8%80%E5%9C%BA&rev=1602077030&do=diff 2020HDU暑期多校第一场 比赛链接 A. upsolved by 题意 题解 B. upsolved by 题意 题解 C. upsolved by 题意 题解 D. solved by 2sozx Bazoka13 JJLeo 题意 统计多少个长度为 $n$ 的由小写字母构成的串 $S$ 的回文子串数最少。$n\le3$$26^n$$n>3$$A(26,3)$$n\le3$$n>3$$abcabc\cdots$$A(26,3)$$N,C,k$$F_0^k+F_{C}^k+F_{2C}^k+\cdots+F_{NC}^k(mod 10^9+9)$$F$$N,C\le10^{18},k\le10^5$$F_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i)$$5$$10^9+9$$x=\frac{1}{\sqrt{5}},a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}$$$S=x^k\sum_{i=0}^{k}(-… text/html 2020-10-07T21:31:07+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020hdu%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%B8%83%E5%9C%BA&rev=1602077467&do=diff 2020HDU暑期多校第七场 比赛链接 A. upsolved by 题意 题解 B. upsolved by 题意 题解 C. upsolved by 题意 题解 D. solved by JJLeo 题意 给定$t,a,c,m$，等概率地从$[0,t]$中选择两个数$v_1,v_2$，设$X_0=v_1+v_2$，$X_{n+1}=(aX_n+c) \mod m (n \ge 0)$，求$X_{|v_1-v_2|}$是偶数的期望，输出最简分数。$(2 \leq m \leq 10^6, 0 \leq a, c < m, 0 \leq t < \frac{m}{2})$$X$$v_1+v_2=b$$|v_1-v_2|$$v_1+v_2$$t$$2n+1$$x_i$$998244353$$(n \le 3000, \sum n \le 10^6)$$|x_i-x_j|$$-x_i$$x_i$$0$$f_{i,j}$$i$$j$$O(n^2)$$(i+j)$$\sum_{i=1}^{2n+1}(f_{n-i,i-1}x_i-f_{i-1,n-i}x_i… text/html 2020-10-07T21:24:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020hdu%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E4%BA%8C%E5%9C%BA&rev=1602077090&do=diff 2020HDU暑期多校第二场 比赛链接 A. solved by 2sozx 题意 给定一个无向图，每个点有个权值 $b_i$ ，每次操作可以选择一个连通块并且将这个连通块所有点的 $b_i-1$，问最少要操作几次使得$b_i=0(i=1,2\cdots n)$。$(n\le10^5,m\le2\cdot10^5)$ 题解 暴力的思路很好想，每次选择一个不包含 $b_i=0$$b_i-1$$b_i$$b_i$$b_i$$b_i$$b_i$$n \times n$$a_{i,j}$${(n^2)}^{a_{i,j}}$$q$$10^9+7$$(n \le 400, q \le 2 \times 10^5)$$n^2$$1$$n$$m$$i$$j$$a_ij^2+b_ij+c_i$$1,2,\cdots ,n$$(n \le 50, m \le 10^9,a_i > 0, {b_i}^2-4a_ic_i \le 0)$$n$$O(n^5)$$a*b=c+f[k]$$a*b-c$$n$$a_i$$b_i$$k$$a_i$$b_i$$(n \le 2 \times 10^4, k… text/html 2020-12-22T09:10:43+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2020hdu%E6%9A%91%E6%9C%9F%E5%A4%9A%E6%A0%A1%E7%AC%AC%E5%85%AD%E5%9C%BA&rev=1608599443&do=diff 2020HDU暑期多校第六场 比赛链接 A. solved by JJLeo 题意 给出一个序列，等概率地选择左右端点$l \le r$，求$[l,r]$区间平均数的期望值。 题解 题目本质是问长度为$1,2, \cdots , n$的连续子区间中，每个数各出现了多少次。可以发现如下规律：$$1 1 1 1 1 1 1$$$$1 2 2 2 2 2 1$$$$1 2 3 3 3 2 1$$$$1 2 3 4 3 2 1$$$$1 2 3 3 3 2 1$$$$1 2 2 2 2 2 1$$$$1 1 1 1 1 1 1$$$a \ opt \ b \ = \ c$$opt=+,-,*,/$$0+0=0$$(10,1,1) (6,4,2) (6,5,1)$$n$$1145141919$$()\times+$$x$$x=1,2, \cdots , 5000$$11$$3,7$$i$$2^i$$i-1$$i$$dfs$$k$$x$$t$$n$$$\sum_{a_1=1}^{n}\sum_{a_2=1}^n\dotsb\sum_{a_x=1}^n\left(\prod_{j=1}… text/html 2020-05-15T12:46:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:acm_southeastern_europe_regional_contest_2016&rev=1589517968&do=diff ACM Southeastern Europe Regional Contest 2016 比赛链接 A. Three Squares solved by bazoka13 题意 给定$n(n\leq1e5)$个点，坐标$x,y$的范围为$0~1e9$，用三个正方形覆盖所有的点，求正方形的最小边长。 题解 找出$x,y$坐标的最大/小值，显然最值点应该尽量位于正方形的边界上。考虑$dfs$$(minx,maxy-d),(minx,miny)$$dfs$$x,y$$n$$t_i$$q$$S$$t_x$$t_y$$S$$n\le3\times10^5,\sum{|t|}\le3\times10^5,q\le1\times10^5$$S$$t_x$$t_y$$t_y$$t_x$$|t_x|$$t_x$$t_y$$t_x$$t_x$$t_x$$t_y$$S$$T$$S$$S$$T$$T$$S$$m{\le}12*10^5$$|S|{\le}10^3$$KMP$$fail$$a$$b$$a$$b$$k$$pos$$k{\le}40$$pos{\le}10^5$$string$$n$… text/html 2021-01-22T22:27:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:bazoka13&rev=1611325670&do=diff BZKContest * 2020.05.07 Codeforces Round #639(Div. 2) Virtual participation * 2020.05.12 Codeforces Round #641(Div. 2) Virtual participation BZKStudy * 2020.05.14 李超树 * 2020.06.26 闵可夫斯基和 BZKTodo * 网络流（在学了在学了）题单 * 写完这个图论题单（13/44） * 把之前一些常见结论翻翻（比如最小路径覆盖QAQ） BZKbuti 开个新坑 text/html 2020-06-14T00:26:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:bazoka13_2019_icpc_malaysia_national&rev=1592065618&do=diff A B C D E F G H I J K + + + + + + + （熬夜VP，打完$H$实在打不动了，直接溜了，rank 21） text/html 2020-06-12T22:40:20+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:bazoka13_educational_codeforces_round_89_rated_for_div._2&rev=1591972820&do=diff A、B、C * 手速题 D * 题意：对于给定的数字$a[i]$，判断其是否存在两个不为$1$的因子，其和与$a[i]$互质 * 题解：筛一下，然后将$a[i]$分解为$b_1^{p_1}+b_2^{p_2}+\ldots$的形式，取$d_1=b_1^{p_1},d_2=a[i]/d_1$ * 证明：$x,y互质时，gcd(x+y,xy)=1$ * $gcd(x,y)=1\rightarrow gcd(x+y,x)=gcd(x+y,y)=1$ * $gcd(x+y,xy)=gcd(x+y,x)=1$ E * 题意：$b$是有$m$项的严格递增的单调数列，将$a$$m$$i$$b[i]$$b$$a$$b$$+1$ text/html 2020-06-15T22:20:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:bazoka13_namomo_test_round_1&rev=1592230838&do=diff 比赛传送门 赞美namomo！ A sort * 题意：给你一段排序的代码，相当于操作一次排序$b$个，每次从第一位开始操作，直到第$n-b+1$位，重复$a$次，询问对于给定的$n,a,b$是否能将任意$n$项数列排好序。 * 题解：考虑最小的在最右边，如果不能排序成功，显然最小的无法移动到最左边，根据代码可以看出最小的每次移动距离是一个定值，计算出来移动$a$$n$$m$$k$$1$$swap$$p$$(n-2)*p/n$$2/n$$(1-x)/(n-1)$… text/html 2020-07-31T13:39:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:contest&rev=1596173966&do=diff A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解: text/html 2020-05-08T21:04:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:dp%E4%B8%93%E9%A2%98&rev=1588943074&do=diff DP专题 团队VjudgeDP专题 总结 text/html 2022-07-24T10:48:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:front_page&rev=1658630929&do=diff 辉夜大小姐想让我AC 本 wiki 已迁移至下方链接 <https://warwolf.wiki.cvbbacm.com/> 训练记录 训练模板 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-05-03 牛客假日团队赛40 12 12 12 1/692020-05-10 ACM Southeastern Europe Regional Contest 2016 8 10 11 N/A2020-05-17 text/html 2020-10-15T22:15:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:jjleo&rev=1602771336&do=diff 比赛 * 2020.05.06 Codeforces Round #639 (Unrated) * 2020.05.07 Codeforces Round #620 (Div. 2) Virtual participation * 2020.05.09 Codeforces Round #619 (Div. 2) Virtual participation * 2020.05.09 Educational Codeforces Round 82 (Rated for Div. 2) Virtual participation * 2020.05.12 Codeforces Round #641 (Div. 1) * 2020.05.13 Educational Codeforces Round 81 (Rated for Div. 2) Virtual participation * 2020.05.14 Codeforces Round #642 (Div. 3) * 2020.05.19 Codeforces Round #643 (Div. 2)… text/html 2020-08-11T22:08:56+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:knowledge_tree&rev=1597154936&do=diff 知识古树 （咆哮德永不为奴） 图论 知识点 2sozx JJLeo Bazoka13 最短路 Dijkstra √ √ √ SPFA √ √ √ text/html 2020-06-12T19:21:52+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:lichao_tree&rev=1591960912&do=diff 格式： * 画图有一些更好的工具，如 visio ppt geogebra process on，请勿手画 * 公式两边接汉字请空格 内容： * 没有例题吗 李超树 它能干什么 * 维护区间的多条直线 * 单点查询最值 * 区间查询最值$a$$k$$a$$k$$k$$a$$a$$a$$k$$swap$$k$$swap$$now$$val(now)$$\max(当前区间优势线段两端取值,\max(val(ls),val(rs)))$ text/html 2020-05-08T20:41:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:skill_tree&rev=1588941710&do=diff 远古之树 升级你的远古之树以解锁知识古树 点击这里升级 text/html 2020-06-29T20:21:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_1&rev=1593433263&do=diff 2020.05.02~2020.05.8周报 团队训练 2020.05.06 团队Vjudge压位专题 本周推荐 * 一道拉格朗日乘子法的题目 可顺带复习复习数分 * 李超树 （老营销号了） * CF1344C 早八离散数学，晚十离散数学。题意与题解 2sozx 比赛 * 2020.05.06 Codeforces Round #639(Unrated) 题目 * 一道拉格朗日乘子法的题目 可顺带复习复习数分 text/html 2020-06-29T20:21:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_2&rev=1593433276&do=diff 2020.05.09~2020.05.15周报 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-05-10 ACM Southeastern Europe Regional Contest 2016 8 10 11 N/A 本周推荐 * 阿狸的打字机2.0 B题 * 离散化+组合dp F题 * 几何+二分 A题 2sozx 比赛 text/html 2020-06-29T20:21:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_3&rev=1593433286&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-05-17 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest 7 9 10 23/834 本周推荐 * 数论+树的重心 F题 * 费用流 2sozx 比赛 * 2020.05.17 Codeforces Round #643(Div. 2) 题目 Bazoka13 比赛 * 2020.05.16 Codeforces Round #643(Div. 2) JJLeo text/html 2020-06-29T20:23:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_4&rev=1593433428&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-05-24 2009-2010 ACM-ICPC, NEERC, Western Subregional Contest 10 12 12 3/369 本周推荐 * 组合数+$SOS DP$B题 * 上下界费用流 F题 * 数论+容斥+莫比乌斯函数 F题 2sozx 比赛 本周认真复习党史知识，没参加比赛，下周补上 text/html 2020-06-29T20:23:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_5&rev=1593433438&do=diff 团队训练 组团参加了北交校赛。 本周推荐 * 矩阵快速幂 fib数列 * wqs二分 * 二维平面求$n$条线段是否有交点 F题 2sozx 比赛 * 2020.05.30 Educational Codeforces Round 87 (Rated for Div 2) * 2020.05.31 北交校赛 * 2020.05.31 Codeforces Round #646(Div. 2) * 2020.06.04 Codeforces Round #646(Div. 1) Bazoka13 比赛 * Codeforces Round #646 (Div. 2)(VP) 题目 JJLeo text/html 2020-06-25T23:29:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_6&rev=1593098955&do=diff 团队训练 周末考试+烤漆临近，摸了。 本周推荐 * 交互+构造 G题 * 图论+计算几何 F题 2sozx 比赛 * 摸了 Bazoka13 比赛 * Educational Codeforces Round 89 (Rated for Div. 2) 题目 JJLeo 比赛 * 2020.06.07 Codeforces Round #647(Div. 2) Virtual participation * 2020.06.11 Codeforces Round #648(Div. 2) Virtual participation * 2020.06.12 Educational Codeforces Round 89 (Rated for Div. 2) Virtual participation 题目 * 补题 text/html 2020-06-29T20:24:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_7&rev=1593433455&do=diff 团队训练 烤漆，摸了。 本周推荐 * 交互题+概（乱）率（搞） E题 2sozx 比赛 * 又摸了 Bazoka13 比赛 * 2019 ICPC Malaysia National(Virtual Participation) * Namomo Test Round 1 题目 JJLeo 比赛 * 2020.06.14 Codeforces Round #649 (Div. 2) Virtual participation * 2020.06.15 Codeforces Round #610 (Div. 2) Virtual participation * 2020.06.16 Codeforces Round #609 (Div. 2) Virtual participation * 2020.06.17 Codeforces Round #650 (Div. 3) Virtual participation 题目 * 补题… text/html 2020-06-29T20:24:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_8&rev=1593433472&do=diff 团队训练 烤漆，摸了。 本周推荐 * 交互题+思维 F题 * 博弈论 F题 * 期望+dp F题 2sozx 比赛 Bazoka13 比赛 题目 * 闵可夫斯基和 JJLeo 比赛 * 2020.06.20 Codeforces Global Round 8 Virtual participation * 2020.06.22 Codeforces Round #651 (Div. 2) Virtual participation * 2020.06.23 Codeforces Round #652 (Div. 2) * 2020.06.25 Educational Codeforces Round 78 (Rated for Div. 2) Virtual participation * 2020.06.26 Educational Codeforces Round 90 (Rated for Div. 2) Virtual participation 题目… text/html 2020-07-04T17:21:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_9&rev=1593854507&do=diff 团队训练 本周推荐 2sozx 比赛 Bazoka13 比赛 题目 JJLeo 比赛 题目 text/html 2020-07-07T16:53:01+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_10&rev=1594111981&do=diff 团队训练 本周推荐 2sozx 比赛 Bazoka13 比赛 题目 JJLeo 比赛 题目 text/html 2020-07-17T23:32:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_11&rev=1594999958&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-07-12 2020牛客暑期多校第一场 5 7 10 33/11162020-07-13 2020牛客暑期多校第二场 6 11 11 47/1159 本周推荐 2sozx 牛客2020多校第一场D Quadratic Form * 分类：数学，KKT。$n\times n$$A$$1\times n$$B$$(x_1,x_2,\cdots,x_n)$$X^T A X \le 1$$BX^T$$n\le200$$BA^{-1}B^T$$KKT$$F(x)=BX^T+\lambda(XAX^T-1)$$$\begin{cases}B_i+2\lambda\sum_{j=1}^{n}A_{i,j}x_j=0 \\ XAX^T-1\le 0 \\ \lambda (XAX^T-1) = 0 \\ \lambda \ge 0\end{cases}$$$X=\frac{-B{(A^{-1})}^T}{2\lambda}$$\lambda (XAX^T-1) = … text/html 2020-07-24T17:14:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_12&rev=1595582089&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-07-18 2020牛客暑期多校第三场 8 10 12 35/11752020-07-20 2020牛客暑期多校第四场 4 7 10 54/11122020-07-22 2020HDU暑期多校第一场 4 6 12 N/A2020-07-23 2020-2021 BUAA ICPC Team Supplementary Training 01 6 7 11 5/19 本周推荐 2sozx HDU 多校第一天 Fibonacci Sum $N,C,k$$F_0^k+F_{C}^k+F_{2C}^k+\cdots+F_{NC}^k(mod 10^9+9)$$F$$N,C\le10^{18},k\le10^5$$F_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i)$$5$$10^9+9$$x=\frac{1}{\sqrt{5}},a=\f… text/html 2020-07-31T17:27:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_13&rev=1596187653&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-07-25 2020牛客暑期多校第五场 5 10 11 87/11162020-07-27 2020牛客暑期多校第六场 6 8 11 64/10192020-07-29 2020HDU暑期多校第二场 6 11 12 N/A 本周推荐 2sozx CF 1388 E * 分类：计算几何$n$$x$$y_i>0$$x$$x$$(n\le2000,-10^6\le xl_i<xr_i\le10^6,1\le y_i\le10^6)$$x$$x_i,y_i$$v=(a,b),b<0$$(x_i-y_i*a/b,0)$$x_i,y_i$$dp$$n$$n \leq 2000$$d(d\leq 10^6)$$n^2$$n^2$$dp$$dp$$atan2$$n \times n$$a_{i,j}$${(n^2)}^{a_{i,j}}$$q$$10^9+7$$(n \le 400, q \le 2 \times 10^5)$$n^2$$1$… text/html 2020-08-07T18:10:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_14&rev=1596795029&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-08-01 2020牛客暑期多校第七场 4 6 10 66/10902020-08-03 2020牛客暑期多校第八场 4 6 11 32/6852020-08-06 2020-2021 BUAA ICPC Team Supplementary Training 02 6 8 10 6/19 本周推荐 2sozx Codeforces 804D Expected diameter of a tree $DP$$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})$$dp$$n$$dp$$dp_i=x_i*y_i-a_i+\max (-x_j*y_i+dp_j)$$max$$(0,0)$$dp$$1E$$n$$T$$(n,T \le 5000)$$n$$h_i… text/html 2020-10-26T06:58:59+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_15&rev=1603666739&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-08-08 2020牛客暑期多校第九场 6 10 12 52/9752020-08-10 2020牛客暑期多校第十场 5 6 10 23/9062020-08-13 HDU 2020 Multi-University Training Contest 6 7 8 11 73/792 本周推荐 2sozx 牛客多校第十场 D 炉石传说 $1/1$$1/10^9$$\begin{cases}1.如果咱们有小亡语 对面有圣盾 优先撞 如果有圣盾亡语 撞圣盾亡语 \\ 2.如果咱们有没有圣盾的 对面有小亡语 白吃一个\\ 3.如果有只有亡语的，优先撞亡语>小兵>圣盾亡语>其它\\ 4.如果咱们有圣盾亡语的 优先撞亡语>圣盾亡语>小兵>其它\\ 5.如果咱们有小兵 优先撞亡语>圣盾亡语>小兵>其它\\ 6.如果咱们有圣盾的 优先撞亡语>圣盾亡语>小兵>其它\\ 7.如果有小亡语 撞小亡语>亡语的\\ 8.如果有小亡语 对面有小兵，圣盾，圣盾亡语则我们… text/html 2020-10-16T06:27:04+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_16&rev=1602800824&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 2020-08-20 HDU 2020 Multi-University Training Contest 7 4 6 11 28/757 本周推荐 2sozx WC2013 平面图 * 分类：平面图对偶图，点定位，扫描线，最小生成树，倍增$n\le10^5$$q$$q\le10^5$$0.5$$treap$$treap$$l$$n$$k$$dp[i][j]$$i$$j$$2n+1$$x_i$$998244353$$(n \le 3000, \sum n \le 10^6)$$|x_i-x_j|$$-x_i$$x_i$$0$$f_{i,j}$$i$$j$$O(n^2)$$(i+j)$$\sum_{i=1}^{2n+1}(f_{n-i,i-1}x_i-f_{i-1,n-i}x_i)$$O(n^2+\sum n)$$n$… text/html 2020-08-28T17:46:52+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_17&rev=1598608012&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 本周推荐 2sozx CF895E Eyes Closed * 分类：线段树，概率 * 题意：给定一个长度为 $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}$$n$$w_i$$a$$b$$w_b-w_a$$l~r$$i$$i+1$$p_i$$c$$i$$l_i-r_i$$p_l-p_r$$c$$a_r+b_l$$n(2 \le n \le 2 \times 10^5)$$1$$1$$n$$a_i$$\operatorname{dist}(i,j)$$$\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n} \varphi(a_i… text/html 2020-09-04T17:53:54+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_18&rev=1599213234&do=diff 团队训练 2020暑假精选题目 本周推荐 2sozx CF 1396D Rainbow Rectangles * 分类：线段树， $set$ * 题意：$L \times L$ 的网格平面，其中有 $n$ 的点，每个点在网格的中心。每个点有一个颜色，总共有 $k$ 个颜色，现在求多少个矩形包含了所有 $k$$n,k \le 2000, L \le 10^9$$x$$x_l$$pre_i$$y$$y$$nxt_i$$y$$y$$x_l \sim L$$f(i)$$i$$k$$y$$i$$f_i$$ans = \sum_{i = 0}^{L} (L + 1 - f_i)$$f_i$$i$$pre_i + 1 \sim y_i$$f$$nxt_i$$f_i$$O(n^2\log(n))$$q$$x$$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) \le… text/html 2020-08-07T16:18:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:week_template&rev=1596788317&do=diff 团队训练 比赛时间 比赛名称 当场过题数 至今过题数 总题数 排名 本周推荐 2sozx 题目名称 * 分类： * 题意： * 题解： * comment： Bazoka13 题目名称 * 分类： * 题意： * 题解：