18duangduang

题解

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

/ 注册

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

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 753

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

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

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

2020-08-02

0 607

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

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

01背包优化随机化算法

2020-08-02

0 825

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

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

序列自动机

2020-07-29

1 604

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

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

并查集

2020-07-29

0 541

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 675

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

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

2020-07-24

0 544

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

B. Boundary 题意：给定n个点的点坐标，求所有过(0,0)的圆中，圆上能覆盖最多给定点的圆。输出覆盖点的最大个数。分析： n=1,那么答案就是1. n>1,因为三个点能确定一个圆，n^2枚举两个点与原点连成三角形，求三角形的外心，然后存储坐标。这样我们可以枚举c出所有覆...

2020-07-22

2 734

石子合并

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

dp

2020-07-10

0 677

花店橱窗

题目大意：给定种花个花瓶，每种花插在花瓶上都有一个美观值 ,对于第种花，满足第种花插在的花瓶位置一定是在第种花插在花瓶位置之前.每个花瓶只能插一种花。问将朵花插入花瓶最大的美观值之和是多少.并且输出插入花瓶的位置方案。(如果有方案美观值相同，按字典序最小输出) 分析：动态规划. 表示...

dp优化

2020-07-10

3 739