头像

hjahgkhrhjg




离线:3小时前


活动打卡代码 AcWing 338. 计数问题

hjahgkhrhjg
23小时前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/

int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}

int power10(int x)
{
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n) return 0;

    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();

    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i -- )
    {
        if (i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);
        }

        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b , a)
    {
        if (a > b) swap(a, b);

        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 900. 整数划分

#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9+7;
int f[N], n;

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


活动打卡代码 AcWing 899. 编辑距离

#include <iostream>
#include <cstring>

using namespace std;

const int N = 15, M = 1010;
int n, m;
int f[N][N];
char str[M][N];

int edit(const char* str, const char* s)
{
    int la = strlen(str+1);
    int lb = strlen(s+1);
    for(int i = 0;i <= la;++i) f[i][0] = i;
    for(int i = 0;i <= lb;++i) f[0][i] = i;

    for(int i = 1;i <= la;++i)
        for(int j = 1;j <= lb;++j)
        {
            f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
            if(str[i] == s[j])
                f[i][j] = min(f[i][j], f[i-1][j-1]);
            else
                f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
        }
    return f[la][lb];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;++i) scanf("%s",str[i]+1);

    char s[N];
    int lim;
    while(m--)
    {
        scanf("%s%d", s+1, &lim);

        int ans = 0;
        for(int i = 0;i < n;++i)
            if(edit(str[i],s) <= lim)
                ++ans;
        printf("%d\n",ans);
    }

    return 0;
}


活动打卡代码 AcWing 902. 最短编辑距离

#include <iostream>
#include <cstring>

using namespace std;

const int N  = 1010;
char a[N], b[N];
int n, m, f[N][N];

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    //memset(f,1e9,sizeof(f));
    for(int i = 0;i <= n;++i) f[i][0] = i;
    for(int j = 0;j <= m;++j) f[0][j] = j;

    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
        {
            f[i][j] = min(f[i-1][j], f[i][j-1])+1;
            if(a[i] == b[j])
                f[i][j] = min(f[i][j], f[i-1][j-1]);
            else
                f[i][j] = min(f[i][j], f[i-1][j-1]+1);

        }
    printf("%d\n", f[n][m]);
    return 0;
}



#include <iostream>

using namespace std;

const int N = 1010;
char a[N], b[N];
int n, m, f[N][N];

int main()
{
    cin>>n>>m;
    cin>>a+1>>b+1;

    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if(a[i] == b[j])
                f[i][j] = max(f[i][j], f[i-1][j-1]+1);
        }
    cout<<f[n][m]<<endl;
    return 0;
}



#include <iostream>

using namespace std;

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

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;++i) scanf("%d",&q[i]);

    for(int i = 0;i < n;++i)
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l+r+1>>1;
            if(p[mid] < q[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r+1);
        p[r+1] = q[i];
    }

    printf("%d",len);
    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int q[N], f[N], n;

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

    for(int i = 0;i < n;++i)
    {
        f[i] = 1;
        for(int j = 0;j < i;++j)
            if(q[i] > q[j])
                f[i] = max(f[i],f[j]+1);
    }

    int ans = *max_element(f,f+n);
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

#include <iostream>

using namespace std;

const int N = 510;
int f[N][N], n;

int main()
{
    cin>>n;
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= i;++j)
            cin>>f[i][j];

    for(int i = n-1;i;--i)
        for(int j = i;j;--j)
            f[i][j] += max(f[i+1][j],f[i+1][j+1]);

    cout<<f[1][1];
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

#include <iostream>

using namespace std;

const int N = 110;
int f[N], v[N][N], w[N][N], s[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;++i)
    {
        scanf("%d", &s[i]);
        for(int j = 0;j < s[i];++j)
            scanf("%d%d", &v[i][j], &w[i][j]);
    }

    for(int i = 1;i <= n;++i)
        for(int j=m;j >=0;--j)
            for(int k = 0;k < s[i];++k)
            {
                if(j >= v[i][k])
                    f[j] = max(f[j],f[j - v[i][k]]+w[i][k]);
            }
    printf("%d",f[m]);
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

#include <iostream>

using namespace std;

const int N = 12010, M = 2010;

int n,m;
int v[N], w[N];
int f[M];

int main()
{
    cin>>n>>m;

    int cnt = 0;
    for(int i = 1;i <= n;++i)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            ++cnt;
            v[cnt] = k*a;
            w[cnt] = k*b;
            s-=k;
            k*= 2;
        }
        if(s > 0)
        {
            ++cnt;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }

    n = cnt;

    for(int i = 1;i <= n;++i)
        for(int j = m;j >= v[i];--j)
            f[j] = max(f[j], f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}