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

2020年牛客算法入门课练习赛1 题解

A.第k小数大致题意：多组输入，求序列中的第k小数。分析：两种解法，一个是快速排序求第k小，一个是STL自带的nth_element函数，O(n)求第k小的. 快排求第k小...... #include<bits/stdc++.h> using namespace std; c...

快速排序差分三分尺取法

2020-05-26

1 712

【每日一题】5月22日中位数图来自专栏

大致题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。分析：将奇数序列排序，对于比中位数小的元素和比中位数大的元素的个数是相同的，那么我们将比中位数小的元素置为-1，比中位数大的元素置为1，那么合法的序列...

后缀和

2020-05-25

1 876

【每日一题】5月21日图的遍历来自专栏

题目大意:给定一张个点条边的无向图，小sun可以选择一个起始点出发，每次行走都是夸两条边行走，问小sun要遍历所有点，需要添加多少条边. 分析:题目没有说图一定连通，那么要遍历所有点肯定要使得图连通，那么要连通的加边数为：所有连通块的个数-1.加完边后，图上所有点都是连通的.假如图上没有环，那么...

判奇环二分图染色

2020-05-21

0 549

厦门大学程序设计大赛月赛 A. 环鸽的CHONG

题目大意:给定n个元素的序列，判断序列的所有连续的子序列是否全是好序列。好序列:序列存在唯一元素-------存在满足序列中其他所有元素， . 分析:考虑对区间进行分治.首先是最大的区间我们需要找到区间内唯一的元素，假如位置为 ,那么连续区间的左端点在选取,区间右端点在选取，所构成的区间一定...

分治

2020-05-20

2 627

【每日一题】5月20日简单瞎搞题来自专栏

一共有 n个数，第 i 个数是可以取中任意的一个值。设，求 S 种类数。分析:分组背包问题，的值表示前i个数是否能表示j, 我们要求最后能表示的数的种类数，就是求 .考虑每一个dp状态只有两种0和1.那么我们可以用bitset优化背包，将第二维的值变成二进制下1的位置.那么转移状态:...

背包优化

2020-05-20

1 659

【每日一题】5月19日比赛来自专栏

题目大意：12个题目，给定每个题目能做出来的概率，求总共做对 0-12 道题的概率.分析：一共12道题，我们可以二进制枚举做对题目的所有情况 ,然后每一种情况的算出做对题数的概率，然后累加输出即可. #include<bits/stdc++.h> using namespace std;...

二进制枚举

2020-05-19

0 684

厦门大学程序设计大赛月赛 D.小C的棋王之路

题目大意:给定一个有个元素序列,有四种操作和一种询问. 1 L R K 让区间的元素加上 . 2 L R K 让区间的元素乘上 . 3 L R K 让区间的元素变为 . 4 L R K 在末尾位置添加一个元素值为 . 5 L R 询问区间元素的值的和. 分析: 赛中分析，前四个...

线段树

2020-05-18

0 657

【每日一题】5月14日 maze 来自专栏

题目大意: 的网格，，网格上有一些点不能行走，给定Q个传送门((x1,y1),(x2,y2)),表示点(x1,y1)到点(x2,y2)额外有一条路径耗时为3秒，给定起点与终点，问从起点走到终点的最短时间是多少。分析:网格上点数为9e4,可以直接跑dij,网格加边和额外的Q条边.注意坐标化点:(x,...

最短路

2020-05-16

0 678

【每日一题】5月18日「土」秘法地震来自专栏

题目大意: 帕秋莉掌握了一种土属性魔法这种魔法可以在一片k×k大小的一个正方形区域内产生地震但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法整个地图大小为n×m，其中一些地方有建筑请问有多少种可能的情况，使得帕秋莉会停止施法. 分析：枚举子矩阵，判断矩阵中是否有1.判断方法...

子矩阵

2020-05-16

0 590

【每日一题】5月15日储物点的距离来自专栏

题目:一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间 ,查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点有个东西，要运到储物点，代价为就是储物点间的距离。表示第i个储物点与第i+1个储物点的距离表示每个储物点的东西个数分析：对于...

前缀和

2020-05-15

1 641