hnust_yangyanjun

题解

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

/ 注册

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

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

最短路

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小...

最短路并查集 LCA

2020-07-08

0 684

[SCOI2005]最大子矩阵

题意：在一个n*m的矩阵中选择k个子矩阵，这k个子矩阵互不相交，求这k个子矩阵分值最大为多少？思路：dpdp[k][i][j]为在第一列前i个，第二列前j个，选择k个矩阵的最大值。分析我们动态所加的一个元素参与结果的情况。既枚举所加元素在第一列前i个，第二列前j个中所有矩阵加上在该矩阵外选（k-1...

dp

2020-06-12

0 543

小A与小B

题意：小A与小B被困在一个n*m的迷宫中，'.'为可通过，'#'为障碍不可通过，'C'为小A初始位置，'D'为小B初始位置。小A可以上下左右左上左下右上右下8个方向移动，而小B只能上下左右移动，不过小B能一秒移动二次，而小A只能一秒移动一次。求小A与小B最早什么时候相遇？不能相遇只输出NO. 思路：...

bfs

2020-06-10

0 526

[CQOI2010]扑克牌

题意：有n种牌，每种牌有ci张，还有m张万能的joker牌，每一套牌可以用一张joker牌代替任意一张牌，求最多能组成多少套牌？思路：二分求最大值，因为能组成k套牌则必能组成（k-1）套牌。是否能组成k套牌，首先我们最多用min（m,k）张万能牌，用万能牌补数目少于k的牌，最后看万能牌是否够用。 ...

二分

2020-06-10

0 569

德马西亚万岁

题意：有一个n*m的地图，为0不可以站人，为1可以站人，二个人不能相邻，求合理的方案数？思路：状压dpdp[i][j]为第i行状态为j的方案数（状态为第i行二进制转化为十进制的值，既一个二进制为该行的整数）。d[i]表示地图中第i行这m位取反表示的十进制。如果该状态合法，则j&(j-1)=...

dp

2020-06-09

0 527

Sumo and Electricity(easy)

题意：n个核电站，m条电缆，每个核电站有一个耗电量，电缆传输功耗为两个核电站耗电量之间的异或值。其中有一个核电站为耗电量为-1，表示我们可改变该核电站的耗电量，求总最低传输功耗，并求在此基础上的最低总耗电量？思路：我可以改变的只有一个核电站，所以我能决定的传输功耗为与该核电站相连的电缆，所以将于该...

2020-06-09

0 610

旅游

题意：有一个n个城市有（n-1）条道路的无向图，有二人打算旅游，第一天住在s市，并浏览了周围距离不大于1的城市，每天会选择一个城市住，他们不想住在已经浏览过的城市，并且他们想旅游时间尽可能长.求最长旅游多少天？思路：树状dp,dp[v][0/1]表示以v为根节点的树，根节点分是否住的的最大旅游天数...

树状dp

2020-06-04

1 689

Contest

题意：有n支队伍一共参加了三场比赛。一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强（既互相觉得比对方强），(x, y), (y, x)算一组。思路：当x自己觉得比y强，y自己也觉得比x强，只有这二种情况，第一...

树状数组

2020-06-04

1 699