头像

Mr.Z2001

Northerneast University (China)




离线:4小时前


最近来访(23)
用户头像
jxj777
用户头像
dancebyte
用户头像
快晴

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

Mr.Z2001
13天前

如果一个牧场内没有奶牛,那么统计最短路线时,即使到不了这片牧场也没有关系,所以应该优先判断该牧场有没有奶牛,没有就直接continue就好了。
如果有,再考虑能不能到这片牧场的事情。

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

const int N = 810;
const int M = 3e3;
const int INF = 0x3f3f3f3f;

int h[N], val[M], nxt[M], w[M], idx;
int d[N][N];
bool vis[N];
int num[N];

int cow_num, n, m;

typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> heap;

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

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

    int x, y, z;
    for (int i = 1; i <= cow_num; ++i)
    {
        cin >> x;
        num[x]++;
    }

    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    int ans = INF;
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; ++i)
    {
        d[i][i] = 0;
        memset(vis, false, sizeof(vis));
        heap.push({0, i});
        while (!heap.empty())
        {
            auto t = heap.top();
            heap.pop();

            int dist = t.first;
            int ver = t.second;

            if (vis[ver])
                continue;
            vis[ver] = true;

            for (int k = h[ver]; ~k; k = nxt[k])
            {
                int j = val[k];
                if (!vis[j] && d[i][j] > dist + w[k])
                {
                    d[i][j] = dist + w[k];
                    heap.push({d[i][j], j});
                }
            }
        }
        int temp = 0;
        bool flag = true;
        for (int j = 1; j <= n; ++j)
        {
            if(!num[j])
                continue;
            if (d[i][j] == INF)
            {
                //cout << i << " " << j << " ";
                //cout << "break" << endl;
                flag = false;
                break;
            }
            temp += d[i][j] * num[j];
        }
        if (flag)
            ans = min(ans, temp);
    }
    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

Mr.Z2001
15天前

$x$在$a$和$b$之间,那么距离就是最小值$b-a$
所以在满足 $ a_1 \leq x \leq a_n $后,再继续满足 $ a_2 \leq x \leq a_{n-1} $ 就好了
最后推出来是在中位数位置。

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

const int N = 1e5 + 10;
int n;
int a[N];

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

    int p = a[(n + 1) >> 1];

    long long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += abs(a[i] - p);

    cout << ans << endl;

    return 0;
}


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

Mr.Z2001
15天前

注意边界处理。。

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

const int N = 5e4 + 10;

struct cow
{
    int w;
    int s;

    constexpr bool operator<(const cow &a) const
    {
        return w + s < a.w + a.s;
    }
};
cow a[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].w >> a[i].s;

    sort(a + 1, a + 1 + n);

    long long w = 0;
    long long ans = a[0].w - a[1].s;

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

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 901. 滑雪

Mr.Z2001
15天前

可能有多个合法的出发点(海拔最高点),所以需要遍历所有点求出最优解。

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

const int N = 310;
int g[N][N];
bool vis[N][N];
int dp[N][N];
int r, c;

const int step[][2] = {
    {0, 0},
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
};

int dfs(int x, int y)
{
    if (vis[x][y])
        return dp[x][y];
    vis[x][y] = true;
    int res = 0;
    for (int i = 1; i <= 4; ++i)
    {
        int xx = x + step[i][0];
        int yy = y + step[i][1];
        if (xx < 1 || xx > r || yy < 1 || yy > c || g[xx][yy] >= g[x][y])
            continue;
        res = max(res, dfs(xx, yy));
    }
    dp[x][y] = res + 1;
    return dp[x][y];
}

int main()
{
    int mx = 0, my = 0;
    cin >> r >> c;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
        {
            cin >> g[i][j];
            if (g[i][j] > g[mx][my])
                mx = i, my = j;
        }

    int res = 0;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            res = max(res, dfs(i, j));

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1969. 品种邻近

Mr.Z2001
15天前

开一个数组记录每一个品种的最后出现的位置(因为用贪心思想,所以需要用到最后的位置)
如果出现一对拥挤奶牛,那就更新一下答案,取个max就好了。

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

const int N = 5e4 + 10;
const int M = 1e6 + 10;
int a[N];
int pos[M];
int n, k;

int main()
{
    int ans = -1;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
    {
        if (pos[a[i]])
            if (i - pos[a[i]] <= k)
                ans = max(ans, a[i]);
        pos[a[i]] = i;
    }
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1987. 粉刷栅栏

Mr.Z2001
16天前

map实现离散化维护差分前缀和。
用左端点表示一个区间

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

map<int, int> m;

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

    int x;
    char d;
    int pos = 0;

    for (int i = 1; i <= n; ++i)
    {
        cin >> x >> d;
        if (d == 'L')
        {
            m[pos - x]++;
            m[pos]--;
            pos -= x;
        }
        else
        {
            m[pos]++;
            m[pos + x]--;
            pos += x;
        }
    }

    int ans = 0;
    auto i = m.begin();
    auto j = m.begin();
    ++j;
    for (; i != m.end(); ++i, ++j)
    {
        j->second += i->second;
        if (i->second >= 2)
            ans += j->first - i->first;
    }
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 2005. 马蹄铁

Mr.Z2001
17天前
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10;
typedef pair<int, int> pii;

bool vis[N][N];
char g[N][N];
int n;

const int step[][2] = {
    {0, 0},
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
};

int dfs(int x, int y, pii temp)
{
    vis[x][y] = true;
    if (g[x][y] == '(' && temp.second != 0)
    {
        vis[x][y] = false;
        return 0;
    }
    if (g[x][y] == '(')
        temp.first++;
    else
        temp.second++;
    if (temp.first == temp.second)
    {
        vis[x][y] = false;
        return 2 * temp.first;
    }
    int xx, yy;
    int ans = 0;
    for (int i = 1; i <= 4; ++i)
    {
        xx = x + step[i][0];
        yy = y + step[i][1];
        if (xx < 1 || xx > n || yy < 1 || yy > n || vis[xx][yy])
            continue;
        ans = max(ans, dfs(xx, yy, temp));
    }
    vis[x][y] = false;
    return ans;
}

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

    pii temp = {0, 0};
    int ans = 0;
    ans = dfs(1, 1, temp);

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 2014. 岛

Mr.Z2001
17天前

如果手动unique()的话,需要定义cnt来记录每个变量对应的位置,不能用循环的i

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii; // hight, idx
vector<int> a;
priority_queue<pii, vector<pii>, greater<pii>> heap;

int main()
{
    a.push_back(0);
    int n;
    cin >> n;
    int x;
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x;
        if (x != a.back())
            a.push_back(x), heap.push({x, ++cnt});
    }
    a.push_back(0);
    n = a.size() - 2;

    int now = 1;
    int ans = 1;
    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();

        int h = t.first;
        int idx = t.second;
        // printf("idx = %d ", idx);
        if (h > a[idx - 1] && h > a[idx + 1])
            now--;
        else if (h < a[idx - 1] && h < a[idx + 1])
            now++;

        if (!heap.empty() && heap.top().first == h)
            continue;
        else
            ans = max(ans, now);
        // printf("h = %d ",h);
        // printf("ans = %d\n",ans);
    }

    cout << ans;

    return 0;
}


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

Mr.Z2001
23天前
#include <iostream>
#include <algorithm>
using namespace std;

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

int main()
{
    int k;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> k;
        v[i][0] = k;
        for (int kk = 1; kk <= k; ++kk)
        {
            cin >> v[i][kk] >> w[i][kk];
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= 0; --j)
            for (int k = 1; k <= v[i][0]; ++k)
                if (j >= v[i][k])
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
    cout << dp[m];

    return 0;
}


活动打卡代码 AcWing 2060. 奶牛选美

Mr.Z2001
23天前

第一次bfs把其中一组X全换成Y
第二次bfs从所有的Y出发,找最短路到X
很暴力了…

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

const int N = 60;
const int M = 60;
const int INF = 0x3f3f3f3f;

int n, m;

struct coord
{
    int x;
    int y;
};

char g[N][M];
int ans[N][M];

queue<coord> q;
bool vis[N][M];

const int step[][2] = {
    {0, 0},
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
};

int fin = INF;

int main()
{
    cin >> n >> m;
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> g[i][j];

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (g[i][j] == 'X')
            {
                g[i][j] = 'Y';
                q.push((coord){i, j});
                ans[i][j] = 0;
                while (!q.empty())
                {
                    int x = q.front().x;
                    int y = q.front().y;
                    q.pop();
                    for (int i = 1; i <= 4; ++i)
                    {
                        int xx = x + step[i][0];
                        int yy = y + step[i][1];
                        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy] && g[xx][yy] == 'X')
                        {
                            g[xx][yy] = 'Y';
                            ans[xx][yy] = 0;
                            vis[xx][yy] = true;
                            q.push((coord){xx, yy});
                        }
                    }
                }
                memset(vis, false, sizeof(vis));
                q.push((coord){i, j});
                vis[i][j] = true;
                while (!q.empty())
                {
                    int x = q.front().x;
                    int y = q.front().y;
                    q.pop();
                    for (int i = 1; i <= 4; ++i)
                    {
                        int xx = x + step[i][0];
                        int yy = y + step[i][1];
                        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
                        {
                            switch (g[xx][yy])
                            {
                            case 'Y':
                                break;
                            case '.':
                                ans[xx][yy] = min(ans[xx][yy], ans[x][y] + 1);
                                break;
                            case 'X':
                                ans[xx][yy] = min(ans[xx][yy], ans[x][y] + 1);
                                fin = min(fin, ans[xx][yy]);
                                break;
                            }
                            if (!vis[xx][yy])
                                q.push((coord){xx, yy});
                            vis[xx][yy] = true;
                        }
                    }
                }
                goto END;
            }
        }
    }
END:
    cout << fin - 1 << endl;

    return 0;
}