头像

羊羊向前冲

牢固的记忆-深刻的理解-灵活的应用




离线:19分钟前


最近来访(165)
用户头像
名为溶菌酶的溶酶菌
用户头像
潘潘_the_panda
用户头像
mjd
用户头像
scc
用户头像
拓荒
用户头像
东方不败_1
用户头像
Kazimierz
用户头像
背书包的小新
用户头像
朗道十卷
用户头像
兔牙
用户头像
王一然
用户头像
huangbq
用户头像
望予闲
用户头像
上海市精神科主治医师
用户头像
kaggle
用户头像
托起彩虹的年轻人
用户头像
xxxxx123
用户头像
等等__
用户头像
4_SS.
用户头像
Carson_cyc

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

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

int n;
const int N = 5010;
int q[N];
int cnt[N], res[N];

int main()
{
    cin>> n;
    for(int i = 1; i <= n; i++)
        cin>> q[i];
    for(int i = 1; i <= n; i++)
    {
        memset(cnt, 0, sizeof cnt);
        int mx = 0, id;
        for(int j = i; j <= n; j++)
        {
            cnt[q[j]] ++;
            int t = cnt[q[j]];
            if(t > mx || t == mx && id > q[j])
                mx = t, id = q[j];
            res[id] ++;
        }
    }
    for(int i = 1; i <= n; i++)
        cout<< res[i] << " ";
    return 0;
}


活动打卡代码 AcWing 1127. 香甜的黄油

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

const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, m, p;
int id[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N];

void add(int a, int b, int c)  // 添加一条边a->b,边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa(int start)  // 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
{
    int hh = 0, tt = 1;
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;
    q[0] = start;
    st[start] = true;

    //循环队列
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j,则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int j = id[i];
        if(dist[j] == INF)
            return INF;
        res += dist[j];
    }
    return res;
}

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

    int res = INF;
    for(int i = 1; i <= p; i++)
        res = min(res, spfa(i));

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


活动打卡代码 AcWing 1128. 信使

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

const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N];

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

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j)  d[i][j] = 0;
            else    d[i][j] = INF;

    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin>> a >> b >> c;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int res = 0;
    for(int i = 1; i <= n; i++)
        if(d[1][i] == 0x3f3f3f3f)
        {
            res = -1; 
            break;
        }
        else
            res = max(res, d[1][i]);
    cout<< res << endl;
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

朴素版Dijkstra,堆优化版Dijkstra,spfa都可以写

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

const int N = 2510, M = 6200*2+10;
int n, m, S, T;
int h[N], w[M], e[M], ne[M], idx;
int dist[N];
bool st[N];

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    queue<int> que;
    que.push(S);

    while(que.size())
    {
        int t = que.front();
        que.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    que.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[T];
}

int main()
{
    cin>> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a, b, c;
        cin>> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    spfa();
    cout<< dist[T];
    return 0;
}


活动打卡代码 AcWing 1024. 装箱问题

//从前N个物品中选,体积要尽可能大
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 35, M = 2e4+10;
int v[N];
int f[N][M]; //从前n个物品中选,体积是m

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


活动打卡代码 AcWing 423. 采药

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

const int N = 1010;
int T[N], w[N];
int f[N][N];

int main()
{
    int t, m;
    cin>> t >> m; //采药时间,药材数目

    for(int i = 1; i <= m; i++)
        cin>> T[i] >> w[i];
    //1~m, 1~t
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= t; j++)
        {
            if(T[i] > j)
                f[i][j] = f[i-1][j];
            else
                f[i][j] = max(f[i-1][j], f[i-1][j-T[i]] + w[i]);
        }
    }
    cout<< f[m][t];
    return 0;
}


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

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

typedef pair<int, int> PII;

const int N = 50010;
int n;
PII cow[N];

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

    sort(cow, cow + n);

    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        int s = cow[i].first - cow[i].second, w = cow[i].second;
        res = max(res, sum - s);
        sum += w;
    }

    printf("%d\n", res);
    return 0;
}



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

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

typedef long long LL;

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

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

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

    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * i;

    printf("%lld\n", res);
    return 0;
}



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

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

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

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

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


活动打卡代码 AcWing 91. 最短Hamilton路径

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

const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];

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

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1];
    return 0;
}