当前位置:网站首页>[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])
边栏推荐
- 滲透測試 ( 1 ) --- 必備 工具、導航
- C语言是低级和高级的分水岭
- SSM框架常用配置文件
- STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
- Opencv learning log 19 skin grinding
- 洛谷P1102 A-B数对(二分,map,双指针)
- China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
- 【练习-10】 Unread Messages(未读消息)
- Essai de pénétration (1) - - outils nécessaires, navigation
- Learning record: STM32F103 clock system overview working principle
猜你喜欢
C语言学习笔记
用C语言写网页游戏
【高老师UML软件建模基础】20级云班课习题答案合集
渗透测试 ( 1 ) --- 必备 工具、导航
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
C语言是低级和高级的分水岭
Learning record: USART serial communication
Learning records: serial communication and solutions to errors encountered
Learning record: STM32F103 clock system overview working principle
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
随机推荐
Learning records: serial communication and solutions to errors encountered
【高老师UML软件建模基础】20级云班课习题答案合集
信息安全-威胁检测引擎-常见规则引擎底座性能比较
Cost accounting [15]
Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
力扣刷题记录--完全背包问题(一)
程序员的你,有哪些炫技的代码写法?
【练习4-1】Cake Distribution(分配蛋糕)
Borg Maze (BFS+最小生成树)(解题报告)
Cost accounting [13]
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
0 - 1 problème de sac à dos (1)
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
Accounting regulations and professional ethics [1]
Alice and Bob (2021牛客暑期多校训练营1)
Perinatal Software Industry Research Report - market status analysis and development prospect forecast
Opencv learning log 31 -- background difference
B - 代码派对(女生赛)
China's earthwork equipment market trend report, technical dynamic innovation and market forecast