18duangduang

题解

未归档(23) 计算几何(1)

/ 注册

全部文章 / 题解（共9篇）

石子合并

类似题目：https://ac.nowcoder.com/acm/problem/50493 石子位置成一个环(就是多存一遍石子，跑2*n大致题意：个石子，每个石子有一定的价值，每次可以合并相邻个石子，合并的代价是两个石子的价值和，合并完后两个石子的价值累加一成石子的价值，问将个石子合并成一个石...

dp

2020-07-10

0 677

队伍配置

题意：给定花费上限 ,你有件物品，有m 件装饰品，每件物品和每件装饰品都有两个值攻击力和花费。一个物品最多被一个装饰品所装饰，每个装饰品不能独立存在，问在不超过花费上限的前提下，攻击力最大能到达多少.购买限制：物品最多只能买五个.并且同一种商品不能重复购买. 分析：每种商品只能选购一次，那么就...

dp 01背包

2020-07-09

0 661

牛客练习赛62 D.牛牛的呱数

大致题意:给定n个数字和p，选择一些将数字拼接成一个新的数字ans(可以重复选择)，ans可被p整除.(n个数字长度总和<=1e6,p<=200 )分析：参考jls代码..%%%九峰大佬.. 考虑p的范围不大，可以写动态规划并且对于每一个数而言模p下的贡献方案最多只有p次,那么我们只需...

dp dp的优化

2020-04-25

0 921

Educational Codeforces Round 84 (Rated for Div. 2) 来自专栏

D - Infinite Path 题意：给定n个点,a数组，b数组.a[i]表示点 i - > 点a[i] 有一条有向边,b[i]表示边的颜色.定义：p^1=[ a[1],a[2],a[3]...a[n] ],p^2=[ a[a[1]],a[a[2]],....,a[a[n]] ],p^k ...

差分数组 dp 最小环

2020-03-25

0 666

牛客多校赛第八场总结来自专栏

本场总结： A.单调栈B.区间贡献C.构造D.三维树状数组----维护曼哈顿距离E.线段树区间维护dfs并查集撤销G.签到I.树上差分和树状数组区间差分J.组合数学和dp 小结：---矩阵中子矩阵问题单调栈继续练---构造先蒙---学习三维树状数组如何维护，后缀最小值转前缀最大值---学习线段树...

树上差分线段树单调栈构造三维树状数组区间交贡献并查集组合数容斥 dp

2020-02-24

0 708

牛客多校赛第六场总结来自专栏

本场总结： A.签到B.模拟C.回文树D.猜结论checkE.构造G.全排列和蔡勒公式check----O(1) 判断星期几J.前缀和dp 小结----练构造----回文树就是个**板子选手，还要再学----构造想法----学到了蔡勒公式----练dp A. Garbage Classif...

构造回文树回文子集全排列蔡勒公式判断星期几 dp 技能树

2020-02-10

0 682

牛客多校赛第五场总结来自专栏

本场总结: 题目类型：A.签到B.广义斐波那契数列求第n项----十进制倍增C.BSGS基础题 ---预处理打表E.位元状压dpF.二分图求解最大独立集G.基础dpH.拓扑排序D.I.J 留坑暂时不填小结:----广义斐波那契可以先找最小循环节加速，然后用十进制倍增取模----学习了一下BS...

广义斐波那契数列+十进制倍增+循环节优化 BSGS预处理打表位元状压dp 二分图求最大独立集拓扑排序广义斐波那契数列 dp

2020-02-05

0 846

牛客多校赛第二场总结来自专栏

本场总结: 题目类型:A.概率问题D.bfs第K小团E.线性dp，线段树维护矩阵加速F.dfs剪搜H.单调栈维护第二大子矩阵J.区间合并问题其他题目暂时鸽了小结:--概率问题脑子不够用--k小团问题bit<int.> & 极好用--线段树还能维护矩阵加速震惊--单调栈找第二...

概率第k小团 dfs 单调栈第二大子矩阵区间合并 dp 线段树矩阵加速线性dp

2020-02-02

0 599

牛客多校赛第三场总结来自专栏

本场总结: 题目类型:A.分块B.签到C.巨巨才能A的题D.数论---找最小循环节E.kruskal重构树--巨巨才能A的题F.单调队列G.ST表分治、贪心H.构造I:dpJ. unordered_map<string,list<node>::iterator>mp; 模拟&...

分块随机hash 最小循环节单调队列 ST表分治贪心构造 dp

2020-01-29

2 766