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

牛客练习赛67 F.牛妹的苹果树

题目大意：个点的无根树，条带权边。有次询问，每次询问区间的点的. 表示点到点的最短距离。参考出题人题解：https://blog.nowcoder.net/n/13d05ab8ac22444a81fbe475de2f563eHDU多校也出了一道这个题目求区间 .(怀疑出题人巨巨是同...

树的直径树链剖分

2020-08-19

0 695

2020牛客暑期多校训练营（第十场）来自专栏

D.Decrement on the Tree 给定一颗无根树，有n个结点，n-1条边，每条边有一个权值。修改操作：选择两个点，两个点之间的最短路径上的边权减一。询问:将第i条边的权值赋值为x，询问要执行多少次修改操作可以使得所有边权变为零。分析：修改操作可以看成将树划分成若干条路径。每个点将它...

2020-08-14

0 637

2020牛客暑期多校训练营（第九场）来自专栏

A. Groundhog and 2-Power Representation 题意：给一个正则表达式，求正则表达式的值。例子：2(0)=2^02(2+2(0))=2^(2+2^0) 分析：队友写的py. a = input() a = a.replace('(', '**(') prin...

2020-08-09

1 764

2020HDU多校第四场 Go Running 来自专栏

题意：同学们在操场跑步(操场看做无限长的数轴),每个同学如果开始跑步那么他跑步的方向不会改变直到时间结束。老师为了检查是否有同学偷懒没有跑步，手上有份监测报告，每份监测报告说明了在时刻时，位置至少有一个人在跑步。问操场上至少有多少名学生没有偷懒在跑步。分析：将每个时刻的(t,pos) 看作...

二分图匹配二分图最小点覆盖

2020-08-02

0 625

2020HDU多校第四场 Contest of Rope Pulling 来自专栏

题意：两班各选几人参加比赛，每个人都有体重和魅力值，要求在两边体重相等的情况下魅力值最大。分析：01背包问题，不过直接写的话复杂度是O(10^9)显然不行。(比赛时有人竟然用容量和为上界水过了官方题解的优化:通过随机化算法进行优化背包容量。(random_shuffle)将所有选手随机排列然后依...

01背包优化随机化算法

2020-08-02

0 857

2020HDU多校第二场 String Distance 来自专栏

题意：给定A,B字符串，询问A字符串的[l,r]子字符串最少多少次操作能够变成B字符串。(可以操作A串，也可以操作B串)操作：增加一个字符，或者减少一个字符。分析:因为只能插删，所以最优的肯定是留下最长公共子序列。表示到串的第个位置，长度为的子序列，在串的最小位置。序列自动机预处理...

序列自动机

2020-07-29

1 611

2020HDU多校第三场 Little W and Contest 来自专栏

题意：给定n个人，第i个人为1 表示是读者，2表示为程序员，ACM赛制是三人一组，规定三人至少有两个为程序员，而且三个人互相不认识。一开始所有人都是互相不认识。然后依次给出n-1条朋友关系(关系满足传递)使得所有人都互相认识。求给出第i条朋友关系时，可以三人一组组队的方案数是多少。答案模1e9+7....

并查集

2020-07-29

0 551

2020HDU多校第三场 Triangle Collision 来自专栏

HDU6798 http://acm.hdu.edu.cn/showproblem.php?pid=6798参考博客 >https://www.cnblogs.com/stelayuri/p/13393651.html 大致题意：给定等边三角形的三个点，内有一动点，给定动点的速度向量，点与...

计算几何二维碰撞问题

2020-07-29

0 682

dp

简单dp:https://ac.nowcoder.com/acm/problem/16664 背包1.https://ac.nowcoder.com/acm/problem/178712.https://ac.nowcoder.com/acm/problem/512163.https://ac.no...

2020-07-26

0 491

2020牛客暑期多校训练营（第三场）来自专栏

A.Clam and Fish 题意：一个游戏有n个阶段。每个阶段是四种状态中的一种. 0：没有鱼、没有蛤蜊 1：没有鱼、有一个蛤蜊 2：有一条鱼、没有蛤蜊 3: 有一条鱼、有一个蛤蜊游戏规则：一个蛤蜊可以做成鱼饵存储起来，在0状态下如果有鱼饵，那么可以钓到一条鱼。有蛤蜊并且也有鱼，可以直...

2020-07-24

0 560