当前位置:网站首页>[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])
边栏推荐
- 【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
- Essai de pénétration (1) - - outils nécessaires, navigation
- Nodejs+vue online fresh flower shop sales information system express+mysql
- China's earthwork equipment market trend report, technical dynamic innovation and market forecast
- VS2019初步使用
- Opencv learning log 18 Canny operator
- HDU - 6024 Building Shops(女生赛)
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
- 【练习-5】(Uva 839)Not so Mobile(天平)
- Research Report on market supply and demand and strategy of China's Medical Automation Industry
猜你喜欢
C语言学习笔记
Essai de pénétration (1) - - outils nécessaires, navigation
Matlab example: two expressions of step function
Gartner: five suggestions on best practices for zero trust network access
C语言是低级和高级的分水岭
Matlab comprehensive exercise: application in signal and system
Web based photo digital printing website
Determine the Photo Position
洛谷P1102 A-B数对(二分,map,双指针)
Borg Maze (BFS+最小生成树)(解题报告)
随机推荐
信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
动态规划前路径问题优化方式
JS调用摄像头
If you want to apply for a programmer, your resume should be written like this [essence summary]
Opencv learning log 32 edge extraction
C语言数组的概念
Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
Cost accounting [14]
Accounting regulations and professional ethics [4]
【练习4-1】Cake Distribution(分配蛋糕)
Market trend report, technical innovation and market forecast of geosynthetic clay liner in China
Cost accounting [22]
【练习-6】(Uva 725)Division(除法)== 暴力
Gartner:关于零信任网络访问最佳实践的五个建议
Web based photo digital printing website
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
China medical check valve market trend report, technical dynamic innovation and market forecast
Opencv learning log 33 Gaussian mean filtering
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
MySQL授予用户指定内容的操作权限