hnust_zhouzisheng

分类

算法(3) 题解(27)

/ 注册

全部文章（共30篇）

【每日一题】平衡二叉树

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

2020-07-09

0 1248

【题解】 Counting Cliques

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

2020-07-04

0 549

【题解】 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 664

【每日一题】毒瘤xor

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

2020-07-02

0 700

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

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

2020-07-02

0 865

【题解】分特产

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

2020-06-16

1 735

【每日一题】 Paint Box

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

2020-06-16

4 936

【每日一题】字符串

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

2020-06-15

1 640

【算法】排列组合——插板法

插板条件：1.每个元素相同2.分成的组不为空原始问题：将10个相同的球放到3个不同的篮子里，每个篮子至少有一个球，有多少种方法？用0代表球、-代表板子，则有：0-0-0-0-0-0-0-0-0-0，相邻两球之间插个板，共有9个板，我们只要从中选出两个板即可分成3个部分，也就是三个篮子。即C(9,2...

2020-06-14

2 3474

【算法】主席树

解决问题：m次询问，每次给定一段区间，求静态区间kth。考虑对每个点i建一棵权值线段树，维护1-i区间里的数出现的次数。例如给定6个数：1 3 2 3 6 1，第4棵树如下：n棵权值线段树形状一样，考虑对两棵树相减：第i棵树维护1-i区间里的数出现的次数，第j棵树维护1-j区间里的数出现的次数(i...

2020-06-11

0 786