lifehappy

题解

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

/ 注册

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

brz的函数

brz的函数 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 10; int prime[N], mu[N], ans[N], cnt, n...

2020-11-10

6 594

[SDOI2014]数表

[SDOI2014]数表 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int pr...

2020-11-09

2 597

[SDOI2015]约数个数和

[SDOI2015]约数个数和 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e4 + 10; int...

2020-11-09

4 572

[SDOI2017]数字表格

[SDOI2017]数字表格 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10, mod =...

2020-11-09

3 682

Rinne Loves Sequence

Rinne Loves Sequence 思路写完后看了一下ac代码，果然就我的最暴力了。代码 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long...

2020-11-09

3 758

Lady Layton with Math（杜教筛）

Lady Layton with Math /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 10...

2020-11-07

3 686

求和

求和利用dfs序在子树上的连续性，然后通过单点修改，区间查询即可，这点只要用一颗树状数组即可完成。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long ...

2020-11-07

4 730

Tree Requests（dsu on tree）

Tree Requests 经典的树上启发式合并题目了（其实就是瞎暴力）。对于一颗有根树，我们先做一次dfs找到每个节点的重儿子，然后在答案统计的时候优先遍历轻儿子，不保留答案，最后遍历重儿子保留答案。这颗树显然我们要维护的信息就是每一层字母的奇偶性，所以我们直接在每一层开一个30大小的bits...

2020-11-07

5 735

Military Problem

Military Problem DFS序模板题了，l[rt]标记rt节点第一次进入，r[rt]表示rt节点退出，然后只要判断l[rt] + k - 1 是否小于等于r[rt]即可。 /* Author : lifehappy */ #include <bits/stdc++.h> ...

2020-11-06

4 803

金字塔（区间dp）

金字塔利用dfs序的通性，如果[l, r]是一颗完整的子树，一定有str[l] = str[r]，接下来就是考虑如何划分子树了。考虑对[l, r]的子树进行划分，枚举中间划分值mid，那么因为dfs序一定有str[l] = str[mid] = str[r]。我们定义dp[l][r]，为区间[l...

2020-11-05

4 624