2020杭电多校第8场 B.Breaking Down News @ Wings            分类 ACM
发布于 星期六, 一月 30 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

有一个长度为$n$的数组$a$, 满足$a_i \in \{0, 1, 2\}$, 你要将其划分成一些连续的区间, 每个区间的长度在$[L, R]$之间, 每个区间的贡献是:

  • $-1$: 这个区间的和小于$0$
  • $0$: 这个区间的和等于$0$
  • $1$: 这个区间的和大于$0$

问最后总的贡献最大是多少

$1 \le L \le R \le n \le 10^6$

题解

显然dp. 设$dp(i)$为前$i$个划分区间的最大贡献, 有

$$ dp(i) = \max_{L \le i-j \le R} \begin{cases} dp(j) + 1, & s_i - s_j > 0 \newline dp(j), & s_i - s_j = 0 \newline dp(j) - 1, & s_i - s_j < 0 \end{cases} $$

($s_i$ 表示$a_i$的前缀和)

朴素转移是$O(n^2)$的, 考虑优化.

限制了只能从前面的某段区间转移的dp是一类单调队列的题目, 但是这题由于转移方程不仅和 $s_j$ 有关, 还和 $s_i$ 有关, 所以普通的单调队列就不可行了.

这里的做法很巧妙, 既然转移和$s$有关, 那就构建一个以$s$为下标的权值线段树, 表示$s_i$对应的最大dp值. 如果$s_i > s_j$, 那么就查询$[mn, s_i-1]$中的最大值, 加上1; 如果$s_i < s_j$, 那么就查询$[s_i+1, mx]$, 减去1; 如果$s_i = s_j$, 那么就查询$[s_j, s_j]$. 三个值取max转移.

每次递推$i$的时候维护一下能够转移的区间, 每次增加右边一个, 减少左边一个, 要在线段树上更新这两个值.

那么问题来了, 可能一个$S$有多个$s_i$和他相等, 然后区间递推要更新线段树的时候, 怎么能够知道要更新成哪一个点的dp值? 或者说怎么能够知道某一点是否不在更新区间内?

Smile学长讲题的时候是说维护一个单调递减的队列, 我搞了半天没懂, 感觉要对每个$s_i$都开一个队列才可以, 就很迷.

然后查了一下题解, 找到一个神仙离散化的做法.

对$s_i$进行离散化, 但是sort以后不要unique. 让每一个相等的$s_i$对应不同的离散化的值, 也就是说, 对之前的下标做一个一一映射id, 使得$s[id] \le s[id+1]$.

例如

i 1 2 3 4 5 6 7 8 9...
s 3 2 3 3 1 2 1 1 2...

i  5 7 8 2 6 9 1 3 4...
s  1 1 1 2 2 2 3 3 3...
id 1 2 3 4 5 6 7 8 9...

然后对id开权值线段树, lower_boundupper_bound 查一下和$s_i$相等的id区间$[l, r)$, 然后分别从$[1, l-1]$, $[l, r)$, $[r, tot]$转移即可.

复杂度$O(n \log n)$

代码
const int MAXN = 1e6+10;

int t, n, L, R, tot;
int a[MAXN], c[MAXN], s[MAXN], dp[MAXN];
int id[MAXN];

struct Idx {
	int val, id;
	bool operator < (const Idx &I) const {
		return val < I.val;
	}
} b[MAXN];

struct Node {
	int l, r, mid, mx;
} tree[MAXN << 2];

void build(int u, int l, int r) {
	tree[u] = {l, r, (l+r) >> 1, -INTINF};
	if (l == r)
		return;
	build(LCH(u), l, tree[u].mid);
	build(RCH(u), tree[u].mid + 1,r);
}

void update(int u, int l, int x) {
	if (tree[u].l == tree[u].r)
		tree[u].mx = x;
	else {
		if (l <= tree[u].mid)
			update(LCH(u), l, x);
		else
			update(RCH(u), l, x);
		tree[u].mx = max(tree[LCH(u)].mx, tree[RCH(u)].mx);
	}
}

int query(int u, int l, int r) {
	if (tree[u].l == l && tree[u].r == r)
		return tree[u].mx;
	else if (r <= tree[u].mid)
		return query(LCH(u), l, r);
	else if (l > tree[u].mid)
		return query(RCH(u), l, r);
	else
		return max(query(LCH(u), l, tree[u].mid), query(RCH(u), tree[u].mid + 1, r));
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &L, &R);
		tot = 0;
		b[++tot] = {0, 0};
		for (int i = 1; i <= n; i++) {
			scanf("%d", a + i);
			s[i] = s[i - 1] + a[i];
			b[++tot] = {s[i], i};
		}
		sort(b+1,b+1+tot);
		for (int i = 1; i <= tot; i++)
			id[b[i].id] = i, c[i] = b[i].val;
		build(1, 1, tot);
		int ll=0, rr = -1, l, r;
		dp[0] = 0;
		for(int i = 1; i <= n; i++) {
			dp[i] = -INTINF;
			if(ll < i - R)
				update(1, id[ll], -INTINF), ll++;
			if(rr < i - L)
				++rr, update(1, id[rr], dp[rr]);
			l = lower_bound(c + 1, c + 1 + tot, s[i]) - c;
			r = upper_bound(c + 1, c + 1 + tot, s[i]) - c;
			if(r <= tot)
				dp[i] = max(dp[i], query(1, r,tot ) - 1);
			if(l < r)
				dp[i] = max(dp[i], query(1, l, r - 1));
			if(l > 1)
				dp[i] = max(dp[i], query(1, 1, l - 1) + 1);
		}
		printf("%d\n", dp[n]);
	}
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch