头像

LWN


访客:426

离线:2天前


活动打卡代码 AcWing 791. 高精度加法

LWN
9个月前
#include<iostream>
#include<vector>
using namespace std;

vector<int> sum(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0, i = 0;
    while(i < A.size() || i < B.size())
    {
        int x;
        if(i >= A.size()) 
        {
            x = B[i] + t;
        }
        else  if(j >= B.size()) 
        {
            x = A[i] + t;
        }
        else
        {
            x = A[i] + B[i] + t;
        }
        t = x / 10;
        C.push_back(x % 10);
        i++;
    }
    if(t)
    {
        C.push_back(t);
    }
    return C;
}
int main()
{
    string a,b;
    cin>>a>>b;
    vector<int> A,B;
    for(int i = a.length() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }
    for(int i = b.length() - 1; i >= 0; i--)
    {
        B.push_back(b[i] - '0');
    }
    vector<int> C = sum(A,B);
    for(int i = C.size() - 1; i >= 0; i--)
    {
        printf("%d",C[i]);
    }
}


活动打卡代码 AcWing 790. 数的三次方根

LWN
9个月前
#include<iostream>

using namespace std;

int main()
{
    double n;
    cin>>n;
    if(n < 1e-6)
    {
        n *= -1;
        cout<<"-";
    }

    double l = 0, r = n;
    while(r - l >= 1e-8)
    {
        double mid = (l + r) / 2;
        if(mid*mid*mid >= n) r = mid;
        else l = mid;
    }
    printf("%.6lf",l);
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

LWN
9个月前
#include<iostream>

using namespace std;

int main()
{
    double n;
    cin>>n;
    double l = 0, r = n;
    while(r - l >= 1e-8)
    {
        double mid = (l + r) / 2;
        if(mid*mid*mid >= n)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    printf("%.6lf",l);
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

LWN
9个月前
#include<iostream>


using namespace std;

const int N = 1e5 + 10;
int a[N];
int n,q;

int main()
{
    cin>>n>>q;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    while(q--)
    {
        int x;
        cin>>x;
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(a[mid] >= x)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if(a[l] != x)
        {
            cout<<"-1 -1"<<endl;
        }
        else
        {
            cout<<l<<" ";
            r = n - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(a[mid] <= x)
                {
                    l = mid;
                }
                else
                {
                    r = mid - 1;
                }
            }
            cout<<l<<endl;
        }

    }



    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

LWN
9个月前
#include<iostream>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

int a[N],tmp[N];
int n;
LL res = 0;

LL merge_sort(int a[], int l, int r)
{
    if(l >= r) return 0;

    int mid = l + r >> 1;
    res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);

    int k = 0;
    int i = l;
    int j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

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

    return res;
}

int main()
{
    cin>>n;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
    }

    cout<<merge_sort(a,0,n-1);
    return 0;
}


活动打卡代码 AcWing 787. 归并排序

LWN
9个月前
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], tmp[N];
void merge_sort(int a[], int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int k = 0;
    int i = l;
    int j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) tmp[k ++] = a[i ++];
        else tmp[k ++] = a[j ++];
    }
    while(i <= mid) tmp[k ++] = a[i ++];
    while(j <= r) tmp[k ++] = a[j ++];

    for(i = l , j = 0; i <= r; i ++, j ++)
    {
        a[i] = tmp[j];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    merge_sort(a,0,n-1);
    for(int i = 0; i < n; i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

LWN
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦
#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N];
int n,k;

int fun(int a[], int l, int r, int k)
{
    if(l >= r)
    {
        return a[l];
    }

    int x = a[l + r >> 1];
    int i = l - 1;
    int j = r + 1;
    while(i < j)
    {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j)
        {
            swap(a[i],a[j]);
        }
    }
    if(j - l + 1 >= k) 
    {
        return fun(a,l,j,k);
    }
    else
    {
        return fun(a,j+1,r,k-(j-l+1));
    }
}
int main()
{
    cin>>n>>k;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    cout<<fun(a, 0, n-1, k);
    return 0;
}



活动打卡代码 AcWing 785. 快速排序

LWN
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

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

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

    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d",&a[i]);
    }
    quick_sort(a, 0, n - 1);
    for(int i = 0; i < n; i ++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}



LWN
9个月前

class Solution {
public:
ListNode merge(ListNode l1, ListNode* l2) {
if(!l1)
{
return l2;
}
if(!l2)
{
return l1;
}

    ListNode* p = nullptr;
    if(l1 -> val <= l2 ->val)
    {
        p = l1;
        l1 = l1 -> next;
    }
    else
    {
        p = l2;
        l2 = l2 -> next;
    }
    ListNode* head = p;
    while(l1 && l2)
    {
        if(l1 -> val <= l2 -> val)
        {
            p -> next = l1;
            l1 = l1 -> next;
        }
        else
        {
            p -> next = l2;
            l2 = l2 -> next;
        }
        p = p -> next;
    }
    if(l1)
    {
        p -> next = l1;

    }
    if(l2)
    {
        p -> next = l2;
    }
    return head;
}

};