18duangduang

分类

未归档(23) 计算几何(1) 题解(71)

/ 注册

TA的专栏 46篇文章 1人订阅

14篇文章 876人学习

2019牛客暑假多校赛补题

10篇文章 914人学习

3篇文章 771人学习

2020牛客暑假多校赛补题

4篇文章 764人学习

2020HDU暑假多校赛补题

6篇文章 857人学习

2020牛客国庆集训派对

1篇文章 774人学习

网络模型工程化专题（ VC++ 2017 ）

3篇文章 1374人学习

1篇文章 969人学习

扩散模型学习

4篇文章 423人学习

全部文章（共98篇）

【每日一题】5月11日 Moovie Mooving 来自专栏

题目大意：给定部电影,影片放映时间 ,对应次影片放映的开始时间.求在时间内可以连续观看电影的最少数量.(一部电影放映时可以切换另一部正在放映的电影)分析:状压dp 小于等于20，可以枚举所有选电影的方案. 表示状态下连续放电影的结束时间. 考虑的转移, 方案没有选的电影就是二进制位下为...

状压dp

2020-05-12

0 585

【每日一题】5月9日过河来自专栏

题意:河宽，河中有个石子，青蛙想要过河，青蛙每次可以跳的距离,问青蛙过河至少要踩多少块石子。分析：经典的状态压缩dp. 我们先不考虑范围,先将所有石子的位置进行排序，到第的位置最少踩的石子数量.转移方程: 显然空间太大，那么考虑如何优化空间.其实很多是没有意义的,假如远大于 ,那么...

状态压缩dp

2020-05-12

0 786

牛客练习赛63 F.牛牛的树行棋

题目大意：给定一棵树，每个结点上都有一个棋子，牛牛和牛妹两个人每次选择任意一个结点的棋子，将棋子移动到该节点子树下的节点位置。(不可以不移动)牛牛先手，牛妹后手。现在假设双方都采用最优策略，请问牛牛能否赢。如果牛牛（先手）能够赢，请问牛牛第一步有多少种不同的必胜策略。我们认为两个策略是不同的，当且仅...

SG函数树上差分

2020-05-09

1 972

各种矩阵选数问题

最近做的矩阵选数问题比较多，写一篇博客。 1.每个人戴不同帽子的方案数. https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/ 题目大意:有n个人40顶帽子，每个人喜欢不同的帽子...

2020-05-06

1 945

牛客小白月赛9 E.换个角度思考

分析:一个新的方法求任意区间小于等于k的个数.-------离散+树状数组.将询问按照大小从小到大排序,并且将也从小到大排序，然后根据询问从小到大插入到树状数组对应编号中,当大于时候更新询问答案.复杂度可以做到O(nlogn).十分优美的方法 #include<bits/stdc++.h&...

树状数组

2020-05-04

1 774

牛客IOI周赛16-普及组 D. 杀树

题意：给定一棵树,第i个结点有权值,删除一些结点的代价是删除结点的权值和,求满足树上任何一条链长度小于等于l的删除方案代价最小.(n<=5000, <=5000 )分析: 从n的范围可以知道复杂度可以是n^2,那么可以搞树形二维dp. 表示以第i个结点为根节点的子树满足最长链小于等于...

树形dp

2020-05-02

4 571

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

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

dp dp的优化

2020-04-25

0 917

牛客练习赛62 C.牛牛染颜色

题意：牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。求一共有多少种好的染色的方案。答案 mod(1e9+7).分析：树形dp.考虑当前节点为根节点的子树方案数，dp...

树形dp lca

2020-04-25

0 867

牛客练习赛62 B. 病毒扩散

大致题意:自行看题.分析:打表前10秒的情况，发现就是n次多项式系数问题.手推规律 t秒合法答案: C[t-x][y]*C[t][x]. 然后再判断一下没有感染的情况---( x+y>t ). #include<bits/stdc++.h> using namespace std;...

打表找规律 n次多项式系数

2020-04-25

1 1201

牛客练习赛62 A.牛妹的游戏

题目大意:给定n个点m无向边，求该图和图的补图是否有度数为3的环.分析：比赛时疯狂讨论边情况...wa自闭了正确题解: 拉姆塞结论--点数超过5的图和对应补图必有度数为3的环.不会证明(只会举例子) 那么点数少于6的图直接暴力找环即可. #include<bits/stdc++.h>...

2020-04-25

0 565