先思考这样一个问题，若存在一个逆序对，那么这个逆序对会被多少个子序列包含呢？数组的长度为n，除去逆序对所包含的两个元素外，其余的元素都有存在或者不存在两种选择，由此构成的子序列数量应为2^(n-2)个。显而易见，最终答案就是逆序对数量乘以 2^(n-2)。而求逆序对数量有多种实现方法，常见的有并归排序和树状数组。这里我使用的是树状数组。原数组a，其中元素的最大值为maxa。那么创建一个树状数组c，长度为maxa+1。当我们要统计数组值中小于等于x的元素个数的时候，可以将其分解为若干个区间。以数字7为例，统计数组中小于等于7的元素的个数。那么ans = c[7] + c[6] + c[4]。其中...

看到很多人说二位前缀和，不禁有些奇怪，有那么复杂吗？这题完全就用不到动态规划呀，纯数字计算不就好了？说说我的思路，首先维护两个一维数组row和col，分别保存矩阵每一行的元素和，与每一列的元素和。这一步在数据输入的时候就完成了，同时我们还得到了矩阵所有元素的和sum。接下来分别计算横着切和竖着切，以横着切为例，初始时ans = sum，s1 = 0，s2 = sum。遍历数组row，s1 += row[i]，s2 -= row[i]。如果s1和s2差的绝对值 < ans，更新ans。当s2 < s1时跳出循环。竖着切一样操作，只不过吧数组row换成col即可。最后输出ans。下面贴...

虽然题目标题写的线段树，但实际上更适合用树状数组求解。先上传一下代码，后续再试试线段树。链接 - 树状数组详解 #include <iostream> #include <vector> using namespace std; int n; vector<long long> c; int lowbit(int x) { return x & -x; } //计算a[1]至a[x]的和 long long getSum(int x) { long long ans = 0; while (x > 0) { ans += c[x]; x -= ...

看了其他人的题解，感觉都挺复杂。我来个简单易懂的，五重循环搞定。 #include <iostream> using namespace std; int main() { int k; cin >> k; for (int a = 9; a >= 0; --a) { for (int b = 9; b >= 0; --b) { if (a == b) continue; for (int c = 9; c >= 0; --c) { if (a == c || b == c) continue; for (int d = 9; d >= 0; -...

首先说一个概念，任意自然数N，其各位数字相加之和为M，那么N与M对模3同余。根据同余定理，可以先对N的每一位数字除以3取余，再相加后除以3取余，结果依然和N直接除以3取余相同。举个例子1234567除以3余1，1+2+3+4+5+6+7 = 28除以3余1。分别对计算1-7除以3的余数再相加，得到1+2+0+1+2+0+1 = 7除以3余1。这里的数学原理其实很简单，我们令个位数字是第0位，十位数字是第1位，百位数字是第2位，以此类推。假设自然数N的第i位数字是n，那么这位数字n实际代表的数是n乘以10的i次方。注意到10的i次方减去1得到999...99（i个9）必然被3整除，因此10^i ...

step1：创建一个字典map，其key表示数组中的元素，value表示该元素在数组中出现的个数。我们维护所有key中的最小值minK。step2：由于map底层是红黑树，其key是按照从小到大排列的，因此我们很容易获得其最大的key。对这个key，先将其从map中移除，然后对该key值进行二进制右移的操作（即题目中的除以2向下取整），每一次操作，实际的操作数为key对应的value。经过若干次操作，直到key的值小于等于minK。此时将新的键值对key-value更新到map中。step3：重复step2，直到map中只剩下一个key-value为止。 #include <iostre...