shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

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

Blood Cousins Return 来自专栏

板子题...并没有太多的变化.和之前做的,唯一的变化就是对于字符串可以哈希成数字的变成点权.代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+50; //可以用map把每个字符串做一次离散化,这样就相当...

树上启发式合并

2020-12-02

5 643

E. Xor Tree 来自专栏

1.题意给你n个数,n个数的权值,然后它们连边的规则是每个数连向它们异或最小的边.然后问你最少删掉多少个数,才能使得它们构成一棵树? 2.思路对于位运算,我们应该从高位向低位进行.既然是从高位向低位进行,那么思考一下,假如那个高位有两个1,两个0,它们会如何连边.必定是1与1相连,0与0相连,...

字典树

2020-12-02

7 770

Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 来自专栏

这题思路就还行! 1.思路可以思考下如何判断回文串,回文串的组成必定奇数字母小于等于一个.如此,我们把每个数都表示成二进制的形式.只和奇偶有关.这里开(1<<23)即可.D[u]表示从根节点1到u节点,a-v的奇偶性情况.然后我们只需要开个C数组,C[D[u]]表示当前子树下,值为D...

树上启发式合并

2020-11-26

7 681

Tree and Queries 来自专栏

树状数组维护下dsu on tree即可.复杂度为O(nloglogn). #include <bits/stdc++.h> using namespace std; const int N=1e5+50; int c[N],cnt[N],ans[N]; vector<int>...

树状数组树上启发式合并

2020-11-24

10 676

Tree Requests 来自专栏

1.思路对于这题来说,总的来说还是dsu的一个板子,我们计算完了之后暴力更新就好了.复杂度是O(26*nlogn)的. 2.代码 #include <bits/stdc++.h> using namespace std; const int N=5e5+50,M=26; struct...

树上启发式合并

2020-11-23

5 600

Shortest-path tree 来自专栏

幸好有大佬帮我,不然就死翘翘了hhh #include <bits/stdc++.h> using namespace std; const int N=3e4+50; int dis[N],vis[N],n,m,k; struct node{ int to,val; ...

点分治

2020-11-11

5 736

启发式合并来自专栏

启发式合并顾名思义就是得到启发后进行合并.把原本合并时的(n>m) O(nlogm)->O(mlogn).本题题意那么长,说白了就是给你n段,然后询问在所有段最多重叠k次可以的最大权值是多少.直接建树分治合并即可~代码如下: #include <bits/stdc++.h> ...

启发式合并

2020-11-07

5 817

DSU练习题来自专栏

https://www.luogu.com.cn/problem/P5787 https://www.luogu.com.cn/problem/P3402 https://codeforces.com/problemset/problem/891/C

DSU

2020-11-05

5 550

Revenge of BBuBBBlesort! 来自专栏

当我只是水结论敲个板子吧...下次不开这么没意思的题目..必要性证明完了就可以过,有些题解证明不是很懂.那就按必要性水一发吧. #include <bits/stdc++.h> using namespace std; const int N=3e5+4; long long odd=0...

思维题

2020-11-04

4 745

Lottery 来自专栏

题目:是给你n个ai,一个xi,代表有xi个2^ai,然后问你拿这些最多可以组成多少个不同的数.xi和ai的范围都是1e9级别的,n是1e5级别的.首先对于每个ai和xi来说,我们考虑它能延申到的长度.假如没有交集很显然就是直接乘起来就好了.假如有交集也挺显然的,就是拿前面能扩展到这里的最低位ai,...

计数

2020-11-03

5 690