C++ 代码

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

const int N = 5e4 + 10;

int p[N], d[N];//d[x]表示：x到父节点的距离(经路径压缩后才为到root的距离)

int find(int x)
{
    if (p[x] != x)
    {
        int t = p[x];
        p[x] = find(p[x]);
        d[x] += d[t];//经过路径压缩后，p[t]一定为root，因此d[t]表示为父节点到root的距离
    }
    return p[x];
}

int main()
{
    int res = 0;
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++)p[i] = i;
    while (k--)
    {
        int D, x, y; cin >> D >> x >> y;
        int px = find(x), py = find(y);
        if (x > n || y > n) { res++; continue; }
        if (D == 2 && x == y) { res++; continue; }//不加continue就会多计数

        if (px != py)
        {
            if (D == 1)//同类合并
            {
                d[px] += d[y] - d[x];
                p[px] = py;
            }
            else if (D == 2)//捕食合并
            {
                d[px] += -1 + d[y] - d[x];
                p[px] = py;
            }
        }
        else
        {
            if (D == 1 && (d[x] - d[y]) % 3 != 0)res++;
            if (D == 2 && (d[x] + 1 - d[y]) % 3 != 0)res++;
        }
    }
    cout << res;
}

int main()
{
    //函数的凹凸性质可以使用打表制作图像，或者求导判断

    //三分本质：每次消去不可能存在正确答案的区间

    int l = 0, r = 3.14159265 / 2;//取值范围
    //浮点型凹函数
    while (r - l > 1e-7)
    {
        int lmid = l + (r - l) / 3.0, rmid = r - (r - l) / 3.0;
        if (f(lmid) > f(rmid))l = lmid;
        else r = rmid;
    }
    //浮点型凸函数
    while (r - l > 1e-7)
    {
        int lmid = l + (r - l) / 3.0, rmid = r - (r - l) / 3.0;
        if (f(lmid) < f(rmid))l = lmid;//>改为<
        else r = rmid;
    }
    //整型凹函数
    while (l < r)
    {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (f(lmid) > f(rmid))l = lmid + 1;
        else r = rmid - 1;
    }
    //整型凸函数
    while (l < r)
    {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (f(lmid) < f(rmid))l = lmid + 1;
        else r = rmid - 1;
    }
}

C++ 代码

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

const int N = 1e6+10;
int n;
int num[11];

int calc(int l, int r)
{
    int res = 0;
    for (int i = l; i <= r; i++)res = res * 10 + num[i];
    return res;
}

int main()
{
    int cnt = 0;
    for (int i = 1; i <= 9; i++)num[i] = i;
     cin >> n;

     do
     {
         //枚举中间区间（分为三段，枚举出中间段，其余两段自然可得）
         for (int i = 2; i <= 8; i++)
             for (int j = i; j <= 8; j++)
             {
                 int a = calc(1, i - 1);
                 int b = calc(i, j);
                 int c = calc(j + 1, 9);
                 // 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
                 if (c * (n - a) == b)cnt++;
             }
     } while (next_permutation(num+1,num+10));

     cout <<cnt;
}


/*

next_permutation函数
    组合数学中经常用到排列，这里介绍一个计算序列全排列的函数：next_permutation（start,end）
    ，和prev_permutation（start,end）。这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，
    后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后
    ，严格来讲，就是对于当前序列pn，他的下一个序列pn+1满足：不存在另外的序列pm，使pn<pm<pn+1.

    next_permutation(首地址，首地址+长度)
    作用:将区间内数组修改为下一个全排列（按照字典序），如果成功return 1 如果当前是最后一个则return 0
    因为返回的是下一个，所以一般配合do while使用
*/

C++ 代码

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

const int N = 6e3 + 10;

//h[N]内部存的是idx，e[N], ne[N]是用于描述idx的，（idx，e[N], ne[N]共同组成节点）
//但h[N]的下标存的是题目中的点
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

//添加有向边 u->v
void add(int u, int v)//因为只有上司有多位下属，而下属只有一位上司，因此邻接表的方向是父节点->子节点
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        dfs(v);//计算方向为：自下而上，因此必须先计算好子节点，然后以此计算父节点

        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }

}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &happy[i]);
    memset(h, -1, sizeof(h));

    for (int i = 0; i < n - 1; i++)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = 1;
    }

    int root = 1;//注意：此为题中的节点（1~N）而不是idx
    while (has_fa[root])root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}

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

const int N = 6e3 + 10;

//e[N], ne[N]是用于描述idx的，而h[N]内部存的就是idx
//但h[N]的下标存的是题目中的点
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int u, int v)//添加有向边 u->v
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        dfs(v);

        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }

}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &happy[i]);
    memset(h, -1, sizeof(h));

    for (int i = 0; i < n - 1; i++)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(b,a);
        has_fa[a] = 1;
    }

    int root = 1;
    while (has_fa[root])root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}

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

const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

int f[N];

int main()
{
    int n; cin >> n;
    f[0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % MOD;
    cout << f[n];
}

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

const int N = 1e3 + 10;
char a[N][15], b[15];
int f[N][N];

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

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

    for (int j = 1; j <= m; j++)
    {
        scanf("%s", b + 1); int x; cin >> x;
        int cnt = 0;


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

        for (int k = 1; k <= n; k++)
        {
            int la = strlen(a[k]+1);
            int lb = strlen(b+1);
                for (int i = 1; i <= la; i++)
                    for (int j = 1; j <= lb; j++)
                    {
                        f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                        if (a[k][i] == b[j])f[i][j] = min(f[i][j], f[i - 1][j - 1]);
                        else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
                    }
                if (f[la][lb] <= x)cnt++;
        }
        cout << cnt << endl;
    }

}

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

const int N = 1e3 + 10;
char a[N], b[N];
int f[N][N];

int main()
{
    int n, m; 
    cin >> n; scanf("%s", a + 1);
    cin >> m; scanf("%s", b + 1);

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j])f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m];
}

C++ 代码

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

const int N = 1e3 + 10;
int f[N][N];
char a[N], b[N];

int main()
{
    int n, m; cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j])f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }

    cout << f[n][m];
}

**[//]: # (打卡模板，上面预览按钮可以展示预览效果 ^^)

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

const int N = 1e3 + 10;
int f[N][N];
char a[N], b[N];

int main()
{
    int n, m; cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j])f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m];
}

**