题意：在一棵每一个节点的左右子树高度差小于d的n高度的树上，求出节点的左右子树节点差的最大值？ 思路：是左子树的节点尽可能多，所以左子树为满二叉树。右子树的节点尽可能少，所以右子树高度为n-d-1。n高度的右子树节点个数=n-1高度的右子树节点个数+（n-d-1）高度的右子树节点个数+1。（将一棵树分为左子树，右子树，根，由于要使节点尽可能少，所以生成的左子树，右子树性质类似于该树）。注意：当n=0和d=0时节点差为0. 代码： #include <bits/stdc++.h> #define inf 1000000007 using namespace std; typedef...

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。 思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小生成树，多余的边我们先保存。在做完Lca的预处理后将多余的边加入，对每一条多余的边的一个端点进行求取该点到每一个点的距离，可以用求最短路的算法求取。最后我们求二个点的最短路时可以用树上的距离与这二个点到每一个求了最短路的点的距离和中取最小值。我的代码水平有点低，交了几次才卡过去。 代码： #incl...

题意：在一个n*m的矩阵中选择k个子矩阵，这k个子矩阵互不相交，求这k个子矩阵分值最大为多少？ 思路：dpdp[k][i][j]为在第一列前i个，第二列前j个，选择k个矩阵的最大值。分析我们动态所加的一个元素参与结果的情况。既枚举所加元素在第一列前i个，第二列前j个中所有矩阵加上在该矩阵外选（k-1）个子矩阵的值。 代码： #include<bits/stdc++.h> #define ll long long #define inf 1e9 using namespace std; ll dp[105][105][105], d[105][5], sum[105][5]; ...

题意：小A与小B被困在一个n*m的迷宫中，'.'为可通过，'#'为障碍不可通过，'C'为小A初始位置，'D'为小B初始位置。小A可以上下左右左上左下右上右下8个方向移动，而小B只能上下左右移动，不过小B能一秒移动二次，而小A只能一秒移动一次。求小A与小B最早什么时候相遇？不能相遇只输出NO. 思路：分别bfs小A和小B，求出分别到达每一个位置的最早时间，初始时间为inf（一个很大的数），一个位置的相遇时间为二个到达时间的最大值，求所有位置相遇的最小值。 代码： #include<bits/stdc++.h> #define ll long long #define inf 1000...

题意：有n种牌，每种牌有ci张，还有m张万能的joker牌，每一套牌可以用一张joker牌代替任意一张牌，求最多能组成多少套牌？ 思路：二分求最大值，因为能组成k套牌则必能组成（k-1）套牌。是否能组成k套牌，首先我们最多用min（m,k）张万能牌，用万能牌补数目少于k的牌，最后看万能牌是否够用。 代码： #include<bits/stdc++.h> #define ll long long #define inf 100000000 using namespace std; int n, m, c[1005]; bool fun(int k) { ll p=min...

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

题意：n个核电站，m条电缆，每个核电站有一个耗电量，电缆传输功耗为两个核电站耗电量之间的异或值。其中有一个核电站为耗电量为-1，表示我们可改变该核电站的耗电量，求总最低传输功耗，并求在此基础上的最低总耗电量？ 思路：我可以改变的只有一个核电站，所以我能决定的传输功耗为与该核电站相连的电缆，所以将于该核电站相连电缆所连的核电站提出来，用数组保存，又由于电缆传输功耗为两个核电站耗电量之间的异或值，所以从位考虑，如果该位为1则所连的核电站中该位为0的会产生等价于位权值的传输功耗，所以当所连的核电站中该位为0小于为1的时候该位为1。 代码： #include<bits/stdc++.h> ...

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

题意：有n支队伍一共参加了三场比赛。一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强（既互相觉得比对方强），(x, y), (y, x)算一组。 思路：当x自己觉得比y强，y自己也觉得比x强，只有这二种情况，第一种是x二场比y弱，一场比y强，第二种是x二场比y强，一场比y弱。无论哪一种都会产生二组逆序对，所以我们对第一场降序排序，对第二和第三场求逆序对(既已遍历中比当前值小的数目，可以树状数组维护，遍历一个，对值位置加一)，再对第二场排序，对第三场对逆序对（同理）。最终对答案除二即可。 代码： #inclu...

题意：链接：https://ac.nowcoder.com/acm/problem/17621来源：牛客网 管道取珠是小X很喜欢的一款游戏。在本题中，我们将考虑该游戏的一个简单改版。游戏画面如图1所示：游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。每一次操作，可以从左侧选择一个管道，并将该管道中最右侧的球推入右边输出管道。 例如，我们首先从下管道中移一个球到输出管道中，将得到图2所示的情况。 假设上管道中有n个球,下管道中有m个球，则整个游戏过程需要进行n+m次操作，即将所有左侧管道中的球移入输出管道。最终n +m个球在输出管道中从右到左形...

题意：有n只奶牛在吃花，为了减少花的损失，将奶牛放回谷仓去，每只奶牛距离各自的谷仓ti分钟时间的距离，并且每只在花园的奶牛每分钟吃di朵花，一次只能放一只奶牛回去，由于回去回来，所以需花费2*ti的时间，求奶牛最少吃多少花？ 思路：当AB二只奶牛回去顺序相邻时,我们可以发现AB前面的奶牛和AB后面的奶牛吃的花不变，设AB前面花的时间为T，所以当A一定在B之前时需满足T * da+(T+ta) * db < T * db+(T+tb) * da化简为ta * db < tb * da所以按ta * db < tb * da 排序计算即可。 代码： #include<bit...

题意：有n种货币，每一种货币面值为a[i]，并且每种货币有无穷个，请问只需多少种货币可以达到和这n种货币一样的支付范围？ 思路：多重dp，将a数组按升序排列，如果第i种货币的值可以被前i-1种货币组成，则该面值的货币可以不要，计算不能被组成的货币种类数即可。 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 1000000007 int a[2005], dp[30000]; int main() { int t; scanf("%d",&...