120 lines
3.5 KiB
Markdown
120 lines
3.5 KiB
Markdown
Q1
|
||
```
|
||
给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、*、/、^、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过10位。运算结果为整数，值域为[−2
|
||
31
|
||
,2
|
||
31
|
||
)。除法运算结果若为小数则进行截尾取整。若除法运算中除数为0，则输出INVALID。幂运算须自行实现，不允许调用pow等系统函数。
|
||
|
||
测试数据保证幂运算中指数为非负，底数不为0，且不会出现诸如n^a^b连续多次幂运算。
|
||
|
||
输入格式:
|
||
输入为多行，每行为一个长度不超过1000的字符串，表示中缀表达式。
|
||
|
||
输出格式:
|
||
对每个表达式输出一行：为一个整数（表达式的值）或为一个字符串INVALID。
|
||
|
||
输入样例:
|
||
5+(10*2)-6
|
||
8*(999+1)
|
||
1+5/(1-1)
|
||
7*2^3
|
||
|
||
输出样例:
|
||
19
|
||
8000
|
||
INVALID
|
||
56
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q2
|
||
```
|
||
2021年11月6日，英雄联盟全球总决赛打响，中国电子竞技战队Edward Gaming（EDG）以3:2力克韩国强敌DWG KIA（DK）战队，历史上首次夺得全球总冠军。一时间全网沸腾，大家纷纷在社交平台上直呼“edgnb”。现给定一段文本，请编写程序识别出连续的k个“edgnb”组成的字符串在该文本中出现了多少次。
|
||
|
||
输入格式:
|
||
第一行为1个整数T，表示数据组数。对于每组数据，第一行为1个字符串，表示给定的文本。第二行为1个整数k，含义如题目所述。（1≤T≤10。各组数据给定的字符串长度之和不超过10
|
||
5
|
||
，且字符串中只包含a-z的小写字母。k≥1且k×5小于给定字符串长度）。
|
||
|
||
输出格式:
|
||
对于每组数据输出一行，为1个整数，表示所求的出现次数。
|
||
|
||
输入样例:
|
||
5
|
||
xyzedgnbabcedgnb
|
||
1
|
||
xyzedgnbabcedgnb
|
||
2
|
||
defedgnbedgnbxyz
|
||
2
|
||
edgnbedgnbedgnb
|
||
2
|
||
fxedgnbedgnbedgnbedgnbmem
|
||
3
|
||
|
||
输出样例:
|
||
2
|
||
0
|
||
1
|
||
2
|
||
2
|
||
|
||
数据规模:
|
||
测试点0：5≤T≤10，400≤T个字符串长度之和≤500，k=1
|
||
测试点1：5≤T≤10，400≤T个字符串长度之和≤500，k≥1
|
||
测试点2：5≤T≤10，4000≤T个字符串长度之和≤5000，k≥1
|
||
测试点3：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1
|
||
测试点4：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
400 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q3
|
||
```
|
||
波比和哈丽在玩一个字母游戏，波比给出一个字符串S，要求哈丽按照一定规则，基于该字符串算出一个数字X。
|
||
|
||
规则是：
|
||
|
||
（1）求出S的最长重复后缀P（P是S的后缀且在S中出现大于1次，例如yacbacba的最长重复后缀是acba），
|
||
|
||
（2）求出在S中去除第二长相等前后缀（S中所有相等的前后缀中第2长者，例如abcabcxxxabcabc中最长相等前后缀是abcabc，第二长的相等前后缀则是abc）后剩下的子串Q（例如abcabcxxxabcabc去除第二长相等前后缀后，剩下abcxxxabc）。
|
||
|
||
则X=P的长度+Q的长度。
|
||
|
||
注意一个字符串不能称为自己的前缀或后缀。子串Q至少为空串，其长度大于等于0，不能为负数。
|
||
|
||
请编写程序帮助哈丽根据给定字符串S，根据上述规则计算出数字X。
|
||
|
||
输入格式:
|
||
输入为若干行，每行为一个字符串，包含不超过100000个字母。
|
||
|
||
输出格式:
|
||
输出为若干行，每行一个整数，表示输入字符串所计算出的数字。
|
||
|
||
输入样例:
|
||
abcabcxxxabcabc
|
||
xacbacba
|
||
abc
|
||
aaa
|
||
|
||
输出样例:
|
||
15
|
||
12
|
||
3
|
||
3
|
||
``` |