hnust_zhouzisheng

题解

算法(3)

/ 注册

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

【每日一题】平衡二叉树

递推要求所有高度为n的平衡树中不平衡度的最大值，没必要考虑所有的树，只要想办法构造出一棵不平衡度最大的树即可。要想不平衡度最大，只要根节点的左右子树节点数差值最大即可。若不选取根节点，则高度上限会减少，得到的树不平衡度不是最大。而要使左右子树节点数差值最大，只要使左子树节点数最大、右子树节点数尽可...

2020-07-09

0 1236

【题解】 Counting Cliques

dfs优化题意：给定一个n个点、m条边的无向图，要找出图中大小为s的完全图的个数。思路：先看一个常规思路，不过会TLE：从所有节点开始都进行一次dfs，将不在集合中并且能与集合中的点形成完全图的点加入集合，集合大小等于s时ans加一，逐层返回。为什么所有节点都要进行一次dfs？因为题目没说图一定...

2020-07-04

0 554

【题解】 Recursive sequence

矩阵快速幂。题意：一组数的递推公式如下：F(1)=a,F(2)=b,F(n)=F(n-1)+2* F(n-2)+ (n>2)。现要求出该序列中的第n个数。思路：由于n的值太大，直接递推不行，这里采用构造系数矩阵的方法。本人目前的理解：当以递归得到数的效率太低时，可以研究递归过程，拆分或者合...

2020-07-03

0 663

【每日一题】毒瘤xor

数学+前缀和。对于序列中的每一个数，采用二进制表示，以此判断X在每一位的值。先考虑区间[1,n]，假设这n个数有t个数的第j位为1，则有(n-t)个数的为0。接下来判断X在第j位应该是0还是1。已知异或的运算规则：相同为0，不同为1。如果要使求和得到的值尽可能大，那么X与每一个数的第j位异或运算...

2020-07-02

0 704

【每日一题】珂朵莉的数列

离散化 + 树状数组先看一下一般求逆序数的思路：设置vis数组，表示数字在前面遍历过程中出现的次数；遍历数组，vis[ar[i]]加一，然后求出大于ar[i]的数在前面出现的次数并加入到ans中。当序列数字过大是可以采用离散化处理，因为只需要知道大小关系即可，不必知道到底大了多少；对于求大于ar[...

2020-07-02

0 862

【题解】分特产

题意：有m种物品，每个物品有ar[i]个，将其分予n人使得每人至少有一个，求分配方法种数。容斥原理。运用容斥原理关键在于求得至多或至少然后去重。题目中有一个“至少”，不过显然不是我们要找的。不妨这样理解：每人至少有一个，也就是有0人没有被分到。那么我们可以找至少有x人没被分到，容斥一下便是0人没被...

2020-06-16

1 738

【每日一题】 Paint Box

数论——容斥原理。从m种颜色中选出k种颜色给n个盒子上色，要求k种颜色都要用到且相邻盒子不能同色，求方法数。首先，计算C(m,k)为选出k种颜色的方法数。其次，k种颜色都要用到，换一句话说就是恰好用到k种颜色，显而易见应该转化为至少或者至多再考虑用容斥原理去重。记f(i)表示至多用i种颜色上色...

2020-06-16

4 932

【每日一题】字符串

尺取法。 1.从第一个字符开始，向右移动右界至子串合法，用vis数组记录每个字母出现的次数，cnt表示vis记录次数为零的字母数。 2.当cnt=0时，此时每个字母都至少出现了一次，也就是说此时的长度就是一个合法子串的长度。更新ans。同时向右移动左界至子串不合法，移动过程中不断更新ans。返回第一...

2020-06-15

2 649

【每日一题】粉刷匠

动态规划。原问题：n个木板粉刷t次的最多粉刷个数子问题：前i个木板刷j次的最多粉刷个数描述：记dp1[i][j]表示前i个木板刷j次的最多粉刷个数推出dp1[i][j]=max{dp1[i-1][j-k]+第i个板粉刷k次的最多粉刷个数},k<=j 这又产生了新问题，如何求某个板粉刷某次的最...

2020-06-10

0 987

【每日一题】失衡天平

动态规划。首先，题目说不限操作次数，但其实只要操作一次即可，因为每次操作得到的两堆重量差值均<=m，只要将每次得到的两堆按大小互补的方式与前一次的两堆合并到一起即可，最后相当于得到一次操作的结果。其次，动态规划。原问题：从n个物品中选出两堆重量差不超过m时最大重量和。子问题：从前i个物品选...

2020-06-10

2 872