程序员进阶之算法练习（八十五）
题目1
题目链接 题目大意： 有n个整数的数组a，现在需要给数组每个元素进行染色，注意： 1、每个元素只能有一个颜色； 2、每个元素都要染色； 每个颜色的收益，等于染该色的元素中最大值减去最小值； 问，染色完所有元素后，最大的收益是多少。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例2行，第一行整数𝑛 (1≤𝑛≤50) 第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤50)
输出： 每个样例一行，输出最大的收益。
Examples input 6 5 1 5 6 3 4 1 5 4 1 6 3 9 6 1 13 9 3 7 2 4 2 2 2 2 5 4 5 2 2 3
output 7 0 11 23 0 5
题目解析： 每个颜色如果只有1个元素，没有收益； 如果有3个元素，生效的只有最小和最大值，所以每个颜色最多染色2个元素； 那么将元素排序，每次选择最小和最大值即可。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
int sum = 0;
for (int i = 0; i < n / 2; ++i) {
sum += a[n - i - 1] - a[i];
}
cout << sum << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目2
题目链接 题目大意： 有n个整数的数组a，现在可以对数组进行操作： 将数组区间[l, r]内的数值乘以-1； 比如说[1,2,3,4,5]，对区间[2, 3]进行操作，则得到[1, -2, -3, 4, 5]； 现在可以进行任意次（包括0次），问最少多少次，才能将数组所有元素的和最大；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例2行，第一行整数𝑛 (1≤𝑛≤2e5) 第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛(-1e9≤𝑎𝑖≤1e9)
输出： 每个样例一行，输出2个整数，第一个整数表示最大的元素和，第二个整数表示最小的操作次数；
Examples input 5 6 -1 7 -4 -2 5 -8 8 -1 0 0 -2 1 0 -3 0 5 2 -1 0 -3 -7 5 0 -17 0 1 0 4 -1 0 -2 -1
output 27 3 7 2 13 1 18 1 4 1
题目解析： 要让结果最大，所有数字都应该变成非负数，最大和就是所有数字的绝对值之和； 关键在于如何让次数尽可能少，我们对题目进行简化，在考虑正负数时，数值大小没有意义，可以将所有数字简化成：-1、0、1； 由于操作的时候，可以选择一个区间进行操作，那么[-1、-1]和 [1, 1]这样的区间，可以简化成[-1]和[1]；（0也是同样道理） 那么数组就变成了由[-1, 0, 1]组成的； 同样简化思路，由于[-1, 0, -1]也同样看成一个[-1]，于是数组就变成了-1和1交错的情况； 假设简化后的数组长度为m，结果就是m/2;（-1都是单独的，直接消除）
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const lld N = 201010;
int a[N];
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n, ans = 0;
cin >> n;
for (lld i = 0; i < n; ++i) {
cin >> a[i];
ans += abs(a[i]);
}
lld sum = 0;
lld cur = 0, last = 0;
while (cur < n && a[cur] >= 0) {
++cur;
}
if (cur < n) {
++sum;
last = a[cur];
}
++cur;
while (cur < n) {
if (a[cur] != 0) {
if (a[cur] * last < 0) {
last = a[cur];
++sum;
}
}
++cur;
}
cout << ans << " " << (sum + 1) / 2 << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目3
题目链接 题目大意： 有如图的二叉树； 数字从1到n有且只有一条路径，求这个路径上的整数和。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行整数𝑛 (1≤𝑛≤1e16)
输出： 每个样例一行，输出路径上的累加和。
Examples input 6 3 10 37 1 10000000000000000 15
output 4 18 71 1 19999999999999980 26
题目解析： 二进制分析思路： 完全二叉树，每次有两个选择，左或者右； 对应到二进制，左边是0，右边是1； 5是101，对应到二进制树就是左+右；
搜索分析思路： 1到12为例，1到12的路径有且仅有1-3-6-12； 将这些数字的二进制写出来： 1 11 110 1101 容易发现二进制的前缀是相同的；
这样不断能去掉n最为后一位二进制数，可得上一位数字，累加即可。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const lld N = 201010;
int a[N];
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n;
cin >> n;
lld ans = 0;
while (n) {
ans += n;
n /= 2;
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目4
题目链接 题目大意： 有n个节点的树，由n-1条边组成； 已知根节点1为最上面节点，其他节点向下成长； 现在有两个苹果，生长在节点x和节点y上面； 苹果成熟后会顺着每个节点的边，朝着远离根节点的方向下落； 如果某个节点是叶子节点，则会从树上落下；
现在有q个询问，每次输入苹果生长节点x和节点y，问苹果落下的位置节点组合（posX，poxY)）的可能性，posX和posY分别表示节点X和节点Y苹果落下的节点位置；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例，第一行整数𝑛 (1≤𝑛≤2e5) 接下来有n-1行表示相连边，每行两个整数 𝑢𝑖 and 𝑣𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛 , 𝑢𝑖≠𝑣𝑖 ) 然后是整数𝑞，表示q个询问 (1≤𝑞≤2⋅1e5) 接下来是q行整数，每行有整数 𝑥𝑖 and 𝑦𝑖 ，表示苹果生长节点 (1≤𝑥𝑖,𝑦𝑖≤𝑛 )
输出： 每个样例q行，输出每次询问的位置组合数；
Examples input 2 5 1 2 3 4 5 3 3 2 4 3 4 5 1 4 4 1 3 3 1 2 1 3 3 1 1 2 3 3 1
output 2 2 1 4 4 1 2
题目解析： 题目看起来复杂，其实就是算每个节点的子树中，有多少个叶子节点，用数组cnt[i]来表示； 由于苹果x和苹果y是相互独立的，最终答案就是cnt[x] ✖️cnt[y]；
快速求cnt[i]可以用dfs，对于每个节点，统计其子节点的叶子节点数量，然后累加即可。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const lld N = 201010;
vector<int> g[N];
lld cnt[N];
lld dfs(int u, int f) {
int sub = 0;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (v == f) continue;;
sub += dfs(v, u);
}
cnt[u] = sub == 0 ? 1 : sub;
return cnt[u];
}
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n;
cin >> n;
for (int i = 1; i <= n; ++i) {
g[i].clear();
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << cnt[x] * cnt[y] << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目5
题目链接 题目大意： 有n个整数的数组，初始状态元素都是0； 有m个区间[ 𝑙𝑖,𝑟𝑖]，我们定义一个区间是beautiful的，只要这个区间内，数字1的数量严格大于数字0的数量； 有q个操作依次执行，每次操作是将q𝑖位置的元素变为1； 现在想知道，当第几次操作后，m个区间中将出现至少1个beautiful的区间。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例，第一行整数𝑛 and 𝑚 (1≤𝑚≤𝑛≤1e5 ) 接下来有m行，每行两个整数表示区间 𝑙𝑖 and 𝑟𝑖 (1≤𝑙𝑖≤𝑟𝑖≤𝑛 ) 然后是整数𝑞，表示q个操作 (1≤𝑞≤ n) 接下来是q行整数，每行有整数 𝑥 (1≤𝑥≤𝑛)
输出： 每个样例1行，输出该次操作后，m个区间中将出现至少1个beautiful的区间。
Examples input 6 5 5 1 2 4 5 1 5 1 3 2 4 5 5 3 1 2 4 4 2 1 1 4 4 2 2 3 5 2 1 5 1 5 4 2 1 3 4 5 2 1 5 1 3 5 4 1 2 3 5 5 5 1 5 1 5 1 5 1 5 1 4 3 1 4 3 3 2 2 2 1 3 3 2 3 1
output 3 -1 3 3 3 1
题目解析： 假设不考虑复杂度，对于每次操作，遍历每个区间得到区间内整数1的数量，判断是否有解； 总的复杂度是操作次数q ✖️区间数量m ✖️区间长度n，远远超过题目要求。 分析优化空间，我们发现区间[l, r]总是比[l, r+1]更优，那么所有区间可以拆分为，左右区间节点各不相同的区间（只要有一个节点相同，则存在更优解）； 操作同样如此，对于某个位置的重复操作是无意义的，操作可以优化为无重复位置的操作； 但是，上述两个操作都属于常数级别优化，对于特定样例优化空间很小。
当我们考虑最坏情况，即结果是否有解的时候，我们可以把所有操作都执行一遍，得到一个0/1数组，此时再去判断是否存在beautiful区间； 方式有很多，这里可以用前n项和，即sum[i]表示位置i前面所有元素的1数量，这样区间[x, y]就可以用sum[y] - sum[x]快速计算得到区间1的数量，从而很快判断区间是否为beautiful； 这样就可以用O(N)的复杂度，快速判断； 接着就可以用二分的方式，来处理1-q个操作的情况。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const lld N = 102010;
pair<int, int> seg[N];
int a[N];
int b[N];
int sum[N];
bool check(int n, int m, int len) {
for (int i = 0; i <= n; ++i) {
b[i] = sum[i] = 0;
}
for (int i = 0; i < len; ++i) {
b[a[i]] = 1;
}
for (int i = 1; i <= n; ++i) {
sum[i] += sum[i - 1] + b[i];
}
for (int i = 0; i < m; ++i) {
int x = seg[i].first, y = seg[i].second;
if ((sum[y] - sum[x - 1]) * 2 > (y - x + 1)) {
return true;
}
}
return false;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) cin >> seg[i].first >> seg[i].second;
int q;
cin >> q;
for (int i = 0; i < q; ++i) cin >> a[i];
if (!check(n, m, q)) {
cout << -1 << endl;
}
else {
int left = 1, right = q;
int ans = right;
while (left < right) {
int mid = (left + right) / 2;
if (check(n, m, mid)) {
ans = mid;
right = mid;
}
else {
left = mid + 1;
}
}
cout << ans << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目6
题目链接 题目大意： 有棵树初始时只有根节点1，该节点的值为1； 现在可以往树上增加节点，每个节点新增时序号是当前树上最大节点的加1，节点的值为1或者-1； 现在想知道，随着不断增加节点，对于某两个节点u和v之间，是否存在路径，使得经过的节点和为k；（每个节点只能经过一次，集合可以为0）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例，第一行整数𝑛 (1≤𝑛≤2e5 ) 接下来有n行，每行有两种情况： 情况1，由符号'+'和两个整数v x组成，表示增加一个新节点v，值为x (x为-1或者1） 情况2，由符号'?'和三个整数u v k组成，表示询问u到v的路径中，是否存在某一个段路径的值为k；（u=1，v保证是存在节点）
输出： 对于每一个询问，如果存在则输出YES，如果不存在则输出NO；
Examples input
1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0output NO YES NO YES YES YES
题目解析： 先简化题目思考，假如不是树，而是线段； 这个题目在考虑是否存在区间和为k时，其实就询问这条线段中，最大和是多少、最小和是多少； 因为最大和就是每个节点的累加值，而节点的值为1和-1，证明能覆盖1、2、3、4、5、、、、MaxSum整个区间；
于是题目简化为，在每新增一个节点时，我们计算以这个节点结尾时，路径的最大和dpMax、最小和dpMin； 同时我们维护一个ansMax和ansMin表示从根节点1到该节点路径上，所有节点的dpMax的最大值、dpMin的最小值； 假设n是新增节点序号，fat是新增节点的父节点序号，那么有状态转移方程： dpMax[n] = max(0, dpMax[fat]) + a[n]; dpMin[n] = min(0, dpMin[fat]) + a[n]; ansMax[n] = max(dpMax[n], ansMax[fat]); ansMin[n] = min(dpMin[n], ansMin[fat]);
扩展思考： hard version是去掉u=1的限制，题目就复杂很多。 通过lca算法找到u和v的共同祖先，在这条路径上，按照上述思路再处理一次，但是这样的复杂度达到了O(N)级别。 没有太好的优化思路了。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const lld N = 201010;
static const int inf = 1e9;
vector<int> g[N];
int dpMax[N], dpMin[N];
int ansMax[N], ansMin[N];
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n = 1;
a[1] = dpMax[1] = dpMin[1] = 1;
ansMax[1] = ansMin[1] = 1;
int tmp;
cin >> tmp;
while (tmp--) {
char c[10];
cin >> c;
if (c[0] == '+') {
int fat;
++n;
cin >> fat >> a[n];
dpMax[n] = max(0, dpMax[fat]) + a[n];
dpMin[n] = min(0, dpMin[fat]) + a[n];
ansMax[n] = max(dpMax[n], ansMax[fat]);
ansMin[n] = min(dpMin[n], ansMin[fat]);
}
else {
int u, v, sum;
cin >> u >> v >> sum;
if ((ansMin[v] <= sum && sum <= ansMax[v]) || sum == 0) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}