BeauWill

分类

/ 注册

全部文章（共49篇）

题解 | 游游的二进制树

#include <iostream> #include <vector> #include <string> #include <functional> using i64 = long long; int main() { std::ios...

2026-01-27

0 59

题解 | 音符

#include <iostream> #include <vector> #include <numeric> #include <algorithm> int main() { std::ios::sync_with_stdio(false)...

2026-01-26

0 58

题解 | 邮递员送信

由于邮递员只能一封一封地送信，为了使总时间最少，每次应该走最短路到达各个路口，然后从各个路口返回时也应走最短路回到邮局。但是由于道路是单向的，因此邮递员出发的时候是单源最短路，可以用堆优化版dijkstra算法计算最短路，而回来的时候是多源最短路，但我们可以反向思考，若建立的是反图，邮递员回邮局的路...

2026-01-23

1 74

题解 | 二进制不同位数

计算m和n二进制表示上的不同位数，等价于计算m异或n的值中二进制'1'的个数C++版本 #include <iostream> int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std:...

2026-01-22

1 58

题解 | 【模板】静态区间和（前缀和）

谁说前缀和不是dp(手动滑稽)我们发现前i个数的和pre[i]就等于前i-1个数的和pre[i-1]加上第i个数a[i]状态设计为pre[i]，表示前i个数的前缀和转移方程为pre[i] = pre[i-1]+a[i]再考虑查询，我们发现要统计[l,r]区间内的数字之和，如果取pre[r]就多算了前...

2026-01-21

0 52

题解 | 小红删数字

考虑线性dp状态设计为dp[i][j]，表示考虑了后i个元素，结果为j的所有方案数我们发现dp[i+1][(a[i+1]+j)%10]和dp[i+1][(1LL*a[i+1]*j)%10]可以从dp[i][j]转移过来，转移方式就是前者直接加上后者的值，估转移方程为dp[i+1][(a[i+1]+j...

2026-01-20

1 52

题解 | 有趣的区间

根据二进制按位或的性质，我们不难发现"有趣的区间"就是至少包括一个奇数的区间。我们考虑枚举数组A下标i从1~n，枚举的时候我们只统计以当前下标为区间右端点的答案。（可以证明，这样统计是不重不漏的）如果当前枚举的数A[i]是奇数，那么所有区间[j,i]，j取遍1~i，都是"...

2026-01-17

2 56

题解 | 【模板】拓扑排序

#include <iostream> #include <vector> #include <queue> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); ...

2026-01-16

1 64

题解 | 小A取石子

直接给结论，不考虑作弊的情况下，所有石子数的异或和不为0则先手胜利，否则后手胜利。此结论的推导和证明请自行搜索了解。若不作弊且先手的小A胜利即此时异或和xorSum不为0，则直接输出"YES"，否则考虑小A能否作弊（因为不作弊肯定输，所以看作弊能否改变输的局面）。对于这些堆石子，...

2026-01-15

2 79

题解 | 子数列求积

题目是离线区间查询，想到使用前缀和比较合适。对于区间[l,r]的所有ai乘积，若暂不考虑取模，它的值应该等于区间[1,r]的所有ai乘积除以[1,l-1]的所有ai乘积即pre[r]/pre[l-1]。故预处理pre[i]表示前i个数相乘并模1E9+7的值。由于此题需要对1E9+7取模，因此查询时的...

2026-01-13

1 58