头像

仅存老实人

$CJer{~}in{~}SJTU$




在线 


活动打卡代码 AcWing 2816. 判断子序列

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e5+10;

int a[N],b[N];
int n,m;

int main()
{
    cin >> n >> m;
    for(int i=0;i<n;i++)cin >> a[i];
    bool res=false;
    for(int i=0,j=0;i<m;i++)
    {
        cin >> b[i];
        if(b[i]==a[j] and j<n)j++;
        if(j==n)
        {
            res = true;
            break;
        }
    }
    if(res)cout<<"Yes";
    else cout<<"No";
    return 0;
}



活动打卡代码 AcWing 794. 高精度除法

     0112
 11  1234
     0
     12
     11
      13
      11
       24
       22
        2

$$
C_{3}C_{2}C_{1}C_{0}\\
b A_{3}A_{2}A_{1}A_{0}\\
r=A_{3}\\
r’ \times 10+A_{2}\\
r’‘ A_{1}\\
r’‘’ A_{0}\\
r’‘’‘\\
$$

/*
    C_{3}C_{2}C_{1}C_{0}
 b  A_{3}A_{2}A_{1}A_{0}
    r=A_{3}
    r'\times10+A_{2}
     r''\A_{1}
      r'''\A_{0}
       r''''
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);//1/11 12/11 13/11 24/11 
        r %= b;//1%11 12%11 13%11 24%11
    }
    reverse(C.begin(), C.end());// 0112 -> 2110
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    vector<int> A;

    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    int r=0;
    auto C = div(A, B, r);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];//2110 -> 211 cout 112

    cout << endl << r << endl;

    return 0;
}



活动打卡代码 AcWing 793. 高精度乘法

1423
  12
t = 0
C.push (3*12+t)%10=6
t = (3*12+t)/10=3
C.push (2*12+t)%10=7
t = (2*12+t)/10=2
C.push (4*12+t)%10=0
t = (4*12+t)/10=5
C.push (1*12+t)%10=7
t = (1*12+t)/10=1
C.push (0*12+t)%10=1
#include<iostream>
#include<cstring>
#include<vector>
#include<cstring>

using namespace std;

vector<int> mul(vector<int> &A,int b)
{
    vector<int> C;
    // t为往更高位传的数
    for(int i=0,t=0;i<A.size()||t;i++)
    {
        if(i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    // vector<int>C;
    auto C = mul(A,b);
    if(b<0)cout<<'-';
    for(int i=C.size()-1;i>=0;i--) cout << C[i];
    return 0;
}


活动打卡代码 AcWing 792. 高精度减法

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(vector<int> &A,vector<int> &B)
{
    if(A.size()!=B.size())return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i++)
        if(A[i]!=B[i])
            return A[i]>B[i];
    return true;
}

vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    for(int i=0,t=0;i<A.size();i++)
    {
        t = A[i]-t;
        if(i<B.size())t-=B[i];
        C.push_back((t+10)%10);
        if(t<0)t=1;
        else t=0;
    }
    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');
    vector<int> C;
    C = cmp(A,B)?sub(A,B):sub(B,A);
    if(!cmp(A,B)) cout << '-';
    for(int i=C.size()-1;i>=0;i--)cout << C[i];
    cout << endl;
    return 0;
}


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

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

vector<int> add(vector<int> &A,vector<int> &B)
{
    if(A.size()<B.size()) return add(B,A);
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size())t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)C.push_back(t);
    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 = add(A,B);
    for(int i=C.size()-1;i>=0;i--) cout << C[i];
    cout << endl;
    return 0;
}



底下的牛的强壮程度$S$越大越好
上面牛的重量和$W$越小越好(越重的放越下面)
=>
直觉是S[i]+W[i]越大的放越下面

证:

贪心得到的答案≥最优解(根据最优解定义:所有排序方案的最小值)

贪心得到的答案≤最优解

如果不是按S[i]+W[i]从小到大排序一定存在相邻ii+1有$w_{i}+s_{i}>w_{i+1}+s_{i+1}$

  • 可以发现此时交换第$i$头牛和第$i+1$头牛不影响$[0,i-1]$和$[i+2,n]$的风险
变化 第$i$个位置上的牛 第$i+1$个位置上的牛
交换前 $$w_1+…+w_(i-1)-s_i$$ $$w_1+…+w_(i)-s_(i+1)$$
交换后 $$w_1+…+w_(i-1)-s_(i+1)$$ $$w_1+…+w_(i-1)+w_(i+1)-s_(i)$$
  • 前$i-1$项减去
变化 第$i$个位置上的牛 第$i+1$个位置上的牛
交换前 $$-s_i$$ $$w_(i)-s_(i+1)$$
交换后 $$-s_(i+1)$$ $$w_(i+1)-s_(i)$$
  • 加上$s_{i}+s_{i+1}$
变化 第$i$个位置上的牛 第$i+1$个位置上的牛
交换前 $$s_(i+1)$$ $$w_i+s_i$$
交换后 $$s_i$$ $$w_(i+1)+s_(i+1)$$

$$
w_i+s_i>s_i\\
w_i+s_i \geq w_(i+1)+s_(i+1)\\
w_i+s_i \geq max(s_i,w_(i+1)+s_(i+1))\\
max(s_(i+1),w_i+s_i) \geq max(s_i,w_(i+1)+s_(i+1))\\
max(交换前) \geq max(交换后)\\
所有风险的最大值起码不会变大\\
即只要w_{i}+s_{i}不是严格递增,则我们可以把他们变成递增的\\
并且所有风险的最大值不会变大
$$

#include<iostream>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
const int N=50010;
#define x first
#define y second

int n;
PII cow[N];

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int w,s;
        cin >> w >> s;
        cow[i] = {w+s,w};
    }
    sort(cow,cow+n);
    int res = -1e9,sum=0;
    for(int i=0;i<n;i++)
    {
        int s;
        s = cow[i].x-cow[i].y;
        res = max(res,sum-s);//风险 = 上面的重量-当前的承受
        sum+=cow[i].y;
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

#include<iostream>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
const int N=50010;
#define x first
#define y second

int n;
PII cow[N];

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int w,s;
        cin >> w >> s;
        cow[i] = {w+s,w};
    }
    sort(cow,cow+n);
    int res = -1e9,sum=0;
    for(int i=0;i<n;i++)
    {
        int s;
        s = cow[i].x-cow[i].y;
        res = max(res,sum-s);//风险 = 上面的重量-当前的承受
        sum+=cow[i].y;
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    priority_queue<int,vector<int>,greater<int>> h;
    while(n--)
    {
        int x;
        cin >> x;
        h.push(x);
    }

    int res = 0;
    while(h.size()>1)
    {
        int t1 = h.top();h.pop();
        int t2 = h.top();h.pop();
        res +=t1+t2;
        h.push(t1+t2);
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;
int n;
int q[N];

int main()
{
    cin >> n;
    for(int i=0;i<n;i++) cin >> q[i];
    sort(q,q+n);
    int res = 0;
    for(int i=0;i<n;i++) res+=abs(q[i]-q[n/2]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1000010;

int n;
int t[N];

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

    sort(t,t+n);
    reverse(t,t+n);

    long long res = 0;
    for(int i=0;i<n;i++)
    {
        res+=t[i]*i;
    }
    printf("%lld\n", res);
    return 0;
}