19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

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

Round Numbers 来自专栏

题意：求以内有多少个数的二进制位里的数量大于的数量，数据范围。思路：把转为二进制，记忆化搜索二进制数，（写数位一定要看清参数，参数写反把自己搞蒙了，血亏）。二进制的前导零是无效的，当前的长度、出现的次数以及出现的次数三个状态才能保证结果一样（写这么多题了我居然没加出现的次数这个状态） Code： ...

数位dp 二进制

2020-11-19

1 557

Bomb 来自专栏

题意：找里有多少个数包含了. 思路：典型的特定数字问题，数位入门题。 ,表示第位，当前位是不是，是否出现了.刚开始没有加第三维，一直对不上案例，后面发现只有两维的保存的结果不一定能通用，比如: 前两个可以是同一个结果，但第三个和前两个不一样，可以任意取。 Code： #include <bit...

数位dp

2020-11-18

1 586

XHXJ‘s LIS 来自专栏

题意：题目意思就是给你L到R区间，和一个数字K，然后让你求L到R区间之内满足最长上升子序列长度为K的数字有多少个；比如就是上升子序列长为的数字思路：的状态应该包含长度、状态、以及题目的要求（刚开始没考虑到以后每组的答案受到前面答案的影响，没有多开一维数组存就错了）最长上升子序列有个的解法，数组存...

数位dp 状压dp

2020-11-18

1 638

不要62 来自专栏

思路：数位的一道入门题，表示第位，第是否是的结果。 Code： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3+7; inline ll read() { ...

数位dp

2020-11-18

1 482

CF741D Mehrdad’s Dokhtar-kosh paths 来自专栏

思路： 1.与前面的题不同的是，这是一类无修改统计链信息的问题2.一个串能重排形成是回文串当且仅当其字符数量均为偶数或者恰好有一个奇数，实际上对于任意的一条路径我们只关注其任意字符的奇偶性3.因为只有个字符，所以可以用二进制状压到4，表示节点到根结点的异或值5.假设现在我们处理以为根的子树，如果一条...

树上启发式合并

2020-11-12

1 754

CF375D Tree and Queries 来自专栏

思路： 1.题目要求维护的颜色数量，因此和模板类似的考虑什么情况下会对答案产生贡献2.维护颜色出现的次数，维护出现次数大于的颜色种类数3.显然出现次数的颜色都对有贡献4.颜色每次出现，必有5.将每次查询用容器存储，方便离线操作复杂度： MyCode: #include<bits/stdc++....

树上启发式合并

2020-11-12

1 516

CF1009F Dominant Indices 来自专栏

思路： 1.可以理解为的级儿子的个数2.题目要求一个最小的使得最大，3.存每个深度的节点个数，维护的最大值，维护对应的最小的深度4.子树的答案就复杂度：用来标记的重儿子，然后统计的答案时绕过重儿子，统计完后取消重儿子的标记，因为除非要清空该重儿子，否则不会再访问到该重儿子。每次都是在对以为根的子...

树上启发式合并

2020-11-12

1 622

CF246E Blood Cousins Return 来自专栏

思路： 1.询问一个节点的共有多少个不同的名字，可以用类型的数组来存子树某个深度某个名字出现的次数，来记录子树某个深度有多少个不同名字的节点2.将每次查询用容器存储，方便离线操作3.题目给的是森林，需要存每颗树的根节点复杂度： MyCode: #include<bits/stdc++.h>...

树上启发式合并

2020-11-12

1 689

CF208E Blood Cousins 来自专栏

思路： 1.询问一个点与多少个点拥有共同的级祖先，可以理解为一个点的级祖先有多少个级儿子即有多少深度为的孩子，最后答案别忘了，因为把自己也算了在内2.求出相关的点的级祖先可以用求的倍增法3.将每次查询用容器存储，方便离线操作4.题目给的是森林，需要存每颗树的根节点复杂度： MyCode: #inc...

树上启发式合并

2020-11-12

1 590

CF570D Tree Requests 来自专栏

思路： 1.要能形成回文串，所以最多只能有一种字母的出现次数为奇数2.用一个数组存每个深度每个字母出现的次数3.查询以为根的子树内深度为的节点上的字母重新排列之后是否能构成回文串只要另外判断深度为的节点上是否只有一种字母的出现次数为奇数4.为了方便离线查询，用容器存每次查询，存节点是第次询问以及...

树上启发式合并

2020-11-12

1 593