【前言】简单题。【暴力】可以有2^n的暴力。还有其他暴力方式，不赘述。【正解】假设答案为ans，初始时，我们把ans设为所有额外共鸣的和的相反数。并且将额外共鸣分别加到两个音符的优美程度上，得到一个新的价值。最后，只有音符的价值大于0我们才将它加入答案。这样显然是正确的。具体请参照代码理解，非常简单的贪心。参考代码： class Solution { public: /** * * @param n int整型 * @param m int整型 * @param a int整型一维数组 * @param aLen int a数组...

【前言】充满欺骗意味的题目。【暴力】记录每个羁绊是否出现，根据打法不同，复杂度亦不相同。【比较厉害的暴力】我们有一个稍微奇妙一点的做法。用f[i]表示i与i+1到f[i]都建立了羁绊，可以发现f[i]具有单调性，那么在暴力的过程中，f[i]>=r则可以退出了。这样的话可以优化不少，但还不够。【正解】我们还是用f[i]表示相同的东西，但这一次，我们用一些数据结构来维护区间最大值、最小值、区间和。复杂度O(mlogn) 参考代码： class Solution { public: /** * * @param n int整型 * @param m i...

【前言】非常简单的题目。【暴力】枚举起点和终点即可。复杂度O(n^2)【正解】我们把0看成-1，然后求出前缀和数组s[]，可以发现，如果区间[i,j]满足条件，那么s[j]-s[i-1]=0，即s[j]=s[i-1]，那么对于每个s[]中可能的取值，保留最前面的那一个，用来更新答案即可。用桶来实现。复杂度O(n) 参考代码： class Solution { public: /** * * @param n int整型 * @param a int整型一维数组 * @param aLen int a数组长度 * @return i...

【前言】比较难的题目。【暴力】每次搜索最佳路径。复杂度很大。【正解】正难则反。把问题变成，牛牛要按顺序出村子，尽量不经过有其他牛牛的位置。考虑一个优美一点的暴力，假设我们知道当前每个点出发离开网格时的最小内疚值，一个牛牛出村子可能会影响一些牛牛的答案，我们就暴力地更新，这样做最坏情况看起来是O(n^4)的，因为假设每个点都会影响很多点，似乎是会达到上界的。但我们再将牛牛出村子带来的影响量化，很直观的，只会使一部分其他牛牛出村子的答案-1，对于不改变答案的点，它及其它可能延伸的后继都是没必要去遍历的，所以最终复杂度应该是和最初始情况下牛牛们的答案的和有关，大概O(n^3)，可能还很不满，足以通过...

【前言】此题比较简单。【暴力】枚举一条简单路径，枚举另一条简单路径，暴力判断是否有公共边。复杂度O(n^4)或更高。【正解】根据异或的性质，x^y^y=x，所以说，两条简单路径的公共边在异或的过程中被抵消了，相当于没有选这些边，两条简单路径删除公共边的结果还会是两条简单路径，因此，有公共边这个条件可以无视。所以问题变成了，找两条简单路径，求边最大异或和。路径数最多n^2，但值域很小。开个数组记录每个数是否出现即可。复杂度O(1024*1024) 参考代码： class Solution { public: /** * * @param n int整型 ...

【前言】非常简单的数学题。 【暴力】直接模拟即可，复杂度O(n) 【正解】有很多项是完全相同且连续的，因此可以采用计算这一项出现了多少次来简化计算。我们采用这样的做法，枚举1到x，计算以这个数作为答案被记录了多少次，这时我们就快速计算了很大一段的和，我们假设已经计算了y到n这几项的和，对于剩下的1到y-1，暴力。可知y=[n/(x+1)]+1我们来看复杂度，是O(x+n/(x+1))的，可以近似为O(x+n/x)，根据基本不等式，x取 时达到最小。所以最后复杂度为O( ). 参考代码： class Solution { public: /** * * @param...

【前言】如题，不可思议。 【暴力】模拟整个过程，O(n^2)级别。 【正解】交了暴力居然过了...其实出题人(wo)写的也是暴力，wo暂时没有找到除了暴力意外更优秀的做法，毕竟那个(y+i)xor(y+2i)，wo也不知道怎么变形成可以快速计算的形式。观察题目，构造树和询问的方式几乎是无规律可循的，可将这个过程看做完全随机。结论：以1到n的顺序，每次等概率选择1到i-1中的一个点作为i的父亲，以此方式构造出来的树，树的深度是O(logn)级别的。对于暴力地模拟这个过程，虽然看似是O(n^2)级别，但是严谨一点，上界应该是O(n*max(depth(x)))，即每次询问深度最大的点。实际上由于随...

【前言】这是一道思维题，本质是贪心，没什么代码量。偶尔抖机灵抖出来的题目。 【暴力】O(n!)枚举，我的数据最小的n是100.很遗憾。当然可能有稍微优秀一点点的暴力做法。 【正解】目标是最大化答案，答案最大的情况就是每条边被选正好一次，因为无论如何改变排列p[],p[i]和p[i+1]的路径的并集都会是整棵树，你需要到达每一个点，因此每条边都需要经过至少一次。尝试证明这个答案可以达到，假设初始所有点都未放入p[]中，且w最大的边为x，若计算一次w[x]，需要将u[x]和v[x]放在排列p[]的相邻位置，则将u[x]和v[x]放入p[]中，位置不管，但必定相邻，再看次大边，若次大边的某一段已经在...

【前言】一道稍微想起来有一点点难的数学题。这是一个叫做吉尔布雷德定理的拓展。吉尔布雷德原理本身的内容是将黑白相间的牌分为两堆，使两堆牌底的那张不同，然后交错洗成一堆，最终得到的结果依旧是黑白相间的一堆牌。稍微拓展了一下，便有了这道题目。 【暴力】O(n*m)的模拟即可。 【正解】如果你使用了模拟，你可以过绝大部分数据，数据中很大一部分是可以接受这个复杂度的。但是对于极限数据，模拟还不够。当然，如果你使用了模拟，也许可以发现一些规律... 结论：把新牌库均分为n份，分别为1到m，m+1到2m，2m+1到3m...，你会发现每一份的m张牌恰好1~m这些数值每个数值出现了1次。 如果你模拟了一些小数...

【前言】非常简单的数学题。 【正解】问题可以拆分为许多子问题，子问题就是：给一个数m，将他拆分为尽可能少的若干个质数的和。解题的关键就是哥德巴赫猜想。对于质数，显然贡献就是1.对于1，贡献也是1.剩下的数分奇偶考虑，对于偶数，由哥德巴赫猜想，任意一个非2的偶数可以拆分为两个质数的和，所以偶数的贡献是2.对于不是质数的奇数z，贡献只可能是2或3：1、拆分为2个质数，必然为1奇1偶，分别为2和z-2，其中z-2为质数2、拆分为3个质数，一种可行的拆分方法是拆分为一个奇质数和一个非2偶数，这个偶数根据哥德巴赫猜想可以拆分为两个质数。 贪心即可。 关于哥德巴赫猜想，虽然还没有被成功证明，但至少在我们现...

这是一道比较困难的数据结构题。 【暴力法】暴力的方法，是直接枚举点对，求两次lca，但这复杂度是O(n^2logn)的，必然超时。 【正解】将暴力的思路反过来，我们枚举树1中的lca，设为z，问题变成了求所有在树1中lca为z的点对在树2中的lca深度的最大值。 首先，满足树1中lca为z的点对，两点在树1中必然分别在z的不同儿子的子树中。这是显然的。 对子树分开处理，假设z的孩子们分别为p[1],p[2],p[3]...假设我们处理到p[i]，暴力地求解，则是枚举子树p[i]的所有点，另外枚举p[1]~p[i-1]的子树中的点，再在树2中求点对的lca，这样看下来复杂度变成了O(n^3log...

想出一道期望题，就这样了。 综合题目条件，简化一下题意。不妨将n对(x和ax)看做n个区间[x,ax]，根据题意，这n个区间只有包含和相离两种情况。那么，一个点x被取反，当且仅当x被选或者包含x的区间被选。单独计算每个点对答案的贡献，当一个点x自己被选，那么贡献为1，如果它没有被选，而是支配它的区间将它取反的话，贡献就是0.由于是等概率选取，假设支配x的区间有c个(包括[x,ax])，那么x的贡献就是1/c。 答案就是 问题变成了求c。c的话，便有了一个非常简单的做法，需要知道每个点被多少区间覆盖，直接想到区间+1和区间查询。线段树做法是O(nlogn)，但这样不够优美，可以在假设区间为[x...

在很早之前研究线段树的时候发现，以常规方法构造出的线段树编号可能并不连续。因此便有了这一题。 结论1：手写若干个线段树可以发现，若给线段树分层，设区间[1,n]代表的点为第1层，下面是第2层第3层以此类推，我们可以发现，第i+1层的编号永远大于第i层的编号。证明：首先同层的情况下，左边节点编号小于右边的。第i层最大的编号为最右边的节点，编号为1,3,7,15,31...2^i-1，第i+1层编号最小的节点为最左边的节点，编号为2^i,得证。 结论2：而且对于线段树上的节点x[l,r]，它下方的子树的形态，与l和r具体是多少无关，只与r-l+1的大小有关。证明：显然。 根据上述结论，我们找寻最大...

刚开的时候我还没有恰饭...... 先去喝了个汤，然后肥来看题。 先去看A（重大失误） 复制三遍CE？？？？？？？？？？ 公告一来天呐再见兄弟。 尝试填空，发现，如果这样直接按照给定的代码填空，复杂度是O(n^2logn)的，这是陷阱。 仔细分析了一波，数据随机+区间修改，突然想起这两天一直在研究的ODT，不过ODT只能处理区间赋值，这个貌似并不好做。 再想了一下，线段树貌似就可以了，加入一个线段看做区间+1，维护区间最大值最小值，当区间最大值由0变1时加一下答案，删除同理，由于数据随机，序列上相同高度的连续段是O(log)级别的，复杂度是对的...