区间合并最后的 segs = res; 改写成 swap(res, segs); 应该效率更高一些，容器交换的时间复杂度是 $O(1)$ ，不用再拷贝一次了。

多个 $O(n)$ 影响不大

我有一种高精度乘高精度的写法，用的是数组的方式：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 1e8;
int a[N], b[N], c[M];
int main(){
    char a1[N], b1[N];
    int lena, lenb, lenc, jw = 0;
    cin >> a1 >> b1;
    lena = strlen(a1);
    lenb = strlen(b1);
    lenc = lena + lenb;
    for (int i = 0; i < lena; i++) a[i] = a1[lena - i - 1] - '0';
    for (int i = 0; i < lenb; i++) b[i] = b1[lenb - i - 1] - '0';
    for (int i = 0; i < lena; i++){
        for (int j = 0; j < lenb; j++){
            c[i + j] += a[i] * b[j] + jw;
            jw = c[i + j] / 10;
            c[i + j] %= 10;
        }
        c[i + lenb] = jw;
    }
    for (int i = lenc - 1; i >= 0; i--){
        if (0 == c[i] && lenc > 1) lenc--;
        else break;
    }
    for (int i = lenc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

最多能输入十万位，最多能输出一千万位

lih 牛

请问板子上的高精度乘法有必要去除前导零吗？我觉得不会出现前导零呀

可能数据里有前导0

1235 X 0就有必要

信息学奥赛一本通上的吗？

不是

我自己想的（因为y总说过可以用数组的形式做，于是我就做了）。

#include<iostream>
using namespace std;

const int N=3010;

int main()
{
    int a[N]={1};
    int n;
    cin>>n;
    int m=1;
    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=0;j<m;j++)
        {
            t+=a[j]*2;
            a[j]=t%10;
            t/=10;
        }
        if(t)
        a[m++] =1;

    }

    for(int i=m-1;i>=0;i--)
    cout<<a[i];
    cout<<endl;

    return 0;
}

之前在语法基础课的时候讲过一个2的n次方的题目，这里就用到了高精度乘法，当时看了好多遍才理解

你代码有错，在c[i+lenb]%=10;后j w=0;要初始化。。。

c[i+lenb]%=10???

评论地方错了难受上面那个高精度乘法j w要=0

感谢您的鞭策，只不过请您说清楚点，具体是哪一行或关键词等

爱你

没有闫总的模版简洁。

y总的是高乘低，我的是高成高

厉害了，我没仔细看。闫总为啥不讲高乘高呢，感觉用vector好象做不了。

雀食

你这个的方法输入十万位乘十万位就TLE了啊，建议加上FFT优化，思想不难的。

是，但是FFT/NTT/FWT/FMT不是基础课的内容吧

在你提供的代码基础上，优化后的代码，如下。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 1e8;
int a[N], b[N], c[M];
int main(){
    char a1[N], b1[N];
    int lena, lenb, lenc, jw = 0;
    cin >> a1 >> b1;
    lena = strlen(a1);
    lenb = strlen(b1);
    lenc = lena + lenb;
    for (int i = 0; i < lena; i++) a[i] = a1[lena - i - 1] - '0';
    for (int i = 0; i < lenb; i++) b[i] = b1[lenb - i - 1] - '0';
    for (int i = 0; i < lena; i++){
        jw = 0; // 修复：每次外层循环开始时重置进位
        for (int j = 0; j < lenb; j++){
            c[i + j] += a[i] * b[j] + jw;
            jw = c[i + j] / 10;
            c[i + j] %= 10;
        }
        c[i + lenb] = jw;
    }
    // 去除前导零
    while (lenc > 1 && c[lenc - 1] == 0) {
        lenc--;
    }
    for (int i = lenc - 1; i >= 0; i--) cout << c[i];
    return 0;
}

thanks大佬

有没有Java的模板啊

我也想说

在打卡里有别人的java代码

java的考友加一下

java的考友加一下

【Java版本】常用代码模板1——基础算法 + 模板题参考实现
https://www.acwing.com/blog/content/31431/

【Java版本】常用代码模板1——基础算法 + 模板题参考实现
https://www.acwing.com/blog/content/31431/

Google acwing 题号 java 就能找到很多别人的题解了

有没有python版本的代码模板

蹲

蹲

蹲

快排的这个模版确实经典，但是分界 [l, j] 和 [j+1, r] 非常难以理解 而且只能选j不能用i，改成任何别的都是错的或死循环，比如 [l, j-1] 和 [j+1, r]， [l, j-1] 和 [j, r]， [l, i-1] 和 [i, r]， [l, i] 和 [i+1, r]， [l, i-1] 和 [i+1, r] 统统都错。自己研究了下面的Java模版比较好理解 (只有一个循环而且每次只增减一个变量), 但是效率稍微差了一点（swap会多一些)

private void sort(int[] nums, int i, int j) {
      if(i>=j) {
            return;
      }
      int pivot = partition(nums, i, j);
      sort(nums, i, pivot-1);
      sort(nums, pivot+1, j);
  }

  private void swap(int[] nums, int i, int j) {
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
  }

  private int partition(int[] nums, int i, int j) {
      swap(nums, i+(j-i)/2, j); // swap pivot to the back
      int lo = i, hi = j-1;
      int x = nums[j];
      while(lo<=hi) { // must check lo==hi because we don't know nums[lo] compare x
          if(nums[lo] > x) {
              swap(nums, lo, hi--);
          } else {
              lo++;
          }
      } // after the loop, lo will the the number >= pivot, so swap it with pivot
      swap(nums, lo, j);
      return lo;
  }

这个不错，quick select也可以用

这个有点复杂，还是 y 总的好…

赞！这个好理解多了

我也是只能理解这种，并且我不明白y总的写法怎么做快速选择。更简洁的版本：

private int partition(int[] nums, int l, int r) {
        swap(nums, l, l + r >> 1);
        int pivot = nums[l];
        int j = l;
        for (int i = l + 1; i <= r; i++)
            if (nums[i] <= pivot) swap(nums, ++j, i);
        swap(nums, l, j);

        return j;
    }

void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
    do i ++ ; while (q[i] < x);
    do j -- ; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);

}
为什么我跟他写的一样，我输出的却是死循环

不应该的呀，

确实，我自己也把递归那块字母改了又改，一开始还以为[l, i] 和 [i+1, r]可以的，后来发现数据大了就不行，研究了一个小时

他来了他来了
【Java版本】常用代码模板1——基础算法 + 模板题参考实现
https://www.acwing.com/blog/content/31431/

模板很不错，全看完了，打卡

#高精度乘高精度的y总模版

vector<int> mul(vector<int> &a, vector<int> &b)
{
    vector<int> c(100010);
    for(int i = 0;i < a.size();i++)
    {
        for(int j = 0;j < b.size();j++)
        {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }

    while(c.size() > 1 && c.back() == 0)
    c.pop_back();

    return c;
}

##全部代码的话是这样

#include<bits/stdc++.h>
using namespace std;


vector<int> mul(vector<int> &a, vector<int> &b)
{
    vector<int> c(100010);
    for(int i = 0;i < a.size();i++)
    {
        for(int j = 0;j < b.size();j++)
        {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }

    while(c.size() > 1 && c.back() == 0)
    c.pop_back();

    return c;
}
int main()
{
    string A, B;
    cin >> A >> B;
    vector<int> a, b;
    for(int i = A.size() - 1;i >= 0;i--)
    {
        a.push_back(A[i] - '0');
    }

    for(int i = B.size() - 1;i >= 0;i--)
    {
        b.push_back(B[i] - '0');
    }

    auto C = mul(a, b);

    for(int i = C.size() - 1;i >= 0;i--)
    {
        cout << C[i];
    }
    cout << endl;


    return 0;
}

LeetCode上好像就有一道高精度×高精度

https://www.acwing.com/blog/content/26305/

python新手看得一脸懵逼

或许可以试试用chatgpt把c++代码转成python代码

会炸的

chatgpt现在还做不到算法翻译

chatgpt收费了

不收啊

只有我觉得quick sort的do while loop很不舒适嘛

可以转成while阿。

稍微优雅一点：

void quick_sort(int a[], int l, int r) {
    if (l >= r) return ;

    int x = a[l + r >> 1], i = l, j = r;

    while (i <= j) {
        while(a[i] < x) i++;
        while(a[j] > x) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }

    quick_sort(a, l, j);
    quick_sort(a, i, r);
}

quick_sort(a, l, j);
quick_sort(a, i, r);

上面一个的右边界i和下面一个的左边界j是怎么得到的，能解释一下不，大佬。

有两种情况吧；
一种是 i 和 j 相等，此时a[i] 就是x，下一步 i 加1， j 减1，[l, j]就是左区间，[i, r]就是右区间。
还有就是 i = j - 1，相当于把 i 和 j 与 a[i] 和 a[j] 一起交换，也是满足的。

多谢大佬的新模版，背这个了

但这样记的时候比较简单，就是全都不要等号，while条件、if条件判断都不需要等号^^

quick_sort(a,i,r)把i换成j+1为什么会爆内存

大佬，请问 int x= a[ l + r >> 1] 是什么意思
还有 如果i<=j ，为什么要交换 a[ i++] 和 a [ j– ] 呢？（我觉得应该交换a[ i ] 和 a[ j ]）

不是交换q[i+1]和q[j-1]，而是交换之后i+1，j-1;

真的优雅

有没有Java的模板啊

同问

大佬们，归并排序最后为什么要加这句代码？直接输出tmp为什么不行？输出tmp跟没排序之间是一样的，为什么？

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

扫尾

大佬，请问能详细一点吗？

你要放到整个递归过程来看，你认为的可以直接输tmp是对最后一次归并而言的。

懂了，谢谢

tmp是一个临时存储的数组，用于存当前合并的两个有序子数组合并后的有序数组。
q才是主力数组，每次tmp数组合并处理完的要写入q数组，才算完成。你看前面的代码，都是基于q数组的操作，tmp只是临时存储结果而已。

扫尾应该是这段代码
‘’‘
while (i <= mid) tmp[k ] = q[i ];
while (j <= r) tmp[k ] = q[j ];’‘’

piaoliang

大佬 捉

第一个快排好像并不能实现让x的左面都小于等于x，右面都大于等于x

是每一步的过程比如 1，5，6，3，2，5，4，8 x = 1 的话这一步的结果是 1 5 6 3 2 5 4 8

快速排序更新过了，x = q[l + r >> 1]

时隔四个月再回来看，这些很简单啦，超感激y总，草根福音！！！

高精度乘高精度：

vector<int> mul(vector<int> &a, vector<int> &b) {
  vector<int> c(a.size() + b.size(), 0);
  int t = 0;
  for(int i = 0; i < a.size(); i++) {
    for(int j =0; j < b.size(); j++) {
      c[i + j] += a[i] * b[j] + t;
      t = c[i + j] / 10;
      c[i + j] %= 10;
    }
    c[i + b.size()] = t;
  }
  while(c.size() > 1 && c.back() == 0) c.pop_back();
  return c;
}

c[i + b.size()] = t;这一句是啥意思啊，求大佬解答

就是把a[i]位乘b[b.size()-1]位之后出现的进位赋值给乘积c的下一位：c[i+b.size()-1+1]位

还行

哈哈哈哈哈哈哈