头像

南风可知意.




离线:12小时前


最近来访(38)
用户头像
qlc23333
用户头像
dp_53
用户头像
LiHaoyu
用户头像
Forelsket_2
用户头像
Jettblue
用户头像
南风意西洲梦
用户头像
凌乱之风
用户头像
shengshu_
用户头像
Dr孟
用户头像
AsarumZJ

活动打卡代码 AcWing 4403. 修剪灌木

模拟

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int first = (n - 1) * 2;
    if (n % 2) // 奇数
    {
        for (int i = 1; i <= n; ++i)
        {
            printf("%d\n", first);
            if (i < (n + 1) / 2)
                first -= 2;
            else
                first += 2;
        }
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            printf("%d\n", first);
            if (i < (n + 1) / 2)
                first -= 2;
            else if (i > (n - 1) / 2 + 1)
                first += 2;
        }
    }

    return 0;
}


活动打卡代码 AcWing 523. 组合数问题

递推 二维前缀和

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

const int maxn = 2010;
int C[maxn][maxn];   // 组合数
int st[maxn][maxn];  // 0不是倍数 1是倍数
int sum[maxn][maxn]; // 前缀和数组
int n, m, k, t;

void pre(int N)
{
    for (int i = 0; i <= N; ++i)
    {
        C[i][0] = 1 % k;
        st[i][0] = 1; // 0是k的倍数 ?
    }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j)
        {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k; // 递推式
            if (!C[i][j] && j <= i)
                st[i][j] = 1;
        }

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j) // 对每个位置求前缀和
            sum[i][j] = st[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}

int main()
{
    cin >> t >> k;
    pre(maxn - 10);
    while (t--)
    {
        cin >> n >> m;
        cout << sum[n][m] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1171. 距离

LCA Tarjan算法

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int maxn = 10010;
int n, m;
int h[maxn], w[maxn * 2], e[maxn * 2], ne[maxn * 2], idx;
int res[maxn * 2];           // 存储查询的答案
vector<PII> query[maxn * 2]; // query[i][first][second]  first存查询 距离i的另外一个点j,second存查询编号idx
int p[maxn];                 // 并查集 祖宗结点
int dist[maxn];              // 每个结点到根节点的距离
int st[maxn];                // 标记结点状态 0未遍历 1已遍历未回溯 2已遍历并完成回溯

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, int father)
{
    for (int i = h[u]; ~i; i = ne[i]) // 每一条边
    {
        int j = e[i]; // 结点
        if (j == father)
            continue;
        dist[j] = dist[u] + w[i]; // w[i]边权
        dfs(j, u);
    }
}

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u] = 1; // 标记遍历到此处
    // 将u这条路上的根节点的左下的点用并查集合并到根节点
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j); // 往左下搜
            p[j] = u;  // 从左下回溯后把左下的点合并到根节点
        }
    }
    // 对于当前点u 搜索所有和u有关的询问
    for (auto item : query[u])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2) // 如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2)
        {
            int anc = find(y);                           // x与y的LCA
            res[id] = dist[y] + dist[u] - dist[anc] * 2; // 距离公式
        }
    }
    // 点u已经搜索完且要回溯了 把st[u]标记为2
    st[u] = 2;
}

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

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x != y)
        {
            query[x].push_back({y, i});
            query[y].push_back({x, i});
        }
    }

    for (int i = 1; i <= n; ++i)
        p[i] = i; // 初始化并查集

    dfs(1, -1); // 先算出每个点到根的距离,任意指定一个结点为根,此处指定为1
    tarjan(1);  // 求LCA

    for (int i = 0; i < m; ++i)
        printf("%d\n", res[i]);

    return 0;
}


活动打卡代码 AcWing 1234. 倍数问题

背包+贪心优化

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> // 模m的余数相同的数的数量不一定,用vector存
using namespace std;

const int maxn = 1010;
int n, m;
vector<int> a[maxn];
int f[4][maxn];

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

    memset(f, -0x3f, sizeof f); // 初始化
    f[0][0] = 0;                // 边界
    for (int i = 0; i < m; ++i)
    {
        sort(a[i].begin(), a[i].end());
        reverse(a[i].begin(), a[i].end()); // 降序

        for (int u = 0; u < 3 && u < a[i].size(); ++u) // 只枚举每类前3大的数
            for (int j = 3; j > 0; --j)                // 倒序
                for (int k = 0; k < m; ++k)
                    f[j][k] = max(f[j][k], f[j - 1][(k - a[i][u] % m + m) % m] + a[i][u]);
    }
    printf("%d\n", f[3][0]);

    return 0;
}


活动打卡代码 AcWing 1242. 修改数组

并查集

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

const int maxn = 1100010; // 共1e5个数,每个数最大1e6,最大值1e6+1e5
int p[maxn];              // 每个数的下一个未被使用过的数

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]); // 路径压缩
    return p[x];
}

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

    for (int i = 1; i < maxn; ++i)
        p[i] = i; // 都未被使用过 初始化为自环

    for (int i = 0; i < n; ++i)
    {
        int x;
        scanf("%d", &x);
        x = find(x);
        if (i)
            printf(" ");
        printf("%d", x);
        p[x] = x + 1;
    }

    return 0;
}


活动打卡代码 AcWing 1217. 垒骰子

线性DP 矩阵快速幂

// 数据范围1e9,需要用 矩阵快速幂 优化

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

typedef long long LL;
const int maxn = 6, mod = 1e9 + 7;
int op[7] = {0, 4, 5, 6, 1, 2, 3};
int A[maxn][maxn] = {0};
int n, m;

void mul(int c[], int a[], int b[][maxn])
{
    int tmp[maxn] = {0};
    for (int i = 0; i < maxn; ++i)
        for (int k = 0; k < maxn; ++k)
            tmp[i] = (tmp[i] + (LL)a[k] * b[i][k]) % mod;

    memcpy(c, tmp, sizeof tmp);
}

void mul(int c[][maxn], int a[][maxn], int b[][maxn])
{
    int tmp[maxn][maxn] = {0};
    for (int i = 0; i < maxn; ++i)
        for (int j = 0; j < maxn; ++j)
            for (int k = 0; k < maxn; ++k)
                tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % mod;

    memcpy(c, tmp, sizeof tmp);
}

int main()
{
    cin >> n;
    for (int i = 0; i < 6; ++i)
        for (int j = 0; j < 6; ++j)
            A[i][j] = 4; // 初始化系数为4

    cin >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        A[op[a] - 1][b - 1] = 0;
        A[op[b] - 1][a - 1] = 0;
    }

    n--;
    int F1[maxn] = {4, 4, 4, 4, 4, 4}; // 初始向量,下标从0~n-1

    while (n)
    {
        if (n & 1)
            mul(F1, F1, A);
        mul(A, A, A);
        n >>= 1;
    }

    int ans = 0;
    for (int i = 0; i < 6; ++i)
        ans = ((LL)ans + F1[i]) % mod;
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1078. 旅游规划

树形DP 树的直径

法一:换根DP

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

const int maxn = 200010;
int first[maxn], second[maxn], up[maxn], p[maxn]; // 该点向下走的最大长度、次大长度、该点向上走的最大长度、该点向下最大长度上的下一个点
int h[maxn], e[maxn * 2], ne[maxn * 2], idx;
int n, lp; // 结点数 最长路径

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

void dfs_down(int root, int father) // 返回该点到叶子的最大长度 用于求直径 自下往上
{
    for (int i = h[root]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father)
            continue;
        dfs_down(j, root); // 先递归到下层,算出下方最大长度
        int d = first[j] + 1;
        if (d > first[root]) // 更新根结点的最大与次大
        {
            second[root] = first[root];
            first[root] = d;
            p[root] = j; // 记录该点为向下最大路径上的点
        }
        else if (d > second[root])
            second[root] = d;
    }

    int ans = first[root] + second[root];
    if (ans > lp)
        lp = ans;
}

void dfs_up(int root, int father) // 算出每个结点向上走的最大路径长 自上而下
{
    for (int i = h[root]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father)
            continue;
        up[j] = up[root] + 1;
        if (p[root] == j)
            up[j] = max(up[j], second[root] + 1);
        else
            up[j] = max(up[j], first[root] + 1);
        dfs_up(j, root); // 向下一层
    }
}

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

    cin >> n;
    for (int i = 0; i < n - 1; ++i) // n个结点n-1条边
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs_down(0, -1); // 规定0为根
    dfs_up(0, -1);
    // printf("lp = %d\n", lp);
    for (int i = 0; i < n; ++i)
    {
        int d[3] = {first[i], second[i], up[i]};
        sort(d, d + 3); // 取最大的两个
        if (d[1] + d[2] == lp)
            printf("%d\n", i);
    }

    return 0;
}

法二

// 找到直径上的点,标记他们向下走前二长的路径经过的点
#include <iostream>
#include <cstring>
using namespace std;

const int N = 2 * 100010, M = 2 * N;

int n;
int d1[N], d2[N];
int h[N], e[M], ne[M], idx, ans;
bool st[N]; // 标记直径上的点

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

int dfs1(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father)
            continue;
        int d = dfs1(j, u) + 1;
        if (d > d1[u])
        {
            d2[u] = d1[u];
            d1[u] = d;
        }
        else if (d > d2[u])
            d2[u] = d;
    }
    ans = max(ans, d1[u] + d2[u]);
    return d1[u];
}

void dfs2(int u)
{
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (d1[u] == d1[j] + 1)
            dfs2(j);
    }
}

void dfs3(int u)
{
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (d2[u] == d1[j] + 1)
            dfs2(j);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs1(0, -1);
    for (int i = 0; i < n; ++i)
    {
        if (d1[i] + d2[i] == ans) // 树的最高点
        {
            dfs2(i);
            dfs3(i);
        }
    }

    for (int i = 0; i < n; ++i)
        if (st[i])
            printf("%d\n", i);

    return 0;
}


活动打卡代码 AcWing 1070. 括号配对

区间DP

// 区间DP 求最小值 O(N^3)
// 状态计算 枚举顺序?

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

const int maxn = 110, INF = 0x3f3f3f3f; // 要求最小值 初始化为无穷大
char s[maxn];
int f[maxn][maxn]; // 在l r闭区间内最少要加几个括号使整体合法

bool match(int l, int r)
{
    if ((l == '(' && r == ')') || l == '[' && r == ']')
        return true;
    return false;
}

int main()
{
    scanf("%s", s);
    int n = strlen(s);

    for (int i = 0; i < n; i++)
        f[i][i] = 1;                   // 长度为1时要特判
    for (int len = 2; len <= n; ++len) // 从长度为2开始
    {
        for (int l = 0; l + len - 1 < n; ++l)
        {
            int r = l + len - 1;
            f[l][r] = INF; // 初始化为无穷大
            if (match(s[l], s[r]))
                f[l][r] = f[l + 1][r - 1];
            f[l][r] = min(f[l][r], min(f[l][r - 1], f[l + 1][r]) + 1);

            for (int k = l; k < r; ++k)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]); // AB情况
        }
    }

    printf("%d\n", f[0][n - 1]);

    return 0;
}


活动打卡代码 AcWing 1226. 包子凑数

完全背包 裴蜀定理

// 裴蜀定理:任意两个数的组合必定是他们gcd的倍数
// 若一些数的gcd是d,则他们的组合一定是d的倍数。若d!=1,则必有无限个无法被表示

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

const int maxn = 110;
int w[maxn], n;
bool f[maxn][10000]; // 能否从前i中选出体积为j
// 数据范围<=100 最大不能表示的数为 (100-1)*(99-1)-1 不超过10000

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

int main()
{
    cin >> n;
    int d = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i];
        d = gcd(d, w[i]); // 求n个数的gcd
    }

    if (d != 1) // 多个整数互质,不一定两两互质 6 10 15
        puts("INF");
    else
    {
        f[0][0] = true;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= 10000; ++j)
                f[i][j] = f[i - 1][j] || (j >= w[i] ? f[i][j - w[i]] : false);

        int cnt = 0;
        for (int i = 0; i <= 10000; ++i)
            if (!f[n][i])
                cnt++;
        cout << cnt << endl;
    }

    return 0;
}



快速幂

#include <iostream>
using namespace std;

typedef long long LL;

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

int qmi(int a, int k, int m)
{
    int res = 1;
    while (k)
    {
        if (k & 1)
            res = (LL)res * a % m;
        a = (LL)a * a % m;
        k >>= 1;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, p;
        cin >> a >> p;
        // if (gcd(a, p) == 1) // 存在逆元的充要条件是a p互质
        if (a % p) // 又因为p一定是质数,故根据性质,只要a不是p的倍数,a p一定互质
            printf("%d\n", qmi(a, p - 2, p));
        else
            puts("impossible");
    }

    return 0;
}