题目1

题目链接
题目大意：
n个黑球，m个红球，将这些球分成若干堆，要求：
1、每一堆都有至少一个黑球；
2、每一堆都有至少一个红球；
3、每一堆的黑球和红球数量差不超过d；

输入：
第一行是整数 𝑡，表示t个样例 (1≤𝑡≤1000)
每个样例一行，整数 𝑟, 𝑏, and 𝑑 (1≤𝑟,𝑏≤1e9; 0≤𝑑≤1e9)

输出：
如果可以按照要求拆分，则输出YES；如果无法拆分，则输出NO；

Examples
input
4
1 1 0
2 7 3
6 1 4
5 4 0

output
YES
YES
NO
NO

题目解析：
用贪心的思想，在满足1和2的情况下，球堆的数量越多，那么3更容易满足；
那么就可以直接分出min(n, m)堆，然后剩下的球再平分到这些球堆中，最后再计算是否满足条件3。
为了方便计算，我们可以假设n<m；（如果n>m则进行调换，红黑色并不影响）
那么会有m堆，每堆最多有球(n+m-1)/m个，这样就可以快速计算是否满足条件3。

class Solution {
    static const int N = 105;
public:
    int n, m, k, t;
public:
    void solve() {
        cin >> t;
        while (t--) {
            cin >> n >> m >> k;
            if (n < m) {
                swap(n, m);
            }
            cout << (((n + m - 1) / m - 1) <= k ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目2

题目链接
题目大意：
在一个n x m的网格中，小明现在站在[1, 1]的位置，想要走到[n, m]；
当小明在位置[x, y]时，每次可以选择：
走到[x, y+1]，花费x的代价；
走到[x+1,y]，花费y的代价；
问，小明能否走到位置[n, m]并花费的代价和刚好是k；

输入：
第一行是整数𝑡，表示样例数 (1≤𝑡≤100)
每个样例一行，整数 𝑛, 𝑚, and 𝑘 (1≤𝑛,𝑚≤100; 0≤𝑘≤10000)

输出：
每个样例一行，可以则输出YES；不可以则输出NO；

Examples
input
6
1 1 0
2 2 2
2 2 3
2 2 4
1 4 3
100 100 10000

output
YES
NO
YES
NO
YES
NO

题目解析：
对于一个4x4的格子，我们有随便选择一种走法
1 0 0 0
2 0 0 0
3 4 5 6
0 0 0 7
这种走法的步伐是：
(1,1) - (2,1) - (3,1) - (3,2) - (3,3) - (3,4) - (4,4)

再随机选择一种走法
1 2 3 4
0 0 0 5
0 0 0 6
0 0 0 7
这种走法的步伐是：
(1,1) - (1,2) - (1,3) - (1,4) - (2,4) - (3,4) - (4,4)

容易知道，第一种的代价是1+1+3+3+3+4，都是步伐组合中数字的一半；
第二种的代价是1+1+1+4+4+4，都是步伐组合中数字的一半；

我们知道步伐的组合，本质就是6次选择，每次选择x=x+1或者y=y+1，一共有C(6,3)种可能；（从6个元素中选择3个元素的可能）
计算几次，发现价格是一样的。

怎么证明呢？
我们用dp[i][j]表示，走到i、j的代价，容易知道dp[i][j+1]=dp[i][j]+i 以及 dp[i+1][j]=dp[i][j]+j，并且在边界情况是唯一解；
那么dp[i+1][j+1]=dp[i][i+1]+j=dp[i][j]+i+j。
我们由dp[1][1]开始，可以递推出来dp[1_100][1100]的价格。

思考🤔：
这里也可以用数学方式去解，但用dp会更直观一些。

class Solution {
    static const int N = 105;
public:
    int n, m, k, t;
    int dp[N][N];
public:
    void solve() {
        cin >> t;
        dp[1][1] = 0;
        for (int i = 2; i < N; ++i) {
            dp[1][i] = dp[1][i - 1] + 1;
            dp[i][1] = dp[i-1][1] + 1;
        }
        for (int i = 2; i < N; ++i) {
            for (int j = 2; j < N; ++j) {
                dp[i][j] = dp[i-1][j] + j;
            }
        }
        while (t--) {
            cin >> n >> m >> k;
            cout << (dp[n][m] == k ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
有n个学生想参加比赛，每个学生都有一个自己的学校u[i]，以及能力强度s[i]；
现在已知，假如主办方决定队伍人数是k人一队，则每个学校会按照能力高低，从高开始组队（k个人一队），如果剩余不足k人，则放弃；
问：当k=1、2、3... k的时候，能参加比赛的人，总的能力强度分别是多少。

输入：
第一行整数t，表示有t个样例（1≤𝑡≤1000）
每个样例第一行是整数 𝑛 (1≤𝑛≤2⋅1e5)
第二行是整数𝑢1,𝑢2,…,𝑢𝑛 (1≤𝑢𝑖≤𝑛)
第三行是𝑠1,𝑠2,…,𝑠𝑛 (1≤𝑠𝑖≤1e9)
输出：
每个样例一行，分别输出k个整数，表示当k=1、2、3... k的时候的总能力强度。

Examples
input
4
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567
6
3 3 3 3 3 3
5 9 6 7 9 7
1
1
3083
output
29 28 26 19 0 0 0
24907 20705 22805 9514 0 0 0 0 0 0
43 43 43 32 38 43
3083

题目解析：
先按照学校分类，然后排期得到每个学校能力从小到大的数据； => 极端情况所有人都是同一个学校，复杂度O（NlogN）。
接下来计算k=1.2.3....n的时候，所有学生的能力值。
对于某个学校（学生人数是count[i]），我们知道最终无法组成队伍的人有count[i]%k，也就是前k个；
那么对于k=t，将所有学校排序后的前(count[i]%t)数字累加起来，就是所有无法参加比赛人之和。

注意：
由于k很多种情况，学校也可能有很多个，这里需要注意实现方式，否则很容易超时。
1、只枚举存在的学校；（不需要从1到n去枚举，这个通过map可以实现）
2、每个学校，在枚举k=1.2.3...n的时候，只需要考虑到k=学校人数即可；（由于所有学校的总人数=n，所以k枚举的总次数=n）

class Solution {
    static const int N =200010;
public:
    int n, m;
    int u[N], s[N];
    lld ans[N], sum[N];
    map<int, vector<lld>> h;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            h.clear();
            for (int i = 0; i < n; ++i) {
                cin >> u[i];
                ans[i+1] = 0;
                sum[i+1] = 0;
            }
            for (int i = 0; i < n; ++i) {
                cin >> s[i];
                sum[u[i]] += s[i];
                h[u[i]].push_back(s[i]);
            }
            
            for (map<int, vector<lld>> ::iterator it = h.begin(); it != h.end(); ++it) {
                sort(it->second.begin(), it->second.end());
                
                vector<lld> tmp;
                tmp.push_back(0);
                for (int i = 1; i <= it->second.size(); ++i) {
                    ans[i] += sum[it->first];
                    tmp.push_back(tmp[i-1] + it->second[i-1]);
                    if (it->second.size()%i) {
                        ans[i] -= tmp[it->second.size() % i];
                    }
                    
                }
            }
            for (int i = 1; i <= n; ++i) {
                cout << ans[i] << " ";
            }
            cout << endl;
        }
    }
}
ac;

题目4

题目链接
题目大意：
给出n个整数的数组a和b，数组a和数组b的乘积和等于a[0]*b[1]+a[2]*b[2]+...+a[n]*b[n]；
可以选择一个区间[x, y]（x<=y)，调转数组a区间[x, y]内整数的顺序，比如说数字1,2,3则调转为3,2,1；
求调转之后，数组a和数组b的最大乘积和。

输入：
第一行是整数n，表示数组长度 (1≤𝑛≤5000)
第二行是n个整数a[1]、a[2]、a[3]... a[n]; (1<=a[i] <= 1e7）；
第二行是n个整数b[1]、b[2]、b[3]... b[n];(1<=b[i] <= 1e7）；

输出：
调转一次区间之后，数组a和数组b的最大乘积和。

Examples
input
5
2 3 2 1 3
1 3 2 4 2

output
29

样例解释：
调转区间[4,5]，a=[2,3,2,3,1]，那么数组a和b的成绩和= 2⋅1+3⋅3+2⋅2+3⋅4+1⋅2=29

题目解析：
先不考虑复杂度，一个直接的做法便是枚举区间，然后计算数字相乘和；
这样的复杂度是O（N^3）；

做一些简单的优化：
将求和的过程拆成三部分，假设revert的区间是[x, y]，那么[1, x)和(y, n]部分是可以预处理的；（前i个数字相乘和、后i个数字相乘和）
问题在于，revert的区间[x, y]如何快速计算？
尝试从[x, y]去推导[x, y+1]和[x-1, y]的数字相乘和，发现都需要O（N）的时间去计算；
后面发现从[x, y]去推导[x-1, y+1]就简单了很多。

那么这个题目可以用O（N^2）的空间，来减少O（N）的时间复杂度，使得时间、空间复杂度都控制在O（N^2），在题目可接受范围内。

注意：
题目的核心在于计算revert(i, j)区间数字相乘和，由于推导的时候每次区间都会+2大小，所以需要推导区间[i, i]和[i, i+1]两次。

class Solution {
    static const int N =5001;
public:
    int n;
    lld a[N], b[N];
    lld sumLeft[N], sumRight[N], sumRevert[N][N];
public:
    void solve() {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
        }
        sumLeft[0] = a[0] * b[0];
        for (int i = 1; i < n; ++i) {
            sumLeft[i] = sumLeft[i - 1] + a[i] * b[i];
        }
        sumRight[n - 1] = a[n - 1] * b[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            sumRight[i] = sumRight[i + 1] + a[i] * b[i];
        }
        for (int i = 0; i < n; ++i) {
            // 推导[i, i]=>[i-1, i+1]
            int left, right;
            sumRevert[i][i] = a[i] * b[i];
            left = i - 1, right = i + 1;
            while (left >= 0 && right < n) {
                sumRevert[left][right] = sumRevert[left + 1][right - 1] + a[left] * b[right] + b[left] * a[right];
                --left;
                ++right;
            }
            left = i, right = i + 1;
            if (right < n) {
                sumRevert[left][right] = a[left] * b[right] + b[left] * a[right];
                while(true) {
                    --left;
                    ++right;
                    if (left < 0 || right >= n) {
                        break;
                    }
                    sumRevert[left][right] = sumRevert[left + 1][right - 1] + a[left] * b[right] + b[left] * a[right];
                }
            }
        }
        lld ans = sumLeft[n - 1];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // revert的区间为[i, j]
                lld tmp = 0;
                if (i > 0) {
                    tmp += sumLeft[i - 1];
                }
                if (j + 1 < n) {
                    tmp += sumRight[j + 1];
                }
                tmp += sumRevert[i][j];
                ans = max(ans, tmp);
            }
        }
        cout << ans << endl;
    }
}
ac;

题目5

题目链接
题目大意：
一棵树有n个节点，每一条边有一个价值，等于两边节点的差的绝对值；
每个节点有两个值l[i]和r[i]，节点的值x[i]需要满足l[i] <= x[i] <= r[i];
现在问，按照要求分配各个节点的值，这棵树所有边的最大的价值是多少。

输入：
第一行是整数t，表示有t个样例 (1≤𝑡≤250).
每个样例第一行是整数 𝑛 (2≤𝑛≤1e5)；
接下来n行，每行两个整数𝑙𝑖 and 𝑟𝑖 (1≤𝑙𝑖≤𝑟𝑖≤1e9).
接下来n-1行，每行两个整数𝑢 and 𝑣，表示u到v有一条边 (1≤𝑢,𝑣≤𝑛, 𝑢≠𝑣)
输出：
每一个样例一行，输出最大的价值数。

Examples
input
3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6
output
7
8
62

样例解释：

题目解析：
只考虑一条边的情况，假设两边的节点取值范围是[L1, R1]和[L2, R2]
可以知道，这条边的价值只有两种情况：(L1 - R2) 或者(R1 - L1）。

对于每一个点，我们存两个值：ans[i][0]表示取节点i的value取最小值的子树价值，ans[i][1]表示取最大值的子树价值。我们从根节点开始遍历这棵树，对于每一个节点u，其ans[u][0]是由多个子树的ans[v][0]+value(u, v)或者ans[v][1]+value(u, v) 组成。

这样只需从根节点1开始dfs整颗树，那么根节点的ans[1][0]或者ans[1][1]就是最大价值。

class Solution {
    static const int N = 200010;
public:
    vector<int> g[N];
    bool vis[N];
    lld val[N][2];
    lld ans[N][2];
    
    void dfs(int u) {
        vis[u] = 1;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (!vis[v]) {
                dfs(v);
                ans[u][0] += max(ans[v][0] + abs(val[v][0] - val[u][0]), ans[v][1] + abs(val[v][1] - val[u][0]));
                ans[u][1] += max(ans[v][0] + abs(val[v][0] - val[u][1]), ans[v][1] + abs(val[v][1] - val[u][1]));
            }
        }
    }
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 1; i <= n; ++i) {
                g[i].clear();
                vis[i] = 0;
                ans[i][0] = ans[i][1] = 0;
            }
            for (int i = 1; i <= n; ++i) {
//                cin >> val[i][0] >> val[i][1];
                scanf("%d%d", &val[i][0], &val[i][1]);
            }
            for (int i = 0; i < n - 1; ++i) {
                int u, v;
//                cin >> u >> v;
                scanf("%d%d", &u, &v);
                g[u].push_back(v);
                g[v].push_back(u);
            }
            dfs(1);
            cout << max(ans[1][0], ans[1][1]) << endl;
        }
    }
}
ac;