牛客多校5
A.Jujubesister
题意：
给出长度为\(n\)数组\(a\)，每次询问一个区间\([l, r]\)，问有多少三元组\((i,j,k)\)满足有
-
\(i<j<k\)
-
\(a_{i}=a_{k}>a_{j}\)
思路：
假设我们现在知道了\([l,r]\)的答案，我们要直到\([l,r+1]\)的答案，我们能否快速计算？
此时，新产生的三元组右端点一定是\(r+1\)，假设此时我们找到了\([l, r]\)内的一个跟\(a_{r+1}\)相等的\(i\)，我们需要做的只用在\([i,r+1]\)之间找有多少数小于\(a_{r+1}\)。
因为这是区间查询，我们考虑用前缀和优化他，我们设\(c_{i}\)为在\([1,i-1]\)中有多少数是小于\(a_{i}\)的，这个用树状数组即可实现。
那么我们要找的\(i,r+1\)的贡献即\(c_{r+1}-c_{i}\)
当然，我们能找到的\(i\)可能不止一个，如果有多个，设他们的第\(i\)个是\(p_{i}\)
我们计算区间的时候，再记录一个tot[x]为\(x\)出现了多少次，sum[x]为区间内权值为\(x\)的位置的\(c\)之和
那么\((1)\)就可以写作
这样，新增一个点的贡献就可以\(O(1)\)计算，扩展节点就只需要交给莫队\(O(n\sqrt{n})\)处理即可
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
struct qInfo {
int l, r, bid, id;
}q[N];
int n, m, a[N];
ll ans[N];
struct fenwick {
ll tree[N];
static int lowbit(int x) {
return -x & x;
}
void add(int x, int k) {
while(x <= n) {
tree[x] += k;
x += lowbit(x);
}
}
ll query(int x) {
ll ret = 0;
while(x) {
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
}T1;
ll tot[N], c[N], sum[N];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
cin >> a[i];
T1.add(a[i], 1);
c[i] = T1.query(a[i] - 1);
}
const int block = 700;
for(int i = 1; i <= m; i++) {
auto &[l, r, bid, id] = q[i];
scanf("%d%d", &l, &r);
id = i;
bid = l / block;
}
sort(q + 1, q + 1 + m, [&](qInfo lhs, qInfo rhs) {
if(lhs.bid != rhs.bid) {
return lhs.bid < rhs.bid;
}
return lhs.r < rhs.r;
});
int l = 1, r = 0;
ll res = 0;
for(int i = 1; i <= m; i++) {
// sum[x] 当前区间内所有权值为x的点的c之和
while(r < q[i].r) {
// add(++r);
int v = a[r + 1];
res += tot[v] * c[r + 1];
res -= sum[v];
sum[v] += c[r + 1];
tot[v]++;
r++;
}
while(r > q[i].r) {
//del(r--);
int v = a[r];
sum[v] -= c[r];
tot[v]--;
res -= tot[v] * c[r];
res += sum[v];
r--;
}
while(l < q[i].l) {
//del(l++);
int v = a[l];
tot[v]--;
sum[v] -= c[l];
res += tot[v] * c[l];
res -= sum[v];
l++;
}
while(l > q[i].l) {
//add(--l);
int v = a[l - 1];
res -= tot[v] * c[l - 1];
res += sum[v];
tot[v]++;
sum[v] += c[l - 1];
l--;
}
ans[q[i].id] = res;
}
for(int i = 1; i <= m; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
B.Circle of Mistery
题意：
给出一个\(n\)个数的数组，对于每一个长度为\(n\)的排列，排列第\(i\)个数的点权是\(a_{i}\)，若他们存在一个置换环，上面的权值之和\(\geq k\)，那么这个排列就是好的。好的排列中最少的逆序对有多少个？
思路：
显然，我们只需要找其中一个置换环进行操作，枚举原数组内包含在置换环内的左右边界为\(l,r\)。考虑如何让这个区间的逆序对最少。
假设这个区间包含在置换环内的数有\(nums\)个，区间长度\(len=r-l+1\)。最少逆序对应该是每个元素都一起后移一位，那么逆序对为\(2len - nums - 1\)，前\(nums-1\)个数产生的逆序对为\(len-nums\)，
最后一个数的逆序对为\(len-1\)。
我们只需要最大化\(nums\)，即尽量多选数，正数一定选，尽量多选负数每次扩展\(r\)时，如果当前\(r\)是负数，把他加入队列，看下一次能不能加入选择即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int &it : a) {
cin >> it;
}
// 2 * len - 1 - nums
int ans = inf;
for(int i = 0; i < n; i++) {
if(a[i] >= k) {
ans = 0;
break;
}
priority_queue<int, vector<int>, greater<>> q;
int value = a[i], nums = 1;
for(int j = i + 1; j < n; j++) {
value += a[j];
nums++;
while(!q.empty() && value + q.top() >= k) {
value += q.top();
nums++;
q.pop();
}
if(value >= k) {
ans = min(ans, 2 * (j - i + 1) - nums - 1);
}
if(a[j] < 0) {
q.emplace(a[j]);
nums--;
value -= a[j];
}
}
}
if(ans == inf) {
ans = -1;
}
cout << ans << "\n";
return 0;
}
C.Cheeeeen the Cute Cat
题意：
左右侧各有\(n\)个点，给出\(\frac{n(n-1)}{2}\)条边，设\(i(i\leq n)\)为左侧的点，右侧的点为\(i+n(i\leq n)\)，如果有边\((i,j+n)\)，那么不会有边\((j,i+n)\)。问这幅二分图图的最大匹配是多少？
思路：
把图看成只有\(n\)个点，原边\((i,j+n)\)看成新图的有向边\((i,j)\)，那么新图是一副竞赛图（强连通图图中给每条边定向）。新图中一条路径\((a,b,c,d)\)就代表着匹配\((a,b)(b,c)(c,d)\)。竞赛图一定有哈密顿路径，所以匹配一定至少是\(n-1\)，考虑什么时候能到\(n\)，即存在有这样的路径\((a,b)(b,c)(c,a)\)回到自己，即哈密顿回路。将所有点的度排序，从小到大加入，判断每个子图是不是有\(\frac{n(n-1)}{2}\)条边即可
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e3 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
int n, a[N][N], in[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
in[j] += a[i][j];
}
}
sort(in + 1, in + 1 + n);
int e = 0, lst = 0;
for(int i = 1; i <= n; i++) {
e += in[i];
if(e == i * (i - 1) / 2) {
if(i - lst < 3) {
cout << n - 1 << "\n";
return 0;
}
lst = i;
}
}
cout << n << "\n";
return 0;
}
E.Red and Blue and Green
题意：
构造一个长度为\(n\)的排列，使他满足\(m\)个限制，每个限制给出\(l,r,op\)，代表区间\([l,r]\)中的逆序对数取余\(2\)的数。这些限制给出的区间要么是相互包含，要么是不相交的关系。
思路：
区间是要么包含，要么不相交，可以考虑一颗类似于线段树的区间树，在上面dfs处理。
如果是叶子节点，直接满足他，如果不能满足，即区间长度为\(1\)，且\(op=1\)，这样是不合法的。
否则考虑现在区间的答案如何由子区间合并
-
如果当前区间含有有\(\geq2\)个子区间限制，只需要交换任意两个，把前面的最大值与后面的最小值交换，逆序对数只会\(+1\)
-
如果当前区间有超过两个位置没有被子区间限制，交换他们两个即可
-
如果只有一个子区间被限制，并且有一个空位，如果空位在前，与限制区间最小值交换，否则交换区间最大值即可
-
不满足以上任意一种情况是无解
找包含在内部的子区间只需要去重后排序，先按\(l\)小优先，再按\(r\)大优先排序，从\(1\)到\(m\)遍历即可，这样做的时间复杂度是\(O(nm)\)的
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
struct info {
int l, r, d;
info() = default;
info(int l, int r, int d)
:l(l), r(r), d(d) {}
bool operator<(const info &rhs) const {
if(l == rhs.l) {
return r > rhs.r;
}
return l < rhs.l;
}
}a[N];
bool vis[N];
int n, m, pos[N];
map<pair<int, int>, int> map1;
void dfs(int l, int r, int op) {
// printf("dfs(%d, %d, %d)\n", l, r, op);
if(l == r && op == 1) {
cout << -1 << "\n";
exit(0);
}
vector<info> son;
vector<int> space;
int lst = l, opSum = 0;
for(int i = 1; i <= m; i++) {
auto [nl, nr, nd] = a[i];
if(l <= nl && nr <= r && nr - nl < r - l && !vis[i]) {
vis[i] = true;
for(int j = lst; j < nl; j++) {
space.emplace_back(j);
}
son.emplace_back(a[i]);
dfs(nl, nr, nd);
opSum += a[i].d;
lst = nr + 1;
}
}
for(int i = lst; i <= r; i++) {
space.emplace_back(i);
}
if(son.empty()) {
for(int i = l; i <= r; i++) {
pos[i] = i;
}
if(op == 1) {
swap(pos[l], pos[r]);
}
} else {
for(int &it : space) {
pos[it] = it;
}
if(map1.count({l, r}) && opSum % 2 != op) {
if(space.size() >= 2) {
swap(pos[space[0]], pos[space[1]]);
} else if(son.size() >= 2) {
swap(pos[son[0].r], pos[son[1].l]);
} else if(space.size() + son.size() == 2) {
if(space[0] < son[0].l) {
swap(pos[space[0]], pos[son[0].l]);
} else {
swap(pos[son[0].r], pos[space[0]]);
}
} else {
cout << -1 << "\n";
exit(0);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
auto &[l, r, d] = a[i];
cin >> l >> r >> d;
if(map1.count({l, r}) && map1[{l, r}] != d) {
cout << -1 << "\n";
return 0;
}
map1[{l, r}] = d;
}
sort(a + 1, a + 1 + m);
if(map1.count({1, n})) {
dfs(1, n, map1[{1, n}]);
} else {
dfs(1, n, 1);
}
vector<int> ans(n);
for(int i = 1; i <= n; i++) {
ans[pos[i] - 1] = i;
}
for(int &it : ans) {
cout << it << " ";
}
return 0;
}
G.Go to Play Maimai DX
题意：
给出一个数组\(a\)，每个元素都在\([1,4]\)范围，问最小的区间长度，使这个区间包含有\(4\)种元素，且至少有\(k\)个\(4\)
思路：
双指针，若当前区间满足，l++，然后一直r++直到满足条件，如果当前的\(l\)不能满足，那么后面的也是
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int &it : a) {
cin >> it;
}
vector<int> c(5);
auto check = [&]() {
return c[1] && c[2] && c[3] && c[4] >= k;
};
int l = 0, r = 0, ans = inf;
c[a[l]]++;
while(l < n) {
while(r + 1 < n && !check()) c[a[++r]]++;
if(check()) {
ans = min(ans, r - l + 1);
c[a[l++]]--;
} else {
break;
}
}
cout << ans << "\n";
return 0;
}
H.Nazrin the Greeeeeedy Mouse
题意：
有\(n\)个点，有\(n-1\)个奶酪，第\(i\)个分布在\(i,i+1\)点中间，尺寸和重量分别是\(sz_{i},w_{i}\)。老鼠若想从\(i\)到\(i+1\)，则需要打地道，若本来存在奶酪，打地道后奶酪消失了，不能再拿取，地道可以重复走。老鼠有\(m\)次机会，每次都有一个背包。能装下总共尺寸不超过\(x\)的奶酪，重量任意。这一次带的背包一定比上一次尺寸大，问能最多拿多少重量的奶酪？
思路：
每一次一定走比上一次更远的地方，贪心考虑，只需要最后\(n\)次最大的背包就可以完成最好的任务了。
定义dp[i][j]第\(i\)次出发，最远拿到第\(i\)块奶酪的最多重量，f[sz][i][j]为用\(sz\)背包，区间\(l,r\)最多能取多少重量，dp是一个线性dp，f是一个区间01背包
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N = 2e2 + 5, M = 1e5 + 5;
const int inf = 0x3fffffff;
struct info {
int sz, w;
}c[N];
int n, m, bag[M];
int f[N][N], dp[N];
int g[N][N][N];
int main() {
#ifdef stdjudge
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int sz, w;
cin >> sz >> w;
c[i] = {sz, w};
}
for(int i = 1; i <= m; i++) {
cin >> bag[i];
}
if(m > n) {
for(int i = 1; i <= n; i++) {
bag[i] = bag[m - n + i];
}
m = min(m, n);
}
for(int sz = 1; sz <= 200; sz++){
for(int i = 1; i <= n; i++){
if(sz >= c[i].sz) g[sz][i][i] = c[i].w;
else g[sz][i][i] = -inf;
}
for(int len = 2; len <= n; len++){
for(int l = 1; l <= n; l++){
int r = l + len - 1;
if(r > n) break;
g[sz][l][r] = -inf;
if(sz >= c[l].sz) g[sz][l][r] = max(g[sz][l][r], g[sz - c[l].sz][l + 1][r] + c[l].w);
if(sz >= c[r].sz) g[sz][l][r] = max(g[sz][l][r], g[sz - c[r].sz][l][r - 1] + c[r].w);
g[sz][l][r] = max(g[sz][l][r], g[sz][l + 1][r]);
g[sz][l][r] = max(g[sz][l][r], g[sz][l][r - 1]);
// printf("g[%d][%d][%d] = %d\n", sz, l, r, g[sz][l][r]);
}
}
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
for(int k = j; k >= 1; k--) {
f[i][j] = max(f[i][j], f[i - 1][k - 1] + g[bag[i]][k][j]);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = max(ans, f[m][i]);
}
cout << ans << "\n";
return 0;
}
I.The Yakumo Family
题意：
给出\(n\)个数，求
思路：
需要考虑拆二进制位，考虑第\(k\)位，假设当前选择的区间的右端点为\(r\)，那么当前这一位异或的结果乘上前面区间的积一定要有我才考虑，即这一位当前区间的异或结果一定要是\(1\)，设当前这一位是\(bits\)，满足第\(k\)位的前缀异或和\(sum_{k,i}\)，有\(sum_{k,i-1}=!bits\)的\(i\)是符合条件的左端点。
设\(f[t][i]\)为选择第\(t\)个区间，右端点为\(i\)的答案，先找到一个能作为左端点的\(i\)，这部分的答案为
这个式子即\(f[t-1]\)的\(i-1\)前缀和。
这一位的答案即把所有的\(i\)的\((4)\)加起来。
根据当前为的前缀异或和是\(0/1\)分类对\(f\)的前缀和再做前缀和即可快速查询
设\(sum_{i,j,k}\)为前\(i\)个元素，第\(j\)位的前缀异或和为\(k\)的所有位置的\(f[t-1]\)的前缀和的前缀和，当前答案即
f[t][i] += sum[i-1][j][bits ^ 1] * (1 << j)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
namespace ModInt {
const int P = mod;
using i64 = long long;
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
bool operator==(const Z &rhs) const {
return this->val() == rhs.val();
}
bool operator!=(const Z &rhs) const {
return this->val() != rhs.val();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Z &a) {
i64 v;
is >> v;
v %= P;
a = Z(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Z &a) {
return os << a.val();
}
};
}
using mint = ModInt::Z;
int n, a[N], sum[N][31];
mint f[N], s[N][31][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int hb = 30;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
for(int j = 0; j <= hb; j++) {
sum[i][j] = sum[i - 1][j] ^ ((a[i] >> j) & 1);
}
}
for(int i = 1; i <= n; i++) {
f[i] = 1;
}
for(int t = 1; t <= 3; t++) {
for(int j = 0; j <= hb; j++) {
s[0][j][0] = t == 1;
}
mint pre = 0;
for(int i = 1; i <= n; i++) {
pre += f[i];
for(int j = 0; j <= hb; j++) {
s[i][j][sum[i][j]] = s[i - 1][j][sum[i][j]] + (t == 1 ? 1 : pre);
s[i][j][sum[i][j] ^ 1] = s[i - 1][j][sum[i][j] ^ 1];
}
}
for(int i = 1; i <= n; i++) {
f[i] = 0;
for(int j = 0; j <= hb; j++) {
f[i] += mint(1 << j) * s[i - 1][j][sum[i][j] ^ 1];
}
}
}
mint ans = 0;
for(int i = 1; i <= n; i++) {
ans += f[i];
}
cout << ans << "\n";
return 0;
}