18duangduang

题解

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

/ 注册

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

Codeforces Round #645 (Div. 2) 来自专栏

D. The Best Vacation 大致题意：规定一个日历有个月，每个月有天，在第个月的第天活动你可以获得的贡献，你只能连续天活动，请问你能获得的最大贡献是多少. 分析：方法一：尺取法.考虑我们选的天数是连续，那么对应月份也是连续的，并且假设中间月份的天数都是取得到的，但是还可以...

尺取法

2020-05-28

0 711

【每日一题】5月27日货币系统来自专栏

题目大意：有n中货币，每种货币都有无限多个，问是否可以简化货币个数，使得能表示的数个数不变。分析：容易想到货币中最小的面值肯定要留下，那么考虑第二小的货币是否可以去掉，如果第二小的货币是最小货币的倍数，那么就能去掉。那么考虑第i小的货币是否能够留下，那么我们是要查看已留下的货币能否表示当前的货币...

多重背包

2020-05-27

0 627

【每日一题】5月26日 [JSOI2007]建筑抢修来自专栏

题目大意：给定n个任务，每个任务完成所需时间和截止完成时间，求最多能完成多少个任务. 分析：考虑贪心策略。我们每次选择任务完成一定是要最后完成任务的时间尽可能的小，并且当前的时间加上完成当前选择任务的时间一定要小于任务的截止时间才有效。这个我们可以将所有任务按照截止时间排序。那么对于当前时间加上任务...

堆

2020-05-27

2 660

【每日一题】5月25日小AA的数列来自专栏

题目大意：小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和。后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，参考wxyww的优美代码. https://blog.nowcoder.net/n/b1816a1594eb41389e78659...

前缀和

2020-05-27

0 665

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 702

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

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

后缀和

2020-05-25

1 874

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

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

判奇环二分图染色

2020-05-21

0 542

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

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

分治

2020-05-20

2 629

【每日一题】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 687