Spy97

分类

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 线段树(7) 莫队(1) 计算几何(30) 贪心(2)

/ 注册

全部文章（共151篇）

codeforces 1025F Disjoint Triangles

题意：给出n个点，保证没有三点共线，求可以组成多少对不相交的三角形。题解：对于两个不相交的三角形A、B，我们发现有且仅有两条共切线能使得直线两侧是完整的三角形。我的思路就是枚举直线，直线上已经有2个点了，假设直线两侧分别有x、y个点，那么可行的方案就是一侧选两个点，和直线上的点构成三...

2018-08-24

0 486

HDU 6419 Rikka with Rain （暴力）

题意：有一个多边形，提问m个圆，求圆被多边形完全包含需要移动的最少距离。题解：做过的一道目前最难的几何题，充分发挥了暴力的思想。看到这个问题的第一想法就是，多边形向内缩R（圆的半径），然后求圆心到缩小的多边形的最短距离即可。方法就是枚举新的多边形的线段，求点到线段的最短距离。那么...

2018-08-23

0 418

HDU 6408

题意：一个公司生产电脑，生产n个月。每个月生产时，原材料的价格、加工费的价格、生产能力、客户需求量是不同的。每个月可以多生产一些电脑，也可以多购买一些原材料储存起来，但每个月储存原材料、电脑的花费也是不一样，而且每个月储存电脑的仓库容量还不一样。问在满足客服要求的前提下，最经济的花费。题解：...

2018-08-18

0 424

HDU 6398

题意：给一个三角形，放在一个给定宽度的无线长的矩形中，要求占得长度最小。题解：分两种情况，一是三角形的边与矩形的边重合，二是三角形的两个点卡在矩形的两条边上。对于第一种情况，枚举底边，算出第三点在底边的投影，就知道要占据的最小宽度，若小于等于矩形宽度，再算出占据的高度。对于第二种...

2018-08-18

0 502

HDU 6393

题意：一个n个点，n条边的图，2中操作，1是将某条边的权值更改，2是询问两点的最短距离。题解：由于n个点，n条边，所以是树加一个环，将环上的边随意取出一条，就是1颗树，以取出的边的一个端点为根，建立有根树。虚线就是取出的边。红色为环上的边。对于更改边的权值的操作，用dfs序+区...

2018-08-15

0 497

HDU 6396

题意： n个怪兽，每个怪兽有5个属性，只有当所有的5个属性都大于等于怪兽时，才能消灭怪兽，每消灭一个怪兽，5个属性都会提升一点，求消灭的怪兽数目和最后5个属性的值。题解：暴力。。。我们将消灭一个怪兽分解成5步，即大于等于第1个属性，大于等于第2个属性。。。大于等于第5个属性。建立5...

2018-08-13

0 415

codeforces 958E3

题意：给出n个A类点和n个B类点，AB配对，要求连线不能有交点，输出方案。题解：感觉是个匹配，想不到解法，学习了别人的代码，原来是分治，长知识了。。。分治的思想是确定一个配对后，然后去解决确定配对的左边和右边。那么如何保证两边一定有解呢？方法比较巧妙。假设当前处理的区间为，我...

2018-08-11

0 365

扫描线

一、矩阵面积并（HDU 1542） #include<bits/stdc++.h> #define N 2010 using namespace std; struct seg { int l,r,h,d; seg(){} seg(int l,int r,...

2018-08-09

0 336

HDU 6365

题意： n个障碍物在空中，每个障碍物都有一个防御值，从原点射激光，激光可以设定攻击力，激光只能消灭防御值小于攻击力的障碍，遇到不能消灭的障碍时就会消失，现在要消灭所有障碍，使激光的攻击力的和最小。题解：区间型动态规划首先，激光一定经过线段的端点，所以最多有2n个射击方向表示消灭掉所...

2018-08-09

0 401

HDU 6363 bookshelf

题解：我们枚举gcd，求score 的期望。首先，多个二进制下每位都是1的数的gcd的求法：如 111111 （2）和 1111 （2）gcd为 11 （2）因为他们的长度 6 和 4 的gcd 为 2 所以令求gcd（f（a），f（b））= f（gcd（a，b））而a...

2018-08-08

0 339