Algorithm notes - day2

the second day!!

Chapter 3 Introduction (1) - Introduction simulation

[exercise A] the remaining trees

Problem Description

A road with a length of integer L (1 < = l < = 10000) can be imagined as a line segment with a length of L on the number axis. The starting point is the coordinate origin. There is a tree at each integer coordinate point, that is, there are L+1 trees at 0,1,2,..., L+1 positions in total.
Now remove some trees. The interval of the removed tree is represented by a pair of numbers. For example, 100 and 200 represent all trees from 100 to 200 (including endpoints).
There may be m (1 < = m < = 100) intervals, and there may be overlap between intervals. Now it is required to remove the number of trees left after all interval trees are removed.

Two integers L (1 < = l < = 10000) and m (1 < = m < = 100).
Next, there are M groups of integers with a pair of numbers in each group.

There may be multiple groups of input data. For each group of input data, a number is output, indicating the number of trees left after removing all interval trees.

Sample Input
4 2
1 2
0 2
11 2
1 5
4 7
0 0

Sample Output

Thinking Notes

1, Topic type:

  • Delete elements within the interval. There are overlapping intervals

2, Variable setting

  • Set the elements as an array, record the values of 0 and 1, the initial value is 0, set 1 for the elements in the interval to be deleted, and finally count the number of 0 as the rest

  • If the initial value is set to 1 here, the compilation is wrong

3, Code design

  1. While input l and m to the end of the file (add condition judgment in while: if m==0 break)
  2. Enter group m interval
  3. Intra interval circulation_ If 0, set 1
  4. Intra interval circulation_ Count the number of 0
  5. Output statistics

Code Implementation(C)

int main(){
    int l,m,z,y,flag[10001]={1},count=0;
    while(scanf("%d %d",&l,&m)!=EOF){
        int flag[10001]={0};
        if(m==0) break;//For separate control at the end of double input (0)
            scanf("%d %d",&z,&y);
                int t;
            for(int i=z;i<=y;i++){
        for(int i=0;i<=l;i++){
            if(flag[i]==0) count++;
    return 0;

Code Implementation(C++)

#include <cstdio>
#Include < algorithm > / / swap header file
#Include < CString > / / memset header file
using namespace std;
int main(){
    int l,m,z,y,flag[10001],sum=0;
    while(scanf("%d%d",&l,&m)!=EOF){//Continuous input: in addition to this writing method, you can also: while(~ scanf ("% d% d", & L, & M))
        memset(flag,0,sizeof(flag));//c + + initialization, each cycle is initialized
        if(m==0) break;//The individual control input is 0 to end the cycle
            scanf("%d%d",&z,&y);//Enter group m interval
                swap(z,y);//According to the input example, there should be statements that control zy size order
            for(int i=z;i<=y;i++)
        for(int i=0;i<=l;i++)
            if(flag[i]==0) sum++;
    return 0;

[exercise b] A+B

Problem Description

Given two integers A and B, their representation is: starting from bits, every three digits are separated by commas "," and ".
Now please calculate the result of A+B and output it in normal form.

The input contains multiple groups of data, each of which occupies one row and consists of two integers a and B (- 109 < A, B < 109).

Please calculate the result of A+B and output it in normal form. Each group of data occupies one row.

Sample Input
-234,567,890 123,456,789
1,234 2,345,678

Sample Output

Thinking Notes

1, Topic type:

  • Removes some elements from the string

2, Variable setting

  • A temporary array temp (after deleting some elements)
  • A subscript variable pos is used to record the retained elements
 		if(a[i]!=',')//For example, remove '‘

3, Code design

  1. dispose function (impurity array)
    Use the temporary storage array to remove some impurity elements and return a clean array
  2. Main function
    Define array + initialize
    Loop input string
    Call dispose to remove impurities
    sscanf extract number
    Output and
    Initialize array (avoid storing dirty data)

4, Initialization method of string

  1. Assigning individual character elements one by one (single quotation mark) does not require the end to be \ 0

    1) If the number of characters is greater than the length of the array, it will be handled as a syntax error

    2) If the number of characters is less than the length of the array, the system will automatically fill in
    char str[10]={'1','2','3','4','5'};
    When this method is defined, the system will automatically start with uninitialized elements and assign subsequent elements to \ 0. For example, the elements in the array str above are actually: '1', '2', '3', '4', '5', '0', '0', '0', '0', '0', '0', '0', '0', \ 0 '

    3) If the number of characters is equal to the length of the array
    char str[5]={‘C’,’h’,’I’,’n’,’a’};// Character constants use single quotation marks, that is, assign 5 characters to str[0] to str[4]5 elements respectively
    When assigning values to elements individually, the last character is not required to be '\ 0', or even does not contain '\ 0', which is completely legal.

    4) When the array length is not specified
    char str[]={'1','2','3','4','5'};
    When this method is defined, the system will not automatically add a string terminator to the end of the string;
    In this case, the sizeof() function can be used to correctly calculate the memory size occupied by it; However, the strlen() function cannot correctly calculate its length, because strlen judges the end of the string through \ 0.
    Therefore, when using this method to define, generally add \ 0 artificially, that is, char str [] = {1 ',' 2 ',' 3 ',' 4 ',' 5 ',' 0 '};

  2. The whole string assignment (double quotation marks) is automatically generated by the system \ 0
    1) String assignment
    char str[]="12345";
    Or brace the string:
    char str[]={"12345"};
    When this method is defined, the system will automatically add a string terminator at the end of the string, that is' \ 0 ', and the corresponding array length will also be added by one, which is 6, not 5
    be careful
    The overall assignment of the above character array can only be used during the initialization of the character array and cannot be used for the assignment of the character array. The assignment of the character array can only use the method of assigning values to its elements one by one. The following overall assignment method is wrong
    char str[ ];
    str=“I am happy”;// Error, the assignment of character array can only use the method of one-to-one assignment of elements

  3. summary
    char str [] = {"12345"} / / length is 6
    Equivalent to char str [] = {1 ',' 2 ',' 3 ',' 4 ',' 5 ',' 0 '}// Length 6
    Not equivalent to char str [] = {1 ',' 2 ',' 3 ',' 4 ',' 5 '}// Length 5

5, About characters and strings

  • The value of character 'C' when participating in numerical calculation is ascii code value

  • Array a[10]: the length of the array is 10, and the subscript ranges from 0 to 9

  • Extract the whole string of numeric characters from the string array and convert them into integer numbers
    sscanf(B,”%d”,&b);// Convert string B into an integer and store it in B

  • To convert a numeric character element into an integer number in a string array

Code Implementation(C++)

#include <cstdio>
#include <cstring>
using namespace std;
void dispose(char a[]){
    char temp[16];//Temporarily save the array after removing commas
    memset(temp,'\0',sizeof(temp));//Initialize to full \ 0
    int pos=0;
    for(int i=0;i<strlen(a);i++){
        if(a[i]!=',') temp[pos++]=a[i];//This method is similar to assigning values one by one. At this time, the system will automatically start with uninitialized elements and assign subsequent elements to \ 0
    for(int i=0;i<strlen(a);i++){//Why not take the temp array (shorter length) to traverse? The actual length of a is longer than that of temp, so the \ 0 in the corresponding temp is also assigned to a, and the redundant old data in a is overwritten with \ 0
int main(){
    char A[16],B[16];
    while(scanf("%s %s",A,B)!=EOF){//String variables are not used&
        int a,b;
        sscanf(A,"%d",&a);//sscanf function: extract the content of type d (integer) from string a and store it in variable a, that is, enter a from a
        sscanf(B,"%d",&b);//Effect: convert strings a and B into integers and store them in a and B
        memset(B,'\0',sizeof(B));//Collocation of while loop and initialization
        //Initialize the string array with 0 and \ 0
    return 0;

Added by Tsukasa on Wed, 05 Jan 2022 14:46:52 +0200