Bernard5

题解

作业(2) 学习笔记(17) 技术教程(45) 期末应试(57) 未归档(17) 赛后分析(7) 题集(15)

/ 注册

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

三棱锥之刻简单计算几何来自专栏

根据发射距离R的不同，可分为四种情况碰不到四个圆圆和三角的交*4 正四面体的全部内表面因为第三种情况忘记*4浪费了一个晚上。具体来说就是计算小三角形的面积，再加上一个最小的扇形面积。重合部分的面积等于 from math import sqrt, acos, pi a, R = ...

计算几何水题

2021-02-01

10 721

图 DFS 来自专栏

tarjan做法显然是违背出题人意图的。本题限制了每个点只有一条出边，所以不存在复杂回路，如果成环，只存在简单环。于是可以直接DFS，如果成环，就把整个回路都置为回路上点的数量。 #include <bits/stdc++.h> #define sc(x) scanf("%lld"...

DFS

2021-01-31

0 438

Sky Garden 计算几何来自专栏

题意有个同心圆，半径分别是，有条直线将这些同心圆切分成等分。求所有交点两两之间的最短距离的和。思路圆心到每个点之间的距离是很好算的单个环内部每个点之间的距离和也是很好算的：枚举两点之间的长度，所有的相邻的点的最短距离和会贡献，所有的间隔一个点的最短距离和也是，直到两点恰好在直径两端的...

计算几何数学 ICPC

2021-01-31

2 589

旅行Journey CF eduRound103 D 来自专栏

题意从0号点到n号点排列在直线上。n条有向边连接着这些点。L表示向左，R表示向右。对于每一个点，求它起点最多可达多少个点。思路首先考虑LRLR相间的情况：在这样的子段上，奇数点（从0开始算）可达子段所有点，偶数点所有点都不可达然后考虑RRRR/LLLL的情况：在这样的子段上，每个点都只能到...

2021-01-30

0 498

最长简单环 CF eduRound 103 C 思维来自专栏

题意给定条链，每条链有个点，表示第条链的第1个点连接上一条链的第几个点，表示第条链的最后一个点连接上一条链的第几个点。问最长的简单环的长度。思路我首先将数据重新处理，是无用的，整体往左移一个位置。这样，表示的就是第条链点分别连接下一条链的第1个点和最后一个点。当重合，会将全图切割成若...

模拟思维

2021-01-30

1 770

Sum of Log 记忆化搜索来自专栏

题意给定和，要求计算思路由于在贡献计算公式中可交换，另外其实就是跳过同时为零的情况，所以可交换。所以对于题目要算什么的理解，其实就是枚举所有的，其对答案的贡献就是的二进制串长。记忆化搜索的本质就是搜索树的复用。 Solution #include <bits/stdc++.h>...

记忆化搜索 ICPC

2021-01-29

3 582

Walker 数学浮点二分来自专栏

题意线段上有两个人，位置和速度分别是。求他们最短把线段覆盖（走）完的时间。 Solution #include <bits/stdc++.h> using namespace std; inline double ct(double x, double pos, double v) ...

二分数学思维 ICPC

2021-01-28

3 595

Mine Sweeper II 贪心思维来自专栏

题意给两个n*m的扫雷图，问能不能至多反转个格子，把图B的的空白区权值和变成和图A相同。思路本题是一道CF式的思维题。比赛的时候没做出来，遗憾。既然是CF式的，样例必然是误导性的。其实就是把B变成A或者A的反图即可。下面证明A和A的反图权值和相同：雷对权值的贡献是雷的八个方向上一共...

构造贪心思维 ICPC

2021-01-27

2 646

Gitignore 贪心思维 STL 来自专栏

题意给n个需要忽视的目录，m个需要保护的目录，求gitignore的最小行数 Solution 用保护去检索ignore。 #include <bits/stdc++.h> using namespace std; int t, n, m; vector<string> v...

模拟字符串贪心 ICPC 思维

2021-01-27

2 530

Charging 来自专栏

题意数轴上有一共个点，个区间分别是。设为所选取的区间数量，为所有所选取的区间的交集长度。求的最大值。最优解标程为线段树，复杂度为 qingzhu思路将所有线段按左端点升序排序。枚举区间：枚举左端点，二分枚举右端点。收纳所有左端点小于等于当前的的线段的右端点。即线段里有可能有的线段。如果...

树状数组线段树二分贪心思维

2021-01-24

4 755