手机网站制作推荐,安徽网站建设微信开发,山东集团网站建设 中企动力,网络服务和 网络管制问题C日常刷题积累 今日刷题汇总 - day0211、爱丽丝的人偶1.1、题目1.2、思路1.3、程序实现 2、集合2.1、题目2.2、思路2.3、程序实现 -- set 3、最长回文子序列3.1、题目3.2、思路3.3、程序实现 -- dp 4、题目链接 今日刷题汇总 - day021
1、爱丽丝的人偶
1.1、题目 1.2、思路
… C日常刷题积累 今日刷题汇总 - day0211、爱丽丝的人偶1.1、题目1.2、思路1.3、程序实现 2、集合2.1、题目2.2、思路2.3、程序实现 -- set 3、最长回文子序列3.1、题目3.2、思路3.3、程序实现 -- dp 4、题目链接 今日刷题汇总 - day021
1、爱丽丝的人偶
1.1、题目 1.2、思路
读完题知道让我们将一个有序的身高序列重新排队要求除了第一个和最后一个元素外不能让x的前、后元素一个比它高一个比它矮求怎么摆能够满足上述条件并摆放所有玩偶。那么分析题目和示例得知不能让x的前后具有相异性那么要么全部比x大要么全部比x小即可。既然如此我第一个摆放最小的1第二个摆放最大的n再接着拜访次小的2再接着摆放次大的n-1即可。发现这个规律后就按照这个逻辑实现即可。接下来就是程序实现。
1.3、程序实现
根据题目和思路分析由于是有序序列那么直接按照先放置小的再放大的顺序循环即可。
#include iostreamusing namespace std;int main()
{int n;cin n;int left 1;int right n;while(left right){cout left ;left;if(left right){cout right ;right--;}}return 0;
}2、集合
2.1、题目 2.2、思路
读完题知道要求实现两个集合的相加其中相加之后的集合中不能出现相同元素。首先能够想到得基本思想就是归并排序先把A,B集合sort排序然后进行归并排序最后去重输出。那么既然如此简化思路就是将A,B集合需要放入同一个容器中然后排序去重即可。恰好得是C提供了一个set关联式容器set作为一个容器也是用来存储同一数据类型的数据类型并且能从一个数据集合中取出数据在set中每个元素的值都唯一而且系统能根据元素的值自动进行排序。需要注意的是set中元素的值不能直接被改变。 底层本质C STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树红黑树也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树所以被STL选择作为了关联容器的内部结构。 所以对于这道题使用set可以完美解决问题。
2.3、程序实现 – set
首先按照要求和思路分析引入#include 头文件然后采用预处理方式按照题目输入和插入到同一个容器s中自动完成排序与去重最后直接遍历输出即可。
#include iostream
#include set
using namespace std;int main()
{int n,m;cin n m;setint s;int A,B;for(int i 0;i n;i){cin A;s.insert(A);}for(int i 0;i m;i){cin B;s.insert(B);}for(auto num : s){cout num ;}return 0;
}3、最长回文子序列
3.1、题目 3.2、思路
读完题知道跟之前做过的题连续子数组最大和类似都不是固定长度的可以是任意长度的可能所以不采用滑动窗口而采用dp动态规划。求一个字符串中最长的回文子序列其中本题中子序列字符串任意位置删除klen(s)k0个字符后留下的子串。那么子序列是不定长的情况所以动态规划法需要状态表示以dp[i][j]表示在第 [ i , j ] 区间的回文字符串最大长度推导状态转移方程当回文字符串长度为一个字符时则 i 等于 j 直接输出1即可然后要求最大回文串那么当字符串本身就是回文时就是最大长度另外本身不是字符串的情况下就又分为左边去掉一个字符组成的区间dp[i1][j]右边去掉一个字符组成的区间dp[i][j-1]为次打区间如果满足回文时就是最大回文。所以状态转移方程情况分为 a、当i j 的时候只有⼀个字符⻓度为1 b、当i j 的时候分情况讨论 (1)、str[i] str[j]时dp[i][j] dp[i 1][j - 1] 2; (2)、str[i] ! str[j]时dp[i][j] max(dp[i 1][j], dp[i][j - 1]) 另外注意初始化为了处理长度为1时的情况所以置dp[i][i] 1;表示每个单独的字符都是长度为1的回文子序列 和 返回值长度为n的字符串满足[0,n)区间所以输出是dp[0][n-1]即可。那么接下来就是程序实现。
3.3、程序实现 – dp
首先根据思路分析得出即可
状态表⽰ dp[i][j] 表⽰字符串[i, j] 范围内的最⻓回⽂⼦序列的⻓度状态转移⽅程 a、当i j 的时候只有⼀个字符⻓度为1 b、当i j 的时候分情况讨论 c、s[i] s[j]dp[i][j] dp[i 1][j - 1] 2; d、s[i] ! s[j]dp[i][j] max(dp[i 1][j], dp[i][j - 1])初始化 dp[i][i] 1 。返回值 dp[0][n - 1] 。
#include iostream
#include string
using namespace std;int dp[1001][1001];int main()
{string str;cin str;int n str.size();for(int i n-1;i 0;i--){dp[i][i] 1;for(int j i 1;j n;j){if(str[i] str[j])dp[i][j] dp[i1][j-1] 2;elsedp[i][j] max(dp[i1][j],dp[i][j-1]);}}cout dp[0][n-1] endl;return 0;
}4、题目链接
爱丽丝的人偶 集合 最长回文子序列
