BUAA_OJ Pitfall Record – C Language Exam Notes by Fauci

Thoughts & Introduction

This note was actually written three months ago while relearning C language, in preparation for the software college entrance practical exam. I studied data structures and algorithms, and solved some problems on LeetCode.

BUAA_OJ Pitfall Record - C Language Exam Notes by Fauci — During exam week, I decided to go to the software college. I threw aside my major courses and focused on high-intensity coding, but after the summer vacation, I visibly slacked off, emphasizing a balance between work and rest.

Welcome to visit my C/C++ repository, where I wrote 10,000 lines of C code from May to July:https://github.com/SteveFauci/Learn_c_again (but after July, I just relaxed during the summer vacation, lying around every day).

The practical exam went smoothly, and I ranked second (actually, there were only seven people 🤪). I successfully entered the software college, where I will systematically study core courses such as discrete mathematics, computer organization, and data structures and algorithms.

Actually, relearning C language is a multi-benefit endeavor. In the short term, it means college admission, participating in the summer programming competition, and working as a programming assistant after school starts to earn some money; in the long term, it prepares for various coding interviews and competitions, where coding skills are a hard currency. I consider this as laying a foundation, and I might need to relearn it again later.

Below are my organized notes, and you can download the markdown files from my repository.

Common WA (Wrong Answers)

1. Make global arrays larger
2. Ten years of competitive programming for nothing, do not openlong long to see ancestors (but I am not a competitive programmer)
3. getchar() consumes empty characters

For example:scanf("%d",&n) reads a single line of numbers, and if you then usefgets()/gets(), there will be a<code>'\n' at the end of the number that needs to be consumed withgetchar(), otherwise the next string read will be<code>'\n', and if you try to remove<code>'\n', you will only get an empty string.

4. Pay attention to initializing with appropriate values

For example, to find the maximum value in an array, it is not advisable to initializeint max = 0, it should beint max = arr[0]. If the array consists of all negative numbers, the former max will become 0.

C Language Programming Section

Basic Debugging (Linux Environment)

EOF – ctrl+d

Redirection – ./main < in.txt > out.txt

Redirection: Input Sample & Output Sample Debugging Steps

Problem solved: In direct terminal debugging, pressing enter gives one output, making it difficult to compare answers.

1. Compile the code to get the executable file and name itmain
2. Createin.txt file, paste the input sample, and save it
3. In the terminal, input ./main < in.txt > out.txt (using relative path)
4. Directly compareout.txt with the output sample

EOF

EOF on Windows isCtrl+Z Enter, while on Linux it isCtrl + D

(In text files) Windows carriage return equals\r\n, while Linux carriage return is\n

Using gets() in My Compiler

You can modify the compilation options, for example, usingC89, but it is unnecessary as the new standard has abolishedgets(), and some competitions also use the new standard. Here, we follow the new standard.

To compare strings for equality, usestrcmp(str1,str2) == 0

#include<string.h>
#include<stdio.h>
void my_gets(char*s,int limit){
    fgets(s,limit,stdin);
    s[strcspn(s,"\n")] = '\0';
}
// int main(){
//     char str[100];
//     my_gets(str,100);
//     puts(str);
// }

For multi-line reading, I had to write it manually, using the following.

#include<string.h>
#include<stdio.h>
char str[1005];
int main(){
    while(fgets(str, 1005, stdin)!=NULL){
        str[strcspn(str, "\n")] = '\0';
        ...
    }
}

Basic Mathematical Functions

int gcd(int a,int b) {
    return b?gcd(b,a%b):a;
}

int lcm(int a,int b) {
    return((a/gcd(a,b))*b);
}

int isPrime(int num) {
    if (num <= 1) return 0;
    if (num == 2) return 1;
    if (num % 2 == 0) return 0;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return 0; 
    }
    return 1;
}

Prime factorization:

void primeFactors(int n)// Prime factorization, can introduce an array for further calculations
{
    while (n % 2 == 0)
    {
        printf("%d ", 2);
        n = n / 2;
    }
    for (int i = 3; i*i<=(n); i = i + 2)
        while (n % i == 0)
        {
            printf("%d ", i);
            n = n / i;
        }
    if (n > 2) // Cannot delete
        printf("%d ", n);
}

int max(int a, int b) {
    return a >= b ? a : b;
}

int min(int a, int b) {
    return a <= b ? a : b;
}

Reverse Integer (without considering overflow)

If you want to try reversing2147483647, you either need to uselong long or string manipulation.

int reserve(int num) {
    int ret = 0;
    while(num) {
        ret = ret * 10 + num % 10;
        num /= 10;
    }
    return ret;
}

Fast Input

Note: f represents the sign, x is the sum.

Core Algorithm: For each (valid) character read,x = x * 10 + (ch - '0');

int fastReadInt() {
    int x = 0, f = 1;
    char ch = getchar(); // consume newline
    // Check for negative sign
    if (ch == '-') {
        f = -1;
        ch = getchar();
    }
    // Read digit characters and convert to integer
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

Dynamic Memory Allocation for Strings

Example: Read and store10,000 strings, each with a length not exceeding1,000. But the total character count does not exceed200,000 (i.e., 200KB of memory)

Dynamic allocation:

char  buffer[1005];
char* ptr[10005]; // This is a pointer array

for (int i = 0; i < 10000; i++) {
    fgets(buffer, 1005, stdin);
    buffer[strcspn(buffer, "\n")] = '\0';
    // The first two lines are just reading, can use gets on buaaOJ
    ptr[i] = (char*)malloc(sizeof(char) * (strlen(buffer) + 1));
    // Allocate as much as needed
    strcpy(ptr[i], buffer);
}

// ......

for (int i = 0; i < 10000; i++) {
    free(ptr[i]); // Return what was borrowed
}

Float Comparison

If you really forget, just copy the following…

#define eps 1e-8
int XGreaterThanY(double x,double y){
    return x-y>eps; // Positive enough → x > y
}
int XLessThanY(double x,double y){
    return x-y<-eps; // Negative enough → x < y
}
int XEqualToY(double x,double y){
    return fabs(x-y)<eps; // Close to 0 → equal
}

Usage example:

if(XGreaterThanY(a,b)){
    //do something
}
if(!XEqualToY(c,d)){
    //do something
}

Output Unique Elements After Sorting

Example: For an already sorted array, remove duplicate elements and output.

For example, arr[] = {1,1,2,2,2,3,3,4,5};

Output1 2 3 4 5

Solution 1: Conventional

// First handle the beginning, then print all different ones.
#include <stdio.h>
int arr[] = {1, 1, 2, 2, 2, 3, 3, 4, 5};
int main() {
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", arr[0]);
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i - 1]) {
            printf(" %d", arr[i]);
        }
    }
    puts("");
}

Solution 2: Two Pointers

// The left and right pointers in the code always print left, and left moves with right.
// Special handling for the last one
#include <stdio.h>
int arr[] = {1,1,2,2,2,3,3,4,5};
int main() {
    int left = 0;
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int right = 0; right < n; right++) {
        if (arr[left] != arr[right]) {
            printf("%d ", arr[left]);
            left = right;
        }
    }
    printf("%d\n", arr[n - 1]);
}

Date Handling

// Return value is 0-6, 0 means Sunday, 1 means Monday
int getWeekday(int y,int m,int d) {
    int c,w;
    if(m<3) {
        y++;
        m+=12;
    }
    c=y/100;
    y%=100;
    w=(y+y/4+c/4-2*c+(26*(m+1))/10+d-1)%7;
    if(w<0) {
        w+=7;
    }
    return w;
}

int isLeap(int y) {
    return(y%4==0)&&(y%100!=0)||(y%400==0);
}

int getDaysOfMonth(int y,int m) {
    int days=0;
    switch(m) {
        case1:case3:case5:case7:case8:case10:case12:
            days=31;
            break;
        case4:case6:case9:case11:
            days=30;
            break;
        case2:
            days=isLeap(y)?29:28;
            break;
    }
    return days;
}

Binary Search

Directly search for key

int binary_search(int arr[], int key, int l, int r) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

The first number smaller than key

int binary_search_floor(int arr[], int key, int l, int r) {
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] < key) {
            ans = mid;          // First record the current candidate answer
            l = mid + 1;        // Continue to find a larger value that meets the condition
        } else {
            r = mid - 1;        // Does not meet the condition, shrink the range to the left
        }
    }
    return ans;
}

Guide to qsort() cmp() Function

Basic Syntax

typedef ... My_type;
int cmp(const void*p1,const void*p2){
    My_type* pp1 = (My_type*)p1; // pp1 pp2 are intermediate variables for easy access
    My_type* pp2 = (My_type*)p2; // Otherwise, each pointer would have to be written as ((My_type*)p1)
    
    // Later use pp1 and pp2 to write comparison rules, supporting multi-field sorting.
}

Principle & Notes

cmp() returns anint. Mainly look at the sign; if a negative value is returned,*p1 is placed before*p2.

Lazy writing return pp1->a - pp2->a; just puts the smaller one in front, but be careful with this:

1. Subtracting two extreme numbers may exceed the range

2. Subtracting two floating-point numbers can yield unpredictable results; converting to int may lead to errors because the return value is int, not double.

Generally, it isif(pp1->a < pp2->a) return -1; (if it is a floating-point comparison, modify according to the rules, or directly call the previously written floating-point comparison function).

Data Structures Section

I rely heavily on the C++ STL library for self-learning data structures and problem-solving, always using ready-made#include<stack> #include<queue>, as well asvector andunordered_map. To adapt to the BUAA style of online judging, I have listed the basic operations of stacks and queues here.

Stack

Just maintain an array and a top pointer.

my_stack[] is the stack array, andtop is the top pointer, initially set to -1, whileMax_size is the maximum capacity of the stack.

Operation	Code Implementation
push	`<span>my_stack[++top]</span>`
pop	`<span>top--</span>`
top	`<span>my_stack[top]</span>`
is_empty	`<span>top == -1</span>`
is_full	`<span>top == Max_size-1</span>`

Queue

Use an array to maintain the queue, with two pointers:front and rear.

Initially, front = 0, rear = -1, and my_queue[] is the queue array, while Max_size is the maximum capacity.

Breadth-first search can be directly used with while(rear >= front){...}

Operation	Code Implementation
enqueue	`<span>my_queue[++rear] = x;</span>`
dequeue	`<span>front++</span>`
front_elem	`<span>my_queue[front]</span>`
is_empty	`<span>front > rear</span>`
is_full	`<span>rear == Max_size - 1</span>`