[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项。

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

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