walkalone

分类

题解(77)

/ 注册

全部文章（共77篇）

牛客多校第二场 B 题题解

B Light B 题题意：给定一个凸多边形 {Cn}\{C_n\}{Cn}，在这一多边形向内延申 www 的范围有一堵高为 hhh 的墙，墙内多边形记为 C′C'C′。现在在点 L(x,y,z)L(x,y,z)L(x,y,z) 处有一点光源，问该点光源照射到 C′C'C′ 的面积。n≤2×103...

计算几何

2022-07-29

0 355

牛客多校第二场补题记录（签到合集）

D Link with Game Glitch 题意：给定 nnn 个物品和 mmm 种物品合成方式 (a,b,c,d)(a,b,c,d)(a,b,c,d)：kakaka 个 bbb 物品合成 kckckc 个 ddd 物品，k∈R+k \in \R^+k∈R+。原定方式会导致出现无穷多个物品，现在...

算法 ACM竞赛补题记录

2022-07-29

0 384

牛客多校第三场 B 题题解

B 题题意：kkk 个城市有 nnn 个人去上班，每个人选一个城市上班，第 iii 个城市需要 eie_iei 个人去上班。第 iii 个人去第 jjj 个城市上班的代价为 ci,jc_{i,j}ci,j，问最小化代价。n≤1×105n \leq 1\times 10^5n≤1×105，k≤10...

网络流图论

2022-07-29

9 795

牛客多校第三场 F 题题解

F 题意：有一个 nnn 个点 mmm 条边的无向图 GGG，qqq 次询问，每次询问给定 xi,yix_i,y_ixi,yi，表示一个长度为 nnn 的排列的第一项和最后一项，问是否能找到一个长度为 nnn 且首尾项为 xix_ixi 和 yiy_iyi 的排列，使得 ∀i∈[1,n−1]...

图论连通性

2022-07-28

6 368

牛客多校第三场 D 题题解

D Directed 题意：给定一个 nnn 个点以 111 为根的树，现在要从 sss 出发到 111 号节点。现在随机选择 kkk 条树边变成单向边，方向由儿子指向父亲。同时人在某一个节点以等概率选择出边，问期望多少步走到 111 号节点。解法：对于一个有根树，从儿子节点 vvv 走到父节点 ...

动态规划期望

2022-07-28

8 320

牛客多校第三场 H 题题解

题意：给定长度为 nnn 的模式串 SSS，和长度为 mmm 的权值数组 {wi}\{w_i\}{wi}。对于一个长度为 mmm 的串，wiw_iwi 表示使用该串上第 iii 个字符与 SSS 匹配可以获得 wiw_iwi 的权值。kkk 次询问一个长度为 mmm 的串 TTT 与 SSS ...

字符串

2022-07-28

1 281

牛客多校第三场 G 题题解

G Geometry 题意：给定两个 nnn 个点和 mmm 个点的凸包和运动方向，问是否会发生碰撞，何时发生碰撞。3≤n,m≤5×1043 \leq n,m \leq 5\times 10^43≤n,m≤5×104。解法：两个多边形速度为 v1⃗,v2⃗\vec{v_1},\vec{v_2}v1...

2022-07-28

0 325

牛客多校第三场 I 题题解

题意：给定 nnn，记随机变量 XXX 为一个长度为 nnn 的排列中满足 ai=ia_i=iai=i 的个数，求所有排列中 E(Xk)E(X^k)E(Xk)。1≤n≤1×10181 \leq n\leq 1\times 10^{18}1≤n≤1×1018，0≤k≤n+50000 \leq k \...

数学

2022-07-28

0 315

牛客多校第九场题解

A A Math Challenge 题意：给定，求。解法：遇到的式子，通常想到类欧几里得算法。此法的核心在于可以将这类的求和在的时间内算出。朴素的类欧几里得算法是计算的。边界条件即是，此时答案等于。考虑以下两种转移：或。将化成，因而有。 ...

2021-08-16

0 516

牛客多校第八场题解

C Fuzzy Graph 题意：给定一个个节点组成的无向图，现给这些点染成红、绿、蓝三色。若一条边的两个端点颜色不同，则该边仍为黑色，否则染成两端点共同的颜色。要求：基础要求：所有的点仍被黑色边连接。（可选）三种颜色的点数量相同。（可选）三种颜色中点数目最多的一个颜色，不存在该颜色的边...

2021-08-11

0 846