目录
1.爱丽丝的人偶
2.集合
3.最长回文子序列
1.爱丽丝的人偶
链接
简单叙述就是每个数的左右两边不能一个比他大，一个比他小。
反之，就是要让每个数的左右两边数都大于或者都小于他。
方法一：一开始我想复杂了，其实用试错法去试（试多几种方法），最后发现可以直接交换该数和其后面的一个数即可。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
arr[i] = i;
for (int i = 1; i <= n; i += 2)
if (i + 1 <= n)
swap(arr[i], arr[i + 1]);
for (int i = 1; i <= n; ++i)
cout << arr[i] << ' ';
cout << endl;
return 0;
}方法二：放个⼩的之后，再放个⼤的
#include <iostream>
using namespace std;
int n;
int main()
{
cin >> n;
int left = 1, right = n;
while (left <= right)
{
cout << left << " ";
left++;
if (left <= right)
{
cout << right << " ";
right--;
}
}
return 0;
}2.集合
链接
方法一：
哈希表存储，从1 往 n 遍历，只要cnt[i] != 0，就存入ret（数组）。
最后遍历数组打印即可。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a1[N];
int a2[N];
int cnt[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> a1[i];
cnt[a1[i]]++;
}
for (int i = 1; i <= m; ++i)
{
cin >> a2[i];
cnt[a2[i]]++;
}
vector<int> ret;
for (int i = 1; i < N; ++i)
if (cnt[i] != 0)
ret.push_back(i);
sort(ret.begin(), ret.end());
for (int x : ret)
cout << x << ' ';
cout << endl;
return 0;
}方法二：
利用set的特性，直接读入，然后打印。
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int n1[N];
int n2[N];
int main() {
cin >> n >> m;
set<int> s;
int x;
for(int i = 0; i < n + m; ++i)
{
cin >> x;
s.emplace(x);
}
for(int e : s)
cout << e << ' ';
cout << endl;
return 0;
}3.最长回文子序列
链接
一道动态规划 - 区间dp题目。
难点就是动态转移方程了：
#include <iostream>
using namespace std;
const int N = 1010;
int dp[N][N];
int main() {
string s;
cin >> s;
int n = s.size();
// 初始化
dp[0][0] = dp[n - 1][n - 1] = 1;
// 填表
for(int i = n - 1; i >= 0; --i)
{
for(int j = 0; j <= n - 1; ++j)
{
if(i > j)
dp[i][j] = 0;
else if(i == j)
dp[i][j] = 1;
else
{
if(s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
cout << dp[0][n - 1] << endl;
return 0;
}
