个人空间 - AcWing

Hdw

关注数

粉丝数

阅读量

2832

+关注发消息

离线：2小时前

最近来访(84)

唐子宸

1665383030

acwing_1896

Clean_up_the_stupid_incra

k_415

BR敏明mi

hong2009

AlanShelby

小偷33

belief_ak

congkaiyi

acwing_30906

20100928

略略略.

Warsaw

烧碱

AAAAAZBX

PuppetK

朱颜

巭

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

Hdw
3天前

                #include<iostream>
#include<cstring>

using namespace std;

const int N = 15, M = 1010;//数组开太大也会超时

char a[M][N], b[N];
int n, m, f[N][N];

int dw(int czcs)
{
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        memset(f, 0, sizeof f);

        int n1 = strlen(a[i] + 1), m1 = strlen(b + 1);
        for(int j = 1; j <= n1; j++) f[j][0] = j;
        for(int j = 1; j <= m1; j++) f[0][j] = j;

        for(int j = 1; j <= n1; j++)
        {
            for(int k = 1; k <= m1; k++)
            {
                f[j][k] = min(f[j - 1][k] + 1, f[j][k - 1] + 1);
                if(a[i][j] == b[k]) f[j][k] = min(f[j][k], f[j - 1][k - 1]);
                else f[j][k] = min(f[j][k], f[j - 1][k - 1] + 1);
            }
        }
        if(f[n1][m1] <= czcs) res++;
    }
    return res;
}

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

    while(m--)
    {
        int num;
        cin >> b + 1 >> num;
        cout << dw(num) << endl;
    }


    return 0;
}

            

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

Hdw
3天前

                #include<iostream>
#include<cstring>

using namespace std;

const int N = 15, M = 1010;

char a[M][N], b[N];
int n, m, f[N][N];

int dw(int czcs)
{
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        memset(f, 0, sizeof f);

        int n1 = strlen(a[i] + 1), m1 = strlen(b + 1);
        for(int j = 1; j <= n1; j++) f[j][0] = j;
        for(int j = 1; j <= m1; j++) f[0][j] = j;

        for(int j = 1; j <= n1; j++)
        {
            for(int k = 1; k <= m1; k++)
            {
                f[j][k] = min(f[j - 1][k] + 1, f[j][k - 1] + 1);
                if(a[i][j] == b[k]) f[j][k] = min(f[j][k], f[j - 1][k - 1]);
                else f[j][k] = min(f[j][k], f[j - 1][k - 1] + 1);
            }
        }
        if(f[n1][m1] <= czcs) res++;
    }
    return res;
}

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

    while(m--)
    {
        int num;
        cin >> b + 1 >> num;
        cout << dw(num) << endl;
    }


    return 0;
}

            

活动打卡代码 AcWing 1082. 数字游戏

Hdw
3天前

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

using namespace std;

const int N = 15;

int f[N][N];

void init()
{
    for(int i = 0; i <= 9; i++) f[1][i] = 1;

    for(int i = 2; i < N; i++)
        for(int j = 0; j <= 9; j++)
            for(int k = j; k <= 9; k++)
                f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if(!n) return 1;

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

    int res = 0, last = 0;
    for(int i = dw.size() - 1; i >= 0; i--)
    {
        int x = dw[i];
        for(int j = last; j < x; j++)
            res +=  f[i + 1][j];

        if(x < last) break;
        last = x;

        if(!i) res++;

    }

    return res;
}

int main()
{
    init();
    int a, b;
    while(cin >> a >> b) cout << dp(b) - dp(a - 1) << endl;

    return 0;
}

            

活动打卡代码 AcWing 1081. 度的数量

Hdw
4天前

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

using namespace std;

const int N = 35;

int x, y, k, b, f[N][N];

void init()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
        {
            if(!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
        }
}

int dp(int n)
{
    if(!n) return 0;

    vector<int> dw;
    while(n)
    {
        dw.push_back(n % b);
        n /= b;
    }

    int res = 0, r = 0;
    for(int i = dw.size() - 1; i >= 0; i--)
    {
        int num = dw[i];
        if(num)
        {
            res += f[i][k - r];
            if(num > 1)
            {
                if(k - r - 1 >= 0) res += f[i][k - r - 1];
                break;
            }
            else{
                r++;
                if(r > k)  break;
            }
        }
        if(!i && r == k) res++;
    }

    return res;
}

int main()
{
    init();
    cin >> x >> y >> k >> b;
    cout << dp(y) - dp(x - 1) << endl;

    return 0;
}

            

活动打卡代码 AcWing 5030. 核心元素

Hdw
5天前

                #include<iostream>
#include<cstring>

using namespace std;

const int N = 5010;

int a[N], b[N], c[N];

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

    for(int i = 1; i <= n; i++)
    {
        memset(b, 0, sizeof b);
        int maxv = 0, res;
        for(int j = i; j <= n; j++)
        {
            b[a[j]] ++;
            int t = b[a[j]];
            if(maxv < t || maxv == t && res > a[j])
            {
                maxv = b[a[j]];
                res = a[j];
            }
            c[res] ++;
        }
    }
    for(int i = 1; i <= n; i++) cout << c[i] << " ";

    return 0;
}

            

题目讨论 AcWing 102. 关于最佳牛围栏这道题我想了一个新思路，就是先预处理前缀和，然后依次将每个区间处理出来存在一个数组中，因为本题要求的是最大的平均值所以我感觉可以用优先队列的二分写法,处理成一个单调上升序列，最后最大的值就是队尾，但一直有3个测试点过不去，有没有大佬给我指正一下错误orz

Hdw
6天前

                代码如下，一直卡3个测试点
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

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

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

    int cnt = 0;
    for(int i = 1; i <= n - m + 1; i++)
        b[cnt++] = (a[i + m - 1] - a[i - 1]) / m * 1000;

    int len = 0;
    for(int i = 0; i < cnt; i++)
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < b[i]) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = max(q[r + 1], b[i]);
        len = max(len, r + 1);
    }
    cout << (long long)q[len] << endl;

    return 0;
}

            

活动打卡代码 AcWing 888. 求组合数 IV

Hdw
9天前

                #include<iostream>
#include<vector>

using namespace std;

const int N = 5010;

int primes[N], cnt, num[N];
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int dw(int n, int d)
{
    int res = 0;
    while(n)
    {
        res += n / d;
        n /= d;
    }
    return res;
}

vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size() || t; i++)
    {
        if(i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

int main()
{
    int a, b;
    cin >> a >> b;
    get_primes(a);

    for(int i = 0; i < cnt; i++)
    {
        int j = primes[i];
        num[i] = dw(a, j) - dw(b, j) - dw(a - b, j);
    }

    vector<int> res;
    res.push_back(1);
    for(int i = 0; i < cnt; i++)
        for(int j = 0; j < num[i]; j++)
            res = mul(res, primes[i]);

    for(int i = res.size() - 1; i >= 0; i--)
        printf("%d", res[i]);

    return 0;
}

            

活动打卡代码 AcWing 878. 线性同余方程

Hdw
9天前

                #include<iostream>

using namespace std;

typedef long long ll;

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

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

    while(n--)
    {
        int a, b, m, x, y;
        cin >> a >> b >> m;

        int d = exgcd(a, m, x, y);
        if(b % d) printf("impossible\n");
        else printf("%d\n", (ll)x * b / d % m);
    }

    return 0;
}

            

活动打卡代码 AcWing 887. 求组合数 III

Hdw
10天前

                #include<iostream>

using namespace std;

typedef long long ll;

int qmi(int a, int b, int p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)res = res * a % p;
        a = (ll) a * a % p;
        b >>= 1;
    }
    return res;
}

int c(int a, int b, int p)
{
    if(b > a) return 0; 

    int res = 1;
    for(int i = 1, j = a; i <= b; i++, j--)
    {
        res = (ll)res * j % p;
        res = (ll)res * qmi(i, p - 2, p) % p;
    }
    return res;
}

int lucas(ll a, ll b, int p)
{
    if(a < p && b < p) return c(a, b, p);
    return (ll)c(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

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

    while(n--)
    {
        ll a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

            

活动打卡代码 AcWing 886. 求组合数 II

Hdw
10天前

                #include<iostream>

using namespace std;

const int N = 1e5 + 10, mod = 1e9 + 7;

typedef long long ll;

ll f[N], fi[N];

ll qmi(int a, int b, int c)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)res = res * a % c;
        a = (ll) a * a % mod;
        b >>= 1;
    }

    return res;
}

int main()
{
    f[0] = fi[0] = 1;
    for(int i = 1; i < N; i++)
    {
        f[i] = f[i - 1] * i % mod;
        fi[i] = (ll)fi[i - 1] * qmi(i, mod - 2, mod) % mod;
    }

    int n;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        cout << (ll) f[a] * fi[b] % mod * fi[a - b] % mod << endl;
    }

    return 0;
}


            

0 评论

0 评论

0 评论

0 评论

0 评论

代码如下，一直卡3个测试点

1 评论

0 评论

0 评论

0 评论

0 评论