【笔试训练】day21

简介: 【笔试训练】day21

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


目录
打赏
0
0
0
0
18
分享
相关文章
kde
|
6天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
3900 8
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
665 1
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
1011 11
【保姆级图文详解】大模型、Spring AI编程调用大模型
【保姆级图文详解】大模型、Spring AI编程调用大模型
440 7
【保姆级图文详解】大模型、Spring AI编程调用大模型
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
|
3天前
typora免费版,激活方法,Typora使用教程
Typora是一款简洁高效的Markdown编辑器,支持即时渲染。本教程涵盖安装方法、文件操作、视图控制、格式排版、字体样式及Markdown语法,助你快速上手使用Typora进行高效写作。
708 0
Excel数据治理新思路:引入智能体实现自动纠错【Python+Agent】
本文介绍如何利用智能体与Python代码批量处理Excel中的脏数据,解决人工录入导致的格式混乱、逻辑错误等问题。通过构建具备数据校验、异常标记及自动修正功能的系统,将数小时的人工核查任务缩短至分钟级,大幅提升数据一致性和办公效率。
让AI时代的卓越架构触手可及,阿里云技术解决方案开放免费试用
阿里云推出基于场景的解决方案免费试用活动,新老用户均可领取100点试用点,完成部署还可再领最高100点,相当于一年可获得最高200元云资源。覆盖AI、大数据、互联网应用开发等多个领域,支持热门场景如DeepSeek部署、模型微调等,助力企业和开发者快速验证方案并上云。
337 24
让AI时代的卓越架构触手可及,阿里云技术解决方案开放免费试用
企业如何用Data Agent实现数据价值效率的飞跃
在数字化转型背景下,数据被视为“新时代的石油”,但多数企业仍面临数据价值难以高效挖掘的困境。文章深入剖析了当前数据分析中存在的“被动响应”模式及其带来的四大挑战,并提出通过Data Agent实现主动智能与数据分析民主化的新路径。Data Agent基于大语言模型和强化学习技术,具备理解、思考与行动能力,能够从“人找数据”转变为“数据找人”,推动数据洞察从专业人员走向全员参与。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问