头像

滑稽_ωノ

河北科技师范学院




离线:3小时前


活动打卡代码 AcWing 1404. 蜗牛漫步

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 130;

int n, res;
int g[N][N];

//  上左下右
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y, int dir, int step)
{
    if(x < 1 or x > n or y < 1 or y > n or g[x][y])  return;

    int a, b;
    stack<PII> stk;
    while(true)
    {
        g[x][y] = 2;
        step ++;
        stk.push({x, y});

        a = x + dx[dir], b = y + dy[dir];
        if(a > n or a < 1 or b > n or b < 1 or g[a][b])  break;
        x = a, y = b;
    }
    res = max(res, step);
    if(g[a][b] != 2)
    {
        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            dfs(a, b, i, step);
        }
    }
    while(stk.size())
    {
        int x = stk.top().x, y = stk.top().y;  stk.pop();
        g[x][y] = 0;
    }
}

int main()
{
    int m;
    scanf("%d%d", &n, &m);
    while(m --)
    {
        char s[20];
        scanf("%s", s);
        int x = 0, y = s[0] - 'A' + 1;
        for(int i = 1; s[i]; i ++)  x = x * 10 + s[i] - '0';
        g[x][y] = 1;
    }

    dfs(1, 1, 2, 0);
    dfs(1, 1, 3, 0);

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 367. 学校网络

有向图的强连通分量

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = N << 1;

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

int n;

int dfn[N], low[N], tot;
int id[N], cnt;
int q[N], tt = -1;
bool st[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++ tot;
    q[++ tt] = u;
    st[u] = true;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(st[j])
            low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++ cnt;
        int y;
        do{
            y = q[tt --];
            st[y] = false;
            id[y] = cnt;
        }while(y != u);
    }
}

int din[N], dout[N];

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

    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int x;
        while(scanf("%d", &x), x)  add(i, x);
    }

    for(int i = 1; i <= n; i ++)
        if(!dfn[i])  tarjan(i);

    for(int i = 1; i <= n; i ++)
        for(int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if(a != b)  dout[a] ++, din[b] ++;
        }

    int x = 0, y = 0;
    for(int i = 1; i <= cnt; i ++)
    {
        if(!din[i])  x ++;
        if(!dout[i])  y ++;
    }
    printf("%d\n%d\n", x, cnt == 1 ? 0 : max(x, y));
    return 0;
}


活动打卡代码 AcWing 1407. 巨大牛棚

DP

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1010;

bool st[N][N];
int f[N][N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    while(k --)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        st[x][y] = true;
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(st[i][j])  continue;
            else
            {
                f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
                res = max(res, f[i][j]);
            }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 1405. 牛奶量取

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 110, M = 20010, INF = 0x3f3f3f3f;

int v[N];
int f[N][M];

vector<int> res, path;
void dfs(int i, int j)
{
    if(!i)
    {
        if(!res.size() or path < res)  res = path;
        return;
    }
    if(f[i][j] == f[i - 1][j])  dfs(i - 1, j);
    path.push_back(v[i]);
    for(int k = j - v[i]; k >= 0; k -= v[i])
        if(f[i][j] == f[i - 1][k] + 1)  dfs(i - 1, k);
    path.pop_back();
}

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

    sort(v + 1, v + n + 1, greater<int>());

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

    for(int i = 1; i <= n; i ++)
    {
        for(int k = 0; k < v[i]; k ++)
        {
            int t = f[i - 1][k];
            for(int j = k; j <= m; j += v[i])
            {
                f[i][j] = min(f[i - 1][j], t + 1);
                t = min(t, f[i - 1][j]);
            }
        }
    }
    printf("%d ", f[n][m]);
    dfs(n, m);
    for(int i : res)  printf("%d ", i);
    return 0;
}


活动打卡代码 AcWing 1392. 麦乐牛块

#include<cstdio>
#include<cstring>

const int N = 12, M = 1e6;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int a[N];
bool f[M];
int main()
{
    int n;
    scanf("%d", &n);

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

    if(d > 1)  return 0 * puts("0");

    f[0] = true;
    for(int i = 0; i < n; i ++)
        for(int j = a[i]; j < M; j ++)
            f[j] |= f[j - a[i]];

    int res = 0;
    for(int i = 0; i < M; i ++)
        if(!f[i])  res = i;
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 1366. 循环数

滑稽_ωノ
1个月前

模拟

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int check(int n)
{
    static int st[10];
    memset(st, 0, sizeof st);

    string s;
    while(n)
    {
        int t = n % 10;
        if(st[t])  return false;
        st[t] = true;
        s += '0' + t;
        n /= 10;
    }
    reverse(s.begin(), s.end());

    n = s.size();
    memset(st, 0, sizeof st);

    int p = 0, times = n;
    while(times --)
    {
        int m = s[p] - '0';
        while(m --)  p = (p + 1) % n;
        if(st[p])  return false;
        st[p] = true;
    }
    return p == 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(!(check( ++ n)));
    printf("%d\n", n);
    return 0;
}


活动打卡代码 AcWing 1365. 子集的和

滑稽_ωノ
1个月前

01背包

#include<cstdio>
#include<cstring>

typedef long long LL;

const int N = 40 * 40;

LL f[N];

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

    if((1 + n) * n / 2 % 2)  return 0 * puts("0");

    int m = (1 + n) * n / 4;

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

    printf("%lld\n", f[m] / 2);
    return 0;
}



滑稽_ωノ
1个月前

拓扑排序DP

const int N = 100010, M = 200010;


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

int q[N], n;
bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 0; i < n; i ++)
        if(!d[i])  q[ ++ tt] = i;

    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if( -- d[j] == 0)  q[ ++ tt] = j;
        }
    }
    return tt == n - 1;
}

int f[N][26];       //  到i位置j颜色出现了几次
class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        memset(h, -1, sizeof h);
        memset(d, 0, sizeof d);
        idx = 0,  n = colors.size();

        for(auto &v : edges)
        {
            int a = v[0], b = v[1];
            add(a, b);
        }

        if(!topsort())  return -1;

        int res = 0;
        memset(f, 0, sizeof f);
        for(int l = 0; l < n; l ++)
        {
            int u = q[l];
            f[u][colors[u] - 'a'] ++;
            for(int i = h[u]; ~i; i = ne[i])
            {
                int j = e[i];
                for(int k = 0; k < 26; k ++)
                {
                    f[j][k] = max(f[j][k], f[u][k]);
                }
            }
            for(int k = 0; k < 26; k ++)  res = max(res, f[u][k]);
        }
        return res;
    }
};



滑稽_ωノ
1个月前

二分&RMQ

傻了,没想起来单调栈

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int n, m;
int a[N];
LL sum[N];
int f[N][18];

void init()
{
    sum[0] = 0;
    for(int i = 1; i <= n; i ++)  sum[i] = sum[i - 1] + a[i];
    for(int j = 0; j < 18; j ++)
        for(int i = 1; i + (1 << j) - 1 <= n; i ++)
            if(!j)  f[i][j] = a[i];
            else  f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r)
{
    int k = log2(r - l + 1);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {

        n = nums.size();
        for(int i = 1; i <= n; i ++)  a[i] = nums[i - 1];
        init();

        LL res = 0;
        for(int i = 1; i <= n; i ++)
        {
            int l = 1, r = i;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(query(mid, i) >= a[i])  r = mid;
                else  l = mid + 1;
            }
            int left = l;

            l = i, r = n;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(query(i, mid) >= a[i])  l = mid;
                else  r = mid - 1;
            }
            l = left;

            res = max(res, (sum[r] - sum[l - 1]) * a[i]);
        }

        int ans = res % mod;
        return ans;
    }
};



滑稽_ωノ
1个月前

二分

class Solution {
public:
    int maxDistance(vector<int>& a, vector<int>& b) {

        int res = 0;
        for(int i = 0; i < a.size(); i ++)
        {
            if(i + 1 >= b.size())  break;
            int l = i, r = b.size() - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(b[mid] >= a[i])  l = mid;
                else  r = mid - 1;
            }
            res = max(res, l - i);
        }
        return res;
    }
};