洛谷--算法题

1. A+B Problem（高精）Code:#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <iomanip>#include <vector>using name

cold Writer

171人浏览 · 2021-09-07 10:58:59

cold Writer · 2021-09-07 10:58:59 发布

1. A+B Problem（高精）

请添加图片描述

Code:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>

using namespace std;
int main() {
    string a,b;
    vector<int>res;
    cin>>a>>b;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); ++i) {
        if (i < a.size()) t += a[i] - '0';
        if (i < b.size()) t += b[i] - '0';
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(1);
    for (int i = res.size() - 1; i >= 0; --i) {
        cout<<res[i];
    }
}

Note:

由于输入的数字范围过大，必须要用字符串输入数字，输入之后为个位开始计算，利用reverse函数使字符串倒置。
然后对a和b上的每一位数字从小到大相加，注意循环的前面定义了一个 t，用来保存进位的值。
只要将每一个数字字符减去‘0’即可得到整型值。
注意循环结束之后还有一个t需要判断是否要进位。

2. A*B Problem

请添加图片描述

Code：

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 50000

int m[MAXN], n[MAXN], t[MAXN];

void multip(string x, string y) {
    int lenx = x.size();
    int leny = y.size();
    int len = lenx + leny;
    for (int i=0; i<lenx; ++i)
        m[i] = x[lenx-i-1] - '0';
    for (int i=0; i<leny; ++i)
        n[i] = y[leny-i-1] - '0';
    for (int i=0; i<lenx; ++i)
        for (int j=0; j<leny; ++j)
            t[i+j] += m[i] * n[j];
    for (int i=0; i<len; ++i)
        if (t[i] > 9) {
            t[i+1] += t[i] / 10;
            t[i] %= 10;
        }
    while (t[len-1] == 0 && len > 1)
        --len;
    for (int i=len-1; i>=0; --i)
        cout << t[i];
}

int main() {
    string a, b;
    cin >> a >> b;
    multip(a, b);
    cout << endl;
    return 0;
}

Note：

关键在于：

for (int i=0; i<lenx; ++i)
        for (int j=0; j<leny; ++j)
            t[i+j] += m[i] * n[j];

3. 求第 k 小的数

请添加图片描述

Code:

#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
void qsort(int l,int r)
{
	int i=l,j=r,mid=x[(l+r)/2];
	do
	{
		while(x[j]>mid)
			j--;
		while(x[i]<mid)
			i++;
		if(i<=j)
		{
			swap(x[i],x[j]);
			i++;
			j--;
		}
	}
	while(i<=j);
	//快排后数组被划分为三块： l<=j<=i<=r
	if(k<=j) qsort(l,j);//在左区间只需要搜左区间
	else if(i<=k) qsort(i,r);//在右区间只需要搜右区间
	else //如果在中间区间直接输出
	{
		printf("%d",x[j+1]);
		exit(0);
	}
}
int main()
{
	int n;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&x[i]);
	qsort(0,n-1);
}