Educational Codeforces Round 69 D E

时间：2022-02-06 04:17:45

Educational Codeforces Round 69 题解

题目编号 A B C D E F
完成情况 √ √ √ ★ ★ -

D. Yet Another Subarray Problem

一个子数组的价值为:

\[\sum_{i=l}^{r} a[i] - k\lceil{\frac{r-l+1}{m}}\rceil
\]

求解其最大值。子数组可以为空，此时价值为0.

\(r-l+1\)自然是子数组的长度\(len\)，可以发现每当\(len\)增加\(m\)后,\(\lceil{\frac{r-l+1}{m}}\rceil\)会增加1。也就是说，子数组的权值受到长度的影响。\(dp[len][n]\)显然是不行的。实际上转移的时候，\(dp[len][n]\)从\(dp[len-1][n-1]\)转移过来，我们真正关心的是\(len\)能否被\(m\)整除，从而要多减一个\(k\)。于是只需要存储\(len mod m\)的余数就可以了。

\[dp[i][j]:include\ a[i]\ and\ len\ mod\ m\ =\ j
\]

\[if\ m\ ==\ 0\ OR\ j\ ==\ 1\ \ \ dp[i][j]\ =\ max\{dp[i\ -\ 1][0],\ 0\}\ +a[i]\ -\ k
\]

\[else\ if\ j==0\ \ \ dp[i][j]\ =\ dp[i-1][m - 1]\ +\ a[i]
\]

\[else\ \ \ dp[i][j]=dp[i-1][j-1]+a[i]
\]

一定要留心\(m=1\)的情况！单独考虑

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

long long max(long long a, long long b){return a > b ? a : b;}

long long min(long long a, long long b){return a < b ? a : b;}

void swap(long long &a, long long &b){long long tmp = a;a = b;b = tmp;}

long long lowbit(long long &x){return x & (-x);}

void read(long long &x)

{

	x = 0;char ch = getchar(), c = ch;

	while(ch < '0' || ch > '9') c = ch, ch = getchar();

	while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();

	if(c == '-') x = -x;

}

const long long INF = 0x3f3f3f3f3f3f3f3f;

const long long MAXN = 300000 + 10;

const long long MAXM = 10;

long long dp[MAXN][MAXM + 10], n, m, k, a[MAXN];

//dp[i][j]表示以i为结尾或者空串，长度余数为j的最大值

//dp[i][j] = dp[i - 1][j - 1] + a[i]

//dp[i][j] = dp[i - 1][j - 1] + a[i] - k  

int main()

{

	read(n), read(m), read(k);

	long long ans = 0;

	for(long long i = 1;i <= n;++ i) read(a[i]);

	for(int i = 0;i <= n;++ i)

		for(int j = 0;j < m;++ j)

			dp[i][j] = -INF;

	for(long long i = 1;i <= n;++ i)

		for(long long j = 0;j < m;++ j)

		{

			if(j == 1 || m == 1)

				dp[i][j] = max(dp[i - 1][0], 0) + a[i] - k;

			else if(j == 0)

				dp[i][j] = dp[i - 1][m - 1] + a[i];

			else

				dp[i][j] = dp[i - 1][j - 1] + a[i];

			ans = max(ans, dp[i][j]);

		}

	printf("%I64d", ans);

	return 0;

}

E. Culture Code

有一些套娃，每个套娃都有\(in_i\)和\(out_i\)两个属性，只有\(in_i\ \geq\ out_j\)，套娃\(j\)才能套在\(i\)的里面。一个相互嵌套的套娃集合的额外值定义为:

\[in_i\ +\ (in_{i+1}\ -out_{i})\ +\ (in_{i+2}\ -out_{i+1})\ +\ (in_{i+3}\ -out_{i+2})\ +\ \cdots\ +\ (in_{j}\ -out_{j-1})\
\]

一个套娃集合为极大集合，当且仅当不能再套在里面或外面任意另一个套娃。

求套娃极大集合的最小额外值的方案数

将套娃按照\(in\)降序排序

\(dp[0][i]\)表示前i个套娃，第\(i\)个套娃在最里面的最小额外值

\(dp[1][i]\)表示上面这个最小额外值的方案

\[dp[0][i]\ =\ min\{dp[0][j]\}\ -\ (out[i]\ -\ in[i])\
\]

相当于把第\(j\)个下面塞上\(i\)，额外值减小。要求$in[j] \geq\ out[i]\ $ 直接二分就能找到合法区间\(1~x\)，用线段树维护前缀最小和最小的个数。

其实也不用二分，在线段树询问操作中实现二分即可。

求最小的过程保证了对于前\(i\)个，第\(i\)个是极大集合。证明方法采用数学归纳法。第一个本身就是极大集合，从第二个开始，对于第\(i个\),因为里面不能再套，外面在\(dp\)后已经套过一个\(j\)，\(j\)是前\(j\)个中的最大集合（假设条件），而\(j+1~i-1\)中的\(in\)小于等于\(in[j]\)，因而小于\(out[j]\)，也不能再套了

最后计算结果时，把所有\(dp[0][i]==min\)的\(dp[1][i]\)累加。能证明最小的\(dp[0][i]\)一定是极大集合，首先放在\(i\)后面的只能往它下面套，会让答案减小，后面的不能

再套了；前面的能不能套再套，证明同上

初始状态:\(dp[0][1] = in[1]\)

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

long long max(long long a, long long b){return a > b ? a : b;}

long long min(long long a, long long b){return a < b ? a : b;}

void swap(long long &a, long long &b){long long tmp = a;a = b;b = tmp;}

long long lowbit(long long &x){return x & (-x);}

void read(long long &x)

{

	x = 0;char ch = getchar(), c = ch;

	while(ch < '0' || ch > '9') c = ch, ch = getchar();

	while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();

	if(c == '-') x = -x;

}

const long long INF = 0x3f3f3f3f3f3f3f3f;

const long long MAXN = 200000 + 10;

const long long MOD = 1e9 + 7;

long long n, in[MAXN], out[MAXN], id[MAXN];

bool cmp(long long a, long long b)

{

	return in[a] > in[b];

}

struct Node

{

	long long cnt, mi;

}node[MAXN << 2];

Node merge(Node& a, Node& b)

{

	Node re;

	if(a.mi == b.mi)

		re.mi = a.mi,

		re.cnt = a.cnt + b.cnt,

		re.cnt >= MOD ? re.cnt -= MOD : 0;

	else if(a.mi < b.mi)

		re = a;

	else

		re = b;

	return re;

}

void pushup(long long o)

{

	node[o] = merge(node[o << 1], node[o << 1 | 1]);

	return ;

}

void build(long long o = 1, long long l = 1, long long r = n)

{

	if(l == r)

	{

		node[o].mi = INF, node[o].cnt = 0;

		return ;

	}

	long long mid = (l + r) >> 1;

	build(o << 1, l, mid);

	build(o << 1 | 1, mid + 1, r);

	pushup(o);

}

//在p位置更新最小值为x，方案数为y

void modify(long long p, long long x, long long y, long long o = 1, long long l = 1, long long r = n)

{

	if(l == r)

	{

		if(node[o].mi == x) node[o].cnt += y;

		else node[o].mi = x, node[o].cnt = y;

		return ;

	}

	long long mid = (l + r) >> 1;

	if(p <= mid) modify(p, x, y, o << 1, l, mid);

	else modify(p, x, y, o << 1 | 1, mid + 1, r);

	pushup(o);

	return ;

}

//1到最后一个大于等于x的位置

Node ask(long long x, long long rr, long long o = 1, long long l = 1, long long r = n)

{

	if(in[id[r]] >= x && rr >= r) return node[o];

	long long mid = (l + r) >> 1;

	Node a, b;

	a.mi = INF, b.mi = INF;

	if(in[id[l]] >= x) a = ask(x, rr, o << 1, l, mid);

	if(in[id[mid + 1]] >= x && rr > mid) b = ask(x, rr, o << 1 | 1, mid + 1, r);

	return merge(a, b);

}

Node dp[MAXN];

long long mi = INF, ans = 0;

int main()

{

	read(n);

	for(long long i = 1;i <= n;++ i)

		read(out[i]), read(in[i]), id[i] = i;

	std::sort(id + 1, id + 1 + n, cmp);

	build();

	modify(1, in[id[1]], 1);

	dp[1].mi = in[id[1]], dp[1].cnt = 1;

	for(long long i = 2;i <= n;++ i)

	{

		dp[i] = ask(out[id[i]], i - 1);

		if(dp[i].mi == INF) dp[i].mi = in[id[i]], dp[i].cnt = 1;

		else dp[i].mi -= out[id[i]] - in[id[i]];

		modify(i, dp[i].mi, dp[i].cnt);

	}

	for(long long i = 1;i <= n;++ i)

		mi = min(mi, dp[i].mi);

	for(long long i = 1;i <= n;++ i)

		if(dp[i].mi == mi)

			ans += dp[i].cnt,

			ans >= MOD ? ans -= MOD : 0;

	printf("%I64d", ans);

	return 0;

}

---恢复内容结束---

#Educational Codeforces Round 69 题解

题目编号 A B C D E F
完成情况 √ √ √ ★ ☆ -

D. Yet Another Subarray Problem

一个子数组的价值为:

\[\sum_{i=l}^{r} a[i] - k\lceil{\frac{r-l+1}{m}}\rceil
\]

求解其最大值。子数组可以为空，此时价值为0.

\(r-l+1\)自然是子数组的长度\(len\)，可以发现每当\(len\)增加\(m\)后,\(\lceil{\frac{r-l+1}{m}}\rceil\)会增加1。也就是说，子数组的权值受到长度的影响。\(dp[len][n]\)显然是不行的。实际上转移的时候，\(dp[len][n]\)从\(dp[len-1][n-1]\)转移过来，我们真正关心的是\(len\)能否被\(m\)整除，从而要多减一个\(k\)。于是只需要存储\(len mod m\)的余数就可以了。

\[dp[i][j]:include\ a[i]\ and\ len\ mod\ m\ =\ j
\]

\[if\ j==0\ dp[i][j]\ =\ max \{ dp[i-1][m-1],0 \} +a[i]-k \}
\]

\[else\ dp[i][j]=dp[i-1][j-1]+a[i]
\]

初始状态:因为\(dp\)中有很多不合题意的量，我们不能用这些量去进行转移，于是初始全部赋值为\(-INF\)。\(dp[1][0]\)和\(dp[1][1]\)是唯两个满足条件的第一维是1的量，为了让他们赋值正确，考虑让dp[0][m-1]=0

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

long long max(long long a, long long b){return a > b ? a : b;}

long long min(long long a, long long b){return a < b ? a : b;}

void swap(long long &a, long long &b){long long tmp = a;a = b;b = tmp;}

long long lowbit(long long &x){return x & (-x);}

void read(long long &x)

{

	x = 0;char ch = getchar(), c = ch;

	while(ch < '0' || ch > '9') c = ch, ch = getchar();

	while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();

	if(c == '-') x = -x;

}

const long long INF = 0x3f3f3f3f3f3f3f3f;

const long long MAXN = 300000 + 10;

const long long MAXM = 10;

long long dp[MAXN][MAXM + 10], n, m, k, a[MAXN];

//dp[i][j]表示以i为结尾或者空串，长度余数为j的最大值

//dp[i][j] = dp[i - 1][j - 1] + a[i]

//dp[i][j] = dp[i - 1][j - 1] + a[i] - k  if j == 0

int main()

{

	read(n), read(m), read(k);

	long long ans = 0;

	for(long long i = 1;i <= n;++ i) read(a[i]);

	for(int i = 0;i <= n;++ i)

		for(int j = 0;j < m;++ j)

			dp[i][j] = -INF;

	dp[0][m - 1] = 0;

	for(long long i = 1;i <= n;++ i)

		for(long long j = 0;j < m;++ j)

		{

			if(j == 0)

				dp[i][j] = max(dp[i - 1][m - 1] + a[i] , a[i]) - k;

			else

				dp[i][j] = dp[i - 1][j - 1] + a[i];

			ans = max(ans, dp[i][j]);

		}

	printf("%I64d", ans);

	return 0;

}

相关文章