当前位置:网站首页>String modification problem solving Report
String modification problem solving Report
2022-07-05 15:25:00 【wch(】
String Modification Problem solving report
label : character string Looking for a regular simulation
The question :
Given a length of n(1≤n≤5000 ) String , Traverse from the beginning , For each k Flip the length subsequence , Find the one with the smallest dictionary order and k Value , If there are multiple dictionaries with the smallest order , requirement k Minimum .
Their thinking
First, find out the rules through simulation
Set string 12345;
k=1 12345
k=2 2345 1
k=3 345 21
k=4 45 123
k=5 5 4321
You can find If we divide strings into pre sequence and post sequence , The inverted sequence will be the exchange position of the front and rear sequences , According to the current example, the original pre sequence follows k And decide whether to flip , In addition, the length of the previous sequence can be determined to be k-1.
Set string 123456
k=3 3456 12
k=4 456 321
From these two examples, we can find : Whether the previous sequence is reversed is determined by k And string length n Of or related to .
Code implementation
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s,ans;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
cin>>s;
ans=s;
int k=1;
for(int i=2;i<=n;i++){
string s1,s2,s3;
s1=s.substr(0,i-1);
s2=s.substr(i-1);// from i-1 Until the position of is taken back
if((n-i)%2==0) reverse(s1.begin(),s1.end());
s3=s2+s1;
if(s3<ans){
k=i;
ans=s3;
}
}
cout<<ans<<endl;
cout<<k<<endl;
}
}
边栏推荐
- 超越PaLM!北大硕士提出DiVeRSe,全面刷新NLP推理排行榜
- Stm32+bh1750 photosensitive sensor obtains light intensity
- Fr exercise topic - simple question
- SQL Server learning notes
- 如何将 DevSecOps 引入企业?
- maxcompute有没有能查询 表当前存储容量的大小(kb) 的sql?
- Photoshop plug-in action related concepts actionlist actiondescriptor actionlist action execution load call delete PS plug-in development
- Can I pass the PMP Exam in 20 days?
- Database learning - Database Security
- Leetcode: Shortest Word Distance II
猜你喜欢
Fr exercise topic - simple question
Talking about how dataset and dataloader call when loading data__ getitem__ () function
CSRF, XSS science popularization and defense
I spring and autumn blasting-1
SQL Server learning notes
lvgl 显示图片示例
Reasons and solutions for redis cache penetration and cache avalanche
I include of spring and Autumn
Bugku alert
Ten billion massage machine blue ocean, difficult to be a giant
随机推荐
lv_font_conv离线转换
做研究无人咨询、与学生不交心,UNC助理教授两年教职挣扎史
Can gbase 8A view the location of SQL statement history?
机器学习框架简述
Magic methods and usage in PHP (PHP interview theory questions)
Where is the operation of convertible bond renewal? Is it safer and more reliable to open an account
Photoshop plug-in action related concepts actionlist actiondescriptor actionlist action execution load call delete PS plug-in development
Talk about your understanding of microservices (PHP interview theory question)
[recruitment position] Software Engineer (full stack) - public safety direction
Huiyuan, 30, is going to have a new owner
Huawei Hubble incarnation hard technology IPO harvester
MySQL之CRUD
数据库学习——数据库安全性
mapper. Comments in XML files
B站做短视频,学抖音死,学YouTube生?
Using tensorboard to visualize the training process in pytoch
ICML 2022 | explore the best architecture and training method of language model
Bubble sort, insert sort
百亿按摩仪蓝海,难出巨头
Fr exercise topic - simple question