青竹qingzhu

分类

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

TA的专栏 2篇文章 0人订阅

2篇文章 648人学习

全部文章（共51篇）

P2408 不同子串个数后缀自动机做法

传送门题意给一个字符串，求它有多少个不同的子串。思路后缀数组当然是能做的，每个sa[i] - height[i]的和就是答案了。后缀自动机也可以做，后缀自动机上从起点到任意状态就是一个子串，每条路径表示的子串都不同，所以只要求出后缀自动机上从起点到其它点的路径条数就是不同子串的个数。 #...

2020-07-13

0 706

K-th Number 二分

题目链接题意 n个元素的数组A，从A数组中所有长度大于等于k的区间中取出第k大放入B数组中，求B数组的第m大。思路这题正常想很难搞，看了题解才懂。mark一下。考虑二分的做法，问题是求B数组第m大的是谁，假设为ans，考虑一个值x，求B数组里大于等于x的值是否大于m个，这个问题具有单调性...

2020-07-13

0 462

2020年牛客算法入门课练习赛1补题

涉及：大量数据的第k小，几何斜率，圆形尺取，离散化，差分约束，前缀和，模拟。 A 第K小数题意给n个数，求第k小的元素。（n<=5e6）思路直接sort超时。可以利用快排的思想，每次选一个基准元素，把小的元素放左边，大的元素放右边，如果左边的元素个数>=k，那么只需要从左边找第...

2020-07-13

0 455

牛客练习赛65 E 网络流点权改变的处理方法

题目链接题意 n点m条边的无向图，每个点的点权是ai，没经过一次点，点权增加bi，即第k次经过i点权值为ai + (k - 1) * bi，现给出q个xi和q个yi，每次从中选出一组xi,yi，统计从xi到yi的代价和（代价为从xi到yi经过的所有点的点权和），每个点只能选一次，q次后（也就是全选...

2020-07-13

0 417

tokitsukaze and Soldier 优先队列

题目链接题意 n个士兵，每个士兵有两个值，战力vi，人数si，从n个人中选任意个人组成一个团，求团的战力最大值，团的战力是所有士兵的战力和，如果选到了士兵i，那么团的人数不能超过si。思路优先队列。首先，很容易想到的思路就是，假设现在是要选k个人，那么把士兵里si>=k的取出来，再选战...

2020-07-13

0 454

城市网络——树上倍增

题目链接题意有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。在每次行程开始时，你手上有价值为 ...

2020-07-13

0 441

P3252 [JLOI2012]树——树上倍增

题意给定一个值 s 和一棵树。在树的每个节点有一个权值，第 i 个点的权值为a[i]，问有多少条路径的节点权值总和为 s。路径中节点的深度必须是升序的。假设节点 1 是根节点，根的深度是 0，它的儿子节点的深度为 1。路径不必一定从根节点开始。思路路径必须是从低深度到高深度，也就是路径端点一定...

2020-07-13

0 372

最少需要转90度的弯几次——建图

传送门题意给你一个N*N（2≤N≤100）的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。思路拐弯才要花费，把一个点拆成四个点，上下左右，从上到下和从左到右建双向边，边权为...

2020-07-13

0 506

栗酱的数列连续子序列和相等——kmp

传送门题意栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A’，满足(a’1+b1)%k = (a’2+b2)%k = …… = (a’m + bm)%k。思路按照题目给的条件式只能暴力做，暴力做又超时。那么对满足式进行修改，(a[i]+b[i])...

2020-07-13

0 442

1e5个点n+100条边求任意两点之间的距离——最短路

传送门题意 n个点m条边，q次询问求任意两点之间的距离。（n<=1e5，m<=n+100，所有边权为1，保证图连通）。思路这个多出的100多条边就很怪，先考虑如果没有多出边，就只有n-1条边，图连通，那么可以建立最小生成树，用LCA来做，任取一点为根，len[i]为i点到根的距离，...

2020-07-13

0 634