walkalone

分类

题解(77)

/ 注册

全部文章（共77篇）

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

A Ancestor 题意：给出两棵 nnn 个节点的树 A,BA,BA,B，A,BA,BA,B 树上每个节点均有一个权值，给出 kkk 个关键点的编号 x1,x2,⋯ ,xkx_1, x_2, \cdots, x_kx1,x2,⋯,xk，问有多少种方案，使得去掉恰好一个关键点使得剩余关键点在...

图论贪心

2022-09-08

0 393

2022 年牛客多校第一场补题记录

A Villages: Landlines 题意：有一个电站位于 xsx_sxs，需要在 [xs−rs,xs+rs][x_s-r_s,x_s+r_s][xs−rs,xs+rs] 的范围内设置至少一个电塔将电引出。n−1n-1n−1 个用电处位于 xix_ixi，需要在其范围 [xi−ri...

动态规划贪心数据结构字符串

2022-09-08

0 428

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

K You are given a tree... 题意：给定一个 nnn 个节点的树，树上每个点有颜色 aia_iai，边有边权。问从中选择 kkk 个颜色不同的点，他们构成的生成子图的边权值和最大值。n≤1×103n \leq 1\times 10^3n≤1×103，k∈[2,5]k \in ...

动态规划状态压缩随机化

2022-08-27

0 323

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

F Shannon Switching Game? 题意：给定一个多重无向图 G(V,E)G(V,E)G(V,E) 和一对点 s,ts,ts,t，起始时 sss 处有一个令牌。先手可以选择删除图上的一条边，后手可以选择删除令牌所在点 uuu 邻接的一条边 (u,v)(u,v)(u,v)，然后将令牌移...

广度优先搜索鸽巢原理

2022-08-27

0 382

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

E Reviewer Assignment 题意：有 nnn 份论文，mmm 个人每个人可以审稿这 nnn 篇论文中的一些论文。找出一种方案，使得每个人只审核一篇论文的同时，设 fif_ifi 为至少被 iii 个人审核的论文数量，找到 (f1,f2,⋯ ,fn)(f_1,f_2,\cdots,f...

图论网络流

2022-08-27

0 344

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

D Mi Re Do Si La? So Fa! 题意：给定串 SSS，询问其每个子串的完整循环节长度和。例如串 aaaa的完整循环节长度有 1,2,41,2,41,2,4 三种。∣S∣≤1×106|S| \leq 1\times 10^6∣S∣≤1×106。解法：显然每个子串 S[l,r]S[l...

字符串 RMQ 数据结构

2022-08-27

1 358

2022 年牛客多校第十场 B 题题解

B Fall Guys-Perfect Match 题意：给定 n×nn \times nn×n 的棋盘，每个格子有一个颜色 ai,ja_{i,j}ai,j，保证每种颜色出现次数不超过 202020 次。问站在哪个格子，到达任意一个格子的曼哈顿距离的最大值最小。n≤1×103n \leq 1\ti...

二分

2022-08-27

1 403

2022 年牛客多校加赛场 C 题题解

C Cmostp 题意：给定字符串 SSS，qqq 次询问 SSS 的全部本质不同子串中有多少个子串的右端点落入 [l,r][l,r][l,r] 中的。 ∣S∣,q≤5×105|S|,q \leq 5\times 10^5∣S∣,q≤5×105。解法：显然在 SAM 上可以将前缀 [1,i][1,...

数据结构字符串

2022-08-26

0 302

2022 年牛客多校加赛场签到题题解

E Everyone is bot 题意：nnn 个人打算复读。一次复读的过程如下，每一轮，nnn 个人按照编号从小到大依次执行以下操作：如果这个人在前几轮已经进行过复读，他不会再次复读，否则他可以选择复读。如果某一轮没有人进行复读，那么复读的过程结束。结束后选择复读的倒数第 ppp 个人会扣分，...

思维

2022-08-26

0 399

2022 年牛客多校加赛场 J 题题解

J Jellyfish and its dream 题意：给定长度为 nnn 的环形序列 a0,a1,⋯ ,an−1a_0,a_1,\cdots,a_{n-1}a0,a1,⋯,an−1，仅由 0,1,20,1,20,1,2 构成。若 ai+1≡ai mod n+1(mod3)a_i+1 \eq...

差分

2022-08-26

0 333