BeauWill - 个人主页动态

01-27 09:19

已编辑

#include <iostream> #include <vector> #include <string> #include <functional> using i64 = long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n; i64 l,r; std::cin >> n >> l >> r; std::string s; std::ci...

0 点赞评论收藏

01-26 13:40

浙江外国语学院算法工程师

题解 | 音符

#include <iostream> #include <vector> #include <numeric> #include <algorithm> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n,q; std::cin >> n >> q; std::vector<int> b(n); for(int i = 0; i < n; i++){ std...

0 点赞评论收藏

01-23 02:38

浙江外国语学院算法工程师

题解 | 邮递员送信

由于邮递员只能一封一封地送信，为了使总时间最少，每次应该走最短路到达各个路口，然后从各个路口返回时也应走最短路回到邮局。但是由于道路是单向的，因此邮递员出发的时候是单源最短路，可以用堆优化版dijkstra算法计算最短路，而回来的时候是多源最短路，但我们可以反向思考，若建立的是反图，邮递员回邮局的路就变成了从邮局出发到各个路口的单源最短路，那此时也可用堆优化版dijkstra算法来计算。那么最后的答案为∑dist1[i]+dist2[i]，2<=i<=n，其中dist1为正向建图的dijkstra计算出的距离函数，而dist2为反向建图的dijkstra计算出的距离函数实现：我习惯...

0 点赞评论收藏

01-22 00:30

浙江外国语学院算法工程师

题解 | 二进制不同位数

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

0 点赞评论收藏

01-21 10:19

已编辑

浙江外国语学院算法工程师

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

谁说前缀和不是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]就多算了前l-1个数之和，而前l-1个数之和恰好就是pre[l-1]，故查询的结果是pre[r]-pre[l-1]实现：C++可以用std::partial_sum计算前缀和，该函数在<numeric>头文件中，C++20开始支持正好最近也在学习Python，贴一份C++代码，再贴一份Python...

0 点赞评论收藏

01-20 11:59

已编辑

浙江外国语学院算法工程师

题解 | 小红删数字

考虑线性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)%10] += dp[i][j]dp[i+1][(1LL*a[i+1]*j)%10] += dp[i][j]那么此时再枚举0~9，就是对应0~9所有情况的方案数了，而dp[n]数组就是我们要的答案。实现：虽然dp的题下标一般从1开始，但是此题从0开始影响也不大，我此处的代码是0base；从后往前考...

0 点赞评论收藏

01-17 00:46

已编辑

浙江外国语学院算法工程师

题解 | 有趣的区间

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

0 点赞评论收藏

01-16 11:35

浙江外国语学院算法工程师

题解 | 【模板】拓扑排序

#include <iostream> #include <vector> #include <queue> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n,m; std::cin >> n >> m; std::vector<std::vector<int>> adj(n+1);//邻接表 std::vector<int> in(n+1);//入度...

0 点赞评论收藏

01-15 02:41

已编辑

浙江外国语学院算法工程师

题解 | 小A取石子

直接给结论，不考虑作弊的情况下，所有石子数的异或和不为0则先手胜利，否则后手胜利。此结论的推导和证明请自行搜索了解。若不作弊且先手的小A胜利即此时异或和xorSum不为0，则直接输出"YES"，否则考虑小A能否作弊（因为不作弊肯定输，所以看作弊能否改变输的局面）。对于这些堆石子，若想从中的某堆石子拿走k个石子，前提是存在一堆石子的数量大于等于k，否则小A无法作弊。再考虑可以作弊的情况，他(她)可以选择某堆大于等于k的石子拿走k个石子，这样的操作的贡献实际上就是对异或和xorSum再异或k（具体证明请自行分析），最后判断此时的异或和xorSum是否不为0，不为0则小A胜利输出...

0 点赞评论收藏

01-13 21:19

已编辑

浙江外国语学院算法工程师

题解 | 子数列求积

题目是离线区间查询，想到使用前缀和比较合适。对于区间[l,r]的所有ai乘积，若暂不考虑取模，它的值应该等于区间[1,r]的所有ai乘积除以[1,l-1]的所有ai乘积即pre[r]/pre[l-1]。故预处理pre[i]表示前i个数相乘并模1E9+7的值。由于此题需要对1E9+7取模，因此查询时的除法应使用逆元来计算，可以使用快速幂求逆元。 #include <iostream> #include <vector> constexpr int P = 1E9+7; int quickPower(int a,int b){ int res = 1; for(; b; a...

0 点赞评论收藏

01-11 00:37

已编辑

浙江外国语学院算法工程师

题解 | 切题之路

模拟题，解释下题目：circle只做时间来得及的简单题(难度<a)，rqy做时间来得及的困难题(难度>=b)和简单题(难度<b)，其中困难题rqy需要两倍的时间来处理。注意数据范围，然而坑的是题目没有明说每个题做题时间和难度的范围，实测不开long long会卡一组测试点，故必须开long long。遍历一遍1~n，时间复杂度为O(n)，不会超时。 #include <iostream> #include <vector> using i64 = long long; int main() { std::ios::sync_with_stdio(fal...

0 点赞评论收藏

01-10 00:32

已编辑

浙江外国语学院算法工程师

题解 | 小红的平滑值插值

首先考虑当前数组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]使得abs(a[j+1]-a[j])>k，思考一下如何插值可以使得总答案次数最小，我们会想到贪心地插差值绝对值刚好为k的数会比较合适。举例：如样例中下标1的值a[1]=1和下标2的值a[2]=4，它们差值绝对值为3，我们就可以插入一个值min(a[1],a[2])+k；再看样例中下标为3的值a[...

0 点赞评论收藏

01-09 00:20

浙江外国语学院算法工程师

题解 | 牛牛喜欢字符串

我们发现牛牛实际上只关心每组对应位置上的字母是否相同，那么就会很自然且贪心地想到，把出现最多的那个字母不动，修改其他字母。首先统计每组的第i个位置各个字母的数量，存储方式可以用数组或者哈希表来存储。然后枚举0~k-1个位置，每次ans都累加所有字母数(实际上就是n/k，有n个字母，每k个字母一组，一共分成了n/k组)减去出现最多的那个字母的数量。时间复杂度为O(max{n,k*26})，n和k的数据量最大为1E6，那么最坏情况下需要处理2.6E7次O(1)的操作，使用C++不会超时。 #include <iostream> #include <vector> #incl...

0 点赞评论收藏

01-08 02:59

浙江外国语学院算法工程师

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

遇到区间问题，考虑双指针，前缀和，树状数组，线段树等算法或数据结构。而本题使用懒标记线段树可以轻松维护所需信息。jiangly老师的懒标记线段树的模板（我删去了一些此处用不到的功能）： /* *此懒标记线段树是0-base的，用于构造的init_数组也是0-base的 *区间查询和区间修改的区间[l,r)皆为左闭右开，也为0-base */ template<class Info, class Tag> struct LazySegmentTree { int n; std::vector<Info> info; std::vector<Tag> tag; ...

0 点赞评论收藏

01-07 00:26

已编辑

浙江外国语学院算法工程师

题解 | 明日DISCO

对于每个位置，我们都贪心的尝试修改，如果可以修改，就把它修改为四个方向中的最大值和最小值(具体看它满足哪个条件)。其实这里修改后的值不为0，已经可以输出"NO"并return了。这是因为第0,n+1的行和列是不能修改的，要想使整个正方形棋盘的值都相等，只能整个棋盘上的数都为0。而且一个点已经像上述被修改过，无论后续的点怎么修改，也不能被二次修改了。遍历结束后说明可以使棋盘上的数均相等，输出"YES"。 #include <iostream> #include <vector> int main() { std::ios::sync...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：