18duangduang

题解

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

/ 注册

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

【每日一题】7月9日矩阵取数游戏来自专栏

类似题目：https://ac.nowcoder.com/acm/problem/14701 取数游戏题意：的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * ，其中表示第次取数（从1开始编号）。并且每次取走的各个元素只能是该元素所在行的行首或行尾。一共取次，问每行取数的...

记忆化搜索

2020-07-09

0 715

队伍配置

题意：给定花费上限 ,你有件物品，有m 件装饰品，每件物品和每件装饰品都有两个值攻击力和花费。一个物品最多被一个装饰品所装饰，每个装饰品不能独立存在，问在不超过花费上限的前提下，攻击力最大能到达多少.购买限制：物品最多只能买五个.并且同一种商品不能重复购买. 分析：每种商品只能选购一次，那么就...

dp 01背包

2020-07-09

0 660

骚区间

%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.求所有骚区间个数.容易想到枚举一个端点，...

树状数组次小值问题

2020-07-07

0 591

箱子装货物问题来自专栏

#Robot Sends Red Packets > https://ac.nowcoder.com/acm/contest/8829/E n个硬币分成若干堆，每堆硬币的价值相同，求最堆最小价值的分配方案。思路：三层dfs剪枝. #include<bits stdc++.h> ...

状压dp

2020-07-06

0 968

位数差

大致题意：给定一个序列，求 . 表示和十进制下的位数差.分析：方法一:离散+树状数组我们可以逆序遍历序列，计算当前作为的左参数的贡献，那么我们与相加能产生数位差 .举个例子：能至少产生一位数位差，设比大的最小十进制数位，那么的大小一定要大于等于 .依次枚举至少产生两位数位差.......

树状数组分治

2020-07-03

0 1090

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

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

线段树区间gcd

2020-06-01

0 622

厦门大学“网宿杯“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 583

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

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

最短路三分

2020-06-01

0 560

逆序数

树状数组简单应用，逆序数转换为：求前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 692

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

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

贪心

2020-05-28

1 742