lifehappy

题解

未归档(1) 每日一题(2)

/ 注册

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

小V和gcd树

小V和gcd树树上问题，每次询问与两点有关，可以确定应该使用树链剖分来求解了。这个问题中涉及到边的查询，树链剖分中有一个很常用的操作就是边权下放到点权上，但这个操作一般是对有根树而言的，当然我们虚拟号节点为跟节点也是一样的。我们假设这棵树的根节点为号节点，然后把所有的边权下放到其对应的节点上...

2020-12-22

2 999

Beautiful Subarrays

Beautiful Subarrays 有所以我们可以先求一遍异或前缀和，然后再通过枚举右端点，去查找有多少个左端点符合要求。假设我们当前枚举到这个位置，前个数的异或前缀和是，我们要查找异或值大于等于的, 这里我们可以去找一个，满足，这个时候大于等于的数就是满足要求的数了，这个操作我们可以通过...

2020-12-22

2 660

阔力梯的树

阔力梯的树一般树上问题的求解有三种方法：点分治、树链剖分、。这道题目中，结实程度是在子树上的定义，所以容易想到，所以我们可以考虑如何通过来维护子树信息。如果使用来考虑求解，我们必然要涉及到点权插入到一个升序的数组中，考虑插入这个点之后，整体结实程度如何变化，大致分为一下几步。一、第一个权值插...

2020-12-22

2 770

小阳的贝壳

小阳的贝壳这里最难维护的应该是区间了，但是我们有一个结论，所以这一步可以转换为维护整个序列的差分。对于操作一：我们只要对端点的值增加，对端点的值减小。对于操作二：我们只要得到差分数组里的绝对值最大值就行了。对于操作三：我们首先要得到，然后得到这一段差分序列的，然后再于求一个即为答案。对一整...

2020-12-21

5 733

算式子

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 10; ll ans1[N], ans2[N], cnt[N], sum[N]; int n, m; ...

2020-12-20

3 477

禁止动规

选出来的个数能凑成或者必然有一个性质，。$$ #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const int N = 2e7 ...

2020-12-20

2 662

老瞎眼 pk 小鲜肉

老瞎眼 pk 小鲜肉利用异或前缀和，离线处理。我们定义为值为的异或前缀和最后一次出现在上。我们通过枚举有区间，然后把异或相同的区间长度存在上，之后我们只要在区间查询区间最小值即为答案了。 #include <bits/stdc++.h> #define mid (l + r &g...

2020-12-16

2 826

函数的魔法

函数的魔法裸的直接写就好了。 #include <bits/stdc++.h> using namespace std; const int mod = 233; int vis[mod + 10]; typedef pair<int, int> pii; int...

2020-12-14

2 730

[SCOI2015]国旗计划

[SCOI2015]国旗计划注意一个关键点，没有一个区间是包含在另一个区间的，这意味着区间之间要么相交要么相离，当有一个区间一定加入时，我们可以二分查找去得到下一个区间的，但是这样速度显然太慢了，所以我们利用倍增来优化。定义表示号节点为左端点，共有条线段连在一起最有可到达的坐标。然后只需要从小到...

2020-11-27

3 833

A and B and Lecture Rooms

A and B and Lecture Rooms 题意要求我们找有多少个点满足，输出点的数量即可。首先特判无解的情况就是为奇数时，接下来我们讨论有解的情况，大致分为两类。首先我们一定可以在的路径上找到一个点满足要求。这个点不在上：如图我们要找的是(5, 6)的满足要求的点有多少个，显然3是...

2020-11-26

3 574