walkalone

分类

题解(77)

/ 注册

全部文章（共77篇）

2022 年牛客多校第九场签到题题解

A Car Show 题意：给定长度为 nnn 的序列 {ai}\{a_i\}{ai}，其中 ai∈[1,m]a_i \in [1,m]ai∈[1,m]，求有多少个连续子区间包含 [1,m][1,m][1,m] 中每个数。n,m≤1×105n, m\leq 1\times 10^5n,m≤1×1...

2022-08-16

0 397

2022 年牛客多校第八场 K 题题解

K Symmetry: Convex 题意：给定 nnn 个点的凸多边形 CnC_nCn，输出前 iii 个点构成的凸包的对称轴。n≤1×105n \leq 1\times 10^5n≤1×105。解法：找对称轴可以使用 Manacher。本题先预处理整个凸包构成的串的 Manacher（注意不...

计算几何字符串

2022-08-14

0 352

2022 年牛客多校第八场 I 题题解

I Equivalence in Connectivity 题意：给定 kkk 个 nnn 的点的图。对于第 iii 个图，其由 pip_ipi 图删除或者新增一条边构成（保证 pi<ip_i<ipi<i），问这 kkk 张图依据连通性可以分成多少组。n,k≤1×105n,k ...

数据结构分治

2022-08-14

0 690

2022 年牛客多校第八场 G 题题解

G Lexicographic Comparison 题意：给定两个长度均为 nnn 的排列 A,PA,PA,P。有以下 qqq 次三类操作：交换 AxA_xAx 与 AyA_yAy；交换 PxP_xPx 与 PyP_yPy；查询 APxAP^xAPx 与 APyAP^yAPy 的大...

数据结构平衡树

2022-08-14

0 307

2022 年牛客多校第八场 F 题题解

F Longest Common Subsequence 题意：给定两个长度分别为 n,mn,mn,m 的序列 S,TS,TS,T，问其最长公共子序列长度。其中 SSS 与 TTT 都是通过 xi+1=f(xi)=(axi2+bxi+c) mod px_{i+1}=f(x_i)=(ax_i^2+bx...

stl

2022-08-14

0 280

2022 年牛客多校第八场 D 题题解

D Poker Game: Decision 题意：桌面上有 666 张扑克牌，Alice 和 Bob 手上各有 222 张且明牌。二人以最优决策依次从桌上抽取一张牌直到二人各有五张牌，最终根据德州扑克的规则比大小。问最终谁会赢。解法：首先写清楚德州扑克的大小比较：依次按照牌型从大到小的顺序看能否...

搜索模拟

2022-08-14

0 372

2022 年牛客多校第八场 A 题题解

A Puzzle: X-Sums Sudoku 题意：考虑一宫大小为 2n×2m2^n\times 2^m2n×2m 的方形数独，求横排字典序最小（4×24\times 24×2 的数独如下）的数度中第 xxx 行或列的前或后 XXX 个数的和，其中 XXX 为第 xxx 行或列的第一个数字。 ...

位运算

2022-08-14

0 305

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

A Floor Tiles in a Park 题意：给定 h×wh \times wh×w 的矩形，将其分为 kkk 个子矩形的方案数。h,w≤1×109h,w \leq 1\times 10^9h,w≤1×109，1≤k≤51 \leq k \leq 51≤k≤5。解法：kkk 很小可以考虑分...

构造栈模拟计数

2022-08-11

0 363

牛客多校第七场 K 题题解

K 题题意：给定 nnn 堆石子，一次一个人选一堆非空的石子拿走至少一个石子，然后可以选择将这堆石子合并到其余非空的石堆去。qqq 次询问，给定区间 [L,R][L,R][L,R]，问有多少个子区间 [l,r]⊂[L,R][l,r] \subset [L,R][l,r]⊂[L,R] 使得先手必胜。n...

博弈论数据结构

2022-08-11

2 331

牛客多校第七场 J 题解

J 题题意：求长度为 nnn，且每个数字都在 [0,k−1][0,k-1][0,k−1]，使得区间连续和为 kkk 倍数的子区间有 ttt 个的序列个数。n,k≤64n,k \leq 64n,k≤64，t≤n(n−1)2t \leq \dfrac{n(n-1)}{2}t≤2n(n−1)。解法：区...

动态规划前缀和

2022-08-11

1 339