CVBB ACM Team 2020-2021:teams:farmer_john:2sozx

2020-2021:teams:farmer_john:2sozx:北交校赛

Anonymous (anonymous@undisclosed.example.com) — 2020-06-05T22:15:31+0800

A B C D E F G I J K + + + + + + + ADFHJ * 水 B * 题意：计算几何射线三维反射问题。 * 题解：暴力。 C * 题意：一次抽卡为 $SSR$ 的概率为 $p$ ，求 $n$$K$$SSR$$k\le n\le 10^5$$dp$$dp[i][0]$$i$$i$$SSR$$K$$SSR$$dp[i][1]$$i$$i$$SSR$$K$$SSR$$$\begin{cases}dp[i][0]=(dp[i-1][0]+dp[i-1][1])\times (1-p) \\ dp[i][1]=\sum_{j=\max(0,i-k+1)}^{i-1}dp[j][0]\times p^{i-j}\end{cases}$$$1-dp[n][0]-dp[n][1]$$a_i$$\sqrt{i}$$\prod_{i=1}^{n}a_i$$\prod_{i=1}^{n}a_i=1^2\times 2^4\tim…

2020-2021:teams:farmer_john:2sozx:字符串

Anonymous (anonymous@undisclosed.example.com) — 2020-05-23T14:26:06+0800

字符串 * shift_and * kmp * manacher * 扩展kmp

2020-2021:teams:farmer_john:2sozx:未知题目

Anonymous (anonymous@undisclosed.example.com) — 2020-05-08T21:49:59+0800

2020.05.04-2020.05.10 A * 题意:平面上有$n(n{\le}8)$个点，告诉你每个点距离原点的距离,求这$n$个点所围成的凸包的最大面积 * 题解:枚举哪些点在凸包上,并且这些点极角排序后的顺序。假设极径依次为$r_1,r_2,⋯,r_n$。 $S={\frac{1}{2}}(r_1r_2sinθ_1+r_2r_3sinθ_2+⋯+r_nr_1sinθ_n)$${\sum_{i=1}^n}{\theta}_i=2\pi$$F(θ_1,θ_2,⋯,θ_n)=S+{\lambda}g(θ_1,θ_2,⋯,θ_n)$$g(θ_1,θ_2,⋯,θ_n)={\sum_{i=1}^n}{\theta}_i-2\pi$$-λ=r_1r_2cosθ_1=r_2r_3cosθ_2=⋯=r_nr_1cosθ_n$$λ$$g=0$$\theta$…

2020-2021:teams:farmer_john:2sozx:数学

Anonymous (anonymous@undisclosed.example.com) — 2020-06-06T20:16:55+0800

拉格朗日乘子法 * 拉格朗日乘子法 * 拉格朗日乘子法 * 一道没有来源的题目扩展欧几里得 * 知识点类欧几里得 * 知识点原根

2020-2021:teams:farmer_john:2sozx:每日亿题07.27

Anonymous (anonymous@undisclosed.example.com) — 2020-07-31T14:37:25+0800

CF Heidi and Library (easy) 题意题解 CF Heidi and Library (medium) 题意题解 CF Marmots (easy) 题意题解 CF Marmots (medium) 题意题解 CF Fake News (medium) 题意题解 CF Fake News (hard) 题意题解 CF Send the Fool Further! (medium)

2020-2021:teams:farmer_john:2sozx:每日亿题07.30

Anonymous (anonymous@undisclosed.example.com) — 2020-07-31T14:39:24+0800

CF Expected diameter of a tree 题意题解 CF Selling Souvenirs 题意题解 CF Card Game 题意题解 CF Anthem of Berland 题意题解 CF Glad to see you! 题意题解 CF Vladik and Favorite Game 题意题解 CF Sagheer and Apple Tree

2020-2021:teams:farmer_john:2sozx:牛客多校第一场c

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T15:35:50+0800

A National Pandemic

2020-2021:teams:farmer_john:2sozx:牛客多校第一天d

Anonymous (anonymous@undisclosed.example.com) — 2020-07-17T16:26:40+0800

题意给定一个 $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) = 0 $ 可知 $\frac{BA^{-1}B^T}{4{\lambda}^2}=1$ 最大值的平方则为 $(BX^T)(BX^T)=\frac{BA^{-1}B^TBA^{-1}B^T}{4…

2020-2021:teams:farmer_john:2sozx:牛客多校第七场c

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T16:41:00+0800

A National Pandemic 此处介绍点分治算法的细节问题，此处不考虑 $w$。首先将整棵树的点分树建出来，对于一个数 $x$ 的操作将其记录在点分树的父亲们上，具体操作如下： * 枚举 $x$ 的父亲们，包括 $x$$i$$dis(fa_i,x)$$y$$x$$fa_i$$y$$dis(fa_i,y)+dis(fa_i,x)$$fa_i$$y$$fa_i$$y$$fa_{fa_i}$$fa_i$$dis(fa_{fa_i},x)$$y$$fa_i$$fa_i$$x$$x$$x$

2020-2021:teams:farmer_john:2sozx:atcoder_beginner_contest_177

Anonymous (anonymous@undisclosed.example.com) — 2020-08-30T19:47:34+0800

F * 题意: * 题解:

2020-2021:teams:farmer_john:2sozx:cf_1396d_rainbow_rectangles

Anonymous (anonymous@undisclosed.example.com) — 2020-09-04T11:27:09+0800

题意 $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))$

2020-2021:teams:farmer_john:2sozx:codeforces_round_561_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-17T17:28:12+0800

vp的时候cf又挂了 A * 水 B * 水 C * 题意：给出一个序列 $a$ ，问有多少对 $i,j$ 满足以下条件 $\min(|a_i+a_j|,|a_i-a_j|)\le\min(|a_i|,|a_j|)\le\max(|a_i|,|a_j|)\le\max(|a_i+a_j|,|a_i-a_j|)$ $n\le 2\cdot10^5$ * 题解：显然可以将 $a$ 的所有数取绝对值，对答案显然没有影响。考虑 $i,j$ 对答案有贡献的条件。设$a_i\le a_j$$a_j-a_i\le a_i \le a_j \le a_i+a_j$$2a_i\ge a_j$$a$$q(q\le10^3)$$a,b,m(a,b,m\le 10^14)$$x$$x_1=a,x_n=b,x_i=x_1+\cdots+x_{i-1}+r_i,1\le r_i\le m$$50$$k$$b=2^{k-2}a+\sum_{i=2}^{k-1}2^{k-i-1}r_i+r_k$$r_i\ge 1$$r_i$$1$$n(n\le 10^4)$$m(m\le 50)$$s_…

2020-2021:teams:farmer_john:2sozx:codeforces_round_639_unrated

Anonymous (anonymous@undisclosed.example.com) — 2020-05-09T22:06:52+0800

A * 题意:一个序列为$0,1…n-1$,定义一个变换,每个位置$i$变换到位置$(i+a_i)\%n$处,$|a_i|\le10^9$,问是否有两个位置经过一次变换后变换到同一个位置 * 题解:注意$a_i$可为负数 B * 题意:如果$N$和$S$在同一列或者同一行，那么$N$将会向$S$$n,m\le1000$$N$$N$$S$$N$$n(n\le2*10^5)$$m(m\le2*10^5)$$x_i

2020-2021:teams:farmer_john:2sozx:codeforces_round_641_div._1

Anonymous (anonymous@undisclosed.example.com) — 2020-05-13T16:10:52+0800

A * 题意：给定一个长度为 $n(n{\le}10^5)$ 序列 $s(s_i{\le}2{\times}10^5)$ ，令 $t=\{lcm(s_i,s_j)|i

2020-2021:teams:farmer_john:2sozx:codeforces_round_643_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-05-21T21:15:57+0800

A * 题意：给定一个数字 $a_1\le10^{18}$ 令 $a_{n+1}=a_n+\max Digit(a_n) \cdot \min Digit(a_n)$ ，求 $a_k(k\le10^{16})$ * 题解：暴力模拟即可，操作至多 $1000$ 次即可使得 $\min Digit(a_n)=0$ B * 题意：给定一个长度为 $n\le2\cdot10^5$ 的序列 $e$ ，其中 $e_i$ 表示第 $i$ 个人至少需要 $e_i$ 个人才能组成团队，可以有人不在团队中，问最多组多少个队。$e$$dp$$A,B,C\le10^5$$x,y,z$$A\le x\le B\le y\le C\le z\le D$$10^9+7$$N,S$$N$$S$$\exists K\le S$$K$$S<2\times n$$\underbrace{2,2,\cdots,2}_{n-1},s-2\times n+2$$n\le10^5$$h(h_i\le10^9)$$h_i+1$$A$$h_i-1$$R$$h_i+1,h_j-1$$M$$h_i$$A,M,R\le10…

2020-2021:teams:farmer_john:2sozx:codeforces_round_645_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T13:56:59+0800

A * 水 B * 水 C * 题意：以一种规则构成一个无穷矩阵，求从点 $(x_1,y_1)$ 到点 $(x_2,y_2)$ 有多少种路径和不同的路径 * 题解：$ans=(x_2-x_1)\times(y_2-y_1)+1$ D * 题意：一年有 $n (n\le 10^5)$ 个月，每个月 $d_i (d_i\le 10^6)$ 天，每个月的第 $i$ 天权值为 $i$ 。要求连续选 $x$$n (n\le 5 \cdot 10^5)$$k$$k$$\lfloor \frac{n}{2} \rfloor$$x$$k$$2k$$x\ge0$$\exists k \iff \sum_{i=1}^{n}a_i > 0$$x<0$$i$$n(n\le 2 \cdot 10^5)$$a$$b$$a$$b$…

2020-2021:teams:farmer_john:2sozx:codeforces_round_646_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-06-01T11:52:38+0800

A * 题意：给 $n$ 个数，问是否能够从中取出 $x$ 个数使得和为奇数。 * 题解：显然偶数可以随便取，奇数只能取奇数个。考虑两种情况，一种是没有偶数时，$x$ 应为小于奇数个数总数的奇数；二是有偶数时，判断 $x$$0/1$$0/1$$101,010$$1\cdots10\cdots0$$0\cdots01\cdots1$$1\cdots1$$0\cdots0$$x$$x$$n$$k$$S ,S_i\cap S_j = \emptyset$$ans_i=\max(a_j)$$j\not\in S_i$$ans_i(i=1,2\cdots k)$$q$$\max(a_{q_i})$$n$$a$$k\le1000,n\le1000$$k$$S$$12$$1$$n(n\le2\times10^5)$$0/1$$0/1$$a_i$$k\times a_i$$-1$$lca$$1$$dfs$$1$$dfs$…

2020-2021:teams:farmer_john:2sozx:codeforces_round_647_div._1

Anonymous (anonymous@undisclosed.example.com) — 2020-06-05T21:53:39+0800

A * 题意：有 $n(n \le 5 \times 10^5)$ 个博客，每个博客有一个目标主题，给定 $m(m \le 5\times 10^5)$ 个限制，表示两个博客有关联，如果要写一个博客，那么这个博客的主题应为已经写过的，与要写的博客有关的主题的 $mex$ ，问是否存在一个写博客的顺序使得每个博客都满足自身的目标主题。$mex$$a$$1\sim a-1$$set$$n(n \le 10^6)$$p(1 \ge p \le 10^6)$$k_i$$k_i$$0$$p^{k_i}$$p^{k_i-k_{i+1}} \ge 10^6$$p^{k_j}$

2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-02T21:39:03+0800

A * 水 B * 水 C * 题意：有两种饼干，第一种有 $a$ 个，第二种有 $b$ 个。有两类人，第一类有 $n$ 个，第二类有 $m$ 个。当此时的饼干数 $a>b$ 时，第一类人吃第一种饼干，第二类人吃第二种饼干，否则相反。问是否有一种人的排列顺序使得每个人都有饼干吃。 $a,b,n,m\le 10^{18}$$a+b$$\min(a,b)\ge m$$a + b \ge n + m$$x$$i$$a_i$$i$$a_i$$+1$$y$$f(x)$$x$$y=x+n$$x$$f(x)\%p \not = 0$$(2 \le p \le n \le 2000,a_i \le 2000)$$x$$\min\{a_i\} \le x \le \max\{a_i\}$$a_i$$x \ge a_i$$a_i$$i$$a_i$$a_j(j

2020-2021:teams:farmer_john:2sozx:codeforces_round_658_div._1

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T15:03:05+0800

A * 题意：$t$ 组数据，每组数据包含两个 $01$ 串 $A,B$，定义一种操作为选定一个串的前缀，将其每位取反并且翻转前缀，问经过多少次操作使得 $A$ 会变成 $B$，并给出具体方案。$\sum n\le 10^5$ * 题解：我们考虑从 $B$ 的最后一位向前进行匹配，如果当前 $A$$B$$A$$A$$A$$B$$A$$n$$2n$$n$$\sum n\le 2000$$2n$$2*n$$dp$

2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-31T14:05:55+0800

C * 题意:给定一颗树，每个节点有一个值 $p$ 代表这个节点最终有多少人。起始所有人从根节点 $1$ 出发向自己的目标沿着最短路径前进，每个人有两种情绪，只有好情绪能变成坏情绪。在每个节点定义一个函数 $h$$n\le10^5$$dfs$$p$$dfs$$abs(h)>p$$a_n,b_n(n\le2\cdot10^5)$$i$$a_i$$b_i\not =-1$$a_{b_i}+=a_i$$b_i$$>0$$topo$$n$$x$$y_i>0$$x$$x$$(n\le2000,-10^6\le xl_i

2020-2021:teams:farmer_john:2sozx:codeforces_round_664_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-14T11:17:37+0800

E * 题意:摸 * 题解:暴力即可，可以hash优化 F * 题意: * 题解:

2020-2021:teams:farmer_john:2sozx:codeforces_round_668_div._1

Anonymous (anonymous@undisclosed.example.com) — 2020-10-06T10:17:00+0800

B * 题意:给一棵树，$A,B$ 两人做游戏，各有一个起点，每个人都有一个步长 $da,db$ ，表示一次最多移动的距离，$A$ 先移动，如果$A$ 遇到了 $B$ 则 $A$ 获胜，否则 $B$ 获胜，游戏进行无穷次。 * 题解:先判断 $A,B$ 两点距离是否小于等于 $da$$2\times da$$2\times da$$A$$B$$db$$2\times da$$a$$a_i = i$$i$$nm$$1\times x$$x\times 1$$\#$$x$$n,m\le 200$$1\times 1$$L$$L$$L$

2020-2021:teams:farmer_john:2sozx:codeforces_round_669_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-10-06T10:20:37+0800

D * 题意:给定一个序列，开始在 $1$ 每次跳跃可以从 $i$ 跳到 $i + 1$ 或者跳到 $j$，其中 $(i, j)$ 需要满足 $\max(a_i, a_j) < \min(a_{i + 1},\cdots,a_{j - 1})$ 和 $\min(a_i, a_j) > \max(a_{i + 1},\cdots,a_{j - 1})$，问跳到 $n$ 最少要多少步。 * 题解:显然用两个单调栈维护即可，注意 $a_i = a_j$ 的处理即可 E * 题意: *

2020-2021:teams:farmer_john:2sozx:codeforces_round_670_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-10-06T10:29:47+0800

C * 题意:给定一棵树，要求删除一条边，连一条边使得依旧是树并且重心唯一。 * 题解:显然重心最多两个，如果只有一个，随便删一条边再连上即可。否则显然两个重心是相连的，将这条边断掉，再将一个重心的儿子与另一个重心连上即可。$a$$b,c$$b$$c$$a_i = b_i + c_i$$\max(b_n, c_1)$$q$$x$$x$$\max(b_n, c_1)$$n \le 10^5$$a$$b$$c$$sum$$\max(b_1 + sum, a_1 - b_1)$$\lceil \frac{sum + a_1}{2} \rceil$

2020-2021:teams:farmer_john:2sozx:codeforces_round_671_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-10-06T10:36:30+0800

E * 题意:$t$ 组询问，每次询问一个 $n$ ，问将所有 $n$ 的因数组成一个环，使得环上相邻的数互质的个数最少，输出方案与最小个数。 * 题解:显然 $n = p^k$ 时随便构造即可。$n = p_1p_2$ 时必然会有一个互质对，随便构造即可。$n = p_1^i p_2^j$$n$$p_1,p_1p_2,p_2,\cdots,p_k,p_kp_1$

2020-2021:teams:farmer_john:2sozx:codeforces_round_672_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-10-06T11:02:35+0800

C2 * 题意:给一个序列 $a$，找一个递增序列$b$ 使得$a_{b_1}-a_{b_2}+a_{b_3}-a_{b_4}+\cdots$最大，有 $q$ 次交换，每次交换 $a_l, a_r$ 并询问交换后的最大值。 * 题解:观察所求的式子与 $a$ 的关系，显然若是 $a_i > a_{i + 1}$ 直接将这两个数加入答案一定是增加的，若 $a_i < a_{i + 1}$$a_{i + 1}$$a_{n + 1} = 0$$0, 1$$(i,j)$$a_i = a_j = 1$$\exists k,i < k < j,a_k = 1$$1$$1$$0 \sim \frac{n(n - 1)}{2}$$n \le 80$$f[i][j][k]$$i$$1$$i$$j$$1$$k$$zyf$…

2020-2021:teams:farmer_john:2sozx:educational_codeforces_round_83_rated_for_div_2

Anonymous (anonymous@undisclosed.example.com) — 2020-05-13T16:27:14+0800

A * 题意：给定两个数 $n,m$ 表示正 $n$、$m$ 边形，问是否有一种方式使得两种多边形共用定点并且多边形中心重合。$3{\le}m

2020-2021:teams:farmer_john:2sozx:educational_codeforces_round_87_rated_for_div_2

Anonymous (anonymous@undisclosed.example.com) — 2020-06-01T12:01:38+0800

A * 题意:小水题。 * 题解:水水水。 B * 题意:给定一个由$123$组成的字符串，求最短的包含$123$的子串。 * 题解:记录每个位置的后继是啥，然后枚举开头是哪个数字，然后往后搜就行。 C * 题意:给定一个正$2n$$n$$n$$k$$n$$m$$n_1, n_2, n_3$$1,2,3$$1$$(1 \le n \le 5000, 0 \le m \le 10^5, n_1 + n_2 + n_3 = n)$$1$$3$$1$$n$

2020-2021:teams:farmer_john:2sozx:educational_codeforces_round_90_rated_for_div_2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-02T21:49:19+0800

A * 水 B * 水 C * 水 D * 题意：给定一个长度为 $n (n \le 2 \cdot 10^5)$ 的数列 $a_i$ ，可以至多选取一段区间进行翻转，求最后偶数位的和的最大值。数列从 $a_0$ 开始。 * 题解：显然翻转的区间长度一定为偶数，并且相对于接过来说可以认为时相邻两项翻转，取连续多个的相邻两项，因此差分后 $dp$

2020-2021:teams:farmer_john:2sozx:educational_codeforces_round_92_rated_for_div_2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-30T20:09:44+0800

F * 题意： * 题解： G * 题意： * 题解：

2020-2021:teams:farmer_john:2sozx:educational_codeforces_round_93_rated_for_div_2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-21T12:20:59+0800

D * 题意:三个颜色，每个颜色有一些木棍，现在每次从两个颜色中取出两个木棍构成一个矩形，问最后矩形面积和的最大值是多少。 * 题解:$dp$ 即可 F * 题意: * 题解: G * 题意: * 题解:

2020-2021:teams:farmer_john:2sozx:namomo_fish_easy_round_1

Anonymous (anonymous@undisclosed.example.com) — 2020-08-30T19:55:58+0800

B * 题意:将 $1,2,\cdots,n^2$ 填入 $n \times n$ 的矩阵中，问存在多少种方式使得任意单调递增的序列 $p_1,p_2,\cdots,p_i$ 有 $p_1 = 1, p_i = n^2$ 且 $\sum_{j = 1}^{i - 1}dis(p_j, p_{j + 1})$ 为偶数，其中 $dis(p_j, p_{j + 1})$ 为两个点的曼哈顿距离。$n\le 10^3$ ，答案模 $10^9 + 7$ * 题解:先只考虑序列的第一个点和最后一个点的排列方式。在第一个点确定之后，$n^2$$n!$$n = 1$

2020-2021:teams:farmer_john:2sozx:problem

Anonymous (anonymous@undisclosed.example.com) — 2020-06-06T19:51:27+0800

fib数列——矩阵快速幂