小男娘

分类

题解(2)

/ 注册

全部文章（共44篇）

以防不知道这题可以 O(n) 做

参考铺设道路，我们对于每一个 x 计算 cnt[x]-cnt[x-1] 就做完了使用哈希表可以避免排序复杂度__gnu_pbds::gp_hash_table 比 std::unordered_map 快，并使用 splitmix64 防造数据卡 #include <cctype> #i...

2026-02-09

1 16

题解 | 谍中谍中谍中谍中谍...

朴素做法：对每一个起点跑一遍，用一个布尔数组记录是否访问过，时间复杂度。优化：找出所有的环，答案为最近的环上点。时间复杂度。 #include <iostream> #include <vector> using namespace std; int n; vector&l...

2026-02-04

0 26

题解 | 小红的字符串构造

考虑二十六个字母拆成二十六位，先使用 a 串，同时将变化插入异或线性基，然后用线性基将权值消到 0 #include <array> #include <iostream> #include <valarray> #include <vector> u...

2026-02-03

0 22

题解 | 线性做法

考虑 sum hash给每一个 n/2 以内的数一个随机权值，预处理所有双排列 sum hash 以及前缀 sum hash，根据长度判断是哪个双排列即可 #include <chrono> #include <iostream> #include <random>...

2026-02-03

0 20

题解 | 小红的gcd

两行用分号可以一行 from math import gcd print(int(input()) * gcd(*map(int, input().split())))

2026-01-30

1 28

直接推导即可

如标题所示，考虑路径长度的异或和，路径中间节点的异或全都被消掉，于是其等于一条边路径的异或和。考虑到一大堆数求和一定大于等于其异或和，于是最短路就是一条边路径。于是题目变成了求。先求，发现四个一组异或和为零可以直接消掉，于是答案就只剩下四种情况，分别求即可 #include <iostream...

2026-01-28

0 32

题解 | 【模板】图的结构Ⅰ ‖ 拓扑排序：Kahn

众所周知，拓扑排序可以任意取入度为零的点，故可以用任意数据结构处理然后我们需要字典序最小，自然就用最小堆就可以了 #include <iostream> #include <queue> #include <vector> using namespace std;...

2026-01-23

0 31

单调队列优化

发现 DP 式子除了一个初始价格以外和部分背包类似，于是直接使用相同的方式优化，时间复杂度。 #include <iostream> #include <deque> using namespace std; using ll = long long; ll dp[301...

2026-01-13

0 41

暴力出奇迹

发现可以 bitset 优化，但是自带的 bitset 不是很好实现这些操作于是考虑手写 bitset，将每 64 位压成一个 ull，每次暴力翻转暴力统计即可。这个做法甚至比部分实现不够优秀的线段树跑的还要快。 #include <iostream> using namespace s...

2026-01-08

8 39

题解 | 圣

吸收律：于是可以得到，故答案为所有数的异或和 #include <iostream> using namespace std; int n; void Solve() { int res = false; cin >> n; int a; ...

2025-12-23

3 52