walkalone

分类

题解(77)

/ 注册

全部文章（共77篇）

牛客多校第七场 I 题题解

I 题题意：定义一个串的最小表示为——按出现某个字符第一次出现顺序从小到大的排序，并依次编号 abc⋯zabc\cdots zabc⋯z。给定串 SSS，对其全部后缀进行最小表示的排序。∣S∣≤2×105|S| \leq 2\times 10^5∣S∣≤2×105。解法：考虑朴素的后缀数组排序，即...

字符串哈希二分

2022-08-11

0 310

牛客多校第七场 B 题题解

B 题题意：给定平面上一 nnn 个点的整点凸多边形，使其绕着任意对称轴在空间中旋转，求其扫过的体积。若无对称轴则输出 000。n≤1×105n \leq 1\times 10^5n≤1×105。解法：由于是整点多边形，因而对称轴至多不超过 O(log⁡n)O(\log n)O(logn) 条，可...

计算几何

2022-08-11

2 438

2022 年牛客多校第七场 E 题题解

E 题题意：给定 nnn 个互不相同的数字和一个初始为空的序列 {a}\{a\}{a}，依次将其插入到序列的末尾，问至少经过几次相邻交换操作可以让序列符合三分特性（单峰）。n≤2×105n \leq 2\times 10^5n≤2×105，对每次插入输出答案。解法：首先离散化。考虑最终的形态为一高...

线段树数据结构

2022-08-11

3 317

牛客多校第六场签到题题解

B Eezie and Pie 题意：给定一个 nnn 个点的树，第 iii 个节点可以到达其第 j,j∈[1,di]j,j \in [1,d_i]j,j∈[1,di] 级祖先。问每个点能被几个点到达。n≤2×106n \leq 2\times 10^6n≤2×106。解法：树上差分。对于每个点...

算法

2022-08-08

1 330

牛客多校第六场 I 题题解

I Line 题意：给定大小为 nnn 的向量集 SvS_vSv，构造一个整点集 SpS_pSp 使得 ∀P∈Sp\forall P\in S_p∀P∈Sp，∀l⃗∈Sv\forall \vec{l} \in S_v∀l∈Sv，直线 (P,l⃗)(P,\vec l)(P,l) 恰好经过 Sp...

构造

2022-08-08

2 260

牛客多校第六场 F 题题解

F Hash 题意：记 nnn 个点的树哈希 H(T)=∑i=1n∑j=i+1nxiyjzlca(i,j) mod P\displaystyle H(T)=\sum_{i=1}^n \sum_{j=i+1}^n x^iy^jz^{{\rm lca}(i,j)} \bmod PH(T)=i=1∑nj...

哈希

2022-08-08

1 383

牛客多校第六场 C 题题解

C Forest 题意：给定 nnn 个点 mmm 条带权边的无向图，问从中选出若干条边和全部的点构成的 2m2^m2m 张子图中，最小生成森林的边权值和。n≤16n \leq 16n≤16，m≤100m \leq 100m≤100。解法：首先从小到大的对边进行排序，等边权的按照边编号排序，保证生...

状态压缩动态规划

2022-08-08

2 445

牛客多校第六场 A 题题解

A Array 题意：给定长度为 nnn 的序列 {an}\{a_n\}{an}。现构造一个序列 {bm}\{b_m\}{bm}，令 {c}\{c\}{c} 为 {bm}\{b_m\}{bm} 序列的无穷拼接，要求 {c}\{c\}{c} 中每连续 aia_iai 个数字就得出现一次 iii...

构造

2022-08-08

1 305

牛客多校第六场 D 题题解

D Fourier and Theory for the Universe D 题题意：记一个整数 NNN 是好的，当且仅当 N=∏i=1kpiαi\displaystyle N=\prod_{i=1}^k p_i^{\alpha_i}N=i=1∏kpiαi 中 ∑αi\sum \alpha_...

min25筛

2022-08-07

1 362

牛客多校第五场补题记录

A Don't Starve 题意：给定平面上 nnn 个点，从原点出发直线前往这些点收集食物，收集完再前往下一个点。每当离开一个有食物的点后该点食物刷新，每次移动距离严格下降。问最多收集到多少食物。n≤2×103n \leq 2\times 10^3n≤2×103。解法：根据距离作为边权构建完全...

2022-08-02

4 486