购买两块巧克力

传送门
暴力枚举下

C++ 代码

class Solution {
public:
    int buyChoco(vector<int>& prices, int money) {
        sort(prices.begin(), prices.end());
        int cnt = prices[0] + prices[1];
        if (cnt > money) return money;
        else return money - cnt;
    }
};

字符串中的额外字符

传送门
设f[i]表示0 到i - 1字符的字符最少个数
我们会发现只要存在dictionary 中的单词，我们就可以推出f[i] = min(f[s], f[i]), s是上一个状态
否则 f[i] = f[i - 1] + 1

C++ 代码

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<int> f(n + 1, 0);
        unordered_set<string> st;
        for (auto d : dictionary) st.insert(d);
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = f[i - 1] + 1;
            for (int j = 1; j <= i; j ++ )
            {
                string tmp = s.substr(j - 1, i - j + 1);
                if (st.count(tmp)) f[i] = min(f[i], f[j - 1]);
            }
        }
        return f[n];
    }
};

一个小组的最大实力值

传送门
设f[i][0]代表前i项的最大，f[i][1]代表前i项最小
f[i][0] = max({f[i - 1][0], f[i][0] * nums[i - 1], f[i][1] * nums[i - 1], nums[i]);
f[i][1] = min({f[i - 1][1], f[i][0] * nums[i - 1], f[i][1] * nums[i - 1], nums[i]);

C++ 代码

class Solution {
public:
    long long maxStrength(vector<int>& nums) {
        int n = nums.size();
        long long f[n + 1][2];
        f[1][0] = nums[0]; //最大
        f[1][1] = nums[0]; //最小
        for (int i = 2; i <= n; i ++ )
        {
            f[i][0] = max(f[i - 1][0], 
            max(f[i - 1][0] * nums[i - 1], 
            max(f[i - 1][1] * nums[i - 1], 1LL * nums[i - 1])));

            f[i][1] = min(f[i - 1][1], 
            min(f[i - 1][0] * nums[i - 1], 
            min(f[i - 1][1] * nums[i - 1], 1LL * nums[i - 1])));
        }
        return f[n][0];
    }
};

最大公约数遍历

传送门
质因数分解 + 并查集

C++ 代码

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        unordered_map<int,int> mp;
        int n = nums.size(), res = 0;
        if (n == 1) return true;
        vector<int> p(n + 1, 0), f(n + 1, 0);
        function<int (int)> find = [&](int x) {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        };
        for (int i = 0; i < n; i ++ ) p[i] = i, f[i] = 1;
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 2; j <= nums[i] / j; j ++ )
            {
                if (nums[i] % j == 0)
                {
                    if (mp.count(j))
                    {
                        int a = find(i), b = find(mp[j]);
                        if (a != b)
                        {
                            f[b] += f[a];
                            p[a] = b;
                            if (res < f[b]) res = f[b];
                        }
                    }
                    else mp[j] = find(i);
                    while (nums[i] % j == 0) nums[i] /= j;
                }
            }
            if (nums[i] > 1)
            {
                if (mp.count(nums[i]))
                {
                    int a = find(i), b = find(mp[nums[i]]);
                    if (a != b)
                    {
                        f[b] += f[a];
                        p[a] = b;
                        if (res < f[b]) res = f[b];
                    }
                }
                else mp[nums[i]] = find(i);
            }
        }
        return res == n;
    }
};

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, k;
char g[N][N], s[N][N];
int len;
inline int power (int a,int b) {
    int ans = 1;
    while (b--) ans *= a;
    return ans;
}
inline void dfs(int x, int y, int num, int dep, int type)
{
    if (type == 1)
    {
        for (int i = x; i <= x + num - 1; i ++ )
            for (int j = y; j <= y + num - 1; j ++ )
                s[i][j] = '*';
        return;
    }
    if (dep == 1)
    {
        for (int i = x; i <= x + num - 1; i ++ )
            for (int j = y; j <= y + num - 1; j ++ )
                s[i][j] = g[i - x][j - y];
        return;
    }
    int cnt = num / n;
    for (int i = x; i <= x + num - 1; i += cnt )
        for (int j = y; j <= y + num - 1; j += cnt )
            dfs(i, j, cnt, dep - 1, g[(i - x) / cnt][(j - y) / cnt] == '*');
}
inline void solve()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> g[i][j];
    len = power(n, k);
    dfs(1, 1, len, k, 0);
    for (int i = 1; i <= len; i ++ )
        for (int j = 1; j <= len; j ++ )
            cout << s[i][j] << ((j == len) ? "\n" : "");
}
int main()
{
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

暴力枚举

极值元素的拆分相邻元素的积一定异号
接下来看代码

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], b[N];
inline void solve()
{
    int n, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i < n; i ++ ) b[i] = a[i + 1] - a[i];
    for (int i = 1; i < n; i ++ )
        if (b[i] * b[i + 1] < 0 && i + 1 < n)
            res ++;
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

暴力枚举

好气，呜呜呜呜呜呜呜
后面才跳出囚牢, 只是模拟而已

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5050;
int a[N], b[N], res[N];
inline void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ )
    {
        memset(b, 0, sizeof b);
        int maxv = 0, cnt = 0;
        for (int j = i; j <= n; j ++ )
        {
            b[a[j]] ++;
            int t = b[a[j]];
            if (t > maxv || t == maxv && cnt > a[j])
                maxv = t, cnt = a[j];
            res[cnt] ++;
        }
    }
    for (int i = 1; i <= n; i ++ ) cout << res[i] << " ";
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 320;
int h[N], e[N], ne[N], w[N], idx;
int n, m, f[N][N];
inline void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        for (int k = m; k >= 0; k -- )
            for (int s = 1; s <= k; s ++ )
                if (f[u][k] < f[u][k - s] + f[j][s])
                    f[u][k] = f[u][k - s] + f[j][s];
    }
    for (int i = m; i >= 1; i -- ) 
        f[u][i]  = f[u][i - 1] + w[u];
}
inline void solve()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        e[idx] = i, ne[idx] = h[a], h[a] = idx ++;
        w[i] = b;
    }
    m ++;
    dfs(0);
    cout << f[0][m] << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

分组背包的树形结构

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 320;
int h[N], e[N], ne[N], w[N], idx;
int n, m, f[N][N];
inline void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        for (int k = m; k >= 0; k -- )
            for (int s = 1; s <= k; s ++ )
                if (f[u][k] < f[u][k - s] + f[j][s])
                    f[u][k] = f[u][k - s] + f[j][s];
    }
    for (int i = m; i >= 1; i -- ) 
        f[u][i]  = f[u][i - 1] + w[u];
}
inline void solve()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        e[idx] = i, ne[idx] = h[a], h[a] = idx ++;
        w[i] = b;
    }
    m ++;
    dfs(0);
    cout << f[0][m] << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

//这里填你的代码^^
#include <iostream>
#define endl '\n'
using namespace std;
const int N = 1001;
int primes[N], cnt;
int phi[N], a[N], res[N];
bool st[N];
inline void get(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] * i <= x; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * phi[primes[j]];
        }
    }
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    int t = 1, maxv = 0;
    cin >> t;
    for (int i = 1; i <= t; i ++ )
    {
        cin >> a[i];
        if (maxv < a[i]) maxv = a[i];
    }
    get(maxv);
    res[0] = 1;
    for (int i = 1; i <= maxv; i ++ ) res[i] = res[i - 1] + (phi[i] << 1);
    for (int i = 1; i <= t; i ++ )
    cout << i << " " << a[i] << " " << res[a[i]] << endl;
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

欧拉函数

根据题目意思，需要用到欧拉函数， 接下来枚举就行

C++ 代码

#include <iostream>
#define endl '\n'
using namespace std;
const int N = 1001;
int primes[N], cnt;
int phi[N], a[N], res[N];
bool st[N];
inline void get(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] * i <= x; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * phi[primes[j]];
        }
    }
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    int t = 1, maxv = 0;
    cin >> t;
    for (int i = 1; i <= t; i ++ )
    {
        cin >> a[i];
        if (maxv < a[i]) maxv = a[i];
    }
    get(maxv);
    res[0] = 1;
    for (int i = 1; i <= maxv; i ++ ) res[i] = res[i - 1] + (phi[i] << 1);
    for (int i = 1; i <= t; i ++ )
    cout << i << " " << a[i] << " " << res[a[i]] << endl;
    return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
int h[N], e[N], ne[N], w[N], idx;
bool father[N];
int f[N][2];
inline void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline void dfs(int u)
{
    f[u][1] = w[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        int cnt = f[j][0] > f[j][1] ? f[j][0] : f[j][1];
        f[u][0] += cnt;
        f[u][1] += f[j][0];
    }
}
inline void solve()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    for (int i = 1; i < n; i ++ )
    {
        int l, k;
        cin >> l >> k;
        father[l] = true;
        add(k, l);
    }
    int root = 1;
    while (father[root]) root ++;
    dfs(root);
    int cnt = f[root][0] > f[root][1] ? f[root][0] : f[root][1];
    cout << cnt << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

作者：navystar
链接：https://www.acwing.com/solution/content/189943/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

树形状态转移

定义f[i][1]为当前节点已选的快乐指数总和最大， f[i][0]为不选当前节点的快乐指数总和最大
我们会发现f[i][1] 可以由f[s][0]推出
f[i][0] 可以由f[s][1], f[s][0]推出
接下来枚举

C++ 代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
int h[N], e[N], ne[N], w[N], idx;
bool father[N];
int f[N][2];
inline void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline void dfs(int u)
{
    f[u][1] = w[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        int cnt = f[j][0] > f[j][1] ? f[j][0] : f[j][1];
        f[u][0] += cnt;
        f[u][1] += f[j][0];
    }
}
inline void solve()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    for (int i = 1; i < n; i ++ )
    {
        int l, k;
        cin >> l >> k;
        father[l] = true;
        add(k, l);
    }
    int root = 1;
    while (father[root]) root ++;
    dfs(root);
    int cnt = f[root][0] > f[root][1] ? f[root][0] : f[root][1];
    cout << cnt << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}