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-07-03

0 1076

厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛）H.时间管理

大致题意：一个序列，可以执行两种操作。对区间内的元素依次对x取，然后将结果赋值给 . 求区间元素和。分析：这道题跟区间开方思路类似。每次对一个区间进行gcd的话一般会有大部分会变成1，可以用一些小技巧来保证复杂度不会太差，用一个tag变量去标记一下这个区间是不是全都相等，再用...

线段树区间gcd

2020-06-01

0 626

厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛） F. 这题多捞啊

规律题，挂一个暴力打表的代码。 #include<bits/stdc++.h> using namespace std; int a[1005]; int n; int vis[2005],b[1005]; int ans; void dfs( int x,int y ) {...

暴力背包搜索

2020-06-01

0 584

厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛）E.芜湖起飞

1.三分+最短路参考苟且的狮子博客 https://blog.nowcoder.net/n/1fb0276367aa44df861b17f185653058 #include<bits/stdc++.h> #define ll long long #define pr pair...

最短路三分

2020-06-01

0 573

逆序数

树状数组简单应用，逆序数转换为：求前i个数小于x的和。 #include<bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; typedef long long ll; const int maxn=2e5+...

树状数组

2020-05-29

5 696

【每日一题】5月28日 Protecting the Flowers 来自专栏

大致题意：给定头牛，每头牛每分钟都会造成破坏，农夫可以将牛拉回牛栏里面花费的时间是 .请问农夫拉回牛的顺序是多少可以使得破坏最少。分析：贪心。考虑第头牛和第头牛，哪头先拉入牛栏.如果先后，那么破坏为：.如果先后，那么破坏为： .要使得破坏程度最少，即：化简：那么我们就按照上...

贪心

2020-05-28

1 751

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

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

尺取法

2020-05-28

0 729

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

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

多重背包

2020-05-27

0 627

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

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

堆

2020-05-27

2 664

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

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

前缀和

2020-05-27

0 663