威风镰鼬

题解

/ 注册

全部文章 / 题解（共151篇）

题解 | #B题#

思路看作无向图的时候，它是一个环，因此遍历每个点只有顺时针和逆时针两种。所以先跑一次无向图的dfs确定顺序，然后在有向边的时候如果方向不对就加上其权值，得到修改代价，答案取一个min就可以了。代码 #include<bits/stdc++.h> using namespace s...

2022-02-05

2 367

题解 | #大家一起来数二叉树吧#

思路第一时间注意到了组合数，发现能过样例，然后就交了，果不其然wa了。看这个数据也不像，于是还是考虑DP思路。（爆搜也不像，得20左右）对于一个子树来说，它的构造方案数实际上就是左子树构造数×右子树构造上，并且对于二叉树来说，左子树的节点数表示出来了，右子树也知道了，所以我们写出dp转移式 ...

2022-01-25

1 383

题解 | #被3整除的子序列#

思路 dfs的数据范围只能出到20左右吧，这道题肯定是要用记忆化思想的。我们先处理一下每一位数字，将他们都模3，然后我们知道一个数能被3整除，那么每一位加起来就是3的倍数。因此我们dp[i][j]表示前i位数字%3余数为j的方案数。首先我们子序列不选第i位必有dp[i][j]=dp[i-1][j...

2022-01-24

3 555

题解 | #音乐研究#

思路暴力枚举，O(nm) 注意要等长，所以母串最多到n-m 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits...

2022-01-24

0 507

题解 | #集合中的质数#

思路考察容斥定理。质因子最多20个，所以我们可以状压一下，枚举每次选定因子的情况。考虑只有一个因子pri的情况下，1~m个数中总共由m/pri个，那么下一次选定两个因子p1,p2时，就要减去m/(p1*p2)个，加减取决于选定因子的个数。代码 #include<bits/stdc++.h&...

状压位运算数论

2021-11-25

3 406

题解 | #托米的游戏#

思路对于每个节点来说，对答案的期望贡献都是其深度的倒数。因此，我们只要将每个点贡献累加就能得到最终期望。用快速幂求每个贡献(1dep[i]\frac{1}{dep[i]}dep[i]1)的逆元，再相加就是最终答案。代码 #include<bits/stdc++.h> #defin...

数学概率数论

2021-11-25

2 525

题解 | #黑猫的小老弟#

思路小老弟树产生的分数都是互质的，由于题目规定第n行产生的分子分母不超过n,而且经过简单推导可以猜测第n代可以表示出分子分母不超过n的所有互质对，那么我们就可以用欧拉函数来做。直接规定第n代产生的数就是欧拉函数的n行前缀和。代码 #include<bits/stdc++.h> #de...

数论

2021-11-25

2 491

题解 | #阶乘分解#

思路我们普通求阶乘的时候，边乘边除质数，就可以保证不爆范围。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e6+7; ...

数论

2021-11-24

1 420

题解 | #约数个数的和#

思路对数论初学者来说可能有点困难，但想通了会觉得相当简单。我们考虑每个数是多少个数的约数，然后贡献到答案中即可，那么对于n个数，数字p是n/p个数的约数，答案直接加上即可。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #def...

数论

2021-11-24

3 425

题解 | #不存在的树#

思路就是树链剖分+线段树的板子，但是因为眼疾看少了”多组数据“导致一直WA（哭了不会的可以看一下我的这篇博客：https://editor.csdn.net/md/?articleId=121182009 代码 #include<bits/stdc++.h> #define inf ...

树链剖分线段树

2021-11-24

1 453