青竹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篇）

2020牛客暑期多校训练营（第二场）A kmp+hash

题意对于字符串s,t,定义f(s,t)为s的前缀和t的后缀的最长匹配长度。给n个字符串,求题解预处理出n个字符串所有后缀的hash值，并记录个数。枚举每一个字符串的所有前缀，求出前缀的hash值，答案加上与前缀相同hash值的后缀个数就行，但是因为要求的是si和sj的最长前后缀长度，例如si...

2020-07-22

0 510

2020牛客暑期多校训练营（第一场）H 网络流边权改变

题意 n个点m条边的有向图，给出边的单位流量费用，q次询问，每次询问有有u,v两个整数，表示所有边的容量为u/v，对于每次询问，输出从1到n流量为1时的最小费用，流量达不到1时，输出“NaN”. 题解每条边的容量是相同的，如果边的容量为1的时候流量为maxflow，那么边的容量为u/v时，流量就是...

2020-07-17

0 581

4月23日边的染色来自专栏

题意 n个点m条边的无向图，每条边有一个权值，-1,0,1，表示这条边的染色情况，-1表示没有染色，0,1表示染的颜色。需要对没有染色的边进行染色（0和1两种），求满足所有环的边异或和为0的染色方案数。题解直接对边赋值很难搞，那么考虑对点赋值，再转换为边的赋值，边的值就是两个端点的异或值，这样...

2020-07-16

0 648

4月21日糖糖别胡说，我真的不是签到题目来自专栏

题意 n个人排成一排，分成两组，第i个人属于a[i]组，每个人有一个能力值b[i]，从左往右每个人在第i秒执行一次动作，可以把前面不属于自己组的且能力值小于自己的消灭。同时有m次操作c[i]，可以在第c[i]秒后把所有前面的人包括自己的能力值增加一，求第n秒后的存活人数。题解要找出每个人能消灭前...

2020-07-16

1 562

POJ 2886 Who Gets the Most Candies?（线段树）

Who Gets the Most Candies? 题目 N children are sitting in a circle to play a game. The children are numbered from 1 to N in clockwise order. Each of t...

2020-07-13

0 491

康托展开——全排列的本质

康托展开——全排列的本质参考链接 X=a[n]* (n-1)!+a[n-1] * (n-2)!+…+a[i] * (i-1)!+…+a[1]*0! 1.求一个排列是原排列的按字典序的第几个排列。 #include<cstdio> #include<iostream> u...

2020-07-13

0 448

hdu4027题解——线段树

hdu4027题解——线段树题意： n个数，m次询问： 0 l r ：将[l, r]内的数取根号并向下取整。 1 l r ：输出[l, r]区间和。思路：线段树，维护区间和。坑点：l 可能会大于 r，需要剪枝，否则直接TLE，当值为1时不需要再取根号了，剪枝后500ms左右。 #inclu...

2020-07-13

0 801

hdu3974题解——线段树，dfs构建结构

hdu3974题解——线段树，dfs构建结构题意：一个公司有N个人，编号1-n，除公司老总外，每个人都有一个上司，每个成员都有若干个或0个下属（一个成员的下属的下属还是他的下属），形成树结构，为公司的人分配任务i，若分配给成员x（可以是老总），则x和他的下属的任务都变为i；m次询问，两种情况，情...

2020-07-13

0 767

P4315 月下“毛景树” 边权改点权问题

洛谷P4315 //Change k w：将第k条树枝上毛毛果的个数改变为w个。 //Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 //Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。由于毛毛虫很贪，于是他会有如下询问： //Max u ...

2020-07-13

0 606

洛谷P4949 最短距离

洛谷P4949 最短距离给出一个 n 个点 n 条边的无向连通图。你需要支持两种操作：修改第 x 条边的长度为 y ；查询点 x 到点 y 的最短距离。共有 m 次操作。思路 n个点n条边的无向连通图（简单图），如果少一条边就是形成一棵树，就是一道LCA题，这题多了一条边，就要用相...

2020-07-13

0 601