熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

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

小A与欧拉路来自专栏

前置芝士：欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次思路：因为求欧拉路的最短长度，且可以把任意边复制任意多次（其实就是每一条边可以走多次）由贪心的思想就是尽可能重复走短边，长边只走一次可以任意造几个数据可得重复走的边最多走两次所以可以得出每...

2020-11-05

2 603

最大异或和来自专栏

做法：可持久化01tire 思路：令s[i] = a[1] ^ a[2] ^ … a[i-1] ^ a[i]则a[p] xor a[p+1] xor … xor a[N] xor x 相当于 s[N] ^ x ^ s[p-1]s[N] ^ x 每次可以看成一个固定值 v提前算出来, 则相当于求 ...

2020-10-27

2 928

Xor-MST 来自专栏

做法：Borůvka+01字典树关于MST中的Borůvka算法详见https://www.luogu.com.cn/blog/Tweetuzki/solution-p3366 思路： dfs走法：有左儿子就走左儿子，有右儿子就走右儿子，同时存在则合并取min后加上深度的值代码 #inc...

2020-10-25

3 774

Perfect Security 来自专栏

做法：01字典树+贪心题意：有长度为n的两个a,b数组，改变b中元素的顺序,使数组c (c[i]=a[i]^b[i])的字典序最小，并输出数组c 思路：这题思路和前两题很相似，唯一不同点是求最小而已每次a[i]上异或上一个b数组中任意元素（不能重复使用），使得c[i]最小即可记录每个节点...

2020-10-24

3 627

Vitya and Strange Lesson 来自专栏

做法：01字典树题意： mex 是一个序列中没有出现过的最小非负整数。给出你一个长度为的非负整数序列以及个询问，每次询问先给你一个整数，然后：把序列中所有数异或上输出序列的 mex 注意，在每个询问过后序列是发生变化的。思路： 1.先插入原数组中每一个数（重复的不...

2020-10-24

4 822

奶牛异或来自专栏

做法：01字典树思路：这一题和The XOR Largest Pair思路很像，唯一不同的是这题求的是一段连续区间的最大值，并且还要维护区间的左端点和右端点.所以我们只需存每个连续区间的右端点.并且上个区间的右端点+1即为所求区间的左端点. 代码 #include <bits/stdc...

2020-10-24

4 831

The XOR Largest Pair 来自专栏

前言：暑假集训时学的字典树orz 太弱了www模板用的是wiki上用一个结构体封装的模板（当时就是看wiki学的字典树链接：https://oi-wiki.org/string/trie/ 做法：01字典树思路：一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二...

2020-10-23

6 759

起床困难综合症来自专栏

做法：位运算思路：确定攻击的每一位填1还是填0填1必须满足：该位为1了以后总和不能大于最大的攻击力填1了之后运算过后答案的二进制位上还是1 其余情况填1也会变成0，否则就大于了m，还不如填0有效代码 #include <bits/stdc++.h> using namespace ...

2020-10-21

6 663

Book of Evil 来自专栏

思路 1.把鬼的位置存起来，双向边建树 2.进行一遍dfs找到离树根最远的鬼 3.对该点进行一遍dfs找到离该鬼点最远的鬼点 4.再对鬼点进行一遍dfs，即找出两个相邻最远的鬼点 5.此时如果有点满足到这两个鬼点小于等于d，则成立代码 #include <bits/stdc++.h>...

2020-10-20

5 760

飞扬的小鸟来自专栏

做法：dp 思路： 1.先用结构体把每个横坐标的情况记录下来 2.dp[i][j]表示到坐标(i,j)最少需要跳的次数 3.考虑上升转移和下降转移，其中上升转移要考虑到顶这种特殊情况代码 #include <bits/stdc++.h> using namespace std; #...

2020-10-19

2 712