2020-2021:teams:farmer_john:jjleo:aising_programming_contest_2020

Anonymous (anonymous@undisclosed.example.com) — 2020-07-17T11:35:42+0800

A B C D E F + + + + O O rank:684 AB * 题意:水。 * 题解:摸了。 C * 题意:设$f(n)$为满足$x^2 + y^2 + z^2 + xy + yz + zx = n$的$(x,y,z)$三元组个数，求$f(1),f(2), \cdots , f(N)$。$(1 \leq N \leq 10^4)$ * 题解:数据范围很小，直接枚举$x,y,z$进行贡献即可。 D * 题意:定义$f(n)=n \mod \mathrm{popcount}(n)$$N$$i$$f$$0$$(1 \leq N \leq 2 \times 10^5)$$f$$1$$x$$x+1$$x-1$$N$$i$$k_i$$l_i$$r_i$$(1 \leq N \leq 2 \times 10^{5})$$l_i>r_i$$l_i

2020-2021:teams:farmer_john:jjleo:codeforces_global_round_8_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:06:13+0800

A B C D E F G H + + + + O O rank:740 A * 题意:过水已隐藏。 * 题解:过水已隐藏。 B * 题意:求最短的字符串使得至少有$k$个不同的子序列$codeforces$。$(1 \leq k \leq 10^{16})$ * 题解:贪心地一个个来，$1$$c$$1$$o$$2$$c$$2$$o$$n$$OR$$AND$$1$$1$$1$

2020-2021:teams:farmer_john:jjleo:codeforces_round_604_div._1_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T17:02:16+0800

A B C D E F + O rank: A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:codeforces_round_608_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-28T11:15:42+0800

A B C D E F + + + + O O rank:350 A * 题意:水。 * 题解:摸。 B * 题意:给出一个长度为$n$的$01$字符串，每次操作可以选择两个相邻字符将他们变为相反的字符，问能否不超过$3n$$(s_x,s_y)$$(x_i,y_i)$$n$$k$$i$$a_i$$b_i$$c_i$$(1 \le n \le 5000, k + \sum\limits_{i = 1}^{n} b_i \le 5000)$$f_{i,j}$$i$$j$$\begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix}$$1$$path(x)$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$x$$path(1),pat…

2020-2021:teams:farmer_john:jjleo:codeforces_round_609_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T14:35:12+0800

A B C D E + + + O O rank:1074 A * 题意:输出两个合数使得两者之差的等于$n$。 * 题解:输出$9n,8n$。 B * 题意:给出序列$a$和$b$，求一个最小的$x$使得$a$中每个元素$a_i=(a_i+x) \mod m$后可以通过排列使其和$b$相等，保证存在答案。$(1 \leq n \leq 2000, 1 \leq m \leq 10^9, 0 \leq a_i,b_i < m)$$a_1$$b$$a$$k$$b$$b \ge a$$b$$b_i = b_{i+k}$$b$$k$$k$$a$$k$$1$$1 \times 2$$2 \times 1$$x$$\ge x$$1 \times 2$$1$$n,n-1,\ldots,2,1$$1$$n$$f(i)$$1,2,\ldots,i$$f(1),f(2),\ldots,f(n)$$(1 \leq n \leq 200\,000)$$f(i)$$1,2,\ldots,i$$距离-中间数字的个数$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_610_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-24T20:51:13+0800

A B C D E + + + + O rank:202 A * 题意:过水已隐藏。 * 题解:过水已隐藏。 B * 题意:$n$个物品，每个有一定的价格，你一共有$m$元钱，每次可以有两种购买方式，一种是直接花对应的价格买一个物品，另一种是恰好选择$k$$k$$(2 \le n \le 2 \cdot 10^5)$$k$$\le$$ab$$300$$300$$ab$$s$$s$$n$$n+2$$0$$a$$x$$x+1$$a$$=x$$b$$300$$b$$301$$ab$$b$$b$$a$$x$$b$$n+2$

2020-2021:teams:farmer_john:jjleo:codeforces_round_612_div._2_virtual_participation

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

A B C D E F + + + O O rank:1125 A * 题意:过水已隐藏。 * 题解:同上 B * 题意:大意就是给出一些字符串，选出三个符合条件的字符串，有多少种方案。 * 题解:只需要暴力枚举map记录一下即可，但是不要重复算了再除一下去重，不然会被卡常。$1$$n$$(n \le 100)$$1$$2$$0$$0$$n+1$$c_i$$a_i$$a_i$$c_i$$a_i$$1$$10^9$$n$$n$$(n+1)^2$$\left\lceil 0.777(n+1)^2 \right\rceil$$(1 \le n \le 100)$$s[2..n]$$s[1..n]$$n$$n$$s[1..\lceil\frac{n}{2}\rceil]$$s[1..n]$$f_{i,j}$$i$$j$$f_{i,j}-f_{i-1,j}$$j$$s[i..n+1-i]$$i$$i-1$$i-1$$i$$j$$s[i..n+1-i]$$i$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_613_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-05-30T00:11:27+0800

A B C D E F + + + + + O rank:118 A * 题意:我也是加把劲骑士 * 题解:全部木大 B * 题意:给定一定长度为$n$的序列，问是否除了$sum[1,n]$的区间和的最大值是否比$sum[1,n]$小。 * 题解:维护前缀最小值，扫一遍。最后以$n$$X$$a,b$$LCM(a, b)=X$$max(a, b)$$(1 \le X \le 10^{12})$$a$$b$$n$$a$$X$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$(1\le n \le 10^5, 0 \le a_i \le 2^{30}-1)$$a$$XOR-MST$$0$$1$$1$$n$$a$$\max\limits_{1 \le i < j \le n} LCM(a_i,a_j)$$(2 \le n \le 10^5)$$gcd$$\frac{X}{gcd}$$x$$x$$O(m)$$O(nm\log n)$$cnt_i$$i…

2020-2021:teams:farmer_john:jjleo:codeforces_round_614_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-05-22T22:02:32+0800

A * 题意:有个人爱爬楼，让你帮他模拟一下。 * 题解:好累啊。 B * 题意:求一下调和级数。 * 题解:模拟即可。 C * 题意:在$2 \times n$的方格上进行数次操作，每次放岩浆或删除岩浆，问每次操作后能否从左上角走到右下角。保证起点和终点没有岩浆。$(x_0, y_0)$$(a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)$$(x_s, y_s)$$t$$(1 \leq x_0, y_0 \leq 10^{16}, 2 \leq a_x, a_y \leq 100, 0 \leq b_x, b_y \leq 10^{16}, 1 \leq x_s, y_s, t \leq 10^{16})$$100$$a_x, a_y \ge 2$$n$$0$$n-2$$\sum_{1 \leq u < v \leq n} mex(u, v)$$mex(u, v)$$u$$v$$mex$$(2 \leq n \leq 3000)$$siz_{i, j}$$i$$j$$fa_{i, j}$$i$$j$$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_619_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-05-15T23:49:03+0800

A * 题意:大水题 * 题解:练习英语阅读和手速。 B * 题意:长度为$n(n\le100000)$的序列中有一些位置确定，其它位置不确定，在不确定的位置上填上同一个数字，使得最大相邻差值最小。 * 题解:一开始写了很复杂的二分答案还WA了，结果发现并不需要。考虑与不确定位置相邻的确定的数字的最大值和最小值，令填上的数字为这两个数字的平均值一定是最优的，最后不要忘记考虑相邻的已确定的数字之间的差值对答案的影响。$n(1 \leq n \leq 10^{9})$$01$$1$$m(0 \leq m \leq n)$$1$$m$$1$$m+1$$0$$0$$0$$n \times m(n,m\le500)$$(4 n m - 2n - 2m)$$k$$3000$$3$$(L,R,D,U)$$k>(4 n m - 2n - 2m)$$3(n-1)+3(m-1)+2=3(n+m)-4<3000$$n \times m$$q$$(1 \leq n , m \leq 500, 1 \leq q \leq 3 \cdot 10^{5})$$K$$K$$k$$k$$mid…

2020-2021:teams:farmer_john:jjleo:codeforces_round_620_div._2_virtual_participation

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

A * 题意:大水题 * 题解:练习英语阅读和手速。 B * 题意:给出$n(n\le100)$个长度为$m(m\le50)$的字符串，求选出任意个任意排序所组成的最长回文串。 * 题解:数据范围很小，直接两两暴力匹配，然后最中间再放一个没匹配上的回文串（如果有的话）。$m$$1°C$$1°C$$n$$t_i$$[l_i,r_i]$$L$$R$$<<>><<>>$$1$$n$$1,2..n$$>$$n..2,1$$<$$n$$q$$x$$y$$a$$b$$k$$a$$b$$k$$k$$a \rightarrow lca \rightarrow b$$a \rightarrow x (\rightarrow_{cycle} x)\rightarrow_1 y \rightarrow b$$a \rightarrow x (\rightarrow_{cycle} x) \rightarrow b$$a \rightarrow y (\rightarrow_{cycle} y)\rightarrow_1 x \rightarrow b$$a \rightarrow …

2020-2021:teams:farmer_john:jjleo:codeforces_round_621_div._1_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-07-03T17:48:59+0800

A B C D E F G + + + O O O O rank:1422 A * 题意:水。 * 题解:摸了。 B * 题意:给出一个整数序列$a$，现在在$(0,0)$点，每次可以向任意一个方向移动一个距离，要求距离的大小出现在$a$$(x,0)$$3$$1,2$$1,2$$n$$m$$k$$1$$n$$(2 \le n \le 2 \cdot 10^5, n-1 \le m \le 2 \cdot 10^5, 2 \le k \le n)$$x_i$$1$$i$$y_i$$n$$i$$z$$min(z,max_{i \ne j}(min(x_i+y_j,y_i+x_j)))$

2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated

Anonymous (anonymous@undisclosed.example.com) — 2020-05-10T22:07:10+0800

A * 题意:有无限个位置，定义一个变换,每个位置$i$变换到位置$(i+a_{i\%n})$处,$|a_i|< =10^9$,问是否有两个位置经过一次变换后变换到同一个位置。 * 题解:求出$0,1…n-1$模$n$意义下变换后的位置，只要没有冲突就可以，因为是无限的；反之如果有冲突，显然能找到至少2个变到一个位置上的。$n*m$$n$$m$$x_i

2020-2021:teams:farmer_john:jjleo:codeforces_round_641_div._1

Anonymous (anonymous@undisclosed.example.com) — 2020-05-15T19:32:18+0800

A * 题意:给出$n(n\le100\,000)$个数$a_i(a_i\le200\,000)$，求两两最小公倍数的最大公约数。 * 题解:对每个数筛质因子统计次幂，最后的结果中每个质因子取第二小次幂即可。 B * 题意:给出一个长度为$n(n\le100\,000)$的序列，每次可以将一个区间全部变成这个区间的中位数（偶数的时候取小的那个），问能否将区间所有数变为$k$$k$$n>1$$3$$\ge k$$n=1$$n \times m$$0$$q$$t$$(1\le n,m\le 1000, 1\le q\le 100\,000, 1\le t\le 10^{18})$$O(1)$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3

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

ABCD * 题意:大水题 * 题解:练习英语阅读和手速。 E * 题意:给定一个长度为$n$的$01$串，每次操作可以更改某一位，要求使得所有相邻的$1$的间隔为$k$，求最少操作数。$(1 \le n \le 10^6; 1 \le k \le n)$ * 题解:设$f[i]$为第$i$位为$1$的最少操作数，dp即可，状态转移看代码。$n \times m$$a_{i,j}$$1$$0$$1$$(1 \le n, m \le 100, 1 \le a_{i, j} \le 10^{15})$$a_{i, j}$$(a_{i,j}-i-j-2)$$O(n^4)$

2020-2021:teams:farmer_john:jjleo:codeforces_round_643_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-06T23:45:48+0800

A * 题意:递推公式$a_{n+1} = a_{n} + minDigit(a_{n}) \cdot maxDigit(a_{n})$，给定$a_1$，求$a_K$。$(1 \le a_{1} \le 10^{18},1 \le K \le 10^{16})$ * 题解:签到题不会，正好物理实验课，直接溜了。其实最多迭代$54$次就会出现$0$，然后就一直是那个数，所以模拟即可。 B * 题意:有$n$个人，组队探险，可以有人不去探险，第$i$$\ge e_i$$e_i$$A \le x \le B \le y \le C \le z \le d$$(x,y,z)$$(1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5)$$x$$y$$z$$S$$N$$K$$N$$K$$2N \le S$$n$$+1$$A$$-1$$B$$+1$$-1$$C$$A+B>C$$A+B$$C$$X$$22$$Q$$gcd(Q,X)$$d$$| ans - d | \le 7,\frac{1}{2} \le \frac{ans}{d} \le…

2020-2021:teams:farmer_john:jjleo:codeforces_round_645_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-19T22:54:47+0800

A B C D E F + + + + O O rank:528 A * 题意:比比谁更快 * 题解:我慢死了 B * 题意:$n$个人，每个人有一个权值$a_i$，一开始家里只有自己一个人，每次可以邀请数个人来，他们会同时到达。必须保证每个人到的时候看到的其他人的数量$\ge a_i$$a_i$$-1$$(y_2-y_1)$$(x_2-x_1)\cdot(y_2-y_1) + 1$$n$$d_i$$i$$i$$x$$x$$n$$k$$k$$\lfloor \tfrac{n}{2} \rfloor$$x$$k$$k$$> \lfloor \tfrac{n}{2} \rfloor$$k$$> \lfloor \tfrac{n}{2} \rfloor$$k$$n-k+1$$[s_1,\ x-a_1,\ x-a_2,\ \ldots,\ x-a_{n-k}]$$k$$1$$[s_1+x,\ x-a_1,\ x-a_2,\ \ldots,\ x-a_{n-k-1}]$$x$$k$$k$$k$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_646_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:34:18+0800

A B C D E F + + + + + O rank:93 A * 题意:$n$个数，问能否选$x$个数使他们的和是奇数。$(x \le n \le 1000)$ * 题解:不带脑子，WA了两发。$n$太小了，直接暴力枚举即可。 B * 题意:$01$串，每次操作将一个字符翻转，问将串变为$01$$10$$\le 1$$1$$0$$0$$1$$\le 1$$2$$n$$a$$k$$a$$a$$k$$12$$a$$k$$(2 \leq n \leq 1000, 1 \leq k \leq n)$$(1)$$(10)$$(1)$$12$$0$$1$$0$$1$$a_i$$k$$a_i \times k$$01$$n$$s$$t$$s[l,l+1 \ldots r]$$s[r,l,l + 1 \ldots r - 1]$$s$$t$$(1\leq n \leq 2000)$$f_{i,j}$$s[1..i]$$t[1..j]$$i \ge j$$s[i]=t[j]$$f_{i,j}=f_{i-1…

2020-2021:teams:farmer_john:jjleo:codeforces_round_647_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-08-12T12:06:45+0800

A B C D E F + + + + + O rank:39 A * 题意:每次可以对$a$乘以$2,4,8$或者在整除的情况下除以$2,4,8$，问最少多少步可以变成$b$或判断无解。 * 题解:不妨设$a \le b$，那么如果有解必须满足$a|b$而且$\frac{b}{a}$是$2$$8,4,2$$n$$s$$k$$k$$(1 \leq n \leq 1024, 0 \leq s_i < 1024)$$1$$2047$$\sum_{i=1}^{n}{\text{pop_count}(i \oplus (i-1))}$$(1 \leq n \leq 10^{18})$$f(n)=\sum_{i=1}^{n}{\text{pop_count}(i \oplus (i-1))}$$f(n)=2f(2^{i-1})+1+f(n-2^i)$$2^i$$n$$1$$f(0)=0$$n$$n$$n$$mex$$mex$$mex$$n$$p^{k_i}$$k_i$$n$$a,b$$x,y$$2^k$$x \o…

2020-2021:teams:farmer_john:jjleo:codeforces_round_648_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-13T11:29:51+0800

A B C D E F G + + + + + O O rank:1044 A * 题意:读错题直接劝退了。给出一个黑白方格，对于一个白格，如果同一列和同一行都没有黑格，那么可以将它涂黑，如果一个人没有格子可以涂了就输了。问先手能不能赢。$1$$min$$01$$a$$0$$bc$$1$$a-b,a-c,a-b$$1$$n$$n$$k$$\max(1, k - 2)$$i$$1$$2^i$$(1 \le n \le 500)$$3$$OR$$3$$s$$t$$s$$s$$t$$n$$a_i$$i$$a_i$$a$$OR$$a$$OR$$13$$(2 \le n \le 1000)$$OR$$OR$$a_i$$2 \log n$$f_{x,0/1}$$x$$0/1$$OR$$i$$x$$0$$f_{x,1}$$2 \log n = 20 > 13$$2$$f_{x,0}$$f_{x,1}$$2$$13$$01$$1$$f_x$$i$$1$$OR$$13$$n$$\binom{13}{6}=1716>…

2020-2021:teams:farmer_john:jjleo:codeforces_round_649_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-19T23:40:06+0800

A B C D E + + + + + rank:38 （竟然AK了，虽然是VP） A * 题意:找出一个最长的连续的子序列使得它不被$x$整除。$(1 \le x \le 10^4)$ * 题解:想不出来，暴力上了个线段树维护每个余数对应的最长前缀和。其实可以证明答案一定是前缀或者后缀，所以只用扫一遍就可以了。$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$a_i$$a_i \le a_{i+1}$$b_i$$MEX(a_1,a_2,\ldots,a_i)=b_i$$0 \le b_i \le 10^6$$b_i \ge i$$a_i$$b_i=a_i$$a_i$$a_i$$b_i=a_{i-1}$$\le k$$\lceil\frac{k}{2}\rceil$$k$$\lceil\frac{k}{2}\rceil$$\sqrt{n}$$k$$k$$k$$\lceil\frac{k}{2}\rceil$$0$$n-1$$OR$$4269$$(3 \le n \le 2048…

2020-2021:teams:farmer_john:jjleo:codeforces_round_650_div._3_virtual_participation

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

A B C D E F + + + + + O rank:394 ABC * 题意:过水已摸。 * 题解:过水已摸。 D * 题意:对于一个字符串$t$，定义数组$b$，$b_i$的值是所有$>t_i$字符串位置到$i$距离之和。现在给出$b$数组和每个字母最多出现次数，要求构造出一个可行的字符串$t$$z$$a$$b_i=0$$\ge$$n$$k$$(1 \le n, k \le 2000)$$k$$n$$(1 \le n \le 2 \cdot 10^5)$$1,\ldots,1,2,\ldots2,\ldots$$x$$x$$f_{i,0/1/2}$$i$$n-最长子序列长度$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_651_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T15:42:08+0800

A B C D E F1 F2 + + + + + + O rank:26 A * 题意:给定$n$，求最大的$gcd(a,b)$，其中$1 \leq a < b \leq n$。$(2 \leq n \leq 10^6)$ * 题解:我太菜了，去线性筛最小质因子。因为$a,b$不同，所以肯定要丢掉一个质因子，最小的质因子是$2$$\lfloor{\frac{n}{2}}\rfloor$$2 \cdot \lfloor{\frac{n}{2}}\rfloor$$\lfloor{\frac{n}{2}}\rfloor$$2n$$n$$1$$-1$$1$$n=1$$n$$1$$n$$-1$$1$$2$$2$$n$$k$$min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$$(2 \leq k \leq n \leq 2 \cdot 10^5)$$\ge mid$$k$$01$$s$$t$$s$$s$$t$$01$$s0t1$$s…

2020-2021:teams:farmer_john:jjleo:codeforces_round_652_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T22:10:42+0800

A B C D E F + + + + O O rank:324 A * 题意:问一个正$n$边形是否有两条垂直的边。 * 题解:答案为$[n \mod 4 = 0]$，相当于把$2\pi$分成四份$\frac{\pi}{2}$。 B * 题意:过水已隐藏。 * 题解:摸了。 C * 题意:将$n$$k$$w_i$$k$$w_i$$k$$n$$f_i=f_{i-1}+2f_{i-2}$$3$$f(n-3),f(n-6)\ldots$$3$$f_i=f_{i-1}+2f_{i-2}+[i \mod 3 = 0]$$n$$w_i$$m$$t$$s$$e(s \le e)$$s$$s+1$$2s$$s$$e$$win(s,e)$$s,e$$e$$s$$+1$$s$$e$$+1$$e$$s$$e$$2s>e$$s$$e$$4s>e$$2s>e$$s$$e$$4s \le e$$win(s,\frac{e}{4})$$\frac{e}{4}$$4s>e$$2s>e$$win(s,\frac{…

2020-2021:teams:farmer_john:jjleo:codeforces_round_653_div._3_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-29T20:25:40+0800

A B C D E1 E2 F + + + + + O O rank:177 ABCD * 题意:水。 * 题解:摸！ E1 * 题意: * 题解: E2 * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:codeforces_round_655_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-07-17T13:34:52+0800

A B C D E F + + + + O O rank:737 A * 题意:水。 * 题解:摸。 B * 题意:给出$n$，求$a,b$使得$a + b = n$且$LCM(a, b)$最小。$(2 \leq n \leq 10^{9})$ * 题解:显然$LCM(a, b) \geq max(a,b)$，盲猜一手$a,b$成倍数关系时最小，$O(\sqrt{n})$枚举$n$的约数即可。 C * 题意:给定一个$1$$n$$n$$n$$(1 \leq n < 2 \cdot 10^5)$$\dfrac{n-1}{2}$$n \times m$$k_i$$a_i$$i$$\sum_{i=1}^{m}{{a_i}^2}$$(1 \le n,m \le 100)$$f_{i,j}$$[i,j]$$f_{i,j}=f_{i,k-1}+x+f_{k+1,j}$$x$$k$$[i,j]$$n$$k$$k$$4k$$(1 \le n \le 2 \cdot 10^5,1 \le k \le…

2020-2021:teams:farmer_john:jjleo:codeforces_round_656_div._3_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T20:16:02+0800

A B C D E F + O rank: ABCD * 题意:水。 * 题解:摸！ E * 题意:给出一个不保证联通的图，$n$个点$m$条边，其中有一些边是有向的，另一些边是无向的，求一种方案给所有无向边定向最后的图无环，或判断无解。$(2 \le n \le 2 \cdot 10^5, 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}))$$0$$n$$k$$(2 \le n \le 2 \cdot 10^5, 1 \le k < n)$$\ge k$$2 \times n$$1$$n$$(1 \le n \le 2 \cdot 10^5)$…

2020-2021:teams:farmer_john:jjleo:codeforces_round_657_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-24T17:48:07+0800

A B C D E F + + + O O O rank:197 A * 题意:有点复杂的签到题。 * 题解:有程设那味儿了。 B * 题意:给定$n,m$，问是否存在$n > 0, l \leq a, b, c \leq r$，使得$n \cdot a + b - c = m$。$(1 \leq l \leq r \leq 500\,000, 1 \leq m \leq 10^{10})$ * 题解:$b-c \in [-r+l,r-l]$，直接枚举$a$，进行取余看能是否存在$n \cdot a$$m$$a_i$$b_i$$n$$(1 \le n \le 10^9, 1 \le m \le 100\,000)$$\ge$$b_i$$a_i$$b_i$$10^9$$n$$k$$(1 \leq n \leq 100\,000)$$k=0$$k \ne 0$$n$$2^x-1$$n=9,k=2$$k \le \dfrac{n-3}{2}$$1,3,7,15 \cdots$$O(n\log n…

2020-2021:teams:farmer_john:jjleo:codeforces_round_658_div._1

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

A B C D E F + O rank: A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:codeforces_round_659_div._1

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

A B C D E F + O rank: A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:codeforces_round_660_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-07-31T16:30:32+0800

A B C D E F + O rank: A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_78_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:06:21+0800

A B C D E F + + + + + O rank:186 A * 题意:略长的签到。 * 题解:摸了。 B * 题意:对于给定的$n$，将$\{1,2,\ldots,i\}$分为两部分，使两部分之和的差值等于$n$，问$i$最小是多少。$(0 \le n \le 10^9)$ * 题解:设分成两部分的和为$x$$y$$\sum_{j=1}^{i}{j}=m$$x+y=m,x-y=n$$x=\frac{n+m}{2}$$i$$\frac{n+m}{2}$$\frac{n+m}{2} \ge m$$i$$\{1,2,\ldots,i\}$$\le \sum_{j=1}^{i}{j}$$n$$1,2,\ldots,2n$$(1 \le n \le 5 \cdot 10^5)$$[l_i,r_i]$$n$$n$$n$$(1 \le n \le 5 \cdot 10^5)$$dfs$$n$$\frac{1}{m}$$x$$x^k$$998244353$$(1 \le n, m < 99824…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_79_rated_for_div._2_virtual_participation

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

A B C D E F + + + + O rank:696 A * 题意:给出三种颜色物品的数量，是否存在一个排列使得相邻颜色都不同。 * 题解:只要数量少的两种颜色可以插空到数量最多的一种颜色中即可，即$x+y>=z-1$$n$$s$$k$$2k+1$$n$$01$$l$$0$$1$$k$$min(0 \text{的数量}, 1 \text{的数量})$$(1 \le n, k, l \le 10^6, l \le n)$$0$$1$$0$$f(x)$$x$$0$$dp[i]$$i$$0$$dp[i-l]$$i < l$$dp[i]$$1,2..i$$0$

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_80_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:05:12+0800

A B C D E F + + + + O O rank:423 A * 题意:求$x + \left\lceil \frac{d}{x + 1} \right\rceil(x \ge 0)$的最小值。 * 题解:有$x + \left\lceil \frac{d}{x + 1} \right\rceil = \left\lceil x + \frac{d}{x + 1} \right\rceil$，因此可以化为对勾函数$x + \frac{d}{x + 1} = (x + 1) + \frac{d}{(x + 1)} - 1$，因此最小值在$\left\lfloor \sqrt{d} -1\right\rfloor$处或$\left\lceil \sqrt{d} - 1 \right\rceil$处取得。 B * 题意:求$a \cdot b + a + b = conc(a, b)$且$1 \le a \le A,1 \le b \le B$的$(a, b)$对数，$conc(a…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_81_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:04:53+0800

A * 题意:无限个$7$位数码管，可以点亮$n$位，问最大数字。 * 题解:显然应该追求所得数字的位数大，因此每一位用的应该尽量少，如果是奇数就填个$7$然后全填$1$，如果是偶数就全填$1$。 B * 题意:一个无限循环的$01$$0$$1$$x$$-1$$01$$+1$$x=0$$s$$t$$s$$t$$f[i][j]$$s$$i$$j$$+1$$T$$a$$m$$x$$0 \le x < m$$\gcd(a, m) = \gcd(a + x, m)$$(1 \le T \le 50, 1 \le a < m \le 10^{10})$$d=gcd(a,m)$$gcd(\frac{a}{d},\frac{m}{d})=gcd(\frac{a+x}{d},\frac{m}{d})=gcd(\frac{a+x}{d} \ mod \frac{m}{d},\frac{m}{d})=1$$0 \le x < m$$\frac{a+x}{d} \ mod \frac{m}{d}$$<\frac{m}{d}$$\phi(\frac{m}{d})$$O(\sqrt{m})$…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_82_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:04:25+0800

A * 题意:给定一个$01$串，问最少删掉多少个$0$使得所有$1$组成连续的一段。 * 题解:扫一遍把第一个$1$和最后一个$1$中间的$0$全删了即可。 B * 题意:天气$g$天好$b$天坏，无限循环，每天可以动工也可以不动工，一共需要动工$n$$n$$n$$2$$1$$2$$m$$m$$m$$s$$t$$(|s|, |t| \le 400)$$t$$t$$f[i][j]$$i$$j$$O(n)$$O(n^4)$$f[i][j]$$s$$i$$j$$n \times m$$0$$q$$0$$(1 \le n, m \le 300,1 \le q \le 2 \cdot 10^6)$$O(q)$

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_87_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:04:36+0800

A * 题意:有个人赖床，让你帮他模拟一下。 * 题解:写困了。 B * 题意:给定一个由$123$组成的字符串，求最短的包含$123$的子串。 * 题解:写的太复杂了，处理出每个位置往左往右的第一个$123$的位置，然后进行组合。$2n$$n$$n$$\frac{\pi}{n}$$\frac{\pi}{2n}$$\frac{\pi}{2n}$$\frac{\pi}{2n}$$\frac{\pi}{2n}$$\frac{\pi}{4n}$$\frac{\cos(\frac{\pi}{4n})}{\sin(\frac{\pi}{2n})}$$k$$28MB$$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$$n$$k$$a_i$$b_i$$(1 \le k \le n \le 75)$$n$$n$$n$$n$$k$$50$$(2 \le n \le 1000, 1 \le k \le \frac{n}{2})$$k \le…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_88_rated_for_div._2

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

A B C D E F + + + + + O rank:433 A * 题意:卡其脱离太 * 题解:莫那莫那一 B * 题意:水题 * 题解:但是我跟没睡醒一样这么水都能卡半个小时，光速下分，太菜了。 $long long$$k$$1 \le a_1 < a_2 < \dots < a_k \le n$$x$$(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k}$$p_i$$1$$k$$(1 \le n, k \le 5 \cdot 10^5)$$a_i(i > 1)$$a_1$$x$$\sum_{i=1}^{n}{\binom{k - 1}{n / i - 1}}$$n$$(1 \le n \le 25000)$$n$$O(n^2)$$O(n \log^ 2 n)$…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_89_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:06:03+0800

A B C D E F G + + + + + O O rank:190 A * 题意:钻石铲要$2$个木棍$1$个钻石，钻石剑要$2$个钻石$1$个木棍，现在有$a$个钻石和$b$个木棍，问最多能做多少把武器。 * 题解:这题叫Shovels and Swords，第一反应就是MC，还真是。$a \le b$$2a>b$$\frac{a+b}{3}$$a$$1$$0$$1$$n \times m$$0$$1$$1$$0$$x$$a|x,b|x,gcd(a+b,x)=1$$a,b$$x$$x$$a,b$$ab=x$$gcd(a,b)=1$$gcd(a+b,x)=gcd(a+b,ab)=1$$gcd(a,b)=gcd(a+b,b),gcd(a,b)=1 \rightarrow gcd(a,bc)=gcd(a,c)$$gcd(a,b)=gcd(a+b,b)=1 \rightarrow gcd(a+b,ab)=gcd(a+b,a)=gcd(a,b)=1$$a,b$$n,m$$b$$a$$m$$i$…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_90_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-06-27T23:03:47+0800

A B C D E F G + + + + + O O rank:411 A * 题意:两种购买模式，单价$a$元一个和打包$c$元$b$个，问是否存在一个购买数量使得前者更便宜，以及一个购买数量使后者更便宜。$b$$01$$01$$01$$0$$f(x)$$x$$x$$f(x) + f(x + 1) + \dots + f(x + k) = n$$(1 \le n \le 150,0 \le k \le 9)$$f(x)$$10$$n$$9-k$$n$$0 \le k \le 9$$a$$9$$1$$9$$x$$8$$y99\ldots998\underbrace{99\ldots99}_{a个9}x$$n$$a_i$$b_i$$(2 \le n \le 10^6,1 \le a_i,b_i \le 10^9)$$b_n$$a_1$$b_i$$b_n$$a_1$$a_i(i

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_91_rated_for_div._2_virtual_participation

Anonymous (anonymous@undisclosed.example.com) — 2020-07-17T15:13:14+0800

A B C D E F G + + + + + + + rank:14 A * 题意:水。 * 题解:摸。 B * 题意:给出一个电脑的石头剪刀布序列，会按照所有循环同构进行一轮，现在求一个你的石头剪刀布序列，对于每一轮都按照这个序列出，使得获胜次数最多。$x$$x$$k$$y$$a$$b$$a,b$$b$$a$$a$$k$$1$$n$$m$$a$$b$$a$$b$$m-1$$(2 \le m \le n \le 2 \cdot 10^5)$$-1$$-1$$m$$m-1$$\log n$$O(n \log ^ 2 n)$$999+999=181818$$n$$c$$m$$(a,b)$$a+b=c$$998244353$$(1 \le n, m \le 5 \cdot 10^5)$$x$$[10,18]$$9 - (x - 9) + 1$$x$$x + 1$$n$$n$$k$$k=1,2, \cdots , n$$998244353$$(2 \le n \le 3 \cdot 10^…

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_92_rated_for_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-07-31T16:30:28+0800

A B C D E F + O rank: A * 题意: * 题解: B * 题意: * 题解: C * 题意: * 题解: D * 题意: * 题解: E * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:m-solutions_programming_contest_2020

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

A B C D E F + + + + O O rank: ABCD * 题意:水 * 题解:摸了。 E * 题意: * 题解: F * 题意: * 题解:

2020-2021:teams:farmer_john:jjleo:wqs二分

Anonymous (anonymous@undisclosed.example.com) — 2020-06-25T23:07:50+0800

WQS二分 * wqs二分可以解决形如在$n$个物品中选$k$个物品最大化/最小化总价值。直接dp一般是$O(nk)$的，而如果题目满足下面的条件并且可以用$O(n)$时间在不考虑选择物品个数的情况下计算出最大值/最小值，就可以用wqs二分做到$O(n \log n)$$x$$f(x)$$x$$f(x)$$x$$(k,f(k))$$f(k)$$

CVBB ACM Team 2020-2021:teams:farmer_john:jjleo

2020-2021:teams:farmer_john:jjleo:暑假题目汇总

2020-2021:teams:farmer_john:jjleo:比赛总结空模板

2020-2021:teams:farmer_john:jjleo:矩阵树定理

2020-2021:teams:farmer_john:jjleo:2020北交校赛

2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22

2020-2021:teams:farmer_john:jjleo:2020.07.11-2020.07.17

2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14

2020-2021:teams:farmer_john:jjleo:aising_programming_contest_2020

2020-2021:teams:farmer_john:jjleo:codeforces_global_round_8_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_604_div._1_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_608_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_609_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_610_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_612_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_613_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_614_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_619_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_620_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_621_div._1_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated

2020-2021:teams:farmer_john:jjleo:codeforces_round_641_div._1

2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3

2020-2021:teams:farmer_john:jjleo:codeforces_round_643_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_645_div._2

2020-2021:teams:farmer_john:jjleo:codeforces_round_646_div._2

2020-2021:teams:farmer_john:jjleo:codeforces_round_647_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_648_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_649_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_650_div._3_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_651_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_652_div._2

2020-2021:teams:farmer_john:jjleo:codeforces_round_653_div._3_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_655_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_656_div._3_virtual_participation

2020-2021:teams:farmer_john:jjleo:codeforces_round_657_div._2

2020-2021:teams:farmer_john:jjleo:codeforces_round_658_div._1

2020-2021:teams:farmer_john:jjleo:codeforces_round_659_div._1

2020-2021:teams:farmer_john:jjleo:codeforces_round_660_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_78_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_79_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_80_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_81_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_82_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_87_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_88_rated_for_div._2

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_89_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_90_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_91_rated_for_div._2_virtual_participation

2020-2021:teams:farmer_john:jjleo:educational_codeforces_round_92_rated_for_div._2

2020-2021:teams:farmer_john:jjleo:m-solutions_programming_contest_2020

2020-2021:teams:farmer_john:jjleo:wqs二分