小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（ ）。

// 判断：在不超过 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; 
}

if (check(L, K, mid)) 
    r = mid; 
else 
    l = mid + 1;

if (check(L, K, mid)) 
    r = mid+1; 
else 
    l = mid + 1;

if (check(L, K, mid)) 
    r = mid + 1; 
else 
    l = mid - 1;

if (check(L, K, mid)) 
    r = mid + 1; 
else 
    l = mid;

下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。

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; 
}

for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)

for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++)

for (int j = 1; j <= sqrt(n); j++)

for(int j = 1; j < n && i * primes[j] <= n; j++)

下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。

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 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; 
    } 
};

Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock->prev;

Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock;

Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock;

Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock->prev;

下面关于单链表和双链表的描述中，正确的是（ ）。

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; 
}

下述C++代码实现了快速排序算法，最坏情况的时间复杂度是（ ）。

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 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; 
}

唯一分解定理描述的内容是（ ）。

下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回arr.size() 。以下说法正确的是（ ）。

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; 
}

对如下定义的循环单链表，横线处填写（ ）。

// 循环单链表的结点 
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; 
}

while (p != nullptr){
	cout << p->data << " ";
	p = p->next;
}

while (p->next != nullptr){
	cout << p->data << " ";
	p = p->next;
}

do {
	cout << p->data << " ";
	p = p->next;
} while (p != head);

for(; p; p=p->next){
	cout << p->data << " ";
}

给定有 个任务，每个任务有截止时间和利润，每个任务耗时 1 个时间单位、必须在截止时间前完成，且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写（ ）。

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; 
}

slot[t] = true; 
totalProfit += task.profit;

slot[t] = false; 
totalProfit += task.profit;

slot[t] = true; 
totalProfit = task.profit;

lot[t] = false; 
totalProfit = task.profit;

下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（ ）。

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; 
}

c.push_back(carry / 10); 
carry %= 10;

c.push_back(carry % 10); 
carry /= 10;

c.push_back(carry % 10);

c.push_back(carry); 
carry /= 10

假设我们有两个数 a=38和b=14，它们对模 同余，即 a=b(mod m)。以下哪个值不可能是 m？

下列关于排序的说法，正确的是( )。2025.12-5

下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

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); 
}

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a，b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。

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

在求解所有不大于 n 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(n log log n)。

贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。

以下 fib 函数计算第 n 项斐波那契数（ fib(0)=0 , fib(1)=1 ），其时间复杂度为为O(n)。

int fib(int n) { 
    if (n <= 1) return n; 
    return fib(n-1) + fib(n-2); 
}

递归函数一定要有终止条件，否则可能会造成栈溢出。

数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。

使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。

在单链表中，已知指针 p 指向要删除的结点（非尾结点），想在删除 p ，可行做法是用 p->next 覆盖 p 的值与 next ，然后删除 p->next 。

二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

相等序列

时间限制： 1.0 s

内存限制：512.0 MB

题目描述

小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · ·  ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作：

 选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai * P ，P 为任意质数；

 选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai /P ，P 为任意质数，要求Ai能被p整除。

小 A 想请你帮他计算出令序列中所有整数都相同 ，最少需要花费多少金币。

输入格式

第一行一个正整数N ，含义如题面所⽰ 。

第二行包含 N 个正整数 A1 , A2 , ·  … ,AN ，代表序列 A。

输出格式

输出一行 ，代表最少需要花费的金币数量。

输入样例

5
10  6  35  105  42

输出样例

8

数据范围

对于60%的测试点 ，保证 1 ≤ N, Ai ≤ 100 。

对于所有测试点 ，保证 1 ≤ N, Ai ≤ 105 。

数字移动

时间限制：1.0 s

内存限制：512.0 MB

题目描述

输入格式

输出格式

输出一行，代表满足要求的 的最小值。

输入样例

6
1 2 1 3 2 3

输出样例

2

数据范围