个人空间 - AcWing

不想学习啊

阅读量

1594

+关注发消息

离线：3小时前

最近来访(16)

王鹏宇

坤坤带你转AC

insistance

喰种丿研

550W

zypnb

ZDC

Acwing_九日

liukebing

Jettblue

GreatestOliveira

为梦奔赴

克兰兹

硝基苯_5

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

坤坤教你如何AC

活动打卡代码 AcWing 282. 石子合并（算法基础课）

不想学习啊
4小时前

                #include<iostream>
#include<cstring>

using namespace std;

const int N = 305;

int s[N];
int f[N][N];//f[i][j] 合并第i到第j堆所需的最小代价

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

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

    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; i++)
        f[i][i] = 0;

    for(int len = 2; len <= n; len++)
        for(int i = 1, j = i + len - 1; j <= n; i++, j++)
            for(int k = i; k < j; k++)
                f[i][j] = min(f[i][j], s[j] - s[i - 1] + f[i][k] + f[k + 1][j]);

    cout << f[1][n];

    return 0;
}

            

活动打卡代码 AcWing 1051. 最大的和（每日一题）

不想学习啊
4小时前

                #include<iostream>

using namespace std;

const int N = 50005;

int a[N];
int f[N], g[N];

int main()
{
    int T; scanf("%d", &T);

    while(T--)
    {
        int n; scanf("%d", &n);

        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);

        f[0] = -10005;
        for(int i = 1, s = 0; i <= n; i++)
        {
            s = a[i] + max(s, 0);
            f[i] = max(f[i - 1], s);
        }

        g[n + 1] = -10005;
        for(int i = n, s = 0; i; i--)
        {
            s = a[i] + max(s, 0);
            g[i] = max(g[i + 1], s);
        }

        int ans = -20005;
        for(int i = 1; i <= n; i++)
            ans = max(ans, f[i] + g[i + 1]);
        printf("%d\n", ans);
    }

    return 0;
}

            

活动打卡代码 AcWing 272. 最长公共上升子序列（算法提高课）

不想学习啊
23小时前

                #include<iostream>

using namespace std;

const int N = 3005;

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

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

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

    for(int j = 1; j <= n; j++)
        cin >> b[j];

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

    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[n][i]);
    cout << ans;

    return 0;
}

            

活动打卡代码 AcWing 897. 最长公共子序列（算法基础课）

不想学习啊
23小时前

                #include<iostream>

using namespace std;

const int N = 1005;

char A[N], B[N];
int f[N][N];

int main()
{
    int n, m;
    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];

    return 0;
}

            

活动打卡代码 AcWing 895. 最长上升子序列（算法基础课）

不想学习啊
23小时前

                $O(n^2)$
#include<iostream>

using namespace std;

const int N = 1005;

int a[N];
int f[N];

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

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

    a[0] = -2e9;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < i; j++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[i]);

    cout << ans;

    return 0;
}


$O(n \log_2 n)$
#include<iostream>

using namespace std;

const int N = 1005;

int a[N];
int f[N], cnt;

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

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

    a[0] = -2e9, f[0] = a[0];
    for(int i = 1; i <= n; i++)
    {
        if(a[i] > f[cnt]) f[++cnt] = a[i];
        else//*lower_bound(f, f + cnt + 1, a[i]) = a[i];
        {
            int l = 0, r = cnt;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(f[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            f[l] = a[i];
        }
    }

    cout << cnt;

    return 0;
}

            

活动打卡代码 AcWing 898. 数字三角形（算法基础课）

不想学习啊
23小时前

                #include<iostream>

using namespace std;

const int N = 505;

int f[N];
int a[N][N];

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

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

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

    cout << f[0];

    return 0;
}

            

题目讨论 AcWing 4005. 贴一个打表代码

不想学习啊
3天前

                贴一个打表代码
#include<iostream>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N = 105;

int s[3] = {1, 2};
int f[N];

int sg(int x)
{
    if(f[x] != -1) return f[x];

    unordered_set<int> S;
    for(int i = 0; i < 3; i++)
    {
        if(s[i] <= x) S.insert(sg(x - s[i]));
    }

    for(int i = 0; ; i++)
    {
        if(!S.count(i)) return f[x] = i;
    }
}

int main()
{
    for(int k = 3; k <= 35; k++)
    {
        printf("******k = %d********\n", k);

        s[2] = k;
        memset(f, -1, sizeof f);

        for(int i = 0; i <= 26; i++)
            printf("%2d ", i);
        puts("");

        for(int i = 0; i <= 26; i++)
        {
            if(sg(i)) printf("Al ");
            else printf("Bo ");
        }
        puts("");
    }

    return 0;
}

            

活动打卡代码 AcWing 893. 集合-Nim游戏（算法基础课）

不想学习啊
3天前

                #include<iostream>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N =  105, M = 10005;

int f[M];
int s[N];
int k, n;

int sg(int x)
{
    if(f[x] != -1) return f[x];

    unordered_set<int> S;
    for(int i = 0; i < k; i++)
    {
        if(s[i] <= x) S.insert(sg(x - s[i]));
    }

    for(int i = 0; ; i++)
    {
        if(!S.count(i)) return f[x] = i;
    }
}

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

    memset(f, -1, sizeof f);

    cin >> n;
    int ans = 0;
    while(n--)
    {
        int x; cin >> x;
        ans ^= sg(x);
    }

    if(ans) puts("Yes");
    else puts("No");

    return 0;
}

            

活动打卡代码 AcWing 891. Nim游戏（算法基础课）

不想学习啊
3天前

                #include<iostream>

using namespace std;

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

    int ans = 0;
    while(n--)
    {
        int x; cin >> x;
        ans ^= x;
    }

    if(ans) puts("Yes");
    else puts("No");

    return 0;
}

            

题解 AcWing 4496. 吃水果--组合计数和dp代码分享

不想学习啊
3天前

                只做代码分享
组合数
#include<iostream>

using namespace std;

typedef long long LL;

const int N = 2005, mod = 998244353;

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

void get_primes(int a, int b)
{
    for(int i = 2; i <= a; i++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;

            for(int j = a; j; j /= i) index[cnt - 1] += j/i;

            for(int j = b; j; j /= i) index[cnt - 1] -= j/i;

            for(int j = a - b; j; j /= i) index[cnt - 1] -= j/i;
        }

        for(int j = 0; primes[j] <= a/i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int qmi(LL a, LL b)
{
    LL ans = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }

    return ans;
}

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

    //C(n-1, k) * m * (m-1)^k
    get_primes(n - 1, k);

    LL ans = (LL)m * qmi(m - 1, k) % mod;
    for(int i = 0; i < cnt; i++)
        ans = ans * qmi(primes[i], index[i]) % mod;
    cout << ans;

    return 0;
}



dp
#include<iostream>

using namespace std;

typedef long long LL;

const int N = 2005, mod = 998244353;

LL f[N][N];//前 i 个小朋友， 恰好有 j 个小朋友与其左边拿的水果不一样

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

    for(int i = 1; i <= n; i++)
        f[i][0] = m;

    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= min(i, k); j++)
            f[i][j] = (f[i-1][j] + f[i-1][j-1] * (m - 1) % mod) % mod;

    cout << f[n][k];

    return 0;
}


一维
#include<iostream>

using namespace std;

typedef long long LL;

const int N = 2005, mod = 998244353;

LL f[N];

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

    f[0] = m;
    for(int i = 2; i <= n; i++)
        for(int j = min(i, k); j; j--)
            f[j] = (f[j] + f[j-1] * (m - 1) % mod) % mod;

    cout << f[k];

    return 0;
}

            