CF1556 - Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)

D. Take a Guess

题意

有一个长度为 $N$ 的序列每次你可以询问两个值的与值和或值，求出原序列中第k大值。

询问不能超过 $2N$ 次。

思路

与位运算有关的恒等式请见blog中的这篇文章，下文使用了文章中一些恒等式。

对 $a+b=(a|b)+(a\&b)$ 的直接应用。

如果有了 $a+b, a+c, b+c$，那么很容易求出 $a = \frac{(a+b)+(a+c)-(b+c)}{2}$，而求每个 $a+b$ 只需要两次询问，所以先求出第一个元素，那么后面所有的元素，都可以通过两次询问得出，询问次数 $2N$ 次。

这里还有更优的方法，只需要询问 $\frac{5N}{3}$ 次来自CF评论，还是考虑求出三元组：$(a, b, c)$，但只通过5次询问 $a\&b, a|b, a\&c, a|c, b\&c$，

先通过恒等式 $a+b=(a|b)+(a\&b)$，求出 $a+b, a+c$，再通过恒等式 $a\oplus b = (a|b)\oplus(a\&b)$，求出 $a\oplus b, a\oplus c$，

进一步可以求出来 $b\oplus c$，于是再通过恒等式 $b+c=2(b\&c)+(b\oplus c)$，可以得出 $b+c$，于是我们就可以通过5次询问，获得 $a, b, c$的值了！

下面代码所用的是 $2N$ 次询问的做法：

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	int n, k;
	cin >> n >> k;
	vi And(n+1), Or(n+1);
	for (int i = 2; i <= n; i++) {
		cout << "and " << 1 << ' ' << i << '\n';
		cout << "or " << 1 << ' ' << i << '\n';
		cin >> And[i] >> Or[i];
		cout.flush();
	}
	cout << "and " << 2 << ' ' << 3 << '\n';
	cout << "or " << 2 << ' ' << 3 << '\n';
	cout.flush();
	int x, y;
	cin >> x >> y;
	vi a(n+1);
	a[1] = (And[2] + Or[2] + And[3] + Or[3] - x - y) / 2;
	for (int i = 2; i <= n; i++) {
		a[i] = And[i] + Or[i] - a[1];
	}
	sort(a.begin(), a.end());
	cout << "finish " << a[k] << '\n';
	return 0;
}

E. Equilibrium

题意

给出两个长度为 $n$ 的序列 $\{a_n\}, \{b_n\}$，你可以进行如下操作：

• 选择一个长度为偶数的严格单调递增序列：$pos_1 < pos_2< \cdots < pos_{2k}$。

• 将 $\{a_n\}$ 中对应下标为 $pos_1, pos_3, \cdots, pos_{2k-1}$ 的数值都+1。

• 将 $\{b_n\}$ 中对应下标为 $pos_2, pos_4, \cdots, pos_{2k}$ 的数值都+1。

接下来有 $Q$ 次询问，每次询问给出一个区间 $[l, r]$，求能否用若干次上述操作，使得 $a_i=b_i, l\leqslant i\leqslant r$。

如果可以输出最小的操作次数，否则输出-1。

思路

由于每次操作，对数组 $a, b$ 发生变化元素的个数和大小总是相同的，所以考虑将两者做差。

令 $c_i=b_i-a_i$，若 $c_i$ 在 $[l,r]$ 上满足以下两个条件，则一定有解：

• $\sum_{i=l}^r c_i=0$

• $\forall k \in [l, r], \sum_{i=l}^k c_i \geqslant 0$

第一个条件：因为每次 $a,b$ 数组同时进行+1，所以两者做差之和总是 $0$。优化方法，对 $c$ 数组求前缀和。

第二个条件：不妨假设 $c_l < 0$，这说明 $a_l > b_l$，又由于第一个元素只能是+1，只会越加越大，所以不满足题意。优化方法，对 $c$ 数组的前缀和数组求区间最大值和区间最小值，记最大值为 $\text{MAX}$，最小值为 $\text{MIN}$，如果 $\text{MIN}-sum[l-1] < 0$ 无解，否则答案即为 $\text{MAX}-sum[l-1]$，因为只需要将最大的一块减成 $0$ 就能保证其他小块都减成 $0$ 了。

用ST表求区间最值，时间复杂度 $O(n\log n + Q)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 1e5 + 10;
int n, Q;
int a[N], b[N], c[N], Log[N], sum[N];
int mn[N][20], mx[N][20];
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> Q;
	Log[0] = -1;
	for (int i = 1; i <= n; i++) Log[i] = Log[i>>1] + 1;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		c[i] = b[i] - a[i];
		sum[i] = sum[i-1] + c[i];
		mn[i][0] = mx[i][0] = sum[i];
	}
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			mn[i][j] = min(mn[i][j-1], mn[i+(1<<(j-1))][j-1]);
			mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
		}
	}
	while (Q--) {
		int l, r;
		cin >> l >> r;
		int len = r - l + 1;
		int Mn = min(mn[l][Log[len]], mn[r-(1<<Log[len])+1][Log[len]]) - sum[l-1];
		int Mx = max(mx[l][Log[len]], mx[r-(1<<Log[len])+1][Log[len]]) - sum[l-1];
		if (Mn < 0 || sum[r] - sum[l-1] != 0) cout << -1 << '\n';
		else cout << Mx << '\n';
	}
	return 0;
}

H. DIY Tree

题意

给出 $n$ 个点的完全图，并给出每条边的边权，求该图的生成树，使得前 $k$ 的节点的度，不超过给定值，并要求整棵生成树的权值最小。（树的权值定义：树上所有边权之和。

数据范围：$2\leqslant n\leqslant 50, 1\leqslant k\leqslant\min(n-1, 5)$。

思路

从CF评论中学的模拟退火。

数据量较小。

1. 先构造一个满足题意的生成树（比如所有节点都和 $n$ 节点连边）

2. 用模拟退火算法，每次随机删除、随机添加有效边。

时间复杂度不会 ′(*>﹏<*)′

下面代码使用了多次退火，卡时5500ms过的，正确率还行。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 60;
int n, k, sum, ans = INF, st;
int mx[N], d[N], w[N][N], fa[N];
vp e;
int getfa(int x) {
	return (fa[x] == x) ? x : fa[x] = getfa(fa[x]);
}
void anneal() {
	for (db T = 100000.0; T >= 1e-5; T *= 0.99996) {
		int x = rand() % e.size();
		d[e[x].first]--;
		d[e[x].second]--;
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 0; i < e.size(); i++) if (i != x) fa[getfa(e[i].first)] = getfa(e[i].second);
		int nw = sum - w[e[x].first][e[x].second];
		int u = rand() % (n-1) + 1;
		int v = rand() % (n-u) + u + 1;
		while (getfa(u) == getfa(v) || mx[u] == d[u] || mx[v] == d[v]) {
			u = rand() % (n-1) + 1;
			v = rand() % (n-u) + u + 1;
		}
		nw += w[u][v];
		if (exp(-(db)(nw - sum)/T) >= (db)rand()/RAND_MAX) {
			sum = nw;
			e.erase(e.begin() + x);
			d[u]++;
			d[v]++;
			e.pb({u, v});
		} else {
			d[e[x].first]++;
			d[e[x].second]++;
		}
		if ((db)(clock() - st) / CLOCKS_PER_SEC >= 5.5) break;
	}
	ans = min(ans, sum);
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	srand(time(NULL));
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= k; i++) cin >> mx[i];
	for (int i = k+1; i <= n; i++) mx[i] = INF;
	for (int i = 1; i < n; i++) for (int j = i+1; j <= n; j++) cin >> w[i][j];
	for (int i = 1; i < n; i++) {
		e.pb({i, n});
		d[i]++;
		d[n]++;
		sum += w[i][n];
	}
	int st = clock();
	do anneal(); while ((db)(clock() - st) / CLOCKS_PER_SEC < 5.5);
	cout << ans << '\n';
	return 0;
}