牛客多校5

yawnsheep / 2023-08-04 / 原文

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}\)

\[\sum c_{r+1}-c_{i} \]

我们计算区间的时候,再记录一个tot[x]\(x\)出现了多少次,sum[x]为区间内权值为\(x\)的位置的\(c\)之和

那么\((1)\)就可以写作

\[tot_{x}c_{r+1}-sum[c_{r+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\)个数,求

\[\sum_{1\leq l_{1}\leq r_{1} < l_{2}\leq r_{2} < l_{3}\leq r_{3} \leq n }XOR(l_{1},r_{1})\times XOR(l_{2},r_{2})\times XOR(l_{3},r_{3}) \]

思路:

需要考虑拆二进制位,考虑第\(k\)位,假设当前选择的区间的右端点为\(r\),那么当前这一位异或的结果乘上前面区间的积一定要有我才考虑,即这一位当前区间的异或结果一定要是\(1\),设当前这一位是\(bits\),满足第\(k\)位的前缀异或和\(sum_{k,i}\),有\(sum_{k,i-1}=!bits\)\(i\)是符合条件的左端点。

\(f[t][i]\)为选择第\(t\)个区间,右端点为\(i\)的答案,先找到一个能作为左端点的\(i\),这部分的答案为

\[2^{bits}\sum_{j=1}^{i-1}f[t-1][j] \]

这个式子即\(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;
}