walkalone

分类

题解(77)

/ 注册

全部文章（共77篇）

牛客多校第四场 M 题题解

M Monotone Chain M 题题意：给定平面 nnn 个点 (xi,yi)(x_i,y_i)(xi,yi)，找到两个向量 a,b\textbf{a},\textbf{b}a,b 满足 ∀1≤i≤j≤n\forall 1 \leq i \leq j \leq n∀1≤i≤j≤n，(OAi...

计算几何

2022-07-31

1 301

牛客多校第四场 J 题题解

J Counting Fish Again J 题题意：在第一象限含坐标轴的无穷大方格纸上，可以画一条斜率为 −1-1−1 的线段 (u1,v1)→(u2,v2)(u_1,v_1) \to (u_2,v_2)(u1,v1)→(u2,v2)，或者擦除已经有的一条线段，问每次操作后鱼的个数。鱼形...

珂朵莉树计数

2022-07-31

2 258

牛客多校第四场 D、E 题题解

D、E Jobs D、E 题题意：有 nnn 家公司，第 iii 家公司有 mim_imi 个工作，对能力要求为 (aj,bj,cj)(a_j,b_j,c_j)(aj,bj,cj)，其中 1≤aj,bj,cj≤4001 \leq a_j,b_j,c_j \leq 4001≤aj,bj,c...

数据结构 stl 单调队列

2022-07-31

2 251

牛客多校第四场 B 题题解

B 2D Internet Angel B 题题意：给定内外同心圆，半径分别为 R1,R2R_1,R_2R1,R2，沿内侧圆外有一 nnn 边外接多边形 {Pi}\{P_i\}{Pi}，与内侧圆的切点为 {Qi}\{Q_i\}{Qi}，保证这一多边形完全在外侧圆内。记此外接多边形外与外侧圆内...

计算几何数值积分

2022-07-31

1 272

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

A Task Computing 题意：给定长度为 nnn 的序列 {(wi,pi)}\{(w_i,p_i)\}{(wi,pi)}，从中选出 mmm 项并重新排列得到子序列 {a1,a2,⋯ ,am}\{a_1,a_2,\cdots,a_m\}{a1,a2,⋯,am}，最大化 ∑i=1mw...

ACM竞赛

2022-07-31

0 334

牛客多校第四场 C 题题解

C Easy Counting Problem C 题题意：给定字符集大小 Σ\SigmaΣ，和每个字符出现次数的下限 {ci}\{c_i\}{ci}，qqq 次询问由 Σ\SigmaΣ 中字符构成的长度为 nnn 的字符串的个数。q≤300q \leq 300q≤300，n≤1×107n \le...

多项式生成函数

2022-07-31

4 693

牛客多校第二场 F 题题解

F NIO with String Game F 题题意：给定 nnn 个串 {Tn}\{T_n\}{Tn} 和一个串 SSS，有以下四种操作：给 TxT_xTx 的末尾增加一个字符；给 SSS 串末尾删除 ppp 个字符；给 SSS 串末尾插入 kkk 个字符；查询 {Tn}\{T_...

字符串

2022-07-29

2 282

牛客多校第二场 E 题题解

E Falfa with Substring E 题题意：给定长度 nnn，问长度为 nnn 的纯小写字母串中出现 kkk 次 bit的字符串个数，需要对 k∈[0,n]k \in [0,n]k∈[0,n] 输出答案。n≤1×106n\leq 1\times 10^6n≤1×106。解法：对于恰好...

多项式计数

2022-07-29

0 388

牛客多校第二场 I 题题解

I let fat tension I 题题意：给定 nnn 个 kkk 维向量 {Xi}\{X_i\}{Xi}，和 nnn 个 ddd 维向量 {Yi}\{Y_i\}{Yi}，求 Yj′=∑i=1nXi⋅Xj∣Xi∣∣Xj∣Yi\displaystyle Y'_j=\sum_{i=1}^n \...

线性代数

2022-07-29

0 314

牛客多校第二场 C 题题解

C Link with Nim Game C 题题意：给定 nnn 堆石子 {an}\{a_n\}{an} 玩 Nim 游戏，若该玩家必输则会尽量拖延时间，否则就会速战速决。问游戏会进行多少轮，并求出先手第一步的方案数。n≤2×105n \leq 2\times 10^5n≤2×105。解法：判...

博弈论

2022-07-29

0 279