CVBB ACM Team 2022-2023:teams:kunkunkun

2022-2023:teams:kunkunkun:2022-codeforces-1

Anonymous (anonymous@undisclosed.example.com) — 2022-09-01T21:50:33+0800

2022-2023 BUAA XCPC Team Supplementary Training 01 C-Cactus Determinant 给定 $n$ 个点，$m$ 条边组成的仙人掌图，求其邻接矩阵的行列式的值。根据行列式的定义 $\sum_{p \in P(N)}{(-1)^{inv(p)}(\prod_{i=1}^{n}{A_{i, p_i}})}$，根据行列式的定义在 $1\sim n$ 行中各取一个点，其编号构成一个长度为 $n$$L$$2$$$ S= \begin{cases} 2 & n\&1 = 1 \\ -2 & n\& 1= 0\ \&\&\ n\ne2\\ -1 & n=2\\ \end{cases} $$$n=2$$-1$$n>2$$i,j$$i,j$$v_1,v_2,\cdots,v_L,v_1$$1,2,\cdots,L,1$$L-1$$(-1)^{L-1} * 2$$dp[i][0/1]$$dp[i][0/1]$$O(n)$…

2022-2023:teams:kunkunkun:2022-codeforces-2

Anonymous (anonymous@undisclosed.example.com) — 2022-09-01T22:09:15+0800

2022-2023 BUAA XCPC Team Supplementary Training 02 E-Export Estimate 给出一个图，通过对于每个 $p$ 通过特定的规则缩点，问每次缩点后图中的点和边的个数。注意到第二种规则中 $i$ 点删去后 $a,b$ 的度数不会变化，对于每个点储存其连接的边中前三大的边，记为 $a\le b\le c$$p\in (a,b]\cup (c,+\infty)$$p\in(a,b]$$p\in(a,b],p\in(c,+\infty)$$p$$p$$p$$$ F[i][j]=a*F[i][j-1]+b*F[i-1][j]+c $$$$ C_{2*n-i-2}^{n-i}*F[1][i]*a^{n-i}*b^{n-1} $$$$ C_{2*n-i-2}^{n-i}*F[i][1]*a^{n-1}*b^{n-i} $$$$ c*C_{2*n-i-j}^{n-i}*a^{n-j}*b^{n-i} $$$$ \sum_{i=2}^n\sum_{j=2}^nc*C_{2*n-i-j}^{n-i}*a^{n-j}*b^{n-i}=c*\s…

2022-2023:teams:kunkunkun:2022-codeforces-3

Anonymous (anonymous@undisclosed.example.com) — 2022-09-01T22:22:17+0800

Replay B和I都是比较签到的题。但是不得不说做B题的时候还是有点急的，多想想可能会好一些。不过还好没咋出错。整套比赛感觉都比较iq。 J算是一道比较结论的题。但是也是猜出了结论就直接写了。没考虑详细证明什么的。

2022-2023:teams:kunkunkun:2022-nowcoder-加赛

Anonymous (anonymous@undisclosed.example.com) — 2022-09-02T14:21:36+0800

2022 牛客暑期多校训练营加赛 D-Directions 赤道上有逆时针排列的 n 座岛屿。给定其中一些岛屿的方位关系（东，西）。问满足这些条件的基础上，n 座岛屿之间的关系矩阵有多少种。（$1\le n\le 500$）由于矩阵的反对称性，只考虑右上角的矩阵，对于第 $i$$j$$i+1\sim j$$j$$j\sim n$$j$$j\sim n$$O(n^3)$$k$$n$$m$$1$$m$$n$$1$$n,m$$k=nm-2$

2022-2023:teams:kunkunkun:2022-nowcoder-1

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T15:42:52+0800

2022 牛客暑期多校训练营1 A-Villages: Landlines 求未被覆盖的区间长度即可 B-Spirit Circle Observation 给定一只包含 $0\sim9$ 的字符串，求有多少对子串 $(S,T)$ 满足 $len(S)==len(T)$ 且 $S=T+1$ 在字符串上建立后缀自动机，记状态 $u$ 对应子串个数为 $cnt[u]$$u$$v_0=(u,0),v_1=(u,1)$$u$$T$$ans[u]$$cnt[v_0]\times cnt[v_1]$$v_{09}=(v_0,9),v_{10}=(v_1,1)$$cnt[v_{09}]\times cnt[v_{10}]$$D[u]$$\displaystyle \sum_{u=0}^{tot}D[u]\times ans[u]$$$ g(i,j)=[x^j]\frac{\prod_{l=1}^n(1+x^{a_l})}{\prod_{(l,i)\in Lim}(1+x^{a_l})} $$$$ F(i,j,b)\times g(i,l)\rightarrow F(i+1,\lfloor\f…

2022-2023:teams:kunkunkun:2022-nowcoder-2

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T14:30:25+0800

2022 牛客暑期多校训练营2 A-Falfa with Polygon 题目大意：给定一个$n$个点的凸包，要求从中选出$k$个点构成一个子凸包，求子凸包的最大周长发现对于子凸包来说，只有一条边是从大标号点连向小标号点，这一条边容易单独考虑，而对于剩下的$k-1$条边可以用DP处理$$ E_{a+b}[i][j]=\max\limits_{i\leq k\leq j}(E_a[i][k],E_b[k][j]) $$$$ G[i]=C_{n-2i}^i*26^{n-3i} $$$$ F[i]=\sum_{j=k}^{n/3}(-1)^{j-k}C_j^kG[j] $$$O(nkd)$$$ \hat{a}=\dfrac{\sum_{i-1}^n(x-\bar x)(y-\bar y)}{\sum_{i=1}^n(x-\bar x)^2}\\ \hat b = \bar y - \hat a\bar x $$$O(n)$…

2022-2023:teams:kunkunkun:2022-nowcoder-3

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T14:55:50+0800

2022 牛客暑期多校训练营3 D 给定一棵树和一个起点，1号节点为终点，随机选其中K条边变成指向终点的单向边，在树上随机游走，求到达终点的期望步数。不考虑选单向边，设 $f_x$ 为从 $x$ 走到其父亲的期望步数，则有 $f_x=\dfrac{1+\sum_v (1+f_v+f_x)}{d(x)}$$f_x=d(x)+\sum_vf_v=2size(x)-1 $$size(x)$$x$$s$$1$$L$$s,v_k,\cdots,v_1,1$$ans=f_s+f_{v_k}+\cdots+f_{v_1}$$L$$len$$L$$1$$L^\prime$$$ -\dfrac{2*size(v)*\sum_{i=0}^{L^\prime-1}C_{n-1-len-i}^{K-1}}{C_{n-1}^{K-1}} $$$O(n)$$$ n!E(x^k)=\sum_{i=0}^nC_n^ii^kD_{n-i} $$$$ n^k=\sum_{i=0}^kS(k,i)\times i!\times C(n,i) $$$$ n!E(x^k)=\sum_{i=0}^nC_n^iD_{n-i…

2022-2023:teams:kunkunkun:2022-nowcoder-4

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T15:19:03+0800

2022 牛客暑期多校训练营4 A B-2D Internet Angel 给出两个同心圆，内圆给出 $𝑛$ 个切点构成的凸多边形，现在在凸多边形与外圆之间随机均匀地选择一个点，求出这个点到这 $𝑛$ 个切点之中最小的距离（路径不跨过任何边界）$𝑋$$𝐸(X^2)$$\theta_1,\theta_2$$\alpha$$\theta_1^\prime=\theta_1-\alpha<0<\theta_2-\alpha=\theta_2^\prime$$(r,\theta)$$X^2=r^2+R_1^2-2rR_1\cos\theta$$$ \begin{aligned} A_i=&\int_{\theta_1}^{\theta_2}\mathrm d\theta\int_{R_1\sec\theta}^{R_2} (r^2+R_1^2-2rR_1\cos\theta)\cdot r\,\mathrm dr\\ =&\int_{\theta_1}^{\theta_2}\left[\dfrac14r^4-\dfrac23R_1\cos\theta r^3+\dfrac12R_1^2r…

2022-2023:teams:kunkunkun:2022-nowcoder-6

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T15:41:18+0800

2022 牛客暑期多校训练营6 C 首先将所有边从邻接矩阵中取出来，设有$m$条边，然后按边权排序，然后依次枚举每条边，考虑该边的贡献对于第$i$条边$(u,v,w)$，只需要知道，只使用前$i-1$条边并且使$u,v$不连通的方案数$Cnt$，则该边的贡献为$$ Cnt*w*2^{m-i} $$$$ C(S)=\sum_{\substack{u\in x,v\notin x\\u\notin y,v\in y\\x\bigcap y=0\\x\bigcup y=S}}F(x)F(y) $$$$ Cnt=\sum_{u,v\in S}C(S)*2^{H(U\bigoplus S)} $$$$ F'(S)=F(S)+[u,v\in S]*(C(S)+F(S)) $$$1$$Hash$$\displaystyle\sum_{i=1}^n\sum_{j=i+1}^nX^iY^jZ^{lca(i,j)}$$Hash$$50$$37$$1$$2\sim 37$$6$$C_5^2\cdot 6=60$$6$$60^6$$X,Y,Z$$1-(\dfrac{Mod-1}{Mod})^{60^6…

2022-2023:teams:kunkunkun:2022-nowcoder-7

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T16:01:58+0800

2022 牛客暑期多校训练营7 B 题目大意：给定二维平面上的一个凸包，该凸包可绕对称轴任意旋转，求最终形成的立体的体积若没有对称轴，则没有体积若只有一条对称轴，则只需要找到这条对称轴，然后求若干圆台的体积和$S[i:]$$S[j:]$$Lcp$$Lcp$$Lcp$$O(26)$$O(26\times n\log n$$O(n^{5})$$O(n^{5})$

2022-2023:teams:kunkunkun:2022-nowcoder-8

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T16:26:49+0800

2022 牛客暑期多校训练营8 A-Puzzle: X-Sums Sudoku 给出一个数独，求在其字典序最小时的 $X-num$。设坐标从 $(0,0)$ 开始，将数独分为 $2^m\times 2^n$ 个区域，且每个区域大小为 $2^n\times 2^m$，给每个区域编号 $A_{a,b}$，显然区域 $A_{0,0}$ 的编号已知，找规律发现 $(i,j)$$A_{0,0}$$(i\%(2^n) \oplus b,j\%(2^m)\oplus a)$$(a,b)$$(i,j)$$a=\left\lfloor\dfrac i{2^n}\right\rfloor,\ b=\left\lfloor\dfrac j{2^m}\right\rfloor$$O(1)$$X$$X$$2^p$$2^{p-1}$$2^{p-1}$$k$$1\sim 2^{n+m}$$O(n+m)$…

2022-2023:teams:kunkunkun:2022-nowcoder-9

Anonymous (anonymous@undisclosed.example.com) — 2022-08-31T16:54:35+0800

2022 牛客暑期多校训练营9 E-Longest Increasing Subsequence 构造一个1,2,...,𝑛的排列，使其恰好有𝑚个不同的最长上升子序列。$1\le m\le 10^9,1\le n\le 100$ 将 $m$ 二进制拆分，设 $m=a_02^0+a_12^1+\cdots+a_k2^k$，其中 $a_k=1$，则可以构造 $2143\cdots (2k)(2k-1)$ 达到 $2^k$，再通过在中间按顺序插入大于 $2k$$2^i,i\in[0,k)$$2k$$𝑆_1,𝑆_2,\ldots,𝑆_𝑘$$1\le k\le 5$$1\le \sum S\le 3\times10^3$$i$$2^{i-1}$$1$$2^k-1$$$ F_i(S)=F_{i-1}(S)*F_1(S) $$…

2022-2023:teams:kunkunkun:2022-nowcoder-10

Anonymous (anonymous@undisclosed.example.com) — 2022-09-03T09:50:42+0800

2022 牛客暑期多校训练营10 B 题目大意：给定$n*n$的矩形，需要选定一个起点，使得起点到所有数字的最小距离的最大值最小考虑二分答案，则对于每种数字，合法的区域是若干菱形的并，若所有颜色的区域的交非空，则当前答案合法$t$$t$$t$$t$$s$$O(n+m)$

2022-2023:teams:kunkunkun:front_page

Anonymous (anonymous@undisclosed.example.com) — 2022-09-01T22:09:59+0800

比赛时间比赛名称 2022.07.23 2022 牛客暑期多校训练营2 2022.07.25 2022 牛客暑期多校训练营3 2022.07.28 2022-2023 BUAA XCPC Team Supplementary Training 01 2022.07.30 2022 牛客暑期多校训练营4 2022.08.04 2022-2023 BUAA XCPC Team Supplementary Training 02 2022.08.06 2022 牛客暑期多校训练营6 2022.08.08 2022 牛客暑期多校训练营7 2022.08.11 2022 牛客暑期多校训练营1 2022.08.13 2022 牛客暑期多校训练营8 2022.08.15 2022 牛客暑期多校训练营9 2022.08.17 2022 牛客暑期多校训练营加赛 2022.08.20 2022 牛客暑期多校训练营10 2022.08.25 2022-2023 BUAA XCPC Team Supplementary Training 03…