Title Link:-P1098 [NOIP2007 Improvement Group] String Expansion
Title Narrative:
[NOIP2007 Improvement Group] String Expansion
Title Description
In the question "Read the program and write the result" in the popularity category of the preliminary round, we have given an example of string expansion: if the input string contains something liked-h or4-8 string, we'll treat it as a kind of shorthand and, when outputting it, replace the minus sign in it with a continuously increasing string of letters or numbers, i.e., output each of the above two substrings asdefgh cap (a poem)45678. In this problem, we make the string expansion more flexible by adding some parameter settings. The specific conventions are as follows:
(1) You need to do string expansion in the following case: in the input string, a minus sign appears- , the minus sign is flanked by the same lowercase letter or the same number, and according to theASCII The order of the codes is such that the character to the right of the minus sign is strictly greater than the character to the left.
(2) Parameter p1: expansion mode. p1=1, for letter substring, fill lowercase letters; p1=2, for letter substring, fill uppercase letters. In both cases, the numeric substrings are filled in the same way. p1=3 uses the same number of asterisks as the number of letters to be filled, regardless of whether it is a letter substring or a numeric string.* to fill.
(3) Parameter p2: the number of repetitions of the filled character. p2=k means that the same character should be filled k consecutively. For example, when p2=3, the substringd-h should be expanded todeeefffgggh. The characters on either side of the minus sign remain unchanged.
(4) Parameter p_3: whether to change to reverse order: p3=1 means to maintain the original order p3=2 means to use reverse order output, note that this time still does not include the characters at the ends of the minus sign. For example, when p1=1, p2=2, p3=2, substringd-h should be expanded todggffeeh。
(5) If the character to the right of the minus sign happens to be the successor of the character to the left, only the middle minus sign is deleted, for example:d-e should be output asde，3-4 should be output as34. If the character to the right of the minus sign follows theASCII The order of the code is less than or equal to the left character, and the minus sign in the middle is retained when outputting, for example:d-d should be output asd-d，3-1 should be output as3-1。
input format
Two lines in total.
The first line is a space-separated set of three positive integers representing the parameters p1,p2,p3.
Line 2 is a one-line string consisting only of numbers, lowercase letters, and a minus sign.- Composition. There are no spaces at the beginning or end of the line.
output format
A total of one line for the expanded string.
Sample #1
Sample Input #1
1 2 1
abcs-w1234-9s-4zz
Sample Output #1
abcsttuuvvw1234556677889s-4zz
Sample #2
Sample Input #2
2 3 2
a-d-d
Sample Output #2
aCCCBBBd-d
draw attention to sth.
40% of the data satisfies: the length of the string does not exceed 5.
100% of the data satisfy: 1<=p1<=3;1<=p2<=8,1<=p3<=2. The length of the string does not exceed 100.
NOIP 2007 Improvement of the second question
reasoning
This may seem like a complicated question, so let's run through the logic of the question carefully.
First, we have to search for the-furthermore-should have elements on both the left and right sides of the string so that we do the padding, so after we receive a string, we only need to iterate through it from the second element to the penultimate element.
Second, we observe that the number, p2, only determines the number of each character we fill, so p2 should be irrelevant in terms of general categorization, and only relevant when we construct the string we want to fill
One more thing is that the value of p3, is the issue that determines whether the fill is reversed or not, so we can just construct the forward-filled string, and if p3==2, we reverse the constructed string and insert it into the originally-It's just a matter of where it's located.
library function
Ideas explained, we began to talk about library functions, the use of library functions in this question can greatly reduce the time we write code, we recommend that we understand the library function well
header file#include<cctype>library function in the
1, toupper(x) if x is a lowercase letter, convert it to uppercase letters
2、tolower(x) if x is an uppercase letter, convert it to a lowercase letter
3、isalpha(x) Judge whether x is an alpha or not
4、isdigit(x) determine whether x is a number
5, islower(x) determine whether x is a lowercase letter
6、isupper(x) Judge whether x is a capital letter or not
7、isalnum(x) Judge whether x is a letter or a number
8, ispunct (x) to determine whether x is a punctuation mark
9, isspace(x) determine whether x is a space
header file#include<string>library function in the
1、(x,y) means to delete y characters from position x of the string s.
2、(x,y) means that the stringy（or charactersy）Inserted intos(used form a nominal expression)xlocation
3、s.push_back(x) means that at the end of s insert the character x
4, reverse ((), ()) will flip the string s
The reader is advised to take a good deep dive into the member functions provided in the string class
step by step disassembly
First, we're going to enter a string and three numbers, and then iterate through the string, from the second element up to the penultimate element, and if we run into the-furthermore-are lowercase letters (or numbers) on the left and right sides, and the left lowercase letter (or number)
The ASCII code is smaller than the right hand side before we process it.
Then, we clarify a point where we need to remove the-The position of this-, then insert a new stringcurrentThe next step is to construct the new string. We construct thecurrentThere are three scenarios
Delete i position of-The code for.
//We need to delete the '-' at position i no matter what character is filled or not, so put it at the very top
(i,1).
1. p1==1We'll fill in the lowercase letters and then determine if we need to reverse the string based on the value of p3currentNext is the construction of thecurrentcourse of action
We start with the next letter of s[i-1] and go up to the previous letter of s[i+1], cycling through each letter p2 times and all in lowercase, with the following code.
string current; //construct the string that needs to be filled in the middle.
// Construct the string to be filled in the middle.
for (char c = s[i - 1] + 1; c <= s[i] - 1; c++) {
char a = c; //Construct the string that needs to be filled in the middle for (char i=1; i=1; i=1)
for (int i=1;i<=p2;i++) current+=a;
}
Then, based on the value of p3, we can determine whether we need to do the inversion, the code is as follows.
//If p3 == 2, then reverse is required, otherwise not
if (p3 == 2) reverse((), ());
Finally, we can just insert the string at this position of i
//Insert the string at this position of i
(i, current);
It's done.p1==1The steps of thep1==2，p1==3It's solved, just change the value of the character a, and you're done!
2. p1==2present situation
else if (p1 == 2) {
string current;
for (char c = s[i - 1] + 1; c <= s[i] - 1; c++) {
char a = toupper(c);
for (int i = 1; i <= p2; i++) current += a;
}
if (p3 == 2) reverse((), ());
(i, current);
}
3. p1==3present situation
else if (p1 == 3) {
string current;
for (char c = s[i - 1] + 1; c <= s[i] - 1; c++) {
char a = '*';
for (int i = 1; i <= p2; i++) current += a;
}
if (p3 == 2) reverse((), ());
(i, current);
}
Finally, we can just output this modified string directly
final code
#include<iostream>
#include<cctype>;
#include<algorithm> #include<algorithm>
using namespace std.
int main()
{
int p1, p2, p3.
cin >> p1 >> p2 >> p3;
string s; cin >> s;
// Starting from the second element, iterates to the end of the penultimate element, since the '-' at the beginning and end don't need to be bothered with
for (int i = 1; i < () - 1; i++) {
// We only deal with the - sign if it's a character (or number) to the left or right of it, and the left side is smaller than the right side
if (s[i] == '-' && ((islower(s[i - 1]) && islower(s[i + 1]) && s[i - 1] < s[i + 1]) || (isdigit(s[i - 1]) && isdigit(s[i + 1]) && s[i - 1] < s[i + 1]))) {
//We need to delete the '-' at position i no matter what character is filled or not, so we put it at the top of the list
(i,1); // Fill lowercase letters.
//fill lowercase letters
if (p1 == 1) {
current; string current; //construct the middle of the string to be filled.
//construct the string that needs to be filled in the middle of the line
for (char c = s[i - 1] + 1; c <= s[i] - 1; c++) {
char a=c;
for (int i=1;i<=p2;i++) current+=a;
}
// if p3 == 2, then it needs to be inverted, otherwise it doesn't
if (p3 == 2) reverse((), ());
//Insert the string at this position of i
(i, current);
}
else if (p1 == 2) {
string current; for (char c = s[i])
for (char c = s[i - 1] + 1; c <= s[i] - 1; c++) {
char a = toupper(c); for (int i = 1; i
for (int i = 1; i <= p2; i++) current += a;
}
if (p3 == 2) reverse((), ()).
(i, current); }
}
else if (p1 == 3) {
current; string current; for (char c = s[i - 1] + 1; c)
for (char c = s[i - 1] + 1; c <= s[i] - 1; c++) {
char a = '*'; for (int i = 1; i
for (int i = 1; i <= p2; i++) current += a;
}
if (p3 == 2) reverse((), ()).
(i, current); }
}
}
}
cout << s << endl.
endl; return 0;
}