对于一个逆序对 i j 来说，其在子序列中出现的次数是固定的，是 2^(n-2)，因为对于 n 个数而言，i 和 j 必须出现在逆序对中，而其他数都可以出现或者不出现，所以每个逆序对都会出现 2^(n-2) 次，答案就是逆序对数量乘 2^(n-2) 而求逆序对数量很简单了，实现方法很多，这里给一个树状数组实现的方法 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; const int mod = 1e9 + 7; int __t = 1, n, a[N...

每次 1 操作之后只有两种情况完成目标，同盒子 x 有过 2 操作，或者所有盒子都有过 1 操作每次 2 操作之后只有两种情况完成目标，同盒子 x 有过 1 操作，或者有其他盒子有过 2 操作可以使用map维护已经操作过的 1 和 2 操作，注意检查某操作是否存在（某个键是否存在）需要使用 count ，如果直接使用 mp[x]==0 来判断会创建这个元素 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m, k, x...

按照题意模拟即可，需要注意的是 a/b 向上取整可以直接写为 (a+b-1)/b #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m, k, c; void solve() { map<int, int> mp; cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> k &g...

维护好二维前缀和sum后，所有可能的 sum[i][m] 和 sum[n][i] 就是小美拥有的，而 sum[n][m] 减去小美拥有的就是小团拥有的，遍历所有可能性，维护好最小的二者的差的绝对值即可 #include <bits/stdc++.h> using namespace std; #define int long long int __t = 1, n, m; void solve() { cin >> n >> m; vector<vector<int>> a(n + 1, vector<int&g...

维护好前缀和b，那么 l 到 r 的要么正着走花费 b[r - 1] - b[l - 1] ，要么反着走花费 b[n] - b[r - 1] + b[l - 1]记得保证 l<r #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e6 + 5; int __t = 1, n, q, l, r, a[N], b[N]; void solve() { cin >> n; for (int i = 1; i <= n; i++) {...

使用差分数组维护区间修改即可 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; int __t = 1, n, m, l, r, k; int a[N], b[N]; void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i < m; i++) ...

使用二维前缀和即可，需要注意不定长的二维数组可以使用vector #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1005; int __t = 1, n, m, q, x11, y11, x2, y2; void solve() { cin >> n >> m >> q; vector<vector<int>> a(n + 1, vector<int>(m + 1, 0)), ...

板子题 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; int __t = 1, n, q; int a[N], bit[N]; void update(int idx, int val) { while (idx <= n) { bit[idx] += val; idx += idx & -idx; } } int query(int idx) { int sum = 0; ...

使用前缀和维护 1 到 i 的元素和，存在 b 数组那么查询 l 到 r 的元素和就是 b[r]-b[l-1] #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e6 + 5; int __t = 1, n, q, l, r, a[N], b[N]; void solve() { cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i];...

首先考虑尽可能的满足想换座位的人我们将想换座位的人单独记录下来，然后将其循环打乱，就是给第一个人最后一个人的座位，第二个人第一个人的座位，以此类推发现很像第一天的最后一题，我们维护一个map给每个需要换座位的人自己到自己的映射，然后将其错位swap即可，实现非常的简单 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n; string s; void solve() { cin >> n >>...

本题关键在于将整形大批量的转为字符串不足5位的用0补齐实现方法很多，个人推荐用 format 来格式化，但是目前牛客不支持c++20用不了string s = format("{:05}", i);所以考虑使用while，将不足5位的字符串前方补0即可判断一个字符串是不是5种字符组成的可以直接记录其中的元素数量，实现方法很多 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n; vector<str...

考虑使用map维护每个数出现的次数，发现可以顺便维护下map中最大的值 maxn ，答案就是 min(maxn + 1, n) #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, x; void solve() { map<int, int> mp; cin >> n; int maxn = 0; for (int i = 1; i <= n; i++) { ...

给大家一种好理解的做法吧简化题意：每个数都可以进行若干次除2的操作，最终需要使所有数相同，输出最少的操作次数我们可以发现，对一个数进行 i 次除2，等效于在将其二进制右移 i 位，而一个 1e9范围内 的数通过除2能得到的数，最多只有29个，我可以轻松的维护出每个数 x 右移 i 位得到的数 y 那我们回到题目，最终要求所有数相同，也就是说所有的数都需要有一个相同的最终状态 Y ，所以我们可以在之前维护 y 的时候将其的权值加一，表示能到达 y 这个状态的数的个数，顺便维护一下当前的 x 到达 y 这个状态需要的步数，也就是 i ，对于每个 y ，我们维护一个 pair<int,int&...

按题意模拟即可，需要注意的是cpp的 insert 函数有多个重载版本，可以按个人喜好使用本题可以是s.insert(j, 1, s[j - 1]); s.insert(s.begin() + j, s[j - 1]); #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, q, l, r; void solve() { cin >> n >> q; string s; ci...