比赛链接：Here
AcWing 3660. 最短时间
比较四个方向和 ((r,c)) 的距离
void solve() {
ll n, m, r, c;
cin >> n >> m >> r >> c;
cout << max(max(r + c - 2, r + m - 1 - c), max(n + c - r - 1, n + m - r - c)) << "
";
}
AcWing 3661. 重置数列
枚举相同值即可
void solve() {
int n, k; cin >> n >> k;
bool f[110] = {false};
vector<int>a(n + 1);
for (int i = 1; i <= n; ++i)cin >> a[i], f[a[i]] = true;
int cnt = n;
for (int i = 1; i <= 100; ++i) {
if (f[i]) {
int t = 0;
for (int j = 1; j <= n; ++j) {
if (a[j] == i)continue;
else t++, j = j + k - 1;
}
cnt = min(cnt, t);
}
}
cout << cnt << "
";
}
AcWing 3662. 最大上升子序列和
(离散化,树状数组) (O(nlogn))
众所周知，与求上升子序列相关的优化一般有两种：
- 单调栈 & 二分优化
- 线段树 | 树状数组 | 平衡树等数据结构优化
这里求的是上升子序列中所有元素的和的最大值，不太好用单调栈+二分，故想到用树状数组。
可能有些人对数据结构优化最长上升子序列不太了解，这里说一下思路。
先考虑暴力DP：设 (f[i]) 表示在 (a_1∼a_i) 中，且以 (a_i) 结尾的所有上升子序列中，元素和的最大值。
转移方程：
[f[i] = a_i + max_{0le j<i,a_j<a_i}f[j]
]
将序列 (a) 离散化，考虑优化对 (f_i) 的转移。
设 (g_x) 表示所有 (j < i) 且 (a_j = x) 的 (f_j) 的最大值，那么 (max_{0le j<i,a_j<a_i}f[j]) 就等于 (max_{x <a_i}g_x) ，注意到这项是 (g) 的一个前缀最大值，这恰可以用树状数组动态维护。
具体可见代码。
时间复杂度：
离散化 (O(nlogn))，树状数组 (O(nlogn))，故总复杂度为 (O(nlogn))。
using ll = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, a[N], diff[N], sz; // 离散化
// 树状数组
ll f[N], res;
inline void add(int x, const ll val) {for (; x <= sz; x += x & -x) f[x] = max(f[x], val);}
inline ll query(int x) {
ll res = 0;
for (; x; x &= x - 1)res = max(res, f[x]);
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i], diff[i - 1] = a[i];
sort(diff, diff + n);
sz = unique(diff, diff + n) - diff;
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(diff, diff + sz, a[i]) - diff + 1;
ll t = diff[a[i] - 1] + query(a[i] - 1);
res = max(res, t), add(a[i], t);
}
cout << res << "
";
}