hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

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

Spy Syndrome 2 来自专栏

题意：描述了一种加密技术，现在将加密后的字符串和字典给出，要你求还原后的字符串。加密方式：①将所有字母改为小写字母②将所单词翻转③将所有空格去掉思路：你可以将字典中的单词按翻转后的结果插入字典树中。然后dfs加密后的字符串从字典树中查找满足的可划分的单词。代码： #include <cst...

dfs 字典树

2021-02-21

2 715

[SCOI2009]最长距离

题意：有一个n*m的地图，为1表示为有障碍物，你可以移走t个障碍物，求二个可以相互到达的点最大的欧几里德距离? 思路：dfs暴力求出每一个点在移走t个障碍物后能到达的点，然后暴力求最大距离。代码： #include <bits/stdc++.h> typedef long long l...

dfs

2020-09-28

0 552

装货物

题意：有n件货物，每件货物有一个重量，我们有x个承重为w的箱子，求是否能全部装上？思路：dfs暴搜：先将货物重量从大到小排序，这样可以降低解空间。dfs时箱子使用个数不超过当前物品数，因为超过没有意义。代码： #include <bits/stdc++.h> typedef long...

dfs

2020-08-21

1 644

华华和月月种树

题意：一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。操作3：输入格式为3 i 表示输出i节点的权值。 ...

dfs 树状数组

2020-08-21

1 666

[SCOI2009]生日快乐

题意：将一块x*y的蛋糕切n-1刀分成n块面积相同的小蛋糕，每次切只能平行于边将一块切成二块。求N块蛋糕的长边与短边的比值的最大值最小为多少？思路：我们发现n<=10,而且每次切只能平行于边将一块切成二块，而且每一块面积相同，所以我们可以用dfs枚举每一种切法。平行于y边切：可以切成(i *...

dfs

2020-07-21

1 888

Alliances

题目：有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。有k个帮派，每个帮派占领ci个城市。帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？思路：在树...

dfs 二分 LCA

2020-07-11

1 701

平衡二叉树

题意：在一棵每一个节点的左右子树高度差小于d的n高度的树上，求出节点的左右子树节点差的最大值？思路：是左子树的节点尽可能多，所以左子树为满二叉树。右子树的节点尽可能少，所以右子树高度为n-d-1。n高度的右子树节点个数=n-1高度的右子树节点个数+（n-d-1）高度的右子树节点个数+1。（将一棵树...

dfs

2020-07-10

0 734

模拟战役

题意：给出一个整数m,再给出8行字符串，前4行为司机基地情况，后四行为齐齐基地情况，求齐齐在摧毁司机全部大炮后最多剩多少门大炮？（无法全部摧毁司机大炮则输出-1）思路：dfs求出司机基地有多少个大炮连通块，再用dfs求出齐齐每一个大炮连通块的大炮个数并保存，由于保存最多的大炮，使用的大炮所在连通块...

dfs 贪心

2020-05-18

0 551

边的染色

题意：小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：对于G中任意一个环，里面所有边的边权的异或值为0。环的定义如下：对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<...

dfs 并查集

2020-04-23

0 688