个人空间 - AcWing

清风qwq

$$初一$$ $${\color{RGB(30, 200, 120)}{\href{https://www.acwing.com/blog/content/26305/}{『算法主页』}}}$$

关注数

粉丝数

123

阅读量

5.6万

+关注发消息

离线：47分钟前

最近来访(1666)

Rorschaches

六便士与月亮

RSqwq

guoweizhi

ZFW_FOR_LJY

王浩_7

shengshu_

konpakuy

IcedAmericanoCoffee

Mr锤子

醉酒听风念故人

源泉

yxc的小迷妹

You-Should-Know-Me

浊

能AC最好了

_yuki

量子态发圈

qweqwerr

题解 AcWing 2184. 餐巾计划问题

清风qwq
1天前

QQ截图20230326134623.png

#include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 100010, inf = 0x3f3f3f3f;
int S, T;
int r[N];
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

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

bool spfa()
{
    memset(incf, 0, sizeof incf);
    memset(d, 0x3f, sizeof d);

    int hh = 0, tt = 1;
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(incf[t], f[i]);
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
    flow = cost = 0;
    while (spfa())
    {
        flow += incf[T], cost += incf[T] * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1] )
        {
            f[pre[i]] -= incf[T];
            f[pre[i] ^ 1] += incf[T];
        }
    }
}

int main()
{
    int day, p, m, f, n, s;
    scanf("%d%d%d%d%d%d", &day, &p, &m, &f, &n, &s);

    S = 0, T = day * 2 + 1;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= day; i ++ )
    {
        scanf("%d", &r[i]);
        add(S, i, r[i], 0);
        add(S, day + i, inf, p);
        add(day + i, T, r[i], 0);
        if (i > 1) add(day + i - 1, day + i, inf, 0);
        if (i > m) add(i - m, day + i, inf, f);
        if (i > n) add(i - n, day + i, inf, s);
    }


    int flow, cost;
    EK(flow, cost);
    printf("%d\n", cost);

    return 0;
}

活动打卡代码 AcWing 2184. 餐巾计划问题

清风qwq
1天前

                #include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 100010, inf = 0x3f3f3f3f;
int S, T;
int r[N];
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

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

bool spfa()
{
    memset(incf, 0, sizeof incf);
    memset(d, 0x3f, sizeof d);

    int hh = 0, tt = 1;
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(incf[t], f[i]);
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
    flow = cost = 0;
    while (spfa())
    {
        flow += incf[T], cost += incf[T] * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1] )
        {
            f[pre[i]] -= incf[T];
            f[pre[i] ^ 1] += incf[T];
        }
    }
}

int main()
{
    int day, p, m, f, n, s;
    scanf("%d%d%d%d%d%d", &day, &p, &m, &f, &n, &s);

    S = 0, T = day * 2 + 1;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= day; i ++ )
    {
        scanf("%d", &r[i]);
        add(S, i, r[i], 0);
        add(S, day + i, inf, p);
        add(day + i, T, r[i], 0);
        if (i > 1) add(day + i - 1, day + i, inf, 0);
        if (i > m) add(i - m, day + i, inf, f);
        if (i > n) add(i - n, day + i, inf, s);
    }


    int flow, cost;
    EK(flow, cost);
    printf("%d\n", cost);

    return 0;
}


            

题解 AcWing 4877. 最大价值

清风qwq
2天前

多重背包

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
int l[N], h[N], v[N], w[N];
int f[N];

int main()
{
    scanf("%d%d%d%d", &n, &m, &v[0], &w[0]);

    for (int i = 1; i <= m; i ++ ) scanf("%d%d%d%d", &l[i], &h[i], &v[i], &w[i]);

    for (int i = 0; i <= n; i ++ ) f[i] = i / v[0] * w[0];

    for (int i = 1; i <= m; i ++ )
        for (int j = n; j >= 0; j -- )
            for (int k = 0; k <= l[i] / h[i]; k ++ )
                if (j >= v[i] * k)
                    f[j] = max(f[j], f[j - v[i] * k] + w[i] * k);

    printf("%d", f[n]);                

    return 0;
}

题解 AcWing 4878. 维护数组

清风qwq
2天前

树状数组

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 200010;
int n, k, a, b, q;
int tr1[N], tr2[N];
long long num[N];

int lowbit(int x)
{
    return x & - x;
}

void add(int tr[N], int x, int y)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += y;
}

long long sum(int tr[N], int x)
{
    long long res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;    
}

int main()
{
    scanf("%d%d%d%d%d", &n, &k, &a, &b, &q);

    while (q -- )
    {
        int op;
        scanf("%d", &op);

        if (op == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            add(tr1, x, min(num[x] + y, (ll)b) - min(num[x], (ll)b));
            add(tr2, x, min(num[x] + y, (ll)a) - min(num[x], (ll)a));
            num[x] += y;
        }
        else
        {
            int p;
            scanf("%d", &p);
            printf("%lld\n", sum(tr1, p - 1) + sum(tr2, n) - sum(tr2, p + k - 1));
        }
    }

    return 0;
}

活动打卡代码 AcWing 1467. 奶牛朝向

清风qwq
3天前

                #include <bits/stdc++.h>
using namespace std;

int n;
char g[1010][1010];

void row(int k)
{
    for (int i = 1; i <= n; i ++ )
        g[k][i] = (g[k][i] == 'L') ? 'R' : 'L';
}

void col(int k)
{
    for (int i = 1; i <= n; i ++ )
        g[i][k] = (g[i][k] == 'L') ? 'R' : 'L';
}

int main() 
{

    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);

    if (g[1][1] == 'L') col(1);

    for (int i = 2; i <= n; i ++ )
        if (g[1][i] == 'L')
            col(i);

    for (int i = 2; i <= n; i ++ )
        if (g[i][1] == 'L')
            row(i);

    int f = 0;
    for (int i = 2; i <= n; i ++ )
        for (int j = 2; j <= n; j ++ )
            f += (g[i][j] == 'L');

    if (f == (n - 1) * (n - 1))
    {
        if (n == 2) printf("-1\n");
        else printf("1 1\n");
        return 0;
    }
    else if (f == 1)
    {
        for (int i = 2; i <= n; i++)
            for(int j = 2; j <= n; j++)
                if(g[i][j] == 'L')
                    return 0 & printf("%d %d", i, j);
    }
    else if (f == n - 1)
    {
        for (int i = 1; i <= n; i ++ )
        {
            int s = 0;
            for (int j = 1; j <= n; j ++ ) s += (g[i][j] == 'L');
            if(s == n - 1) return 0 & printf("%d %d", i, 1);
        }
        for (int i = 1; i <= n; i ++ )
        {
            int s = 0;
            for (int j = 1; j <= n; j ++ ) s += (g[j][i] == 'L');
            if(s == n - 1) return 0 & printf("%d %d", 1, i);
        }
    }
    else puts("-1");

    return 0;
}


            

题解 AcWing 1682. 大型植被恢复

清风qwq
3天前

                #include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int tag[N];

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

bool bfs(int u)
{
    queue<int> q;
    q.push(u);
    tag[u] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (tag[j] != -1)
            {
                if (tag[j] != (tag[t] ^ w[i])) return false;
                continue;
            }
            tag[j] = tag[t] ^ w[i];
            q.push(j);
        }
    }

    return true;
}

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

    memset(h, -1, sizeof h);
    memset(tag, -1, sizeof tag);

    for (int i = 0; i < m; i ++ )
    {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'S') add(a, b, 0), add(b, a, 0);
        else add(a, b, 1), add(b, a, 1);
    }

    string ans = "1";
    for (int i = 1; i <= n; i ++ )
        if (tag[i] == -1)
        {
            if (!bfs(i))
            {
                ans = "0";
                break;
            }
            else ans += "0";
        }

    cout << ans ;

    return 0;
}

            

活动打卡代码 AcWing 1682. 大型植被恢复

清风qwq
3天前

                #include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int tag[N];

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

bool bfs(int u)
{
    queue<int> q;
    q.push(u);
    tag[u] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (tag[j] != -1)
            {
                if (tag[j] != (tag[t] ^ w[i])) return false;
                continue;
            }
            tag[j] = tag[t] ^ w[i];
            q.push(j);
        }
    }

    return true;
}

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

    memset(h, -1, sizeof h);
    memset(tag, -1, sizeof tag);

    for (int i = 0; i < m; i ++ )
    {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'S') add(a, b, 0), add(b, a, 0);
        else add(a, b, 1), add(b, a, 1);
    }

    string ans = "1";
    for (int i = 1; i <= n; i ++ )
        if (tag[i] == -1)
        {
            if (!bfs(i))
            {
                ans = "0";
                break;
            }
            else ans += "0";
        }

    cout << ans ;

    return 0;
}

            

题解 AcWing 1680. 困牛放牧

清风qwq
4天前

                #include <bits/stdc++.h>
using namespace std;

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

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

    sort(a.begin(), a.end());

    int ans = 0;
    for (int i = 0, j = 0, cnt = 1; i < n; i ++ )
    {
        while (j + 1 < n && a[j + 1] - a[i] + 1 <= n) j ++ , cnt ++ ;
        if (cnt != n - 1 || a[j] + 1 != a[i] + n - 1)ans = max(ans, cnt);
        cnt -- ;
    }

    ans = n - ans;

    printf("%d\n%d\n", ans, max(a[n - 1] - a[1], a[n - 2] - a[0]) - n + 2);

    return 0;
}

            

题解 AcWing 1681. 谷仓刷漆

清风qwq
4天前

                #include <bits/stdc++.h>
using namespace std;

int sum[1010][1010];

int main()
{
    int n, k, cnt = 0;
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i ++ )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        x1 ++ , y1 ++ ;
        sum[x1][y1] ++ , sum[x1][y2 + 1] -- , sum[x2 + 1][y1] --, sum[x2 + 1][y2 + 1] ++ ;
    }

    for (int i = 1; i <= 1001; i ++ )
        for (int j = 1; j <= 1001; j ++ )
        {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            if (sum[i][j] == k) cnt ++ ;
        }

    printf("%d", cnt);

    return 0;
}

            

活动打卡代码 AcWing 1681. 谷仓刷漆

清风qwq
4天前

                #include <bits/stdc++.h>
using namespace std;

int sum[1010][1010];

int main()
{
    int n, k, cnt = 0;
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i ++ )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        x1 ++ , y1 ++ ;
        sum[x1][y1] ++ , sum[x1][y2 + 1] -- , sum[x2 + 1][y1] --, sum[x2 + 1][y2 + 1] ++ ;
    }

    for (int i = 1; i <= 1001; i ++ )
        for (int j = 1; j <= 1001; j ++ )
        {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            if (sum[i][j] == k) cnt ++ ;
        }

    printf("%d", cnt);

    return 0;
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论