18duangduang

题解

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

/ 注册

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

厦门大学程序设计大赛月赛 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 645

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

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

最短路

2020-05-16

0 677

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

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

子矩阵

2020-05-16

0 592

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

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

前缀和

2020-05-15

1 636

【每日一题】5月11日 Moovie Mooving 来自专栏

题目大意：给定部电影,影片放映时间 ,对应次影片放映的开始时间.求在时间内可以连续观看电影的最少数量.(一部电影放映时可以切换另一部正在放映的电影)分析:状压dp 小于等于20，可以枚举所有选电影的方案. 表示状态下连续放电影的结束时间. 考虑的转移, 方案没有选的电影就是二进制位下为...

状压dp

2020-05-12

0 576

【每日一题】5月9日过河来自专栏

题意:河宽，河中有个石子，青蛙想要过河，青蛙每次可以跳的距离,问青蛙过河至少要踩多少块石子。分析：经典的状态压缩dp. 我们先不考虑范围,先将所有石子的位置进行排序，到第的位置最少踩的石子数量.转移方程: 显然空间太大，那么考虑如何优化空间.其实很多是没有意义的,假如远大于 ,那么...

状态压缩dp

2020-05-12

0 786

牛客练习赛63 F.牛牛的树行棋

题目大意：给定一棵树，每个结点上都有一个棋子，牛牛和牛妹两个人每次选择任意一个结点的棋子，将棋子移动到该节点子树下的节点位置。(不可以不移动)牛牛先手，牛妹后手。现在假设双方都采用最优策略，请问牛牛能否赢。如果牛牛（先手）能够赢，请问牛牛第一步有多少种不同的必胜策略。我们认为两个策略是不同的，当且仅...

SG函数树上差分

2020-05-09

1 971

牛客小白月赛9 E.换个角度思考

分析:一个新的方法求任意区间小于等于k的个数.-------离散+树状数组.将询问按照大小从小到大排序,并且将也从小到大排序，然后根据询问从小到大插入到树状数组对应编号中,当大于时候更新询问答案.复杂度可以做到O(nlogn).十分优美的方法 #include<bits/stdc++.h&...

树状数组

2020-05-04

1 772

牛客IOI周赛16-普及组 D. 杀树

题意：给定一棵树,第i个结点有权值,删除一些结点的代价是删除结点的权值和,求满足树上任何一条链长度小于等于l的删除方案代价最小.(n<=5000, <=5000 )分析: 从n的范围可以知道复杂度可以是n^2,那么可以搞树形二维dp. 表示以第i个结点为根节点的子树满足最长链小于等于...

树形dp

2020-05-02

4 568

牛客练习赛62 D.牛牛的呱数

大致题意:给定n个数字和p，选择一些将数字拼接成一个新的数字ans(可以重复选择)，ans可被p整除.(n个数字长度总和<=1e6,p<=200 )分析：参考jls代码..%%%九峰大佬.. 考虑p的范围不大，可以写动态规划并且对于每一个数而言模p下的贡献方案最多只有p次,那么我们只需...

dp dp的优化

2020-04-25

0 921