1.爱丽丝的人偶
题目意思就是构造一个序列，序列的每个元素要么比左右两个高，要么比左右两个低。
可以看成是一条上下波动的曲线。
我们可以模拟波动的这个过程。
假设有一个数组，里面元素是1-n.遍历每一个位置。用一个指针pos来表示当前检查的位置，从2开始。
从2开始，看左右两边是不是都大于他或者都小于他，如果不是，说明要调整位置。
怎么调整呢？直接跟后面这个数交换就好了。
后面这个数一定比2大，所以交换之后2原来的位置的那个数一定符合要求。因为他比左右两边的数都大了。然后pos后移动。
假设n为7，具体交换过程如下：
代码：
#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; cin>>n; vector<int> v(n+1); for(int i=1;i<=n;i++)v[i]=i; int pos=2; while(pos<n){ if(v[pos]>v[pos-1]&&v[pos+1]>v[pos]){ swap(v[pos],v[pos+1]); } pos++; } for(int i=1;i<=n;i++)cout<<v[i]<<" "; cout<<endl; return 0; }
2.集合
考察set的使用
代码：
#include <iostream> #include<vector> #include<set> #include<queue> using namespace std; int main() { set<int> s; int n,m; cin>>n>>m; for(int i=0;i<n+m;i++){ int x; cin>>x; s.insert(x); } for(auto& it:s){ cout<<it<<" "; } return 0; } // 64 位输出请用 printf("%lld")
3.最长回文子序列
递归或者动态规划。递归的话，用一个函数表示fun（l,r）最长的回文子序列是多少。自底向上递归。如果str[l]==str[r],说明fun(l,r)=fun(l+1,r-1)+2。因为，相同的两个字符是一定可以添加到子序列回文串的首尾两端的。如果不相等，那就往长度减一的子序列里面去找，即fun(l+1,r)，或者·fun(l,r-1)。
由于题目已经交上去了，就没写递归版本的代码了。
动态规划其实就是模拟这个思路的。
从长度为1开始，逐渐扩散。
dp[l][r]表示，[l,r]的范围内的回文字符串最长能到多少。不一定这个最长序列包含str[l]和str[r].
状态转移方程与递归方程一致.
代码：
#include <iostream> #include<string> #include<vector> using namespace std; int main() { string str; cin>>str; int n=str.size(); vector<vector<int>> f(n+1,vector<int>(n+1)); int ans=1; for(int len=1;len<=n;len++){ for(int l=0;l+len-1<n;l++){ int r=l+len-1; if(len==1){ f[l][r]=1; continue; } if(str[l]==str[r]){ f[l][r]=f[l+1][r-1]+2; }else{ f[l][r]=max(f[l+1][r],f[l][r-1]); } ans=max(ans,f[l][r]); } } cout<<ans<<endl; return 0; }
