寒假训练2024/1/31

今天主要是补题。

codeforce161E - Increasing Subsequences

题意：

T 组询问，每次给你一个 X($[2, 10^{18}]$)，你需要构造一个长度不超过 200，值域 $∈[−10^9,109]$ 的序列使得其单调上升子序列个数恰为 X（包含空子序列且不同位置的相同上升子序列算作不同的上升子序列）。

思路：

折磨死我了，想了好久，想出来又写了俩小时（我是低能儿）

看这个x和n的数据量我觉得这个题一定与二进制有关系。

然后我又推算了一下，长度为m的严格递增的序列能得到的上升子序列是$2^m - 1$个（不加空集）

把空集抠出来，X = 1 + ($2^{a1} + 2^{a2} + ...+2^{ak}$)

按照这个思路，我写了一版代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	cin >> n;

	int t = log2(n + 1);
	if(pow(2, t) == n + 1) {
		cout << t << endl;
		for (int i = 0; i < t; i++) {
			cout << i << " ";
		}
		cout << endl;
	}
	else {
		cout << t + n - pow(2, t) << endl;
		for (int i = 1; i <= t; i++) {
			cout << i << " ";
		}
		for (int i = 0; i < n - pow(2, t); i++) {
			cout << 1 << ' ';
		}
		cout << endl;
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int T = 1;
	cin >> T;

	while(T--) {
		solve();
	}

	return 0;
}

赛后我看wa的原因：题目要求序列元素200个以内，这个就是超过了，计算一下，大约就是$(\log_2x)^2$ 个，所以会超。

我看了一下题解，其实看了半天。

”首先，一个长为 n 的递增串能贡献的数量是 $2^n$-1。但是如果直接做是 $(\log_2x)^2$的，过不了。考虑每次在前，x个数的后面插入一个比它们都大的值的贡献是 2”，所以最开始直接插入 n个数，将减去$2^n$-1.然后再将x二进制拆分即可。“

看了这个博主说的，好像有点道理。

我又看了一眼第三个样例，是

13扣除去空集就是12，12 - 7 = 5

可以推出，一开始是三个数字，3 4 5，根据5的二进制101，在后面2个元素的位置插入和后面0个元素的时候插入，正好是答案。而且注意后面插入的数一定是比之前插入的要小从高位开始看，插入的元素递减。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long

vector<int>pw;
void solve() {
	int n;
	cin >> n;

	vector<int>v;
	n--;
	int t = std::__lg(n + 1);
	v.push_back(t);
	t = n - pw[t] + 1;
	
	int cnt = 0;
	while(t) {
		if(t & 1) {
			v.push_back(cnt);
		}
		cnt++;
		t >>= 1;
	}

	sort(v.begin(), v.end(), greater());
	int nn = v.size() + v[0] - 1;
	cout << nn << endl;

	vector<int>ans;
	int st = nn - v.front() + 1;
	for (int i = st; i <= nn; i++) {
		ans.push_back(i);
	}

	t = v.size() - 1;
	for (int i = 1; i < v.size(); i++) {
		ans.insert(ans.end() - v[i], t--);
	}
	
	for (auto it : ans) {
		cout << it << " ";
	}

	cout << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 1;
	for (int i = 0; i <= 64; i++) {
		pw.push_back(t);
		t *= 2;
	}
	int T = 1;
	cin >> T;

	while(T--) {
		solve();
	}

	return 0;
}

注意两个地方：记得数据范围，会mle。还有就是别用pow，高幂会丢失精度。