C++笔试强训day21

目录

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;
}