BeauWill

分类

/ 注册

全部文章（共24篇）

题解 | 小红删数字

考虑线性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 21

题解 | 有趣的区间

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

2026-01-17

2 24

题解 | 【模板】拓扑排序

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

2026-01-16

1 23

题解 | 小A取石子

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

2026-01-15

2 28

题解 | 子数列求积

题目是离线区间查询，想到使用前缀和比较合适。对于区间[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 25

题解 | 切题之路

模拟题，解释下题目：circle只做时间来得及的简单题(难度<a)，rqy做时间来得及的困难题(难度>=b)和简单题(难度<b)，其中困难题rqy需要两倍的时间来处理。注意数据范围，然而坑的是题目没有明说每个题做题时间和难度的范围，实测不开long long会卡一组测试点，故必须开...

2026-01-11

2 30

题解 | 小红的平滑值插值

首先考虑当前数组a的平滑值小于k的情况，这时我们可以选取任意的区间[i,i+1]，其中i<=1<=n-1，选择在下标i和i+1中间插入值min(a[i],a[i+1])+k，就可以构造出数组a的平滑值刚好等于k的情况。再考虑当前数组a的平滑值大于k的情况，此时存在若干区间[j,j+1]使...

2026-01-10

2 28

题解 | 牛牛喜欢字符串

我们发现牛牛实际上只关心每组对应位置上的字母是否相同，那么就会很自然且贪心地想到，把出现最多的那个字母不动，修改其他字母。首先统计每组的第i个位置各个字母的数量，存储方式可以用数组或者哈希表来存储。然后枚举0~k-1个位置，每次ans都累加所有字母数(实际上就是n/k，有n个字母，每k个字母一组，一...

2026-01-09

2 25

题解 | 区间取反与区间数一

遇到区间问题，考虑双指针，前缀和，树状数组，线段树等算法或数据结构。而本题使用懒标记线段树可以轻松维护所需信息。jiangly老师的懒标记线段树的模板（我删去了一些此处用不到的功能）： /* *此懒标记线段树是0-base的，用于构造的init_数组也是0-base的 *区间查询和区间修改的区间...

2026-01-08

1 24

题解 | 明日DISCO

对于每个位置，我们都贪心的尝试修改，如果可以修改，就把它修改为四个方向中的最大值和最小值(具体看它满足哪个条件)。其实这里修改后的值不为0，已经可以输出"NO"并return了。这是因为第0,n+1的行和列是不能修改的，要想使整个正方形棋盘的值都相等，只能整个棋盘上的数都为0。而...

2026-01-07

1 26