洛谷普及组P1044栈，题目讲解(无数论基础，纯打表找规律)

[NOIP2003 普及组] 栈 - 洛谷

我先写了个打表的代码，写了一个小时，o(╥﹏╥)o只能说我真不擅长dfs。

int n;
std::unordered_map<std::string, int>map;
void dfs(std::vector<int>&a, int step,std::stack<int>p, std::string s) {
	if (step == n + 1) {
		if (map.find(s) == map.end() && s.size() == n) {
			map[s] = 1;
			return;
		}
		else {
			while (!p.empty()) {
				s.push_back('0'+p.top());
				p.pop();
			}
			if (map.find(s) == map.end()) {
				map[s] = 1;
				return;
			}
			return;
		}
	}
	for (int i = 1; i <= 2; i++) {
		if (i == 1&&!p.empty()) {
			s.push_back('0'+p.top());
			int x = p.top();
			p.pop();
			dfs(a,step, p, s);
			s.pop_back();
			p.push(x);

		}
		else if (i == 2) {
			p.push(a[step]);
			dfs(a,step + 1, p, s);
			s.push_back('0'+p.top());
			p.pop();
			dfs(a,step + 1, p, s);
			s.pop_back();
		}
	}
}
int main() {
	std::cin >> n;
	std::vector<int>a(n + 1);
	for (int i = 1; i <= n; i++)a[i] = i;
	std::stack<int>p;
	std::string s;
	dfs(a,1,p,s);
	std::cout << map.size() << '\n';
	std::vector<std::string>c(map.size());
	int i = 0;
	for (auto x : map) {
		c[i] = x.first;
		i++;
	}
	std::sort(c.begin(), c.end());
	for (int i = 0; i < c.size(); i++)std::cout << c[i] << '\n';
	return 0;
}

然后我们可以发现

所以可以得到以下代码

#include<iostream>
#include<vector>

using i64 = long long;
i64 a[19], b[19],sum,sum1,c[19];
int main() {
	a[1] = 1;
	i64 n,m=0,p=0;
	std::cin >> n;
	c[1] = 1; c[2] = 2; sum = 2,a[1]=1,a[2]=1;
	for (int i = 3; i <= n; i++) {
		i & 1 ? (b[1] = sum, b[2] = sum ,sum1=sum*2): (a[1] = sum1, a[2] = sum1,sum=sum1*2);
		if (i & 1) {
			for (int j = 3; j <= i; j++) {
				b[j] = sum - a[j - 2];
				sum -= a[j - 2];
				sum1 += b[j];
			}
			c[i] = sum1;
		}
		else {
			for (int j = 3; j <= i; j++) {
				a[j] = sum1 - b[j - 2];
				sum1 -= b[j - 2];
				sum += a[j];
			}
			c[i] = sum;
		}
	}
	std::cout << c[n] << '\n';
	return 0;
}

?这里模拟了一下缓冲区交换，因为每次都要更改前n项。

不想讲了，有时间把解析补全。

花了我一晚上，这普及有点东西，只能说我太菜了。