CVBB ACM Team 2020-2021:teams:legal_string:jxm2001:contest

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛66

Anonymous (anonymous@undisclosed.example.com) — 2020-08-01T10:15:39+0800

牛客练习赛66 比赛链接 E 骚区间题意给定一个长度为 $n$ 的全排列，问存在多少个闭区间满足区间左端点恰为次小值，区间右端点恰为次大值。题解 $1$ 用权值线段树维护每个结点作为区间右端点且恰为次大值的左端点选区范围和每个结点作为区间左端点且恰为次小值的右端点选区范围。$O(n\log n)$$\text{set}$$\text{set}$$\text{copy}$

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68

Anonymous (anonymous@undisclosed.example.com) — 2020-08-29T12:37:22+0800

牛客练习赛68 比赛链接 D 牛牛的粉丝题意一个长度为 $n$ 的环，初始位置 $i$ 有 $x_i$ 个人。接下来每步，每个人有 $\frac as$ 概率向前一步，$\frac bs$ 概率向后一步，$\frac cs$ 概率不动，其中 $s=a+b+c$。问 $k$ 次后每个位置的人数期望。题解 1 $\text{dp}$${dp}(i,j)$$0$$j$$i$$O(n^2\log k)$$O(n^2\log k)$$$ \begin{pmatrix} \text{ans}_0\\ \text{ans}_1\\ \vdots\\ \text{ans}_{n-1} \end{pmatrix}= \begin{pmatrix} c & b & 0 & \cdots & a \\ a & c & b & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b & 0 & 0 & \cdots & c \end{pmatrix} \begin{pmatrix} x_0\\ x_1\\ \vdots…

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛77

Anonymous (anonymous@undisclosed.example.com) — 2021-02-27T11:08:58+0800

牛客练习赛77 比赛链接 E-小G的GLS图题意给定 $n$ 个点的点权图，$u,v$ 之间有连边当且仅当 $\text{gcd}(u,v)\neq 1$。问图中满足删去该点后图连通分量增加的点的数量。题解将每个点向该点的点权值的素因子连边，然后求这 $n$$1$$O(v+N\sqrt v)$

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛79

Anonymous (anonymous@undisclosed.example.com) — 2021-03-29T11:45:58+0800

牛客练习赛77 比赛链接 E-小G的数学难题题意给定长度为 $n$ 的序列 $A,B,C$ 以及 $p$。其中 $A=\sum_{i=1}^n a_ix_i,B=\sum_{i=1}^n b_ix_i,C=\sum_{i=1}^n c_ix_i,x_i=0/1$。问满足 $A\le p,B\ge p$ 时 $C$ 的最小值。题解设 $\text{dp}(i,p)$ 表示满足 $\sum_{j=1}^n a_jx_j\le p,\sum_{j=1}^n b_jx_j\ge p$ 时 $\sum_{j=1}^n c_jx_j$ 的最小值。于是有状态转移方程 $$ \text{dp}(i,p)\gets\min(\text{dp}(i-1,p),\min(\text{dp}(i-1,p-b_i\sim p-a_i))+c_i) $$ 单调队列维护即可，时间复杂度 $O(np)$…

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛81

Anonymous (anonymous@undisclosed.example.com) — 2021-05-22T11:29:07+0800

牛客练习赛81 比赛链接 C-小Q与构造题意求满足如下条件的集合 $S$ 个数： * $x\in S\to 1\le x\le n$ * $x\in S,y\in S,x\le y\to y \neq kx,y\neq k^px$ 题解把 $1\sim n$ 拆分成若干条链 $a,ak,ak^2,ak^3\cdots$ 易知每条链之间的选择互不影响，答案即为每条边的答案之积。对每条链，直接状压 $\text{dp}$$i$$i-1,i-p$$a$$k\not\mid i$$a$$\log_k n$$a$$k$$O((2^p+\log n)\log n)$$\sum_{u=1}^n\sum_{v=1}^n\min (a_u,a_v)\text{dis}(u,v)$$P(u,v)$$a_u\gt a_v$$a_u = a_v,u\gt v$$u$$\sum_{P(u,v)}a_v\text{dis}(a_v,rt)+\text{dis}(a_u,rt)\sum_{P(u,v)}a_v$$O(n\log^2 n)$…

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83

Anonymous (anonymous@undisclosed.example.com) — 2021-05-23T10:01:16+0800

牛客练习赛83 比赛链接 D-数列递推题意给定 $n,f_0$，求 $f_{1\sim n}$，其中 $$ f_i=\sum_{j=1}^if_{i\mod j} $$ 题解设 $i=kb+r$，考虑整数分块枚举 $k$，设 $t=i\mod k$，此时有 $r=t,t+k,t+2k,\cdots i-k\ast\text{lef}$。当 $k\lt \sqrt n$ 时，如果能提前维护 $f_t,f_{t+2k},f_{t+3k}\cdots$ 的前缀和，就可以 $O(1)$ 计算贡献。当 $k\ge \sqrt n$ 时，显然 $b,r$ 唯一，直接计算贡献即可。于是整数分块部分的时间复杂度为 $O(\sqrt i)$$i$$k\lt \sqrt n$$f_t,f_{t+2k},f_{t+3k}\cdots$$O(\sqrt n)$$O(n\sqrt n)$$a,b$$ax+by(x,y\ge 0)$$k$$a,b$$ax+by(x,y\ge 0)$$ab-na-mb(n,m\ge 1)$$ab-na-mb(n,m\ge 1)$$k$$ab-a-mb(…

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛85

Anonymous (anonymous@undisclosed.example.com) — 2021-06-29T17:04:25+0800

牛客练习赛85 比赛链接 F - 音游家的谱面(Hard version) 题意给定 $n$ 条轨道和一个含有 $m$ 个音符的谱，每个音符出现的轨道为 $p_i$。玩家有两个手指，一开始分别位于轨道 $1$ 和轨道 $n$ 的底部，且两个手指每秒可以向左右移动一格。$(n,m\le 5000)$$f(i,j)$$i$$p_i$$j$$$ f(i,j)\gets f(i-1,k)+|p_i-p_{i-1}|(|j-k|\le |p_i-p_{i-1}|) $$$$ f(i,j)\gets f(i-1,k)+|p_i-k|(|j-p_{i-1}|\le |p_i-k|) $$$O(n^2m)$$k$$f(i,j)$$O(nm\log n)$$t=0\sim n-1$$\min(f(i-1,k)+|p_i-k|(t\le |p_i-k|))$$j$$|j-p_{i-1}|$$O(nm)$$$ f(i,j)= \min(f(i-1,k)+\min(\max(|p_i-p_{i-1}|,|j-k|),\max(|p_i-k|,|j-p_{i-1}|))) $$$O(nm\log …

2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛87

Anonymous (anonymous@undisclosed.example.com) — 2021-08-21T22:40:35+0800

牛客练习赛87 比赛链接 C - 牛老板题意用最少的 $6^k,9^k$ 表示 $n$。$(1\le n\le 10^{12})$ 题解预处理 $n\lt 10^6$ 的答案，然后启发式搜索。 const LL MAXV=1e12+5,MAXN=1e6; vector vec; LL dp[MAXN]; void Init(){ vec.push_back(1); LL base=6; while(base

2020-2021:teams:legal_string:jxm2001:contest:2020牛客国庆集训派对

Anonymous (anonymous@undisclosed.example.com) — 2020-10-07T21:26:32+0800

2020牛客国庆集训派对 Day 1 比赛链接 I、Saba1000kg 题意给定一张图，$q$ 个询问，每次询问只考虑图中 $s_i$ 个点构成的连通块数。数据保证 $\sum s_i\le 10^5$。题解考虑分块。当 $s_i\lt k$ 时暴力 $O(s_i^2)$ 枚举所有点对同时维护并查集。 $s_i\ge k$$O(m)$$\sum s_i$$O(\max(\cfrac {s_i^2}{s_i}(s_i\lt k),\cfrac m{s_i}(s_i\ge k))\log s_i)=O(\max (k,\cfrac mk)\log k)$$k=O(\sqrt m)$$O(\sum s_i\sqrt m\log m)$$A$$\text{dp}(i,j)$$a_j$$a_i$$i$$k\lt i\lt j$$a_k+a_j=a_i$$\text{dp}(i,j)=\text{dp}(k,i)+1$$O(n^2)$$c$$c$$1$$\text{dfs}$$c$$\text{dfs}$$\text{dfs}$$2$$\text{set}$$O((n+q)\…

2020-2021:teams:legal_string:jxm2001:contest:2020_icpc_南京

Anonymous (anonymous@undisclosed.example.com) — 2021-01-14T20:32:25+0800

2020ICPC·南京站比赛链接 M.Monster Hunter 链接题意给定以 $1$ 为根的 $n$ 阶的点权树，假定可以用无费用无限制删去其中 $k$ 个结点，问删除剩余结点的最小费用。其中，对剩余的所有结点，删除它之前需要删除它的父结点，同时删除它的费用为它的点权 $+$$k=0,1\cdots n$$dp(u,k,0/1)$$u$$k$$dp(u,k,0)$$u$$dp(u,k,1)$$u$$$ dp(u,i+j,0)=\min(dp(u,i+j,0),dp(u,i,0)+\min(dp(v,j,0),dp(v,j,1))) $$$$ dp(u,i+j,1)=\min(dp(u,i+j,0),dp(u,i,1)+\min(dp(v,j,0),dp(v,j,1)+w_v)) $$$\text{LCA}$$O(n^2)$$n$$q$$1$$\max$$2$$[l,r]$$x$$2$$S$$a_i-(S\oplus a_i)$$0$$a_i-(S\oplus a_i)\gt 0$$S=0$$a_i$$S$$1$$a_i\gt (S\oplus a_i)$$a_…

2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4

Anonymous (anonymous@undisclosed.example.com) — 2021-04-30T18:55:33+0800

2020-2021 ACM-ICPC, Asia Seoul Regional Contest 比赛链接 I. Stock Analysis 题意给定一个长度为 $n$ 的序列，接下来 $m$ 个询问，每次询问区间 $[L,R]$ 中的所有连续子串中和不超过 $V$ 的最大值。题解离线询问，将询问的 $V$$O(n^2)$$O\left(n^2\log^2 n+m\log^2 n\right)$$O(\log n)$$O(\log^2 n)$$O(\log^2 n)$$O\left(n^2\log^2 n+m\log^3 n\right)$$O\left(n^2\log^2 n+m\log^4 n\right)$$n$$h$$\max((h_l+h_r)(r-l))$$O(n\log n)$

2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training5

Anonymous (anonymous@undisclosed.example.com) — 2021-05-19T22:47:09+0800

2017-2018 ACM-ICPC Northern Eurasia Contest (NEERC 17) 比赛链接 A. Archery Tournament 题意按时间顺序给定 $n$ 个操作。 * 操作 $1$ 表示在坐标 $(x,y)$ 上放置一个半径为 $y$ 的靶子。 * 操作 $2$ 表示在对坐标 $(x,y)$ 进行一次射击，如果命中某个靶子(命中边界不算命中)，则将这个靶子移去。$(x,y)$$x=x_i$$x=x_i$$\log v$$x$$O(n\log^2 v)$$1$$n$$k$$k$$c_1,c_2\cdots c_k,c_{k+1}\cdots c_t$$f(x)=kx+\sum_{i=1}^t \max(c_i-x,0)$$x\in [c_{k+1},c_k]$$k$$c_k$$w\to w-c_k$$k$$c_k=0$$O(m^2\log m)$…

2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training6

Anonymous (anonymous@undisclosed.example.com) — 2021-05-24T20:16:40+0800

2020-2021 ICPC Northwestern European Regional Programming Contest (NWERC 2020) 比赛链接 G. Great Expectations 题意有人尝试游戏速通，速通路径理想耗时 $m$，世界记录耗时 $n$。$(m\lt n)$ 速通路线上有 $k$ 个难点，从起点达到第 $i$ 个难点需要花费 $t_i$$p_i$$d_i$$\frac 1{50000}$$\text{dp}(p,t)$$p$$t$$$ \text{dp}(p,t) = t_{i+1}-t_i+p_{i+1}\ast \text{dp}(p+1,t)+(1-p_{i+1})\begin{cases} \text{dp}(0,n-m-1), & t\lt d_{i+1} \\ \min(\text{dp}(p+1,t-d_{i+1})+d_{i+1},\text{dp}(0,n-m-1)), & t\ge d_{i+1} \end{cases} $$$\text{dp}(0,n-m-1)$$\text{dp}$$\text{dp}(0…

2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training7

Anonymous (anonymous@undisclosed.example.com) — 2021-06-02T09:59:31+0800

2018-2019 ICPC Southwestern European Regional Programming Contest (SWERC 2018) 比赛链接 G. Strings 题意给定初始字符串 $S_0$，接下来 $n$ 条递推式。类型 $1$：$S_i=S_j[l,r]$。类型 $2$：$S_i=S_jS_k$。求 $S_n$ 的所有字符的 $\text{Ascii}$ 码之和，保证所有字符串长度不超过 $2^{63}-1$$\text{dp}(k,l,r)$$S_k[l,r]$$\text{Ascii}$$[1,R],[L,R],[L,|S(k)|]$$[L,R]$$[L(k),R],[L,R(k)]$$L(k),R(k)$$4$$O(n)$$O(n)$$O(n^2)$$O(n)$$O(n^2)$

2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training9

Anonymous (anonymous@undisclosed.example.com) — 2021-06-20T21:37:12+0800

2019 Multi-University Training Contest 2 比赛链接 B. Beauty Of Unimodal Sequence 题意给定一个序列，求最长的单峰序列中字典序最小和最大的序列。其中单峰序列定义为序列 $p_1,p_2\cdots p_t$ 满足约束 $p_1\lt p_2\lt \cdots p_t$ 且 $a_{p_1}\lt a_{p_2}\lt\cdots\lt a_{p_k}\gt \cdots \gt a_{p_t}$。题解首先不难求出 $f(0,i)$$a_i$$f(1,i)$$a_i$$g(i)$$a_i$$$ g(i)=\max\left(f(1,i),\max_{j\gt i,a_j\gt a_i}g(i)+1\right) $$$g(i)$$\max(g(i)+f(0,i)-1)$$f(1,i),g(i)$$O(n)$$O(1)$$O(n\log n)$…

2020-2021:teams:legal_string:jxm2001:contest:agc_054

Anonymous (anonymous@undisclosed.example.com) — 2021-06-28T10:33:32+0800

AtCoder Grand Contest 054 比赛链接 B - Greedy Division 题意给出 $n$ 个物品，第 $i$ 个物品权重为 $w_i$。现有甲乙两人，要求将物品重新排列后依次分配每个物品。分配物品满足如下规则：如果甲当前所得的物品权重和不大于乙，则将物品分给甲，否则分给乙。$x_1,x_2\cdots x_k$$y_1,y_2\cdots y_{n-k}$$x,y$$x_1,x_2\cdots x_k$$\frac {\sum w_i}2$$g_k$$\sum_{k=1}^nk!(n-k)!g_k$$\text{dp}(i,j,k)$$i$$j$$k$$O(n^2\sum w_i)$$1\sim n$$P$$i$$k$$j\lt i$$P_j'\gt P_i'$$P'$$P$$f_i=\sum_{j=1}^{i-1}[P_j\gt P_i]$$f_i$$\sum_{i=1}^n \max(f_i-k,0)$$i$$f_i\gt k$$P_{i-1}\gt P_i$$f_{i-1}=f_i\gt k$$i$$P_{i-1},P_i$$f_i$$…

2020-2021:teams:legal_string:jxm2001:contest:arc_106

Anonymous (anonymous@undisclosed.example.com) — 2021-02-15T17:06:19+0800

Atcoder Rugular Contest 106 比赛链接 E - Medals 题意给定 $n$ 个员工，每个员工第 $[2k*a_i+1,(2k+1)*a_i]$ 天上班，第 $[(2k+1)*a_i+1,(2k+2)*a_i]$ 天休息。每天最多可以给一名当天上班的员工一个奖章，问最少需要多少天才能使每个员工至少有 $k$ 个奖章。$n*k$$\text{Hall}$$U$$T(S)$$S$$S\subset U$$|S|\le |T(S)|$$T(S)$$S$$T(S)$$|S|$$T(S)$$T(S)$$-$$U-S$$nk$$2nk$$nk$$|T(S)|\ge |S|$$2nk$$O((n2^n+nk)\log nk)$$n$$a_i$$d_i$$a_i^{\underline{d_i}}$$\text{prufer}$$$ \sum_{\sum d_i=2n-2}\binom{n-2}{d_1-1,d_2-1\cdots d_n-1}\prod_{i=1}^n a_i^{\underline{d_i}}= \sum_{\sum d_i=2n-2}\f…

2020-2021:teams:legal_string:jxm2001:contest:arc_107

Anonymous (anonymous@undisclosed.example.com) — 2021-02-17T15:08:29+0800

Atcoder Rugular Contest 107 比赛链接 D - Number of Multisets 题意给定 $N,K$。要求将 $K$ 分解为 $N$ 个数，每个数均为 $1,\frac 12,\frac 14\cdots \frac 1{2^i}\cdots$询问分解方案数。题解设 $\text{dp}(i,j)$ 表示需要将当前值分解为 $i$ 个数，且如果使用当前可以用的最大的数分解需要 $j$$\text{dp}(i,j)\gets \text{dp}(i-1,j-1)$$\text{dp}(i,j)\gets \text{dp}(i,j<<1)$$O(nk)$$n$$m$$a_i,b_i$$a_i$$b_i$$-$$\sum b_i$$\sum -b_i$$-a_i,-b_i,b_i$$u,v$$-b_u,b_v$$b_u,-b_v$$i$$x_i$$y_i$$s\to x_i$$-b_i$$x_i\to y_i$$a_i$$y_i\to t$$b_i$$u,v$$y_v\to x_u$$y_u\to x_v$$\infty$$s\to x_…

2020-2021:teams:legal_string:jxm2001:contest:arc_112

Anonymous (anonymous@undisclosed.example.com) — 2021-02-28T10:30:16+0800

Atcoder Rugular Contest 112 比赛链接 E - Cigar Box 题意给定初始序列 $(1,2\cdots n)$，每次操作可以任选一个数将其移动到序列最左边或最右边。问恰好 $m$ 次操作将序列变成 $(a_1,a_2\cdots a_n)$ 的方案数。题解首先最后一次操作一定是将 $a_1$$a_n$$c_1(c_1\ge 0)$$a_n$$a_n$$c_1$$2^{c_1}$$(1,2\cdots n)$$a_n$$m-c_1-1$$(a_1,a_2\cdots a_{n-1})$$c_2(c_2\ge 0)$$a_{n-1}$$a_{n}$$a_{n-1}$$c_2$$4^{c_2}$$a_1,a_2\cdots a_l$$a_{n-r+1},a_{n-r+2}\cdots a_n$$\prod_{i=1}^{l+r}(2i)^{c_i}$$\sum_{i=1}^{l+r} c_i=m-l-r$${l+r\choose l}$$(1,2\cdots n)$$a_1,a_2\cdots a_l$$a_{n-r+1},a_{n-r+…

2020-2021:teams:legal_string:jxm2001:contest:arc_113

Anonymous (anonymous@undisclosed.example.com) — 2021-02-24T10:36:37+0800

Atcoder Rugular Contest 113 比赛链接 F - Social Distance 题意给定 $n+1$ 个数 $X_0,X_1\cdots X_n(X_0=0)$，$y_i\in [X_{i-1},X_i]$ 且 $y_i$ 取值随机，求 $$ E\left(\min_{2\le i\le n}(y_i-y_{i-1})\right)\bmod 998244353 $$ 题解设 $F(x)=P\{\min_{2\le i\le n}(y_i-y_{i-1})\gt x\}$，于是有 $$ E\left(\min_{2\le i\le n}(y_i-y_{i-1})\right)=\int-xF'(x)\mathrm{d}x $$ 问题转化为求 $F(x)$ 的表达式。不妨先考虑固定 $x$，计算 $F(x)$ 的值。记 $z_i=y_i-(i-1)x$，于是 $\min_{2\le i\le n}(y_i-y_{i-1})\gt x$ 等价于 $z_1\lt z_2\cdots \lt z_n,z_i\in [X_{i-1}-(i-1)…

2020-2021:teams:legal_string:jxm2001:contest:arc_115

Anonymous (anonymous@undisclosed.example.com) — 2021-05-02T21:36:03+0800

Atcoder Rugular Contest 115 比赛链接 D - Odd Degree 题意给定一个图，询问满足度数为奇数的点的个数恰好为 $k(1\sim n)$ 的生成图数量。其中生成图的定义为原图的点集 $+$ 原图的边集的子集。题解首先考虑图是树的情况，有结论：如果 $k$$k$${n\choose k}$$n\ge 1$$k(2\mid k)$$n=1$$k=0$$n+1$$k(2\mid k)$$1$$k'=k$$k'=k-2$$k'=k$$n$$k’$$n$$m$$k$$k$$2^{m-n+1}$$k'$$2^{m-n+1}{n\choose k}$$\text{NTT}$$O(n\log^2 n)$$A$$X$$1\le X_i\le A_i$$X_i \neq X_{i+1}$$\text{dp}(i,j)$$X_i=j$$X_{1\sim i}$$S_i=\sum_{j=1}^{A_i}\text{dp}(i,j)$$j\le \min(A_i,A_{i+1})$$\text{dp}(i+1,j)=S_i-\text{dp}(i,j)$…

2020-2021:teams:legal_string:jxm2001:contest:arc_121

Anonymous (anonymous@undisclosed.example.com) — 2021-07-01T21:08:26+0800

Atcoder Rugular Contest 121 比赛链接 D - 1 or 2 题意给定 $n$ 个数，要求将它们分组。每组可以有 $1\sim 2$ 个数，每组的权重为这组里面的所有数的和。要求最小化权重最大的组和权重最小的组的权重差。题解 $(a_1,a_2),(a_3,a_4)$$a_1$$a_2$$a_4$$(a_1,a_4),(a_2,a_3)$$\max(a_1+a_4,a_2+a_3)\le a_3+a_4,\min(a_1+a_4,a_2+a_3)\ge a_1+a_2$$a_1\le a_2\le \cdots a_{2k}$$(a_1,a_{2k}),(a_2,a_{2k-1})\cdots (a_{k},a_{k+1})$$0$$0\sim n$$0$$O(n^2)$$n$$1\sim n$$P$$p_i$$i$$\text{dp}(u,i)$$u$$i$$p_i$$u$$\text{dp}$$u$$p_i$$u$$u$$$ \text{dp}(u,i)\gets (\text{sz}(u)-i)\text{dp}(u,i-1) $$$…

2020-2021:teams:legal_string:jxm2001:contest:arc_122

Anonymous (anonymous@undisclosed.example.com) — 2021-07-02T17:29:09+0800

Atcoder Rugular Contest 122 比赛链接 C - Calculator 题意给定 $x,y$，初值均为 $0$，接下来给定 $4$ 种操作： * $x\gets x+1$ * $y\gets y+1$ * $x\gets x+y$ * $y\gets x+y$ 要求在 $130$ 步操作内将 $x$ 变为 $N(N\le 10^{18})$。赛时解法不妨先规定一个 $y$ 的最终值，然后利用操作 $3,4$ 对 $x,y$ 进行更相减损术，当 $x,y$$0$$1,2$$\text{gcd}(x,y)$$N$$N$$y$$\frac {2N}{\sqrt 5+1}$$\frac {2N}{\sqrt 5+1}-20\le y\le \frac {2N}{\sqrt 5+1}+20$$4,3,4,3,4,3\cdots $$S$$3$$1,2$$F(0)=F(1)=1,F(n)=F(n-1)+F(n-2)$$3$$1$$4$$2$$i(0\le i\le S)$$x$$F(S-i)$$N$$S=\max\{F(S)\le 10…

2020-2021:teams:legal_string:jxm2001:contest:arc_123

Anonymous (anonymous@undisclosed.example.com) — 2021-07-21T16:09:52+0800

Atcoder Rugular Contest 123 比赛链接 E - Training 题意给定 $F(x)=\lfloor a_1+\cfrac x{b_1}\rfloor,G(x)=\lfloor a_2+\cfrac x{b_2}\rfloor$，问 $1\sim n$ 中有多少整数 $x$ 满足 $F(x)=G(x)$。题解设 $f(x)=a_1+\cfrac x{b_1},g(x)=a_2+\cfrac x{b_2}$，则有四种情况： * $f(x)\in (-\inf,g(x)-1)$，此时 $F(x)\neq G(x)$ * $f(x)\in [g(x)-1,g(x))$，此时 $F(x)=G(x)$ 或 $F(x)=G(x)-1$ * $f(x)\in [g(x),g(x)+1)$，此时 $F(x)=G(x)$ 或 $F(x)=G(x)+1$ * $f(x)\in [g(x)+1,\inf)$，此时 $F(x)\neq G(x)$ 显然只有第 $2,3$ 中情况对答案产生贡献。不妨只考虑第 $2$$3$$x$$2$$[L,R]$…

2020-2021:teams:legal_string:jxm2001:contest:arc_124

Anonymous (anonymous@undisclosed.example.com) — 2021-09-03T19:35:05+0800

Atcoder Rugular Contest 124 比赛链接 D - Yet Another Sorting Problem 题意给定一个 $n+m$ 的排列，每次可以选取一个位置位于 $1\sim n$ 的元素和一个位置位于 $n+1\sim n+m$ 的元素交换位置。问使得排列有序的最小操作次数。题解将排列分解成若干置换环，则对于每个交换操作，等价于选取 $1\le i\le n,n+1\le j\le n+m$$i\to p_i,j\to p_j$$i\to p_j,j\to p_i$$i,j$$n$$m$$A_i$$i$$2$$B_i$$i$$2$$C_i$$i$$f(i)=n+m-C_i+2\max(A_i,B_i)$$|C_{i+1}-C_i|=1,|A_{i+1}-A_i|\le 1,|B_{i+1}-B_i|\le 1$$(C_{i+1}-C_i)(A_{i+1}-A_i)\ge 0,(C_{i+1}-C_i)(B_{i+1}-B_i)\ge 0$$f(i+1)\ge f(i)+1$$A_z=B_z=0,C_z=n+m$$f(Z)=0$$f(0…

2020-2021:teams:legal_string:jxm2001:contest:arc_125

Anonymous (anonymous@undisclosed.example.com) — 2021-08-23T21:09:13+0800

Atcoder Rugular Contest 125 比赛链接 D - Unique Subsequence 题意给定一个长度为 $n$ 的序列 $A$，求该序列含有的独特的子序列个数(不包括空序列)。其中，定义独特的子序列为序列 $A$ 的所有子序列构成的可重集中出现次数等于 $1$$\text{dp}(i)$$i$$1\sim n$$\text{dp}(i)$$i$$j$$j\lt i\And a_i=a_j$$j$$a_i$$a_j,a_i$$\in [j,i)$$a_i$$a_i$$\text{dp}(i)=\sum_{k=j}^{i-1} \text{dp}(k)$$a_i$$a_i$$(j\lt i\And a_i=a_j)\to (\text{dp}(j)=0)$$O\left(n\log n\right)$$\text{dp}$$n$$i$$a_i$$m$$i$$c_i$$b_i$$m$$i$$L_i$$j$$R_j$$S\to L_i$$a_i$$L_i\to R_j$$b_j$$R_i\to T$$c_i$$k$$S\to L_i$$R_i$$\mi…

2020-2021:teams:legal_string:jxm2001:contest:arc_126

Anonymous (anonymous@undisclosed.example.com) — 2021-10-09T22:03:58+0800

Atcoder Rugular Contest 126 比赛链接 D - Pure Straight 题意给定长度为 $n$ 的序列，交换任意两个相邻元素的费用为 $1$。每个元素的取值范围为 $[1\sim k]$，问使得序列的一个连续子序列恰好为 $1,2\cdots k$ 的最小费用。题解首先假设固定所选元素的初始下标为 $p_1\lt p_2\lt \cdots \lt p_k$$k$$[x,x+k-1]$$i$$b_i$$c_i=x+i-1$$\sum_{i=1}^k |p_i-c_i|+\text{inv}(b_1,b_2\cdots,b_k)$$\text{inv}B$$B$$\sum_{i=1}^k |p_i-c_i|+\text{inv}(b_1,b_2\cdots,b_k)$$f(P)=\sum_{i=1}^k |p_i-c_i|+\text{inv}(b_1,b_2\cdots,b_k)$$P$$p_1\lt p_2\lt \cdots \lt p_k$$P$$\text{inv}B$$1$$\sum_{i=1}^k |p_i-c_i|$$1…

2020-2021:teams:legal_string:jxm2001:contest:arc_127

Anonymous (anonymous@undisclosed.example.com) — 2021-09-27T16:52:49+0800

Atcoder Rugular Contest 127 比赛链接 D - Sum of Min of Xor 题意给定序列 $A,B$，求 $\sum_{1\le i\lt j\le n}\min(a_i\oplus a_j,b_i\oplus b_j)$。题解从高到低考虑每个位，当 $a_i\oplus a_j$ 和 $b_i\oplus b_j$ 第一个位出现不同时已经可以判断 $a_i\oplus a_j$ 和 $b_i\oplus b_j$ 的大小关系。注意到这也等价于 $a_i\oplus b_i$ 和 $a_j\oplus b_j$ 的第一个位出现不同。$k$$i$$S,T$$S$$i$$a_i\oplus b_i$$k$$0$$T$$i$$a_i\oplus b_i$$k$$1$$\{i,j\}\subseteq S$$\{i,j\}\subseteq T$$(i,j)$$i\in S,j\in T$$(i,j)$$a_i$$k$$0$$S$$S_0,S_1$$T$$T_0,T_1$$i\in S_0,j\in T_0$$\min(a_i\oplus…

2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-20T21:11:52+0800

CCPC Wannafly Camp Day1 比赛链接 A. 期望逆序对题意给定 $n$ 个随机变量，第 $i$ 个变量的取值为 $[l_i,r_i]$ 中的随机一个数。要求将 $n$ 个随机变量重新排列，使得最终的逆序对的期望值最小。询问该方案下逆序对的期望值。$p_1p_2\cdots p_n$$p_i$$p_{i+1}$$p_i$$p_{i+1}$$\frac 12$$l_i+r_i\le l_{i+1}r_{i+1}$$i\lt j$$\sum_{k=l_i}^{r_i}\max(0,\min(k-l_j,r_j-l_j+1))$$O(1)$$O(n^2)$$u,v$$\text{dis}(u,p)\text{dis}(v,p)(p=\text{LCP}(u,v))$$m$$\text{dis}(u,v)=L$$u\to p$$i$$(d_u-d_i)(L-d_u+d_i)$$u\to p(\text{不含} p)$$2(d_u-d_i)+1-L$$v\to p(\text{不含} p)$$0$$u\to p(\text{不含} p)$$p$$2(d_u-d_…

2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day2

Anonymous (anonymous@undisclosed.example.com) — 2021-05-01T20:55:27+0800

CCPC Wannafly Camp Day2 比赛链接 B. 萨博的方程式题意给定方程 $x_1\oplus x_2\oplus \cdots x_n =k$。其中限定 $x_i\le m_i$，问方程的解的个数。题解不妨设 $m=\max(m_1,m_2\cdots m_n)$，且 $m$ 的最高位是第 $y$ 位。假设 $\text{dp}(i,j)$ 表示前 $i$ 个数有 $j$ 个数第 $y$ 位为 $1$ 时 $(x_1,x_2\cdots x_i)$ 的取值方案数。$m_i$$y$$1$$x_i$$y$$0$$1$$$ \text{dp}(i,j)\gets 2^y\text{dp}(i-1,j)+(m_i\bmod 2^y)\text{dp}(i-1,j) $$$m_i$$y$$0$$$ \text{dp}(i,j)\gets (m_i\bmod 2^y)\text{dp}(i-1,j) $$$m_i$$\text{cnt}$$y$$1$$\text{dp}(n,i)(0\le i\le \text{cnt})$$k$$y$$0$$i$$…

2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day3

Anonymous (anonymous@undisclosed.example.com) — 2021-05-02T15:52:03+0800

CCPC Wannafly Camp Day3 比赛链接 C. 无向图定向题意给定无向图，要求对每条边定向，得到 $\text{DAG}$，同时最小化最长路。题解 1 易知可以当拓扑序确定时每条边方向是确定的，考虑枚举所有拓扑序的全排列然后计算最长路。$\text{TLE}$$-1$$O(n2^n)$$O(3^n)$$k$$i(1\le i\le n)$$i$$-$$i$$\text{dp}$$O(n)$$n$$a_i$$$ g(l,r)=\max_{i,j\in [1,l)\cup (r,n],i\le j}\text{gcd}(i,j) $$$(i,j)$$g(l,r)=0$$\sum_{i=1}^n\sum_{j=i}^ng(i,j)$$$ \sum_{i=1}^n\sum_{j=i}^ng(i,j)=\sum_{k=1}^\text{V}k\sum_{i=1}^n\sum_{j=i}^n[g(i,j)==k]=\sum_{k=1}^\text{V}k\sum_{i=1}^n\sum_{j=i}^n([g(i,j)\ge k+1]-[g(i,j)\ge k]) …

2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day5

Anonymous (anonymous@undisclosed.example.com) — 2021-05-27T16:07:44+0800

CCPC Wannafly Camp Day5 比赛链接 B. Bitset Master 题意给定 $n$ 阶树和 $m$ 个操作。每个点 $u$ 维护一个集合 $S(u)$，初始时 $S(u)=\{u\}$。每次操作选定一条树边 $u\to v$，令 $S(u)=S(v)=\text{\old}(S(u)\cup S(v))$。对每个 $u$，输出有多少个 $v$ 满足 $u\in S(v)$。题解设 $m$ 次操作选择的边为 $e_1,e_2\cdots e_m$$u\in S(v)$$\{e\}$$e_{p_1},e_{p_2}\cdots e_{p_k}$$u,v$$e_{p_k},e_{p_{k-1}}\cdots e_{p_1}$$v\in S(u)$$\sum_{v=1}^n [u\in S(v)]=$$\sum_{v=1}^n [v\in S(u)]=$$|S(u)|$$|S(u)|$$|S(u)\cup S(v)|=|S(u)|+|S(v)|-|S(u)\cap S(V)|$$t\in S(u)\cap S(v)$$e_{p_1},e_{p…

2020-2021:teams:legal_string:jxm2001:contest:cf_654_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-01T10:15:56+0800

Codeforces Round #654 (Div. 2) 比赛链接 E2. Asterism (Hard Version) 题意给定 $n$ 个正整数，代表 $n$ 个敌人，每个敌人有 $a_i$ 颗糖，再给定一个素数 $p(p \le n)$。定义游戏规则为一开始玩家拥有若干颗糖，每次玩家可以选取一个未挑战且手上糖果数不大于玩家的敌人，打败他获得一颗糖果。$f(x)$$x$$p\nmid f(x)$$x$$b_i$$i$$C_i(x)=b_{x+i}-i$$f(x)=\prod_{i=0}^{n-1} C_i(x)$$C_{n-1}(x)\le 1$$C_i(x)-C_{i-1}(x)=b_{x+i}-1\ge -1$$p\nmid f(x)\iff \forall i(0\le i\lt n \longrightarrow C_i\lt p)$$C_i(x)\le C_i(x+1)$$x$$A=\max a_i$$x\le A-n$$f(x)= 0$$p\mid f(x)$$x\ge A$$f(x)= n!$$p\mid f(x)$$A-n+1$$A$$i=0\s…

2020-2021:teams:legal_string:jxm2001:contest:cf_662_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-14T16:47:21+0800

Codeforces Round #662 (Div. 2) 比赛链接 D. Rarity and New Dress 题意给定一个 $n\times m$ 的网格，每个网格中有一个字母，问有多少个由同一字母构成的菱形。下面给出边长为 $1,2,3$ 的菱形示例。 a a aaa a aaa aaaaa a aaa a $\text{dp}$$\text{dp}$

2020-2021:teams:legal_string:jxm2001:contest:cf_664_div._2

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

Codeforces Round #664 (Div. 2) 比赛链接 E. Boboniu Walks on Graph 题意给定一个 $n$ 个点 $m$ 条边的有向图，每个点出度 $\in [1,k]$，每条边的权为 $1\sim m$ 且各不相同。要求输出满足下列条件的 $k$ 元组 $(c_1,c_2\cdots c_k)$ 的数目： * $1\le c_i\le i$ * 如果一个点的出度为 $i$$c_i$$k$$(c_1,c_2\cdots c_k)$$f(u)$$u$$(c_1,c_2\cdots c_k)$$f$$1\sim n$$i$$j$$S_{i,j}$$f$$1\sim n$$\bigcup_{i=1}^k S_{i,c_i}=\{1,2\cdots n\}$$S_{i,j}$$O(k)$$\bigcup_{i=1}^k S_{i,c_i}$$O(n+m+k!)$…

2020-2021:teams:legal_string:jxm2001:contest:cf_665_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-23T11:58:26+0800

Codeforces Round #665 (Div. 2) 比赛链接 E. Divide Square 题意给定一个 $10^6\times 10^6$ 的正方形，接下来给定 $n$ 条平行于 $\text{X}$ 轴的线段和 $m$ 条平行于 $\text{Y}$ 轴的线段。问正方形被线段划分为多少区域。数据保证所有线段不共线且至少与正方形边界交于一个点。$1+$$+$$2^n$$\{a\}$$q$$a_x$$k$$[(i-1)2^k+1,i2^k]$$[(2i-2)2^k+1,(2i-1)2^k]$$[(2i-1)2^k+1,(2i)2^k]$$[l,r]$$\{a\}$$2$$a_x$$a_{x\oplus (2^k-1)}$$3$$a_x$$a_{x\oplus 2^k}$$2$$3$$\text{val}$$1$$a_{x\oplus \text{val}}$$4$$[M2^k,M2^k+2^k-1]$$[0,2^k-1]$$\text{val}\And (2^k-1)$$[0,2^k-1]$$[M2^k,M2^k+2^k-1]$$\text{val}$$[M…

2020-2021:teams:legal_string:jxm2001:contest:cf_666_div._1

Anonymous (anonymous@undisclosed.example.com) — 2020-09-04T15:34:29+0800

Codeforces Round #666 (Div. 1) 比赛链接 B. Stoned Game 题意给定 $n$ 堆石头和两个玩家 $A,B$，$A$ 先手。每次轮到某个玩家时，该玩家需要选择一个非空且上一轮没有被另一个玩家拿过的堆，拿走一个石头。如果该玩家无法操作，则该玩家败北。问谁有必胜策略。$v$$s$$v\gt \frac n2$$A$$s$$s=2k$$3$$3,3,4$$1,1,1,2,2,2,3,3,3,3$$i$$i+n$$A$$B$$B$$s$$s=2k+1$$v\le \lfloor \frac n2\rfloor=k$$A$$s=2k$$v\le \frac n2$$s$$A$$A$$n$$a_i$$1$$\text{Hp}$$2$$\text{Hp}$$\text{boos}$$3$$r_1$$1$$\text{boos}$$r_2$$1$$\text{AWP}$$r_3$$2$$\text{boos}$$\text{boos}$$\text{boos}$$d$$\text{boos}$$r_1\le r_2\le r_3$$i$$i-1…

2020-2021:teams:legal_string:jxm2001:contest:cf_698_div._1

Anonymous (anonymous@undisclosed.example.com) — 2021-01-30T21:25:47+0800

Codeforces Round #698 (Div. 1) 比赛链接 A. Nezzar and Board 题意给定 $n$ 个不同的 $x_i$，每次可以选取一对 $x,y$，得到 $2x-y$。(注意该操作不会删去原有的 $x,y$) 问是否能经过有限次操作得到 $k$。题解不妨设 $b=\min(x_i)$，记 $a_i=x_i-b,k'=k-b$，于是有 $2x_i-x_j=2a_i-2b-a_j+b=(2a_i-a_j)-b$。$a_i$$x_i$$k'$$k$$b$$0,a_2,a_3\cdots a_n$$0,a$$2a-0=2a,2*(2a)-a=3a,2*(3a)-(2a)=4a$$a$$n=t$$g_t$$k$$g_t=\text{gcd}(a_2,a_3\cdots a_t)\mid k$$n=2$$0,a$$n=t+1$$x,y$$$ x*g_t-y*a_{t+1}=\text{gcd}(g_t,a_{t+1})=g_{t+1} $$$g_t$$x=2x'$$x'*g_t$$y*a_{t+1}$$g_{t+1}=2x'g_t-y*a_{t…

2020-2021:teams:legal_string:jxm2001:contest:cf_699_div._2

Anonymous (anonymous@undisclosed.example.com) — 2021-02-12T15:42:05+0800

Codeforces Round #699 (Div. 2) 比赛链接 E. Sorting Books 题意给定一个长度为 $n$ 的序列 $\{a\}$，每次操作可以任取一个位置并将该位置的数移到序列末尾。问最少需要多少次操作才能使序列中所有大小相同的数相邻。$\text{dp}(i)$$[i,n]$$v$$l_v$$r_v$$[i,n]$$c_v$$i$$i=l_{a_i}$$[i,r_{a_i}]$$a_i$$\text{dp}(i)\gets c_{a_i}+\text{dp}(r_{a_i}+1)$$i\neq l_{a_i}$$l_{a_i}$$l_{a_i}$$n$$l_{a_i}$$i$$[i,n]$$a_i$$\text{dp}(i)\gets c_{a_i}$$l_{a_i}$$\text{dp}(l_{a_i})$$i$$\text{dp}(i)\gets \text{dp}(i+1)$$n-\text{dp}(1)$$O(n)$$1$$x$$a$$n-x$$b$$d$$0$$d+1$$1\sim d+1$$d+1$$i$$c_i$$c_0,c_1…

2020-2021:teams:legal_string:jxm2001:contest:cf_700_div._1

Anonymous (anonymous@undisclosed.example.com) — 2021-02-10T11:29:31+0800

Codeforces Round #700 (Div. 1) 比赛链接 A. Searching Local Minimum 题意给定一个 $1\sim n$ 的排列，最多允许 $100$ 次询问，每次可以询问指定位置的值。要求找到一个 $i$ 满足 $a_i\lt a_{i-1}$ 且 $a_i\lt a_{i+1}$，假定 $a_0=a_{n+1}=\infty$。题解维护区间 $[l,r]$，满足 $a_l\lt a_{l-1},a_r\lt a_{r+1}$。于是当 $l=r$$a_m\lt a_{m+1}$$r$$m$$l$$m$$\log n$$ps.$$95\text{%}$$[L,R]$$32$$1$$[L,R]$$[L,R]$$[0,R-L]$$[0,2^k-1]$$m$$u_i\to v_i$$\in [l_i,r_i]$$+\text{bitset}$$\text{bitset._Find_next}(l_i-1)$$l_i$$r_i$$O\left(n\sqrt m+\frac {nm}w\right)$$(\text{bitset}>>l…

2020-2021:teams:legal_string:jxm2001:contest:cf_704_div._2

Anonymous (anonymous@undisclosed.example.com) — 2021-02-24T16:17:48+0800

Codeforces Round #704 (Div. 2) 比赛链接 E. Almost Fault-Tolerant Database 题意给定 $n$ 个长度为 $m$ 的数组 $\{a_i\}$。要求找到一个长度为 $m$ 的数组 $b$，使得 $b$ 与每个 $\{a_i\}$ 不同的位置数不超过 $2$。题解首先如果所有 $\{a_i\}$ 与 $\{a_1\}$ 不同的位置数都不超过 $2$$\{a_1\}$$\{a_j\}$$\{a_1\}$$4$$\{a_j\}$$\{a_1\}$$4$$\{a_j\}$$\{a_1\}$$3$$\{a_i\}$$2$$\{a_k\}$$2$$\{a_k\}$$O(nm)$

2020-2021:teams:legal_string:jxm2001:contest:cf_705_div._2

Anonymous (anonymous@undisclosed.example.com) — 2021-03-24T20:37:35+0800

Codeforces Round #705 (Div. 2) 比赛链接 E. Enormous XOR 题意定义 $F(l,r)$ 表示 $l\oplus l+1\oplus\cdots \oplus r$，求 $\max_{L\le l\le r\le R}F(l,r)$。题解设 $R$ 的长度为 $n$，从低位到高位依次编号 $0,1,2\cdots n-1$。若 $L$ 的第 $n-1$ 位为 $0$，取 $l=2^{n-1}-1,r=2^{n-1}$，得 $F(l,r)=2^n-1$。若 $L$ 的第 $n-1$ 位为 $1$，下面证明若 $R$ 为偶数且 $R-L\ge 2$ 时答案为 $R+1$$R$$R-L\gt 2$$R$$R$$L$$[L,L]$$L$$[L,L+1]$$L+1$$L,L+1$$[L,R]$$R'$$[L,R+2]$$r\le R$$F(l,r)\le R$$F(l,R+1)$$F(l,R+1)\gt R+2$$F(l,R+1)$$R+2$$k$$F(l,R+1)$$k$$1$$R+2$$k$$0$$R+2$$k\gt 0$$[l…

2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1

Anonymous (anonymous@undisclosed.example.com) — 2021-03-29T10:28:09+0800

Codeforces Round #706 (Div. 1) 比赛链接 C. Garden of the Sun 题意给定一些黑格和一些白格，要求将一些白格转化为黑格，使得所有黑格连通但不出现环路。题目保证以起始时以每个黑格为中心的 $3\times 3$ 范围内没有其他黑格。$n\equiv 1\bmod 3$$1,4,7\cdots$$3k+2,3k+3$$3k+2,3k+3$$n\not\equiv 1\bmod 3$$1,4,7\cdots$$2,5,8\cdots$$x$$\text{BFS}$$x$$x$$f(x,y)$$x$$\text{BFS}$$y$$\text{BFS}$$x,y$$f(x,y)=0$$x,y$$u$$\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$$\text{dis}(x,y)+1$$x,y$$\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$$\text{dis}(x,y)+1$$x,y$$x,y$$u\to v$$\text{dis}(…

2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1

Anonymous (anonymous@undisclosed.example.com) — 2021-07-09T20:24:47+0800

Codeforces Round #728 (Div. 1) 比赛链接 B. Tree Array 题意给定 $n$ 个点的树，点编号分别为 $1\sim n$。初始时等概率随机选择一个点，接下来每次操作从未选择的且与已经选择的点相连的点中等概率随机选择一个点。$(u,v)$$p=\text{LCA}(u,v)$$u\gt v,d_1=d_u-d_p,d_2=d_v-d_p$$(u,v)$$d_1,d_2$$t$$1-2t$$d_2$$\text{dp}(d_1,d_2)=\cfrac {\text{dp}(d_1-1,d_2)+\text{dp}(d_1,d_2-1)}2$$O(n^3)$$a[1\sim n],b[1\sim n-1]$$1\le i\le n-1$$a_i=\min\left(a_i,\cfrac {a_i+a_{i+1}-b_i}2\right),a_{i+1}=\max\left(a_i,\cfrac {a_i+a_{i+1}+b_i}2\right)$$a[1\sim n]$$x$$a[1\sim n]$$0\le a_i\le c_i$$a_…

2020-2021:teams:legal_string:jxm2001:contest:cf_729_div._2

Anonymous (anonymous@undisclosed.example.com) — 2021-07-09T20:46:55+0800

Codeforces Round #729 (Div. 2) 比赛链接 E. Abnormal Permutation Pairs 题意问有多少对 $1\sim n$ 的排列 $(p,q)$ 满足 $p$ 字典序小于 $q$ 逆序对个数大于 $q$，结果需要取模但不保证模是素数。题解考虑枚举 $x$ 使得 $p[1\sim x]=q[1\sim x],p[x+1]\neq q[x+1]$。记 $\text{inv}(p)$ 表示 $p$ 中的逆序对。于是此时等价于询问有多少对 $1\sim n-x$$(p,q)$$p[1]\lt q[1]$$\text{inv}(p)\gt \text{inv}(q)$$y=q[1]-p[1]$$1\sim n-x-1$$(p,q)$$\text{inv}(p)\gt \text{inv}(q)+y$$p_i$$i$$p$$0\le p_i\lt i-1$$\sum p_i\gt \sum q_i+y$$f(i,j)$$\sum_{k=1}^{i+1}p_k-q_k=j$$t=p_k-q_k$$$ f(i-1,j)\to (i+1…

2020-2021:teams:legal_string:jxm2001:contest:cf_732_div._1

Anonymous (anonymous@undisclosed.example.com) — 2021-07-12T17:12:27+0800

Codeforces Round #732 (Div. 1) 比赛链接 C. AquaMoon and Permutations 题意给定 $2n$ 个 $1\sim n$ 的排列 $p_1,p_2\cdots p_{2n}$，其中有 $p_1,p_2\cdots p_n$ 构成拉丁方。且对于 $k=1\sim n$，$p_k$ 与 $p_{k+n}$ 至少有一个元素相同，保证 $p_1,p_2\cdots p_{2n}$ 中不存在两个完全相同的排列。输入给定打乱顺序后的 $2n$$n$$n\times n$$(i,j)$$i$$j$$P$$n$$(1,P_1),(2,P_2)\cdots (n,P_n)$$n$$n$$P$$(1,P_1),(2,P_2)\cdots (n,P_n)$$n$$(1,P_1),(2,P_2)\cdots (n,P_n)$$n$$p_1,p_2\cdots p_n$$n^2$$n$$k$$n(n-k)$$2n(n-k)$$2(n-k)$$p_i$$p_{i+n}$$k$$k$$2(n-k)$$2(n-k)$$2(n-k)$$p_1,p_2…

2020-2021:teams:legal_string:jxm2001:contest:cf_740_div._1

Anonymous (anonymous@undisclosed.example.com) — 2021-08-25T17:46:23+0800

Codeforces Round #740 (Div. 1) 比赛链接 D. Top-Notch Insertions 题意定义插入排序过程：遍历 $i=2\sim n$，当且仅当 $a_i\lt a_{i-1}$ 时找到最小的 $j$ 满足 $a_i\lt a_j$ 然后将 $a_i$ 插入位置 $j$，用二元组 $(i,j)$ 记录。多组数据，每组数据给定序列长度 $n$ 和排序过程的所有二元组(共 $m$$\in [1,n]$$\sum m\le 2\times 10^5$$n$$p$$a_{p_1}\le a_{p_2}\le\cdots \le a_{p_n}$$a_{p_{i-1}}$$a_{p_i}$$a_{p_{i-1}}\le a_{p_i}$$k$${n+n-1-k\choose n}$$a_{p_{i-1}}\le a_{p_i}$$n$$(x,y)$$y$$y$$y+1$$y$$k$$\sum m$$\sum n$$O(m\log n)$$n$$m$$1$$i$$a_i$$b_i$$1$$u\to v$$v\to u$$i$$i$$2$$S$$S$…

2020-2021:teams:legal_string:jxm2001:contest:cf_deltix_round_summer_2021

Anonymous (anonymous@undisclosed.example.com) — 2021-09-01T23:58:00+0800

Deltix Round, Summer 2021 (Div. 1 + Div. 2) 比赛链接 E. Equilibrium 题意给定两个序列 $\{A\},\{B\}$。每次询问一个区间 $[l,r]$。每次操作可以在 $[l,r]$ 中选择若干对位置 $(a_1,b_1),(a_2,b_2)\cdots (a_k,b_k)$，满足 $a_1\lt b_1\lt a_2\lt b_2\lt\cdots \lt a_k\lt b_k$。然后对每对位置 $(i,j)$$A_i\gets A_i+1,B_j\gets B_j+1$$A_i=B_i(l\le i\le r)$$C_i=B_i-A_i$$(i,j)$$C_i\gets C_i-1,C_j\gets C_j+1$$C_i=0$$\sum_{i=l}^r C_i\neq 0$$C_i$$C_i=0$$0$$(i,j)$$i\sim j-1$$C[l,r]$$0$$[l,r-1]$$O((n+q)\log n)$$n$$i$$j$$\frac {a_i}{a_i+a_j}$$i$$b_1$$b_1$$b_2\c…

2020-2021:teams:legal_string:jxm2001:contest:cf_feb21

Anonymous (anonymous@undisclosed.example.com) — 2021-02-16T19:42:56+0800

CodeChef February Challenge 2021 比赛链接 Prime Game 题意给定一个数 $A$，并且 $A$ 的初始值为 $X!$。接下来两个人轮流操作，每次操作选择一个不超过 $N$ 且质因子种数不超过 $Y$ 的正整数 $D$，得到 $A-D$。先找到 $0$ 的玩家获胜。给定 $T$$X$$p_1,p_2\cdots$$B=\prod_{i=1}^{Y+1} p_i$$B\mid A$$B\nmid A$$B\nmid D$$D\equiv A\mod B$$B\mid A-D$$B\nmid D$$D$$Y$$D$$A$$0$$A$$X$$p_y$$O(X+T)$$A_1,A_2\cdots A_n$$A_i+A_1\ge A_{i+1}$$G$$0\le G\le M$$q$$G$$i$$\{A_l,A_{l+1}\cdots A_r\}$$[l,r]$$G\bmod (l+r)\ge l$$S=\{a_1,a_2\cdots a_k\}$$[\min S,\max S]$$a_i,a_j\in S$$a_i+\min S\lt a…

2020-2021:teams:legal_string:jxm2001:contest:cf_global_13

Anonymous (anonymous@undisclosed.example.com) — 2021-03-01T21:54:11+0800

Codeforces Global Round 13 比赛链接 F. Magnets 题意给定 $n$ 个磁体，编号 $1\sim n$。磁体有三种类型 $S,N,-$，其中 $-$ 代表无磁性。允许 $n+\lfloor \log n\rfloor$ 次询问。每次询问选择若干磁体，分成两组，然后用装置测量两组磁体之间的受力。$i$$s_i$$S$$n_i$$N$$s_1s_2+n_1n_2-s_1n_2-s_2n_1$$n$$1\sim i-1$$i$$0$$i$$1\sim i-1$$1\sim i-1$$i$$i+1\sim n$$n-1+\lceil \log n\rceil$$n(n\ge 3)$$i$$a_i$$n+1$$i$$i$$S$$|S|-2$$S_1,S_2$$|S_1|+|S_2|$$n$$1$$n$$3$$p_1,p_2,p_3$$(p_1,p_2),(p_2,p_3)$$p_1,p_2$$n+1$$a_2\sim a_n$$i$$a_i\lt i$$a_i\to \max(a_i-x,1),i\in [l,r]$$u,v$$\text{LCA}…

2020-2021:teams:legal_string:jxm2001:contest:cf_global_15

Anonymous (anonymous@undisclosed.example.com) — 2021-07-26T20:02:08+0800

Codeforces Global Round 15 比赛链接 C. Maximize the Intersections 题意给定一个圆，圆上有 $2n$ 个点，问作 $n$ 条弦(所有弦的端点都不相同)最多能有多少个交点。其中有 $k$ 弦已经给出，且不考虑三线共点的情况。 $(a,b),(c,d)$$(a,c)(b,d)$$2n-2k$$a_1,a_2\cdots a_{2n-2k}$$(a_i,a_{i+n-k})(i=1\sim n-k)$$n-k$$(a_i,a_j)$$a_j\neq i+n-k$$a_i,a_j$$n-k-1$$(a_i,a_j)$$n-k-1$$n\times k$$i$$c_i$$1\le c_i\le n$$k$$n$$i$$i$$\lfloor \frac n{k-1}\rfloor$$i$$c(i,1),c(i,2)\cdots c(i,k)$$[c(i,j),c(i,j+1)](1\le j\lt k)$$c(i,2)$$\lfloor \frac n{k-1}\rfloor$$[c(i,1),c(i,2)]$$c(i,3)\cd…

2020-2021:teams:legal_string:jxm2001:contest:cf_harbour_space_scholarship_contest

Anonymous (anonymous@undisclosed.example.com) — 2021-07-23T11:30:07+0800

Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2) 比赛链接 F. Pairwise Modulo 题意给定长度为 $n$ 且互不相同序列 $A$，对每个 $k=1\sim n$ 计算 $$ f(k)=\sum_{i=1}^k\sum_{j=1}^k a_i\bmod a_j $$ 题解不难发现 $$ f(k)=f(k-1)+\sum_{i=1}^k a_i\bmod a_k+\sum_{i=1}^k a_k\bmod a_i\\ \sum_{i=1}^k a_i\bmod a_k=\sum_{i=1}^{k-1}a_i-\sum_{i=1}^{k-1}\lfloor \frac {a_i}{a_k}\rfloor a_k\\ \sum_{i=1}^k a_k\bmod a_i=(k-1)a_k-\sum_{i=1}^{k-1}\lfloor \frac {a_k}{a_i}\rfloor a_i\\ $$ 对于 $\sum_{i=1}^{k-1}\lfloor \frac {a_i}{a_k…

2020-2021:teams:legal_string:jxm2001:contest:cf_mar21

Anonymous (anonymous@undisclosed.example.com) — 2021-03-29T21:22:34+0800

CodeChef March Challenge 2021 比赛链接 Paparazzi Gennady 题意给定 $n$ 条垂直的线段，其中第 $i$ 条线段横坐标为 $i$，纵坐标范围为 $[0,h_i)$。求最大的 $d$ 使得存在 $i$ 使得线段 $(i,h_i)\to (i+d,h_{i+d})$ 与其他所有给定垂线都不相交。题解首先构造 $n$$x_1,x_2,x_3\cdots $$x_i\lt j\lt x_{i+1}$$j+d\le x_{i+1}$$j$$d$$x_i$$\max(x_{i+1}-x_i)$$O(n)$$r\times c$$A$$B$$A$$x$$v$$A$$B$$a_i+=v,a_{i+x}-=v$$x\times x$$1$$2$$1$$2$$v$$1$$x$$v$$2$$2$$1$$1$$2$$x\times x$$0$$x\times x$$2n$$a_{i,j}$$i$$j$$a_{i,j}$$v$$v$$0$$\text{dfs}$$O(rc+x^2)$…

2020-2021:teams:legal_string:jxm2001:contest:cf_may21

Anonymous (anonymous@undisclosed.example.com) — 2021-05-20T17:22:56+0800

CodeChef March Challenge 2021 比赛链接 An Interesting Sequence 题意给定 $T$ 个询问，每次询问给定 $k$，求 $$ \sum_{i=1}^{2k}\text{gcd}(k+i^2,k+(i+1)^2) $$ 题解 $$ (k+i^2,k+(i+1)^2)=(k+i^2,2i+1)=(4k+4i^2,2i+1)=(4k+1+(2i+1)\ast(2i-1),2i+1)=(4k+1,2i+1) $$ 于是题目转化为求 $$ \sum_{i=1}^{2k}\text{gcd}(4k+1,2i+1) $$ 记 $f(n)=\sum_{i=1}^n\text{gcd}(n,i),g(n)=\sum_{i=1}^n\text{gcd}(n,i)[2\mid i]$，于是有 $$ g(4k+1)+g(4k+1)=\sum_{i=1}^{2k}\text{gcd}(4k+1,2i)+\sum_{i=1}^{2k}\text{gcd}(4k+1,4k+1-2i)=f(4k+1)-(4k+1) $$ 于是有 $$ \s…

2020-2021:teams:legal_string:jxm2001:contest:cf_raif_div._1_div._2

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

Codeforces Raif Round 1 (Div. 1 + Div. 2) 比赛链接 E. Carrots for Rabbits 题意给定 $n$ 个数 $a_i$，要求数列 $b$ 满足 * $\sum_{j=1}^{k_i} b_{i,j}=a_i$ * $\sum_{i=1}^n k_i=k$ * $k_i,b_{i,j}\in I^{+}$ 要求最小化 $\sum b_{i,j}^2$。题解考虑函数 $f(i,j)$ 表示将 $a_i$ 分成 $j$ 份时的答案，显然均分为最佳策略。考虑维护 $f(1,k_1),f(2,k_2)\cdots f(n,k_n)$$k_i=1$$i$$f(i,k_i)\to f(i,k_i+1)$$k$$n$$O(k\log n)$$n$$k$$n,k\le 10^6$$n$$0,3,6,9$$k$$6$$2$$3$$9$$3$$3$$3k$$F_i$$3\times 10^i$$n$$n$$3$$3$$a,b$$a+b\ge 9$$a+b-9,9$$0,a+b$$3$$n$$k-1$$3$$0\si…

2020-2021:teams:legal_string:jxm2001:contest:edu_92

Anonymous (anonymous@undisclosed.example.com) — 2020-08-01T10:16:05+0800

Educational Codeforces Round 92 比赛链接 D. Segment Intersections 题意给定两种线段 $[l_a,r_a],[l_b,r_b]$ ，每种线段有 $n$ 条，记为 $a_1,a_2\cdots a_n$ 和 $b_1,b_2\cdots b_n$。每次操作可以任选一条线段 $[l,r]$，将其变换成 $[l-1,r]$ 或 $[l,r+1]$。要求输出最小操作步数，使得 $\sum_{i=1}^n f(a_i,b_i)\ge k$，其中 $f(a,b)$ 表示线段 $a,b$$i$$i$$O(n)$$O(1)$$xd+y\equiv yd+x\pmod w$$1\le x,y\le n$$d(x-y)\equiv 0\pmod w$$w'=\frac w{(w,d)}$$w'\mid (x-y)$$(x-y)=iw'$$$\sum_{i=1}^{\lfloor\frac n{w'}\rfloor}n-iw'=n\lfloor\frac n{w'}\rfloor-\frac {\lfloor\frac n{w'}\r…

2020-2021:teams:legal_string:jxm2001:contest:edu_96

Anonymous (anonymous@undisclosed.example.com) — 2020-10-16T09:39:29+0800

Educational Codeforces Round 96 比赛链接 G. Yet Another DAG Problem 题意给定一个有向无环带边权图，要求给每个点赋值 $a$，对边 $u\to v$，要求 $a_u\gt a_v$，且最小化 $\sum_{i=1}^m w_i(a_{u_i}-a_{v_i})$。题解首先，假设 $a$ 的取值不连续，不妨设不存在 $a=v$，于是将 $a\gt v$$\sum_{i=1}^m w_i(a_{u_i}-a_{v_i})$$a$$a\le n-1$$$ \sum_{i=1}^m w_i(a_{u_i}-a_{v_i})=\sum_{i=1}^n \left(\sum_{u_j=i}w_j-\sum_{v_j=i}w_j\right)a_i=\sum_{i=1}^n c_ia_i $$$e_{i,j}$$a_i=j$$jc_i$$b_{i,j}=u_{e_{i,j}}$$s\to b_{i,0}\to b_{i,1}\to \cdots\to b_{i,n-1}\to t$$s\to b_{i,0},b_{i,n-1…

2020-2021:teams:legal_string:jxm2001:contest:edu_102

Anonymous (anonymous@undisclosed.example.com) — 2021-01-17T13:59:17+0800

Educational Codeforces Round 102 比赛链接 D. Program 比赛时用线段树写的，时间复杂度 $O(n+m\log n)$。由于只查询前后缀，根据题目进行预处理可以做到 $O(n+m)$。 E. Minimum Path 题意给定 $n$ 阶连通图，求点 $1$ 到其他各点的最短路，其中路径长度的定义为所有边的权值和减去最大权值加上最小权值。$dis(i,0/1,0/1)$$1$$i$$O(n\log m)$$n$$A$$1\le a_i\le 100$$a_i$$b_i$$S$$i\in S$$j\lt i$$a_j\mid a_i$$j\in S$$S$$\sum_{i\in S}b_i$$S$$j\lt i$$a_j\mid a_i$$i\to j$$k\lt j\lt i$$a_k=a_j\mid a_i$$i\to j$$a_i$$O(n^2)$…

2020-2021:teams:legal_string:jxm2001:contest:edu_104

Anonymous (anonymous@undisclosed.example.com) — 2021-02-17T20:51:58+0800

Educational Codeforces Round 104 比赛链接 F. Ones 题意给定 $1\le n\lt 10^{50}$，要求用若干个形如 $11\cdots 11$ 的数以及加减号表示 $n$。求表达式中字符 $1$ 的个数的最小值。题解 1 设 $\text{dp}(p,i,j,k)$ 表示最低 $p$ 位与 $n$ 相同，第 $p+1$ 位的进位为 $i$ (允许是负数)。$j$$p$$11\cdots 11$$k$$p$$-11\cdots 11$$i$$1$$n$$p$$d$$i+j-k\equiv d\bmod 10$$$ \text{dp}(p,\lfloor\frac {i+j-k}{10}\rfloor,j,k)\gets \min_{x\ge j,y\ge k}\text{dp}(p-1,i,x,y)+j+k $$$\min_{x\ge j,y\ge k}\text{dp}(p-1,i,x,y)$$O(1)$$j,k\le 5\ast\text{len}(n)$$5$$11\cdots 11$$5$$-11\cdots 11$$n…

2020-2021:teams:legal_string:jxm2001:contest:xiaomi_icpc_1

Anonymous (anonymous@undisclosed.example.com) — 2020-10-30T09:14:12+0800

2020ICPC·小米网络选拔赛第一场比赛链接 E. Phone Network 题意给出长度为 $n$ 的序列 $A$，保证 $1\le a_i\le m$。对每个 $1\le i\le m$，询问保证 $1\sim i$ 的连续子序列的最小长度。题解1 设 $R(i,l)$ 表示序列 $A$ 中以 $a_l$ 为左端点且包含 $1\sim i$ 的最短序列的右端点。$R(i,1\sim n)$$R(i+1,1\sim n)$$i+1$$p_1,p_2\cdots p_k$$p_0=0$$p_j \lt l\le p_{j+1}$$R(i+1,l)=\max\left(R(i,l),p_{j+1}\right)$$p_k \lt l\le n$$R(i+1,l)=\inf$$\text{max}$$R(i,l)-l+1$$\text{max}$$R(i,1\sim n)$$(p_j,p_{j+1}]$$\max$$R$$p_{j+1}$$\text{set}$$O(n\log n)$…