当前位置:网站首页>[exercise-4] (UVA 11988) broken keyboard = = (linked list)
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
2022-07-06 15:56:00 【Flame car】
Broken Keyboard
Description
You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally).
You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).
In Chinese, we can call it Beiju. Your task is to find the Beiju text.
Input
There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[’ and ‘]’. ‘[’ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file (EOF).
Output
For each case, print the Beiju text on the screen.
Samples
Input
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
Output
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University
Translate :
You have a broken keyboard . All keys on the keyboard work properly , But sometimes Home Key or End The key will be pressed automatically . You didn't know there was a problem with keyboards , But concentrate on typing , I didn't even turn on the monitor . When you turn on the monitor , In front of you is a tragic text . Your task is to calculate this tragic text before turning on the monitor again .
Um. , This problem is done with a linked list .
AC Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
int main()
{
string s;
while(cin>>s)
{
int len = s.size();
s = '0'+s;
int next[N]={
0},last,pin;
last = pin = 0;
for(int i=1;i<=len;i++)
{
char ch=s[i];
if(ch=='[')
pin=0;
else if(ch==']')
pin=last;
else
{
next[i]=next[pin];
next[pin]=i;// These two sentences correspond to the train of thought 4
if(last == pin)
last = i;
pin = i;
}
}
for(int i=next[0];i!=0;i=next[i])
cout<<s[i];
cout<<endl;
}
}
Tip:Home The key will make the cursor jump to the front of the first character ,End Key will make the cursor jump after the last character .
Ideas :
① We need to know the position of the cursor with pin To record .
② We need to know that the position of the last character is last To record .
③ When ’[' The timeline jumps to the front 0 The location of , When ‘]’ The chronometer jumps to the end last.
④ When inserting characters in the middle , Should be : Let the next Is the previous character next, And put the previous character next Change to this character .( This can also be done at the end , It's just the character next yes 0 That's the end )
Why should I make strings s become ‘0’+s Well …… Because I want to output this linked list , I will have a starting position , But I don't know where I start , So I assumed a starting position ( Location 0 And it won't change ), In this case, it will be better to retreat the whole string by one .
==》( Ideas ④ The idea of inserting in the middle of can be used at the end , But it can't be used in the front , If there are no characters before , So his next There is no such thing as , This character cannot become the character of the previous character next, So we assume that there is a team leader who will not change , When outputting, you can directly i = next[0])
边栏推荐
- Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
- Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
- Interesting drink
- 信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
- Path problem before dynamic planning
- C 基本语法
- Optimization method of path problem before dynamic planning
- 【练习-8】(Uva 246)10-20-30==模拟
- Cost accounting [19]
- MATLAB综合练习:信号与系统中的应用
猜你喜欢
Optimization method of path problem before dynamic planning
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
X-Forwarded-For详解、如何获取到客户端IP
信息安全-安全编排自动化与响应 (SOAR) 技术解析
Gartner:关于零信任网络访问最佳实践的五个建议
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
Information security - threat detection engine - common rule engine base performance comparison
【练习-7】Crossword Answers
1010 things that college students majoring in it must do before graduation
随机推荐
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
Research Report on surgical fluid treatment industry - market status analysis and development prospect prediction
【高老师UML软件建模基础】20级云班课习题答案合集
Nodejs+vue网上鲜花店销售信息系统express+mysql
Opencv learning log 19 skin grinding
Gartner:关于零信任网络访问最佳实践的五个建议
Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
D - Function(HDU - 6546)女生赛
Web based photo digital printing website
TCP的三次握手与四次挥手
Learning record: USART serial communication
Cost accounting [24]
信息安全-安全编排自动化与响应 (SOAR) 技术解析
【练习-7】Crossword Answers
China earth moving machinery market trend report, technical dynamic innovation and market forecast
Research Report on market supply and demand and strategy of China's Medical Automation Industry
动态规划前路径问题优化方式
Borg Maze (BFS+最小生成树)(解题报告)
Cost accounting [15]
Flink 使用之 CEP