出题人：\(\text{D}\color{red}\text{eaphetS}\)
#A. [NOIP2012 提高组] 开车旅行
倍增优化 dp。
这题难就难在预处理。
首先预处理出 A 和 B 每个人从一个城市出发的目标是哪个城市。可以用平衡树找一个点的前驱和后继，或者双向链表。我当然选择了最偷懒的 set。(ps:这里如果用 set 的话有可能迭代器一直加或者减导致越界，又懒得判断，索性用了 multiset)
然后预处理出 \(f[i][j][k(0/1)]\) 表示第 \(k\) 个人从第 i 个城市出发走 \(2^j\) 天到达的城市，同时也更新 \(dp[x(0/1)][i][j][k(0/1)]\) 表示第 \(k\) 个人从第 \(i\) 个城市出发走 \(2^j\) 天后第 \(x\) 个人走了多少路程。
最后预处理完暴力跑几遍就行了。
#include <cstdio>
#include <algorithm>
#include <set>
using std::set;
int n, m, s, h[100005], des[100005][2], Min[100005][2], To[100005][22], dis[100005][22][2], tot[2], x;
struct info {
int h, id;
bool operator < (const info a) const {
return h < a.h;
};
};
set<info>box;
set<info>::iterator I;
int ab(int t) {
return t < 0 ? -t : t;
}
void consider(int i, info p) {
int j = p.id;
if ((ab(h[i] - h[j]) < Min[i][0]) || (Min[i][0] == ab(h[i] - h[j]) && h[j] < h[des[i][0]])) {
if ((Min[i][0] < Min[i][1]) || (Min[i][1] == Min[i][0] && h[des[i][0]] < h[des[i][1]]))
Min[i][1] = Min[i][0], des[i][1] = des[i][0];
Min[i][0] = ab(h[i] - h[j]), des[i][0] = j;
} else if ((ab(h[i] - h[j]) < Min[i][1]) || (Min[i][1] == ab(h[i] - h[j]) && h[j] < h[des[i][0]]))
Min[i][1] = ab(h[i] - h[j]), des[i][1] = j;
}
void doubling(int i, int val) {
for (int k = 20; k >= 0; k--)
if (dis[i][k][0] + dis[i][k][1] <= val && To[i][k])
val -= (dis[i][k][0] + dis[i][k][1]), tot[1] += dis[i][k][1], tot[0] += dis[i][k][0], i = To[i][k];
if (des[i][1] && Min[i][1] <= val)
tot[1] += Min[i][1];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i]);
Min[i][1] = Min[i][0] = 2147483645;
}
for (int i = n; i >= 1; i--) {
box.insert((info) {
h[i], i
});
I = box.find((info) {
h[i], i
});
++I;
if (I != box.end())
consider(i, *I), ++I, I != box.end() ? consider(i, *I), 1 : 1, --I;
--I;
if (I != box.begin())
--I, consider(i, *I), I != box.begin() ? --I, consider(i, *I), 1 : 1;
}
for (int i = 1; i <= n; i++)
To[i][0] = des[des[i][1]][0],
dis[i][0][1] = Min[i][1], dis[i][0][0] = Min[des[i][1]][0];
for (int k = 1; k <= 20; k++)
for (int i = 1; i <= n; i++)
To[i][k] = To[To[i][k - 1]][k - 1],
dis[i][k][1] = dis[i][k - 1][1] + dis[To[i][k - 1]][k - 1][1], dis[i][k][0] = dis[i][k - 1][0] + dis[To[i][k - 1]][k - 1][0];
scanf("%d", &x);
double rate = 2147483645;
int pos = 0;
h[0] = -2147483645;
for (int i = 1; i <= n; i++) {
tot[0] = tot[1] = 0;
doubling(i, x);
double tmp = tot[0] ? 1.0 * tot[1] / tot[0] : 2147483645;
if (tmp - rate < 0.000003 && tmp - rate > -0.000003 && h[i] > h[pos])
pos = i;
if (rate - tmp > 0.000003)
pos = i, rate = tmp;
}
printf("%d\n", pos);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &s, &x);
tot[0] = tot[1] = 0;
doubling(s, x);
printf("%d %d\n", tot[1], tot[0]);
}
return 0;
}
#B. Count The Repetitions*
尝试匹配总字符。假设dp数组中dp[i]表示从s2的i字符开始匹配s1，可以匹配多少个字符。然后用dp数组做转移，统计从第1个s1开始，一直到第n1个s1，可以一共匹配s2中的多少个字符，再除以s2长度和n2即可。
#include <bits/stdc++.h>
using namespace std;
string S, T;
int N, M;
int getMaxRepetitions(string s1, int n1, string s2, int n2)
{
int len = s2.length(), dp[len];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < len; i++)
{
int p = i;
for (int j = 0; j < s1.length(); j++)
if (s1[j] == s2[p])
{
p = (p + 1) % len;
dp[i]++;
}
}
int sum = 0, idx = 0;
for (int i = 0; i < n1; i++)
{
sum += dp[idx];
idx = (idx + dp[idx]) % len;
}
return sum / len / n2;
}
int main()
{
while(cin >> T >> M >> S >> N)
cout << getMaxRepetitions(S, N, T, M) << endl;
return 0;
}
#C. New Year Domino
题目大意
\(n\) 个多米诺骨牌，每个骨牌有两个值 \(x_i,h_i\) 表示每个骨牌的坐标和高度，第 \(i\) 个骨牌被推倒后，所有满足 \(x_j \leq x_i+h_i\) 的骨牌 \(j\) 也会被推倒，多次询问，问如果推倒第 \(x\) 个骨牌，最少需要花费多少代价才能推倒第 \(y\) 个骨牌。
代价定义：可以将任意一个骨牌的高度增加 \(1\)，花费 \(1\) 的代价。
题意转换
每次查询下标在 \([l,r]\) 的线段所覆盖的区间中的 \(0\) 的个数。我们可以发现，对于每次查询推倒 \(l\) 骨牌，那么 \([1,l-1]\) 这些骨牌，就不应该对当前查询有所影响。
所以我们可以考虑将每次查询按左端点从大到小排序，并记一个时间戳，每次判断一下时间戳与查询区间的左端点即可。
做法
我们可以用线段树来进行区间覆盖 \(1\)，区间查询 \(0\) 的数量，但是由于值域 \([1,10^9]\)，普通线段树难以支持，所以我们用动态开点值域线段树（貌似离散化也可以，但是动态开点真的是暴力美学）。
我们每次插入一个新线段，那么则将区间 \([x_i+1,x_i+h_i]\) 这个区间赋为 \(1\)。注意要 \(+1\)，因为每个骨牌自己的坐标不能直接赋为 \(1\)，必须要由上一个骨牌更新过来才行。
一些必须要加的优化：
查询时，如果当前节点的 \(tag\)（区间赋值标记）为 \(1\)，那么说明其子区间所有的值都被赋为 \(1\)，所以 \(0\) 的数量为 \(0\)，直接返回 \(0\) 即可。
对于每个骨牌，要将其坐标全部减去最小的坐标，防止 \(\color{blue}\text{MLE}\)。
其它的一些细节可以看下代码，写的时候注意一下就好。
#include <bits/stdc++.h>
using namespace std;
struct Domino
{
int lc, rc, sum, tag;
}Tree[8000080];
int tot = 0, n, m, rt, maxn = -1, minn = 1e9, ans[200020];;
inline void pushup(int u)
{
Tree[u].sum = Tree[Tree[u].lc].sum + Tree[Tree[u].rc].sum;
}
inline void Lazy(int u, int l, int r)
{
Tree[u].tag = 1;
Tree[u].sum = r - l + 1;
}
inline void pushdown(int u, int l, int r)
{
int mid = (l + r) >> 1;
if (Tree[u].lc == 0)
Tree[u].lc = ++tot;
if (Tree[u].rc == 0)
Tree[u].rc = ++tot;
Lazy(Tree[u].lc, l, mid);
Lazy(Tree[u].rc, mid + 1, r);
Tree[u].tag = 0;
}
inline void Modify(int &u, int l, int r, int L, int R)
{
if (L > R)
return;
if (!u)
u = ++tot;
if (l == L && r == R)
{
Lazy(u, l, r);
return;
}
if (Tree[u].tag)
pushdown(u, l, r);
int mid = (l + r) >> 1;
if (R <= mid)
Modify(Tree[u].lc, l, mid, L, R);
else if (L > mid)
Modify(Tree[u].rc, mid + 1, r, L, R);
else
{
Modify(Tree[u].lc, l, mid, L, mid);
Modify(Tree[u].rc, mid + 1, r, mid + 1, R);
}
pushup(u);
}
inline int query(int u, int l, int r, int L, int R)
{
if (!u)//查询的优化1
return r - l + 1;
if (l == L && r == R)
return r - l + 1 - Tree[u].sum;
if (Tree[u].tag)//查询的优化2
return 0;
int mid = (l + r) >> 1;
if (R <= mid)
return query(Tree[u].lc, l, mid, L, R);
else if (L > mid)
return query(Tree[u].rc, mid + 1, r, L, R);
else return query(Tree[u].lc, l, mid, L, mid) + query(Tree[u].rc, mid + 1, r, mid + 1, R);
}
struct pile
{
int x, h, id;
bool operator < (const pile &u) const { //骨牌和查询的内容和排序方式差不多
return x < u.x; //所以查询按-x加入到数组中方便排序
}
} line[200020], in[200020];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &line[i].x, &line[i].h);
minn = min(minn, line[i].x);
}
for (int i = 1; i <= n; i++) //重点优化
line[i].x = line[i].x - minn + 1;
sort(line + 1, line + 1 + n);
scanf("%d", &m);
for (int i = 1, u; i <= m; i++)
{
scanf("%d %d", &u, &in[i].h);
in[i].x = -u;
in[i].id = i;
maxn = max(maxn, -in[i].x);
}
for (int i = n; i >= maxn; i--)
Modify(rt, 1, 1e9, line[i].x + 1, min(line[i].x + line[i].h, int(1e9)));
sort(in + 1, in + 1 + m);
for (int i = 1; i <= m; i++)
{
while (maxn > -in[i].x)
{
maxn--;
Modify(rt, 1, 1e9, line[maxn].x + 1, min(line[maxn].x + line[maxn].h, int(1e9)));
}
ans[in[i].id] = query(rt, 1, 1e9, line[-in[i].x].x, line[in[i].h].x) - query(rt, 1, 1e9, line[-in[i].x].x, line[-in[i].x].x);//减去后面那个是为了防止，推倒了骨牌l,但是骨牌l的坐标值为0导致多算了一个0
}
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
#D. Sum Over Zero
前置
\(dp_i\) 表示到位置 \(i\) 为止有多少点没有选。
\(sum_i\) 表示 \(\sum_{i=1}^{n}a_i\)。
关于为什么要令 \(dp_i\) 是没有选的最优解：\(dp\) 表示选与不选在复杂度 \(O(n^2)\) 时是都可以实现的，但是在复杂度 \(O(n\log{n})\) 时，由于要将之前的信息放到数据结构里，这个信息是不能随位置而改变的，但是如果是 \(dp_i\) 表示选的话，dp 转移方程就是 \(dp_i=\max(dp_j+i-j)\)，这个信息会改变所以不适合用数据结构维护。这也是“正难则反”的思想。
朴素 dp
\(dp_i\) 可以由两种方法转移:
- \(dp_i\) 不取，此时 \(dp_i=dp_{i-1}+1\)。
- \(dp_i\) 取，从 \(1\) 到 \(i-1\) 枚举 \(j\)。考虑什么样的 \(j\) 可以转移，即 \(j+1\) 到 \(i\) 这一段都取了，即 \(sum_i-sum_j\geq0\)。此时 \(dp_i=\min(dp_j)\)。
复杂度 \(O(n^2)\)。
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
for (int j = 1; j < i; j++)
if (sum[i] >= sum[j])
dp[i] = min(dp[i], dp[j]);
}
如何优化
这个 dp 的复杂度不够优秀，我们考虑用数据结构维护。
发现对于 \(i\) 查询的是，位置在 \(i\) 之前，前缀和小于 \(i\) 的所有 \(dp\) 的最小值。用线段树（其他数据结构也可以）维护这个信息。
将前缀和离散化，更新时查询比当前前缀和小的最小值，在完成 \(dp_i\) 的更新之后将其插入线段树。
复杂度 \(O(n\log{n})\)。
#include <bits/stdc++.h>
using namespace std;
long long n, val[200020], dp[200020], sum[200020], Sum[200020];
struct Node
{
long long val;
}Tree[4000040];
inline void build(long long K, long long l, long long r)
{
Tree[K].val = 0x3f3f3f3f;
if (l == r)
return ;
long long mid = l + r >> 1;
build(K << 1, l, mid);
build(K << 1 | 1, mid + 1, r);
}
inline void modify(long long K, long long l, long long r, long long pos, long long val)
{
if (l == r)
{
Tree[K].val = min(Tree[K].val, val);
return ;
}
long long mid = (l + r) >> 1;
if (pos <= mid)
modify(K << 1, l, mid, pos, val);
else modify(K << 1 | 1, mid + 1, r, pos, val);
Tree[K].val = min(Tree[K << 1].val, Tree[K << 1 | 1].val);
}
inline long long query(long long K, long long l, long long r, long long L, long long R)
{
if (L <= l && R >= r)
return Tree[K].val;
long long mid = l + r >> 1, ret = 0x3f3f3f3f;
if (L <= mid)
ret = min(ret, query(K << 1, l, mid, L, R));
if (R > mid)
ret = min(ret, query(K << 1 | 1, mid + 1, r, L, R));
return ret;
}
int main()
{
scanf("%lld", &n);
for (long long i = 1; i <= n; i++)
{
scanf("%lld", &val[i]);
sum[i] = val[i] + sum[i - 1];
Sum[i] = sum[i];
}
sort(Sum, Sum + n + 1);
long long len = unique(Sum, Sum + n + 1) - Sum;
build(1, 0, len);
long long Rnk = lower_bound(Sum, Sum + len, 0) - Sum;
modify(1, 0, len, Rnk, 0);
for (long long i = 1; i <= n; i++)
{
dp[i] = dp[i - 1] + 1;
if (sum[i] >= 0)
dp[i] = 0;
long long pos = lower_bound(Sum, Sum + len, sum[i]) - Sum, tmp = query(1, 0, len, 0, pos);
dp[i] = min(dp[i], tmp);
modify(1, 0, len, pos, dp[i]);
}
printf("%lld", n - dp[n]);
return 0;
}
#E. Hot Start Up (hard version)
考虑将问题转化一下，将我们要完成的任务划分为若干段区间，然后两个处理器交错处理这些区间。显然，这和原问题等价，考虑以此为切入点 dp。
设 \(f(i,j)\) 表示先执行 \(i\) 再执行 \(j\)，\(j\) 的花费，\(calc(l,r)\) 表示处理完任务 \(l\) 后，顺次执行区间 \([l+1,r]\) 内所有任务的总花费。
设 \(dp_{i}\) 表示以 \(i\) 为一段区间结尾，前面划分后的最小代价。
那么枚举上一段区间结束位置，不难得到转移式：\(dp_{i}=\min\limits_{k<i}\{dp_{k}+calc(k+1,i)+f(las,k+1)\}\)。
此时我们会发现遇到了一点问题：我们无从得知 \(f(las,k+1)\) 的值。如果要再记录一维 \(las\)，状态数肯定爆炸。
这里采用一个很经典的思想：费用预支。
\(f(las,k+1)\) 无法在 \((k+1,i)\) 的区间里处理，那么我们就在 \((las+1,k)\) 的区间转移时把它求出来。
所以正确的转移式为：
\[dp_{i}=\min_{k<i}\{dp_k+calc(k+1,i)+f(k,i+1)\} \]特别的，我们在 \(0\) 和 \(n+1\) 处均加入一个花费恒为 \(0\) 的任务，规避掉一些特殊情况。
固定左端点，不断扩大右端点即可在 \(O(n^2)\) 内预处理所有的 \(calc(l,r)\)，转移 \(O(n^2)\)，可以通过 easy version。
接下来考虑优化，先处理 \(calc\) 函数。
令 \(g_i=f(i,i+1)\)，则有 \(calc(l,r)=\sum\limits_{i=l}^{r-1}g_i\)。
所以我们求出 \(g\) 的前缀和数组 \(sum_i=\sum\limits_{j=0}^ig_j\)，即可得到 \(calc(l,r)=sum_{r-1}-sum_{l-1}\)。
将其代回原转移式可得 \(dp_{i}=\min\limits_{k<i}\{dp_k+sum_{i-1}-sum_k+f(k,i+1)\}\)。
按下标分类一下，\(dp_i=\min\limits_{k<i}\{dp_k-sum_k+f(k,i+1)\}+sum_{i-1}\)。
前面部分的 \(dp\) 求完后，\(dp_k-sum_k\) 是可以统一维护的，那么只剩下 \(f(k,i+1)\) 一项了。考虑这东西等于什么。
\[f(x,y)=\begin{cases}hot_{a_y}& a_x=a_y\\cold_{a_y}& a_x\neq a_y\end{cases} \]由于保证 \(hot_i\le cold_i\)，所以实际上还可以更进一步得到：
\[f(x,y)=\min\begin{cases}hot_{a_y}& a_x=a_y\\cold_{a_y}\end{cases} \]因此转移式也可以进行调整。
\[dp_{i}=sum_{i-1}+\min_{k<i}\begin{cases}dp_{k}-sum_k+cold_{a_{i+1}}\\ dp_k-sum_k+hot_{a_{i+1}}&a_k=a_{i+1}\end{cases} \]那么我们只需要在 dp 的过程中顺带维护 \(dp_i-sum_i\) 的全局最小值和每类最小值即可，复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
long long T, n, k, a[300030], hot[300030], cold[300030], sum[300030], dp[300030], mn[300030];
inline long long calc(long long x, long long y)
{
return a[x] == a[y] ? hot[a[y]] : cold[a[y]];
}
int main()
{
scanf("%lld", &T);
while (T--)
{
scanf("%lld %lld", &n, &k);
for (long long i = 1; i <= n; i++)
sum[i] = dp[i] = 0;
for (long long i = 1; i <= k; i++)
mn[i] = 1e18;
a[n + 1] = hot[n + 1] = cold[n + 1] = 0;
for (long long i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (long long i = 1; i <= k; i++)
scanf("%lld", &cold[i]);
for (long long i = 1; i <= k; i++)
scanf("%lld", &hot[i]);
sum[0] = calc(0, 1);
for (long long i = 1; i <= n; i++)
sum[i] = sum[i - 1] + calc(i, i + 1);
long long alm = 0;
for (long long i = 1; i <= n; i++)
{
dp[i] = alm + cold[a[i + 1]] + sum[i - 1];
dp[i] = min(dp[i], mn[a[i + 1]] + hot[a[i + 1]] + sum[i - 1]);
mn[a[i]] = min(mn[a[i]], dp[i] - sum[i]);
alm = min(alm, dp[i] - sum[i]);
}
printf("%lld\n", dp[n]);
}
return 0;
}
#F. Non-equal Neighbours
设 \(f(i,j)\) 表示考虑前 \(i\) 个数，当前 \(b_i=j\) 的方案数，那么显然有：
\[f(i,j)=\begin{cases}0, &j>a_i\\(\sum_{x=1}^{a_{i-1}}f(i-1,x))-f(i-1,j), &j\le a_i\end{cases} \]把 \(f(i)\) 看作序列，用线段树维护即可。需要支持区间推平（\(j>a_i\) 的情况），区间取反（\(f(i,j)\gets -f(i-1,j)\)），区间加（\(f(i,j)\gets -f(i-1,j)+\sum_{x=1}^{a_{i-1}}f(i-1,x)\)），区间查询（查询 \(\sum_{x=1}^{a_{i-1}}f(i-1,x)\)）。
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
long long ans, c, n, a[200020], b[200020];
inline void Mod(long long &x)
{
x = (x % mod + mod) % mod;
}
struct Segment_Tree
{
struct seg
{
long long l, r, sum, cov, add, neg;
seg() {l = r = sum = add = cov = neg = 0;}
} Tree[800080];
inline void build(long long K, long long l, long long r)
{
Tree[K].l = l;
Tree[K].r = r;
if (l == r)
return;
long long mid = (l + r) >> 1;
build(K << 1, l, mid);
build(K << 1 | 1, mid + 1, r);
}
inline void pushdown(long long K)
{
if (Tree[K].cov)
{
Tree[K << 1].cov = Tree[K << 1 | 1].cov = Tree[K].cov;
Tree[K].cov = 0;
Tree[K << 1].neg = Tree[K << 1 | 1].neg = 0;
Tree[K << 1].add = Tree[K << 1 | 1].add = 0;
Tree[K << 1].sum = 0;
Tree[K << 1 | 1].sum = 0;
}
if (Tree[K].neg)
{
Tree[K << 1].neg ^= 1;
Tree[K << 1 | 1].neg ^= 1;
Tree[K << 1].add *= -1;
Tree[K << 1 | 1].add *= -1;
Mod(Tree[K << 1].add);
Mod(Tree[K << 1 | 1].add);
Tree[K << 1].sum *= -1;
Tree[K << 1 | 1].sum *= -1;
Mod(Tree[K << 1].sum);
Mod(Tree[K << 1 | 1].sum);
Tree[K].neg = 0;
}
if (Tree[K].add)
{
Tree[K << 1].add += Tree[K].add, Tree[K << 1].add %= mod;
Tree[K << 1].sum += 1ll * (b[Tree[K << 1].r] - b[Tree[K << 1].l - 1]) * Tree[K].add % mod, Tree[K << 1].sum %= mod;
Tree[K << 1 | 1].add += Tree[K].add, Tree[K << 1 | 1].add %= mod;
Tree[K << 1 | 1].sum += 1ll * (b[Tree[K << 1 | 1].r] - b[Tree[K << 1 | 1].l - 1]) * Tree[K].add % mod, Tree[K << 1 | 1].sum %= mod;
Tree[K].add = 0;
}
}
inline void modify(long long K, long long l, long long r, long long d)
{ //add
if (l > r)
return;
if (l <= Tree[K].l && Tree[K].r <= r)
{
Tree[K].sum += 1ll * (b[Tree[K].r] - b[Tree[K].l - 1]) * d % mod;
Tree[K].sum %= mod;
Tree[K].add += d;
Tree[K].add %= mod;
return;
}
pushdown(K);
long long mid = (Tree[K].l + Tree[K].r) >> 1;
if (l <= mid)
modify(K << 1, l, r, d);
if (r > mid)
modify(K << 1 | 1, l, r, d);
Tree[K].sum = Tree[K << 1].sum + Tree[K << 1 | 1].sum;
Tree[K].sum %= mod;
}
inline void cover(long long K, long long l, long long r)
{
if (l > r)
return;
if (l <= Tree[K].l && Tree[K].r <= r)
{
Tree[K].cov = 1;
Tree[K].add = Tree[K].sum = Tree[K].neg = 0;
return;
}
pushdown(K);
long long mid = (Tree[K].l + Tree[K].r) >> 1;
if (l <= mid)
cover(K << 1, l, r);
if (r > mid)
cover(K << 1 | 1, l, r);
Tree[K].sum = Tree[K << 1].sum + Tree[K << 1 | 1].sum;
Tree[K].sum %= mod;
}
inline void Modify(long long K, long long l, long long r)
{
if (l > r)
return;
if (l <= Tree[K].l && Tree[K].r <= r)
{
Tree[K].neg ^= 1;
Tree[K].sum *= -1, Tree[K].add *= -1;
Mod(Tree[K].sum);
Mod(Tree[K].add);
return;
}
pushdown(K);
long long mid = (Tree[K].l + Tree[K].r) >> 1;
if (l <= mid)
Modify(K << 1, l, r);
if (r > mid)
Modify(K << 1 | 1, l, r);
Tree[K].sum = Tree[K << 1].sum + Tree[K << 1 | 1].sum;
Tree[K].sum %= mod;
}
inline long long query(long long K, long long l, long long r)
{
if (l > r)
return 0;
if (l <= Tree[K].l && Tree[K].r <= r)
return Tree[K].sum;
pushdown(K);
long long mid = (Tree[K].l + Tree[K].r) >> 1, ans = 0;
if (l <= mid)
ans = (ans + query(K << 1, l, r)) % mod;
if (r > mid)
ans = (ans + query(K << 1 | 1, l, r)) % mod;
return ans;
}
} T;
int main()
{
scanf("%lld", &n);
c = n;
// 离散化一波
for (long long i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + c + 1);
c = unique(b + 1, b + c + 1) - b - 1;
for (long long i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + c + 1, a[i]) - b;
// for(long long i = 1; i <= n; i++) printf("%d ", a[i]);puts("!!!");
T.build(1, 1, c);
for (long long i = 1; i <= a[1]; i++)
T.modify(1, i, i, 1);
for (long long i = 2; i <= n; i++)
{
long long sum = T.query(1, 1, c);
// printf("sum = %lld\n", sum);
T.cover(1, a[i] + 1, c);
// printf("sum = %lld\n", T.query(1, 1, c));
T.Modify(1, 1, a[i]);
// printf("sum = %lld\n", T.query(1, 1, c));
T.modify(1, 1, a[i], sum);
// printf("sum = %lld\n", T.query(1, 1, c));
}
for (long long i = 1; i <= a[n]; i++)
ans = (ans + T.query(1, i, i)) % mod;
printf("%lld", ans);
return 0;
}
#G. Animal Observation (hard version)
Discription.
给定一个矩阵，现在你可以对每一行取出一个这一行和下一行组成的 \(2\times k\) 的子矩阵，并取走其中的所有数（如果最后一行的话就只能取一行。
现在你需要让你取出的所有数最大化。
Solution.
首先，有一个很显然的 \(O(nm^2)\) 的 dp。
设 \(dp_{i,j}\) 表示第 \(i\) 和 \(i+1\) 行选 \([j,j+k-1]\) 这个子矩阵时的最大答案。
那么 \(dp_{i,j}\) 可以从所有的 \(dp_{i-1,k}\) 转移过来，主要就是去重。
但是如果暴力枚举时肯定能算出去重函数的，所以我们得到了一份 TLE on \(13\) 的代码，如下
#include <bits/stdc++.h>
using namespace std;
long long ans, n, m, K, a[55][20020], pre[55][20020], dp[55][20020];
inline long long calc(long long i, long long l, long long r)
{
if (l > r)
swap(l, r);
return max(pre[i][l + K - 1] - pre[i][r - 1], 0ll);
}
int main()
{
scanf("%lld %lld %lld", &n, &m, &K);
for (long long i = 1; i <= n; i++)
for (long long j = 1; j <= m; j++)
{
scanf("%lld", &a[i][j]);
pre[i][j] = pre[i][j - 1] + a[i][j];
}
for (long long j = 1; j <= m - K + 1; j++)
dp[1][j] = pre[1][j + K - 1] - pre[1][j - 1] + pre[2][j + K - 1] - pre[2][j - 1];
for (long long i = 2; i <= n; i++)
for (long long j = 1; j <= m - K + 1; j++)
for (long long k = 1; k <= m - K + 1; k++)
dp[i][j] = max(dp[i][j], dp[i - 1][k] + pre[i + 1][j + K - 1] - pre[i + 1][j - 1] + pre[i][j + K - 1] - pre[i][j - 1] - calc(i, k, j));
for (long long j = 1; j <= m - K + 1; j++)
ans = max(ans, dp[n][j]);
printf("%lld", ans);
return 0;
}
然后我们就能获得……\(0\) 分的好成绩，毕竟 F1 都不让这种方法过。
然后我们考虑优化，F1 那题有一个限制 \(k\le\min(20,m)\)。
思考思考这个限制有什么用：我们会发现，因为上面的重复（calc）中有一个 max，我们考虑去掉它。
首先，矩阵中所有的数都是正数，那么也就是说只有在 l+K-1>=r 时才会取到 pre[i][l + K - 1] - pre[i][r - 1]。
那么这就好办了，只有在 \(j-K+1\le k\le j+K-1\) 时那个 calc 函数才会有用。
然后又因为 \(k\) 很小，那么我们直接暴力转移这样的状态，剩下的因为 calc 函数等于 \(0\)，所以我们直接记录前缀最大值后缀最大值就好了，这样复杂度是 \(O(nmk)\) 的，足以通过 F1，代码
//愿你有一天能和你重要的人重逢。
#include <bits/stdc++.h>
using namespace std;
long long ans, n, m, K, a[55][20020], s[55][20020], dp[55][20020], mx1[55][25005], mx2[55][25005];
inline long long calc(long long i, long long l, long long r)
{
if (l > r)
swap(l, r);
return l + K - 1 >= r ? s[i][l + K - 1] - s[i][r - 1] : 0;
}
int main()
{
scanf("%lld %lld %lld", &n, &m, &K);
for (long long i = 1; i <= n; i++)
for (long long j = 1; j <= m; j++)
{
scanf("%lld", &a[i][j]);
s[i][j] = s[i][j - 1] + a[i][j];
}
for (long long j = 1; j <= m - K + 1; j++)
dp[1][j] = s[1][j + K - 1] - s[1][j - 1] + s[2][j + K - 1] - s[2][j - 1];
for (long long j = 1; j <= m - K + 1; j++)
mx1[1][j] = max(mx1[1][j - 1], dp[1][j]);
for (long long j = m - K + 1; j >= 1; j--)
mx2[1][j] = max(mx2[1][j + 1], dp[1][j]);
for (long long i = 2; i <= n; i++)
{
for (long long j = 1; j <= m - K + 1; j++)
{
long long now = s[i + 1][j + K - 1] - s[i + 1][j - 1] + s[i][j + K - 1] - s[i][j - 1];
dp[i][j] = max(dp[i][j], now + max(j > K ? mx1[i - 1][j - K] : 0, mx2[i - 1][j + K]));
for (long long k = max(j - K + 1, 1ll); k <= min(j + K - 1, m - K + 1); k++)
dp[i][j] = max(dp[i][j], dp[i - 1][k] + now - calc(i, k, j));
}
for (long long j = 1; j <= m - K + 1; j++)
mx1[i][j] = max(mx1[i][j - 1], dp[i][j]);
for (long long j = m - K + 1; j >= 1; j--)
mx2[i][j] = max(mx2[i][j + 1], dp[i][j]);
}
for (long long j = 1; j <= m - K + 1; j++)
ans = max(ans, dp[n][j]);
printf("%lld", ans);
return 0;
}
然后，我们继续思考，如果 \(k\) 很大这样复杂度还是无法通过 F2，我们仔细观察一下，发现上面的暴力转移过程中还可以继续分类讨论，如下
for (int k = max(j - K + 1, 1); k <= j; k++)
dp[i][j] = max(dp[i][j], dp[i - 1][k] + now - pre[i][k + K - 1] + pre[i][j - 1]);
for (int k = j; k <= min(j + K - 1, m - K + 1); k++)
dp[i][j] = max(dp[i][j], dp[i - 1][k] + now - pre[i][j + K - 1] + pre[i][k - 1]);
那么这样就很显然了吧。
在上面那一行中，now + pre[i][j-1]是不变的，而 dp[i - 1][k] + pre[i][k + K - 1]与 \(j\) 无关。
下面那一行中，now - pre[i]是不变的，而dp[i - 1][k] + pre[i][k - 1]是与 \(j\) 无关的。
那么我们只需要用线段树等数据结构来维护区间最大值就好了，复杂度是 \(O(nm\log m)\) 。
#include <bits/stdc++.h>
using namespace std;
long long ans, n, m, K, a[55][20020], pre[55][20020], dp[55][20020], mx1[55][25005], mx2[55][25005], t[25005];
inline long long calc(long long i, long long l, long long r)
{
if (l > r)
swap(l, r);
return pre[i][l + K - 1] - pre[i][r - 1];
}
struct Segment_Tree
{
long long t[100010];
inline void build(long long x, long long l, long long r, long long *c)
{
if (!(l ^ r))
{
t[x] = c[l];
return;
}
build(x << 1, l, (l + r) >> 1, c);
build(x << 1 | 1, ((l + r) >> 1) + 1, r, c);
t[x] = max(t[x << 1], t[x << 1 | 1]);
}
inline long long query(long long x, long long l, long long r, long long L, long long R)
{
if (L > r || l > R)
return -1e9;
else if (L <= l && r <= R)
return t[x];
return max(query(x << 1, l, (l + r) >> 1, L, R), query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R));
}
}T1, T2;
int main()
{
scanf("%lld %lld %lld", &n, &m, &K);
for (long long i = 1; i <= n; i++)
for (long long j = 1; j <= m; j++)
{
scanf("%lld", &a[i][j]);
pre[i][j] = pre[i][j - 1] + a[i][j];
}
for (long long j = 1; j <= m - K + 1; j++)
dp[1][j] = pre[1][j + K - 1] - pre[1][j - 1] + pre[2][j + K - 1] - pre[2][j - 1];
for (long long j = 1; j <= m - K + 1; j++)
mx1[1][j] = max(mx1[1][j - 1], dp[1][j]);
for (long long j = m - K + 1; j >= 1; j--)
mx2[1][j] = max(mx2[1][j + 1], dp[1][j]);
for (long long i = 2; i <= n; i++)
{
for (long long k = 1; k <= m - K + 1; k++)
t[k] = dp[i - 1][k] - pre[i][k + K - 1];
T1.build(1, 1, m - K + 1, t);
for (long long k = 1; k <= m - K + 1; k++)
t[k] = dp[i - 1][k] + pre[i][k - 1];
T2.build(1, 1, m - K + 1, t);
for (long long j = 1; j <= m - K + 1; j++)
{
long long now = pre[i + 1][j + K - 1] - pre[i + 1][j - 1] + pre[i][j + K - 1] - pre[i][j - 1];
dp[i][j] = max(dp[i][j], now + max(j > K ? mx1[i - 1][j - K] : 0, mx2[i - 1][j + K]));
dp[i][j] = max(dp[i][j], T1.query(1, 1, m - K + 1, max(j - K + 1, 1ll), j) + now + pre[i][j - 1]);
dp[i][j] = max(dp[i][j], T2.query(1, 1, m - K + 1, j, min(j + K - 1, m - K + 1)) + now - pre[i][j + K - 1]);
// for(long long k = max(j - K + 1, 1); k <= j; k++) dp[i][j] = max(dp[i][j],dp[i - 1][k] + now - pre[i][k + K - 1] + pre[i][j - 1]);
// for(long long k = j; k <= min(j + K - 1, m - K + 1); k++) dp[i][j] = max(dp[i][j], dp[i - 1][k] + now - pre[i][j + K - 1] + pre[i][k - 1]);
}
for (long long j = 1; j <= m - K + 1; j++)
mx1[i][j] = max(mx1[i][j - 1], dp[i][j]);
for (long long j = m - K + 1; j >= 1; j--)
mx2[i][j] = max(mx2[i][j + 1], dp[i][j]);
}
for (long long i = 1; i <= m - K + 1; i++)
ans = max(ans, dp[n][i]);
printf("%lld", ans);
return 0;
}
#H. Artistic Partition
题意
记 \(c(l,r)=\sum\limits_{i=l}^r\sum\limits_{j=i}^r[\gcd(i,j)\ge l]\)。你可以将\(1\sim n\) 的\(n\) 个数分成 \(k\) 段 \(0=x_1<x_2<x_3<\cdots<x_k<x_{k+1}=n\)，最小化
\[\sum_{i=1}^{k}c(x_i+1,x_{i+1}) \]数据范围：\(n,k\le 10^5,T\) 组询问， \(T\le 3\times 10^5\)。
solution
一个暴力的 DP 做法是：设 \(f_{i,k}\) 表示前 \(i\) 个数分成 \(k\) 段的最小值。转移是
\[f_{i,k}=\min_{j=1}^i\{f_{j-1,k-1}+c(l,r)\} \]边界：\(f_{i,0}=+\infin\)，\(f_{0,k}=0\)。
询问数很多，可以预处理出 DP 数组 \(O(1)\) 查询。
DP状态数是 \(O(n^2)\) 的，无法承受。观察 \(c(l,r)\) 的性质，发现 \(c(l,r)\ge r-l+1\)，也就是说 \(f_{n,k}\ge n\)。其次，\(c(l,2l-1)=(2l-1)-l+1=l\)，也就是说，若 \(n<2^k\)，一定可以把 \(n\) 分成若干段，满足 \(c(l,r)=r-l+1\)，即\(f_{n,k}=n(2^k>n)\)。剩下的需要考虑的 \(k\) 就是 \(O(\log n)\) 级别的了。
状态数没有太大的优化空间了，考虑优化 \(c(l,r)\) 的计算。大力推式子：
\[\begin{aligned} c(l,r)&=\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)\ge l]\\ &=\sum_{k=l}^r\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)= k]\\ &=\sum_{k=l}^r\sum_{i=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{r}{k}\rfloor}\sum_{j=i}^{\lfloor\frac{r}{k}\rfloor}[\gcd(i,j)=1]\\ &=\sum_{k=l}^r\sum_{j=1}^{\lfloor\frac{r}{k}\rfloor}\sum_{i=1}^j[\gcd(i,j)=1]\\ &=\sum_{k=l}^r\sum_{i=1}^{\lfloor\frac{r}{k}\rfloor}\varphi(i) \end{aligned} \]记 \(s(n)=\sum_{i=1}^n\varphi(i)\)，即 \(\varphi\) 的前缀和。则
\[c(l,r)=\sum_{k=l}^rs(\lfloor\frac{r}{k}\rfloor) \]预处理出 \(s(n)\) 之后即可 \(O(\sqrt{r})\) 查询。实际上，\(c(l,r)\) 的计算复杂度大概是 \(O(\sqrt{r-l})\) 的。或者可以 \(O(n\sqrt{n})\) 预处理 \(O(1)\) 查询。
考虑优化 DP 转移。根据这个 DP 分段的形式，大胆猜测 \(c(l,r)\) 满足四边形不等式，那么这样DP转移就可以使用决策单调性优化转移了。\(c(l,r)\) 满足四边形不等式的证明如下：
设 \(l_1<l_2<r_1<r_2\)，我们需要证明 \(c(l_1,r_1)+c(l_2,r_2)\le c(l_1,r_2)+c(l_2,r_1)\)。
设 \(f(l,r,p)=\sum_{k=l}^p(\lfloor\frac{r}{k}\rfloor)\)，那么
\[\begin{aligned} c(l_1,r_2)+c(l_2,r_1)&=f(l_1,r_2,r_2)+f(l_2,r_1,r_1)\\ &=(f(l_1,r_2,l_2-1)+f(l_2,r_2,r_2))+(f(l_1,r_1,r_1)-f(l_1,r_1,l_2-1))\\ &=f(l_1,r_2,l_2-1)-f(l_1,r_1,l_2-1)+c(l_1,r_1)+c(l_2,r_2)\\ \end{aligned} \]显然 \(f(l_1,r_2,l_2-1)\ge f(l_1,r_1,l_2-1)\)，得证。
剩下的部分可以使用 \(\text{1D1D}\) 决策单调性优化 \(\text{DP}\) 的常见套路（分治/单调队列）进行。因为有 \(O(\log n)\) 层，每层的复杂度是 \(O(n\log n)\) 的，转移的时间复杂度是 \(O(n\log^2n)\) 的，加上预处理的复杂度，总时间复杂度 \(O(n\log^2n+n\sqrt{n})\) ，空间复杂度 \(O(n\sqrt{n})\)。
实际上，采用分治做法，假设当前的转移区间是 \([L,R]\)，当前需要寻找转移点的是 \(mid\)。首先\(O(\sqrt{r-l})\) 求出 \(c(R+1,mid)\)，然后从 \(\min(mid,R)\) 到 \(L\) 枚举转移点 \(i\)，\(c(i,mid)=c(i+1,mid)+s(\lfloor\frac{mid}{i}\rfloor)\)。这个做法的时间复杂度不太好证，不过预处理跑的很快，而且代码复杂度很低。
#include <bits/stdc++.h>
#define inf 1e18
using namespace std;
long long prime[100010], pcnt, phi[100010], T, n, k, dp[100010][18];
bool vis[100010];
inline void init(long long n)
{
phi[1] = 1;
for (long long i = 2; i <= n; ++i)
{
if (!vis[i])
{
prime[++pcnt] = i;
phi[i] = i - 1;
}
for (long long j = 1; j <= pcnt && prime[j] * i <= n; ++j)
{
vis[prime[j] * i] = 1;
if (i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (long long i = 1; i <= n; ++i)
phi[i] += phi[i - 1];
}
inline long long calc(long long l, long long r)
{
long long res = 0;
for (long long i; l <= r; l = i + 1)
{
i = min(r / (r / l), r);
res += phi[r / l] * (i - l + 1);
}
return res;
}
inline void query(long long l, long long r, long long L, long long R)
{
if (l > r)
return;
long long mid = (l + r) >> 1, sum = calc(R + 1, mid), pos = 0, mn = inf;
for (long long i = min(mid, R); i >= L; --i)
{
sum += phi[mid / i];
if (sum + dp[i - 1][k - 1] <= mn)
{
mn = sum + dp[i - 1][k - 1];
pos = i;
}
}
dp[mid][k] = mn;
query(l, mid - 1, L, pos);
query(mid + 1, r, pos, R);
}
int main()
{
init(100000);
for (long long i = 1; i <= 100000; ++i)
dp[i][1] = (i * (i + 1)) >> 1;
for (k = 2; k <= 17; ++k)
query(1, 100000, 1, 100000);
scanf("%lld", &T);
while (T--)
{
scanf("%lld %lld", &n, &k);
if (k >= 20 || n < (1 << k))
{
printf("%lld\n", n);
continue;
}
printf("%lld\n", dp[n][k]);
}
return 0;
}