CCF GESP 2025年12月认证 C++ 5级

// 循环单链表的结点
struct Node {
    int data;      // 数据域
    Node* next;    // 指针域
 
    Node(int d) : data(d), next(nullptr) {}
};
 
// 创建一个只有一个结点的循环单链表
Node* createList(int value) {
    Node* head = new Node(value);
    head->next = head;
    return head;
}
 
// 在循环单链表尾部插入新结点
void insertTail(Node* head, int value) {
    Node* p = head;
    while (p->next != head) {
        p = p->next;
    }
    Node* node = new Node(value);
    node->next = head;
    p->next = node;
}
 
// 遍历并输出循环单链表
void printList(Node* head) {
    if (head == nullptr) return;
 
    Node* p = head;
    __________________  // 在此处填入代码
    cout << endl;
}

// 区块（节点）
struct Block {
    int index;           // 区块编号（高度）
    string data;         // 区块里保存的数据
    Block* prev;         // 指向前一个区块
 
    Block(int idx, const string& d, Block* p) : index(idx), data(d), prev(p) {}
};
 
// 区块链
struct Blockchain {
    Block* tail;
 
    // 初始化
    void init() {
        tail = new Block(0, "Genesis Block", nullptr);
    }
 
    // 插入新区块
    void addBlock(const string& data) {
        _______________  // 在此处填入代码
    }
 
    // 释放内存
    void clear() {
        Block* cur = tail;
        while (cur != nullptr) {
            Block* p = cur->prev;
            delete cur;
            cur = p;
        }
        tail = nullptr;
    }
};

struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};
 
// 在双链表中删除指定节点
void deleteNode(DNode* node) {
    if (node->prev) {
        node->prev->next = node->next;
    }
    if (node->next) {
        node->next->prev = node->prev;
    }
    delete node;
}
 
struct SNode {
    int data;
    SNode* next;
};
 
// 在单链表中删除指定节点
void deleteSNode(SNode* head, SNode* node) {
    SNode* prev = head;
    while (prev->next != node) {
        prev = prev->next;
    }
    prev->next = node->next;
    delete node;
}

int gcd1(int a, int b) {
    return b == 0 ? a : gcd1(b, a % b);
}
 
int gcd2(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

vector<int> linear_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
 
    is_prime[0] = is_prime[1] = 0; // 0和1两个数特殊处理
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        ------------------------ {  // 在此处填入代码
            is_prime[ i * primes[j] ] = 0;
            if (i % primes[j] == 0)
                break;
        }
    }

    return primes;
}

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = temp[p];
}
 
void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, temp, l, mid);
    mergeSort(arr, temp, mid + 1, r);
    merge(arr, temp, l, mid, r);
}

int partition(vector<int>& arr, int low, int high) {
    int i = low, j = high;
    int pivot = arr[low];                    // 以首元素为基准
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[low]);
    return i;
}
 
void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

int lower_bound(vector<int>& arr, int x) {
    int l = 0, r = arr.size();
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
bool check(int L, int K, int x) {
    int cuts = (L - 1) / x;
    return cuts <= K;
}
 
// 二分查找最小可行的 x
int binary_cut(int L, int K) {
    int l = 1, r = L;
    while (l < r) {
        int mid = l + (r - l) / 2;
        __________________  // 在此处填入代码
    }
    return l;
}
 
int main() {
    int L = 10;  // 木头长度
    int K = 2;   // 最多切 K 刀
 
    cout << binary_cut(L, K) << endl;
    return 0;
}

int factorial1(int n) {
    if (n <= 1) return 1;
    return n * factorial1(n - 1);
}
 
int factorial2(int n) {
    int acc = 1;
    while (n > 1) {
        acc = n * acc;
        n = n - 1;
    }
    return acc;
}

struct Task {
    int deadline;  // 截止时间
    int profit;    // 利润
};
 
void sortByProfit(vector<Task>& tasks) {
    sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) {
            return a.profit > b.profit;
        });
}
 
int maxProfit(vector<Task>& tasks) {
    sortByProfit(tasks);
 
    int maxTime = 0;
    for (auto& t : tasks) {
        maxTime = max(maxTime, t.deadline);
    }
 
    vector<bool> slot(maxTime + 1, false);
    int totalProfit = 0;
 
    for (auto& task : tasks) {
        for (int t = task.deadline; t >= 1; t--) {
            if (!slot[t]) {
                __________________  // 在此处填入代码
                break;
            }
        }
    }
 
    return totalProfit;
}

vector<int> add(vector<int> a, vector<int> b) {
    vector<int> c;
    int carry = 0;
 
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        _________________________  // 在此处填入代码
    }
    if (carry) c.push_back(carry);
 
    return c;
}