塞蒙尘

题解

/ 注册

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

【每日一题】子序列

Solution 尝试把转换一下：先对两边开次方根，得到；再对两边开次方根，得到；显然，若、，那么有。所以这题就是个变形的"上升子序列个数"，直接dp即可。 n, mod = int(input()), int(1000000007) a = list(map(int, input().split(...

2020-04-23

1 1033

【每日一题】Kth Number

Solution 二分答案，考虑如何判定是否符合要求：若一个区间里有个以上的数大于等于，那么这个区间的第大数大于等于；若有个以上的区间的第大数大于等于，那么答案；否则，答案。双指针扫一遍数组，统计一下第大数大于等于的区间个数即可。复杂度。 Code: #include <bits/...

2020-04-21

1 838

牛客挑战赛39

A - 聚会容易想到，两个传送门放在不同半轴肯定不如放在同一半轴好，所以其中一个门肯定是放在处的；设为正半轴上的朋友们的坐标，为负半轴上的朋友们的坐标；设为另一个门放在正半轴时，正半轴的朋友全都走到处需要的时间；设为另一个门放在负半轴时，负半轴的朋友全都走到处需要的时间；那么答案即为怎么求和？ ...

2020-04-18

3 765

【每日一题】华华给月月准备礼物

Solution 设为长度取时，能得到的木棍数。因为长度为的木棍最多能分成根长度为的木棍，所以。显然这个函数是单调下降的，所以可以二分找到最大的满足的。 Code #include <bits/stdc++.h> using namespace std; using ll = long...

2020-04-16

1 667

【每日一题】逆序对

Solution 当<>时，其他个位置的取值方案都有种，所以<>会出现在个长度为的01串中；同理可得<>、<>、...、<>都出现在个长度为的01串中。所以答案即为。 Code n, mod = int(input()), int(1e9 ...

2020-04-15

1 788

牛客算法周周练2

A - 相反数 Solution 签到题，直接std::stoi即可。 Code #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { cin.sync_with_stdi...

2020-04-14

7 1113

【每日一题】Treepath

Solution 简单的树形dp。设为点的子树中，以为端点且长度模为的路径数量。考虑如何合并点的孩子的结果，因为从的子树内走到的路程比到的路程长个单位，所以有：其中、为合并后的结果；原先已有条以为端点长度为偶数的路径，与条以为端点长度为奇数的路径合并可以得到条长度为偶数的路径；同理，原先...

2020-04-14

1 804

【每日一题】Xorto

Solution (用表示异或运算) 因为当且仅当时才有，所以题目要求的就是有多少对区间的异或和相等且不重叠。设为右端点小于且异或和为的区间的个数，此时，若区间的异或和为，那么它对答案的贡献为。枚举，首先对所有左端点为的区间计算贡献，然后利用右端点为的区间来更新。总复杂度。 Code #inc...

2020-04-13

2 885

【每日一题】Accumulation Degree

Solution 普通的树形dp。首先设为从点向的子树推流，所能达到的最大流量；那么有：其中为的孩子，为和之间的边的流量上限。设为从向整棵树推流，所能达到的最大流量，那么有：作两遍dfs，分别求出和的值，取输出即可，复杂度。 Code #include <bits/stdc++.h...

2020-04-12

2 904

树学

Solution 十分简单的换根dp。首先随便选择一个点作为根，计算出它的结果；考虑它的一个相邻结点作为根时的结果与之间的关系：当根从转移到时，子树内的点到根的距离减少、子树外的点到根的距离增加，如果设为以为根时的子树大小，那么。按照式子暴力dfs转移即可，复杂度。 Code #include...

2020-04-12

1 816