sky3141

分类

题解(13)

/ 注册

全部文章（共13篇）

题解 | #画图#

M. 画图知识点：模拟看起来很吓人，实际就是个模拟。实现的时候最好想一下，如何避免过多的分类讨论。提供一种较为优雅的绘制线段写法，绘制矩形的操作可以复用这个函数，调用4次即可。 void draw_line(int x1, int y1, int x2, int y2) { &...

C++ Java Python3 模拟

2024-07-02

1 142

题解 | #分煎饼#

L. 分煎饼知识点：计算几何、二分直接计算能平分所有圆的直线的方程比较困难，但是给定一条直线，分别计算两侧的圆的面积和是相对容易的。一条直线可以用两个参数确定，考虑固定住直线的一个参数，在调整另一个参数的过程中，如果直线两边的面积是单调变化的，就可以使用二分来解决这个问题。举个例子，可以固定...

C++ Java Python3 计算几何二分

2024-07-02

2 187

题解 | #翻转排序#

K. 翻转排序知识点：选择排序、排列的性质重要发现：可以通过翻转之后再翻转来交换 , 两个元素的位置，而不影响其他位置。维护每个位置的元素、以及每个元素在什么位置这两个数组，每次把元素换到第个位置上，同时更新这两个数组中的信息。如果没发现这个性质，也可以使用 Splay 等...

C++ Java Python3 选择排序

2024-07-02

1 179

题解 | #初等元素论#

J. 初等元素论知识点：排序、贪心、枚举、前缀和先把伤害分为冰火两类，分别从大到小排序。显然，如果某种元素有次伤害要打反应，那一定是用伤害最高的个技能去打。枚举用火元素触发融化反应的次数，反应需要消耗个火元素技能和个冰元素技能。假设打完反应还剩个火元素技能和个冰元素...

C++ Java Python3 排序贪心枚举前缀和

2024-07-01

0 226

题解 | #洗牌#

I. 洗牌知识点：数组、模拟直接暴力模拟就行。标程 C++ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullp...

C++ Java Python3 模拟

2024-07-01

0 202

题解 | #点燃星海#

H. 点燃星海知识点：深搜/广搜/并查集实际上就是计算连通块的数量。搜索入门题，没什么要讲的地方。也可以用并查集进行合并，不用搜索。标程 C++ #include <bits/stdc++.h> using namespace std; constexpr int N = ...

C++ Java Python3 深度优先搜索广度优先搜索并查集

2024-07-01

0 213

题解 | #区间翻转#

G. 区间翻转知识点：时间复杂度、模拟暴力模拟的时间复杂度是，空间复杂度是，显然是过不了的。不难发现实际上这个序列的信息量很少，只需要维护所在的位置就行。如果当前的位置在区间里，则翻转后的位置为，如果当前位置不在区间里，则位置不变。时间复杂度：标程 C++ #...

C++ Java Python3 模拟

2024-07-01

0 167

题解 | #买蛋糕#

F. 买蛋糕知识点：分支、循环比较入门，没什么好讲的。由于的范围不大，如果还没学到循环，可以手敲个分支。标程 C++ 循环版 #include <bits/stdc++.h> using namespace std; int main() { ios::syn...

C++ Java Python3

2024-07-01

0 258

题解 | #激活锚点#

E. 激活锚点知识点：最小生成树对个传送锚点的坐标建无向完全图，边权为两点间的距离。求出最小生成树的权值。再加上距离起点最近的传送锚点的距离，即为答案。最小生成树用 Prim 算法（时间复杂度：）或 Kruskal 算法（时间复杂度：）都能过。常见错误解法：把起点坐标和传送锚点的坐标...

C++ Java Python3 最小生成树

2024-07-01

0 191

题解 | #归零#

D. 归零知识点：动态规划/记忆化搜索记表示数字的所有数位之和，表示数字的答案。则有 f[i] = f[i – S(i)] + 1 初始状态：f[0] = 0 先把以内的预处理出来，每个询问回答即可。标程 C++ #include <bits/stdc++.h...

C++ Java Python3 动态规划

2024-07-01

0 196