计算几何 学习笔记

跟着这个题库完善自己的模板。 三角库函数sin(x)/cos(x)/tan(x) 三角函数 asin(x)/acos(x)/atan(x) 反三角函数 atan2(x,y) 返回点 $(x,y)$ 的反正切值,以弧度为单位。返回值的范围是 $[-\p...

Algorithm

XCPC 2024

2024.8.25 组队由我 SUNCHAOYI 和两位大佬 oahgnail, Erusel 组成。 【说句闲话,由于组队有点匆忙,我和 Erusel 愣是花了一下午从新生群中的强省一个个人肉搜索找到的队友。】 好了,队名还是要乱搞的,于是就有了:...

Journal

求 $[1,n]$ 的异或和

部分参考 此处。 通过打表可以找到规律,给出结论: \oplus_{i = 1}^{n} i =\left\{ \begin{aligned} n \ (n \equiv 0 \bmod 4)\\ 1 \ (n \equiv 1 \bmod 4)\\...

Algorithm

题解:P10864 [HBCPC2024] Genshin Impact Startup Forbidden II

【题目大意】 模拟围棋的落子过程,然后根据围棋的气来计算每一步落子后被提子的个数。 当然强调了,每一步的落子没有限制,也就有可能某个棋子刚落下去后会直接被提掉。 【思路】 直接在落子后暴力搜索计算出相邻的棋子所在块的气,最后在计算落子位置所在块的气。...

Solution

题解:P10865 [HBCPC2024] Genshin Impact Startup Forbidden III

一个位置最多只有 $3$ 条鱼,而所有有鱼的格子不超过 $10$,所以我们可以写一个 $4$ 进制的状态压缩。设 $dp_s$ 表示 $k$ 个有鱼的格子中受到炸弹影响后的状态为 $s$ 时所需要的最小的炸弹的数量。 同时,由于一个炸弹只能影响到五个...

Solution

题解:P10701 [SNCPC2024] 致命公司

看完题目后盲猜二分答案()。 题目的难点显然是如何分配凝视的时间于不同的通道,以及如何在一次凝视时将通道内的子弹进行标记。 二分时刻 $t$,对于所有的子弹,有以下情况: 在 $t$ 时刻,该子弹仍未出现,忽略该子弹。 从子弹出现到 $t$ 时刻,...

Solution

题解:P9778 [HUSTFC 2023] 基因编辑

将题意进行简单的转换,枚举 $S_k$,然后再枚举其中的断点 $i$,将其分为 $S_k[:i]$ 和 $S_k[i + 1:]$。因此只需要求出前缀为 $S_k[:i]$ 和 $S_k[i + 1:]$ 的乘积,不难想到对前缀和后缀分别建立 $\t...

Solution

NOIP 2023 摆烂记

前言已经高三了,但是还是想玩一下,抽空写点题目,顺便记录一下。 【前情提要:本文的撰写具有滞后性,因此流失了大量细节。】 $2023.9.16$初赛,完善程序做得稀烂,好在 $60+$ 还是过线了。真不敢相信今年浙江线会这么低,只有 $50.5 \r...

Journal

题解:CF509C Sums of Digits

一道很好的构造题。简单来说,给你一个序列 $\{b\}$,$b_i$ 表示 $a_i$ 各位数字之和,请还原出序列 $\{a\}$。有两个附加条件,一是序列 $\{a\}$ 单增,二是 $\{a\}$ 尽可能的小。 对于第二个条件,很容易想到要贪心求...

Solution

题解:CF59E Shortest Path

对于 $k$ 对有序的三元组 $(x,y,z)$ 为不能走的路线。本题对选择恰当的工具存储三元组有着较高的要求。 首先想到的是 map 与 set,令 set <int> ban[x][y] 记录形如 $x \to y \to z_i$ ...

Solution
15678916