个人空间 - AcWing

彦辰kkkkk

关注数

粉丝数

阅读量

1.4万

+关注发消息

离线：1天前

题目：1.K倍区间

给定一个长度为 N的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K的倍数
我们就称这个区间 [i,j]是 K倍区间。
你能求出数列中总共有多少个 K倍区间吗？

桶预处理：

对于这类问题，我们先要把ai-aj-b=0这一式子化为等式，即ai-b=aj
K倍区间是因为(s[i]-s[j])%k==0等价于s[i]%k-s[j]%k==0即s[i]%k==s[j]%k
先将所有s[i]%k装进桶中，然后从前往后扫描一边s[j]%k
扫描时，我们就只需从前往后统计有多少s[j]%k满足前面的s[i]%k
最后累加起来，累加这一步应用了组合数的思想

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL a[N], s[N], cnt[N];

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

    LL res = 0;
    cnt[0] = 1;
    for(int i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }
    cout << res << endl;

    return 0;
}

题目2.差分计数

给定n个整数a1,a2……,an和一个整数x。
求有多少有序对(i, j)满足a[i]-a[j]=x
数据范围：
n为2e6
ai为-2e6到2e6
输入样例：
5 1
1 1 5 4 2
输出样例：
3

分析题目的式子a[i]-a[j]==x，我们可以化成a[i]==a[j]-x,
因为a[i]可能为负数，为了防止溢出
因此我们可以先把所有的a[i]+N装进桶中，
从前往后扫描时我们统计有多少数量的a[j]-x+N即可

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n, x;
int a[N];
LL cnt[N];

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

    for(int i = 1; i <= n; i ++ )
        cnt[a[i] + N] ++ ;

    LL res = 0;
    for(int i = 1; i <= n; i ++ )
        res += cnt[a[i] - x + N];

    cout << res << endl;

    return 0;
}

活动打卡代码 AcWing 1079. 叶子的颜色（每日一题）

彦辰kkkkk
4天前

                #include <bits/stdc++.h>

using namespace std;

const int N = 100010, inf = 0x3f3f3f3f;

int n, m;
int h[N], e[N], ne[N], idx;
int c[N];
bool st[N];
int f[N][2];
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    st[u] = true;
    // 先都涂上颜色
    if(u <= n)  
    {
        f[u][c[u]] = 1, f[u][!c[u]] = inf;
        return ;
    }
    else f[u][0] = f[u][1] = 1;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;;
        st[j] = true;
        dfs(j);
        f[u][0] += min(f[j][0] - 1, f[j][1]);
        f[u][1] += min(f[j][1] - 1, f[j][0]);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ ) cin >> c[i];
    for(int i = 1; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    int root = n + 1;
    dfs(root);

    cout << min(f[root][0], f[root][1]) << endl;

    return 0;
}

            

活动打卡代码 AcWing 1220. 生命之树（蓝桥杯辅导课）

彦辰kkkkk
4天前

                #include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int h[N], e[N], ne[N], idx;
int w[N];
bool st[N];
bool has_fa[N];
LL f[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    st[u] = true;
    f[u] += w[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        st[j] = true;
        dfs(j);
        f[u] += max(0ll, f[j]);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> w[i];
    for(int i = 1; i < n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
        has_fa[b] = true;
    }

    int root = 1;
    while(has_fa[root]) root ++ ;

    dfs(root);

    LL res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 323. 战略游戏（算法提高课）

彦辰kkkkk
4天前

                #include <bits/stdc++.h>

using namespace std;

const int N = 3010;

int n;
int h[N], e[N], ne[N], idx;
bool st[N];
bool has_fa[N];
int f[N][3];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    st[u] = true;
    f[u][1] += 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        st[j] = true;
        dfs(j);
        f[u][0] += f[j][1];
        f[u][1] += min(f[j][0], f[j][1]);
    }
}

int main()
{
    while(cin >> n)
    {
        memset(f, 0, sizeof f);
        memset(has_fa, 0, sizeof has_fa);
        memset(h, -1, sizeof h);
        idx = 0;
        memset(st, 0, sizeof st);
        for(int i = 1; i <= n; i ++ )
        {
            int a, cnt;
            scanf("%d:(%d)", &a, &cnt);
            while(cnt -- )
            {
                int b;
                cin >> b;
                add(a, b);
                has_fa[b] = true;
            }
        }

        int root = 0;
        while(has_fa[root]) root ++ ;
        dfs(root);

        cout << min(f[root][0], f[root][1]) << endl;
    }
    return 0;
}

            

活动打卡代码 AcWing 1072. 树的最长路径（算法提高课）

彦辰kkkkk
4天前

                #include <bits/stdc++.h>

using namespace std;

const int N = 20010;

int n;
int h[N], e[N], w[N], ne[N], idx;
int f1[N], f2[N];
bool st[N];
int res;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    st[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        st[j] = true;
        dfs(j);
        if(f1[u] <= f1[j] + w[i]) 
        {
            f2[u] = f1[u];
            f1[u] = f1[j] + w[i];
        }
        else if(f2[u] <= f1[j] + w[i]) f2[u] = f1[j] + w[i];
    }
    res = max(res, f1[u] + f2[u]);
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);

    for(int i = 1; i < n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    dfs(1);

    cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 285. 没有上司的舞会（算法基础课）

彦辰kkkkk
4天前

                #include <bits/stdc++.h>

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;
int w[N];
int f[N][3];
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][1] += w[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++ ) cin >> w[i];

    for(int i = 1; i < n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        has_fa[a] = true;
    }

    int root = 1;
    while(has_fa[root]) root ++ ;

    dfs(root);

    cout << max(f[root][0], f[root][1]) << endl;

    return 0;
}

            

活动打卡代码 AcWing 3996. 涂色（每日一题）

彦辰kkkkk
5天前

                #include <bits/stdc++.h>

using namespace std;

const int N = 5010;

int n;
int c[N], f[N][N];

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

    n = unique(c + 1, c + 1 + n) - c - 1;

    for(int len = 2; len <= n; len ++ )
        for(int i = 1; i + len - 1 <= n; i ++ )
        {
            int j = i + len - 1;
            f[i][j] = 0x3f3f3f3f;
            if(c[i] == c[j]) f[i][j] = f[i + 1][j - 1] + 1;
            else f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
        }

    cout << f[1][n] << endl;

    return 0;
}

            

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

彦辰kkkkk
5天前

                #include <bits/stdc++.h>

using namespace std;

const int N = 50010, inf = 0x3f3f3f3f;;

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

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

        f[0] = g[0] = -inf;
        for(int i = 1; i <= n; i ++ )
        {
            f[i] = max(f[i - 1], 0) + a[i];  //以i为结尾的连续最大字段和 
            g[i] = max(g[i - 1], f[i]);  //前i个数连续最大字段和的最大值
        }

        f[n + 1] = h[n + 1] = -inf;
        for(int i = n; i >= 1; i -- )
        {
            f[i] = max(f[i + 1], 0) + a[i];
            h[i] = max(h[i + 1], f[i]);
        }

        int res = -inf;
        for(int i = 1; i <= n; i ++ )
            res = max(res, g[i] + h[i + 1]);

        cout << res << endl;
    }
    return 0;
}

            

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

彦辰kkkkk
5天前

                区间dp
#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

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

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

    cout << f[1][n] << endl;

    return 0;
}


记忆化搜索写法
#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int n;
int a[N], s[N];
int f[N][N];

int dp(int i, int j)
{
    if(i == j) return 0;

    int &v = f[i][j];
    if(v != -1) return v;

    v = 0x3f3f3f3f;
    for(int k = i; k <= j - 1; k ++ )
        v = min(v, dp(i, k) + dp(k + 1, j) + s[j] - s[i - 1]);

    return v;
}

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

    memset(f, -1, sizeof f);

    cout << dp(1, n) << endl;

    return 0;
}

            

50%

0 评论

题目：1.K倍区间

题目2.差分计数

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

区间dp

记忆化搜索写法

0 评论