塔子哥学算法

分类

未归档(82) 题解(1)

/ 注册

全部文章（共83篇）

Manacher+数据结构维护-2017哈尔滨A

传送门:https://vjudge.net/contest/391081#problem/A 题目大意: 给你一个字符串，让你统计其中两个等长且奇长的互相重叠组合而成的回文子串的个数. 题目思路:类似于HDU5371.都是Manacher+数据结构维护解法一：树状数组我们通过Manache...

2020-09-03

0 622

回文串计数-Manacher

传送门:http://codeforces.com/problemset/problem/159/D 题目大意:给你一个回文串，问你有多少对不相交的回文串对数. 题目思路：解法一:dp预处理 + 后缀和预处理. 首先我们利用dp预处理dp[i][j]代表区间[i][j]是不是一个回文串. 然后...

2020-09-03

0 854

二分答案+树形背包:In Search of Gold

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6769 题目大意：给你一棵树，每条边有两种权值a,b.让你从里面选出k条a,n - k - 1条b.使得整棵树的直径最小. 题目思路: 让我们最小化直径。直径又是树的最大路径。那么就是最小化最大值。自然可以...

2020-09-02

0 608

树形背包-蓝桥杯-金属采集

传送门:https://blog.csdn.net/weixin_44778155/article/details/104725178 题目大意：给你一棵带边权的树，放k个机器人在s点。让你安排这k个机器人遍历完整颗树，使得价值最小。(n <= 1e5 , k <= 10) 题目思路: ...

2020-09-02

0 548

树形计数背包-HDU 6540 Neko and tree

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6540 题目大意：给一棵含有n个点的树，里面含有m个关键点。问你有多少种选关键点的方案使得选出的点中两两之间的距离 <= dist. (1 <= n , m , dist <= 5000)...

2020-09-01

0 655

树形背包-P1272 重建道路

传送门：https://www.luogu.com.cn/problem/P1272 题目大意:给你一棵树，删除尽量少的边使得生成一颗含有P个点的树。题目思路: 显然的树上分组背包。考虑状态：直接跑树上分组背包即可。复杂度: 题目坑点:由于定义是认为每个子树都与父节点相连，所以在计算子问题(每...

2020-09-01

0 497

树形背包-P3177树上染色

传送门:https://www.luogu.com.cn/problem/P3177 题意:给你一棵带边权树，染k个黑点，n - k 个白点.问你同色点两两之间的路径和最大为多少. 思路：这样以来，我们可以将一颗子树的黑点个数看作是背包的体积。然后二元组<子树中黑点个数,点对贡献>...

2020-08-31

0 587

好题：牛牛的粉丝 - 矩阵快速幂优化dp,循环矩阵

传送门:https://ac.nowcoder.com/acm/contest/7079/D 题意:在一个有n个点的环上，每个点上有一些人。每个人每一步独立的以 p1 的概率向左走,p2的概率向右走。p3的概率留在原地。问k轮之后每个点的期望人数分布情况. 问题1:n , k <= 100. ...

2020-08-29

0 578

2017CCPC沈阳：B-二分答案

传送门:https://vjudge.net/contest/391081#problem/B 题意:给你一个数组A，对于【长度 >= k 的所有子数组】，求第k大。将所有结果k存入B数组。问你B数组里的第M大数是多少。思路：这个题看上去好像很难。但是很显然一点：M过大,到1e10.大...

2020-08-27

0 488

好题：1400E-Clear the Multiset

传送门：https://codeforc.es/contest/1400/problem/E 题目大意:给你一个序列 a1 , a2 , ... , an.你有两种操作: 1.选取一段[L,R]，使得a[L~R] -1 . 2.选取一个位置i.使得ai = 0. 现在问你最少操作多少次使得序列变全0...

2020-08-26

0 611