洛谷P8818 题解-献给第一次CSP-S

Author： Zi_Gao
发布时间：November 5, 2022
53 views
No comments
1570 words
Categories： OI

# PART.0 前言

本文同时可以在洛谷“[Zi_Gao的博客][1]”上查看，后续更新在此不会贴出来。本部分与学术无关，可以略过。

这篇题解是我OI生涯的第一篇题解，献给我的第一次CSP-S。本文中想给大家分享一些考场做题的心路历程，解题思路，以及考场做法策略。可能我的方法并不是最优，甚至可能很差，但大家共同讨论与进步才是最终要的。本文在学术方面可能并不严谨，但确实适用于我这样的蒟蒻做法。

# PART.1 读题

读完题可以找出关键句：“小 L 的目标是使得这个**得分尽可能大**，小 Q 的目标是使得这个**得分尽可能小**。同时两人都是足够聪明的玩家，**每次都会采用最优的策略**。”

这样的关键词句，可以让我们很容易联想到要使用**贪心**等方法时分数达到最大/最小，有了贪心的方向之后，再来看怎么贪心，最容易想到的当然是**L选最大，Q选最小**。那么维护区间的最大/最小值的数据结构有很多，所以**没必要现在就细化实现**， _这也是我爱用的策略，没必要一开始就想太多，这样反而会有畏难情绪_ 。继续看到了**样例及其解释**的部分，第一感觉似乎很复杂，最大最小选法有时并不是最优，其实可以隐约感受到还和**0、最小正数和最大负数有关**，这时就要联系**数据范围**的部分来分享，显然，单次询问的复杂度必须要控制在 $O(\log_{2})$ 以内才行。也就是说我们要可以一开始就“确定”我们要选的数，并不可能一个个的看，这时思路有回到的**贪心**上。注意到数据范围中“特殊性质 1 为：保证 $A_i, B_i > 0$ 。”一句话，那么，选最大最小值肯定可以拿到部分分。并且，**从特殊**出发，编写程序，进而可以引伸**到一般**。

# PART.2 细化

算法基于数据结构，我们一定要熟悉**一个数据结构**、**其解决的问题**以及**其时间复杂度**三者相互映射。这道题我们已经明确了要维护区间的最大/最小值。也就是常说的“**RMQ(Range Minimum/Maximum Query)问题是求区间最值问题**”，与其对应的算法有很多比如：

> **ST表**

> > 解决问题:

> > > 区间**静态**查询最大/最小值等

> > 时间复杂度：

> > > 初始化 **$O(n\log{n})$**

> > > 查询 **$O(1)$**

> **线段树**

> > 解决问题:

> > > 区间**动态**查询/维护最大/最小/和/乘积等

> > 时间复杂度：

> > > 初始化 **$O(n)$**

> > > 查询 **$O(\log{n})$**

> > > 修改 **$O(\log{n})$**

> 树状数组

> > 解决问题:

> > > 区间**动态**查询/维护和/乘积/异或等

> > 时间复杂度：

> > > 初始化 **$O(n)$**

> > > 查询 **$O(\log{n})$**

> > > 修改 **$O(\log{n})$**

显然此题使用**ST表**最优

# PART.3 编码

_ST表不会的同学，出门右转[【模板】ST 表](https://www.luogu.com.cn/problem/P3865)_

## Version 0

根据思路第一版部分分代码诞生

```cpp
#include <cstdio>
#include <algorithm>
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))

struct rmq{
	int f_max[100010][20],f_min[100010][20];
	void build(int n,int *arr){
		register int i,j;
		int k=std::__lg(n);
		for(i=1;i<=n;++i) f_max[i][0]=f_min[i][0]=arr[i];

for(j=1;j<=k;++j)
			for(i=1;i<=(n-(1<<j)+1);++i)
				f_max[i][j]=_max(f_max[i][j-1],f_max[i+((1<<(j-1)))][j-1]),
				f_min[i][j]=_min(f_min[i][j-1],f_min[i+((1<<(j-1)))][j-1]);
		return;
	}

int q_max(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}

int q_min(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}
}L_st,Q_st;

int L_arr[100010],Q_arr[100010];

int read(){
	register int x=0;register char f=0,c=getchar();
	while(c<'0'||'9'<c) f|=(c=='-'),c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return f?-x:x; 
}

int main(){
	register int i,l_1,r_1,l_2,r_2;
	register long long L,Q;
	int n=read();
	int m=read();
	int q=read();

for(i=1;i<=n;++i) L_arr[i]=read();
	for(i=1;i<=m;++i) Q_arr[i]=read();

L_st.build(n,L_arr);
	Q_st.build(m,Q_arr);

for(i=0;i<q;++i){
		l_1=read();
		r_1=read();
		l_2=read();
		r_2=read();
		L=L_st.q_max(l_1,r_1);
		Q=Q_st.q_min(l_2,r_2);

printf("%lld\n",L*Q);
	}

return 0;
}
```

期望40pts

## Version 1

然鹅，这个时候连样例都过不了，顺理成章开启 _面向数据样例_。

样例解释1中可以看出如果在区间内有0的情况需要特殊处理。这个时候我们分别从L和Q的角度来看，L要分尽量大，那么如果我们现在答案是负数，我就肯定用0；从Q的角度看，如果现在的分无论如何是正数，我就用0。

```cpp
#include <cstdio>
#include <algorithm>
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))

struct rmq{
	int f_max[100010][20],f_min[100010][20];
	char have_0[100010][20];
	void build(int n,int *arr){
		register int i,j;
		int k=std::__lg(n);
		for(i=1;i<=n;++i) f_max[i][0]=f_min[i][0]=arr[i],have_0[i][0]=(arr[i]==0);

for(j=1;j<=k;++j)
			for(i=1;i<=(n-(1<<j)+1);++i)
				f_max[i][j]=_max(f_max[i][j-1],f_max[i+((1<<(j-1)))][j-1]),
				f_min[i][j]=_min(f_min[i][j-1],f_min[i+((1<<(j-1)))][j-1]),
				have_0[i][j]=_max(have_0[i][j-1],have_0[i+((1<<(j-1)))][j-1]);
		return;
	}

int q_max(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}

int q_min(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}

int q_have_0(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(have_0[l][k],have_0[r-(1<<k)+1][k]);
	}
}L_st,Q_st;

int L_arr[100010],Q_arr[100010];

int read(){
	register int x=0;register char f=0,c=getchar();
	while(c<'0'||'9'<c) f|=(c=='-'),c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return f?-x:x;
}

int main(){

register int i,l_1,r_1,l_2,r_2;
	register long long L_max,Q_min,ans;
	register char L_have_0,Q_have_0;
	int n=read();
	int m=read();
	int q=read();

for(i=1;i<=n;++i) L_arr[i]=read();
	for(i=1;i<=m;++i) Q_arr[i]=read();

L_st.build(n,L_arr);
	Q_st.build(m,Q_arr);

for(i=0;i<q;++i){
		l_1=read();
		r_1=read();
		l_2=read();
		r_2=read();
		L_max=L_st.q_max(l_1,r_1);
		L_have_0=L_st.q_have_0(l_1,r_1);
		Q_min=Q_st.q_min(l_2,r_2);
		Q_have_0=Q_st.q_have_0(l_2,r_2);
        ans=L_max*Q_min;
		if(L_have_0) ans=_max(ans,0);
		if(Q_have_0) ans=_min(ans,0);
		printf("%lld\n",ans);
	}

return 0;
}
```

期望过样例1

## Version 2

然鹅第二组样例还是过不了，但是观察发现，第二组样例的二次询问时，L不管怎选，Q都可以让分值变成负数，那么L肯定选最小的一个正数，那么也可以是最大的负数，我们再维护这两个值。其实到这大概都有感觉，不可能还有一些其他的东西维护了，就这几个特殊值可以。

```cpp
#include <cstdio>
#include <algorithm>
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))

struct rmq{
	int f_max[100010][20],f_min[100010][20],up0[100010][20],down0[100010][20];
	char have_0[100010][20];
	void build(int n,int *arr){
		register int i,j;
		int k=std::__lg(n);
		for(i=1;i<=n;++i) f_max[i][0]=f_min[i][0]=arr[i],have_0[i][0]=(arr[i]==0),up0[i][0]=(arr[i]>0?arr[i]:0x7FFFFFFF),down0[i][0]=(arr[i]<0?arr[i]:0x80000000);
	
		for(j=1;j<=k;++j)
			for(i=1;i<=(n-(1<<j)+1);++i)
				f_max[i][j]=_max(f_max[i][j-1],f_max[i+((1<<(j-1)))][j-1]),
				f_min[i][j]=_min(f_min[i][j-1],f_min[i+((1<<(j-1)))][j-1]),
				down0[i][j]=_max(down0[i][j-1],down0[i+((1<<(j-1)))][j-1]),
				up0[i][j]=_min(up0[i][j-1],up0[i+((1<<(j-1)))][j-1]),
				have_0[i][j]=_max(have_0[i][j-1],have_0[i+((1<<(j-1)))][j-1]);
		return;
	}

int q_max(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}

int q_min(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}

int q_down0(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(down0[l][k],down0[r-(1<<k)+1][k]);
	}

int q_up0(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(up0[l][k],up0[r-(1<<k)+1][k]);
	}

int q_have_0(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(have_0[l][k],have_0[r-(1<<k)+1][k]);
	}
}L_st,Q_st;

int L_arr[100010],Q_arr[100010];

int read(){
	register int x=0;register char f=0,c=getchar();
	while(c<'0'||'9'<c) f|=(c=='-'),c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return f?-x:x; 
}

int main(){

register int i,l_1,r_1,l_2,r_2;
	register long long L_max,L_min,Q_max,Q_min,L_up0,L_down0,Q_up0,Q_down0,ans,temp;
	register char L_have_0,Q_have_0;
	int n=read();
	int m=read();
	int q=read();

for(i=1;i<=n;++i) L_arr[i]=read();
	for(i=1;i<=m;++i) Q_arr[i]=read();

L_st.build(n,L_arr);
	Q_st.build(m,Q_arr);

for(i=0;i<q;++i){
		l_1=read();
		r_1=read();
		l_2=read();
		r_2=read();
		L_max=L_st.q_max(l_1,r_1);
		L_min=L_st.q_min(l_1,r_1);
		L_have_0=L_st.q_have_0(l_1,r_1);
		L_up0=L_st.q_up0(l_1,r_1);
		L_down0=L_st.q_down0(l_1,r_1);
	
		Q_max=Q_st.q_max(l_2,r_2);
		Q_min=Q_st.q_min(l_2,r_2);
		Q_have_0=Q_st.q_have_0(l_2,r_2);
		Q_up0=Q_st.q_up0(l_2,r_2);
		Q_down0=Q_st.q_down0(l_2,r_2);

ans=0x8000000000000000ll;
		temp=0x7FFFFFFFFFFFFFFFll;
		temp=_min(temp,L_max*Q_max);
		temp=_min(temp,L_max*Q_min);
		if(Q_up0!=0x7FFFFFFFll) temp=_min(temp,L_max*Q_up0);
		if(Q_down0!=(int)(int)0x80000000ll)temp=_min(temp,L_max*Q_down0);
		ans=_max(ans,temp);
	
		temp=0x7FFFFFFFFFFFFFFFll;
		temp=_min(temp,L_min*Q_max);
		temp=_min(temp,L_min*Q_min);
		if(Q_up0!=0x7FFFFFFFll) temp=_min(temp,L_min*Q_up0);
		if(Q_down0!=0x80000000)temp=_min(temp,L_min*Q_down0);
		ans=_max(ans,temp);
	
		if(L_up0!=0x7FFFFFFFll){
			temp=0x7FFFFFFFFFFFFFFFll;
			temp=_min(temp,L_up0*Q_max);
			temp=_min(temp,L_up0*Q_min);
			if(Q_up0!=0x7FFFFFFFll) temp=_min(temp,L_up0*Q_up0);
			if(Q_down0!=(int)0x80000000ll)temp=_min(temp,L_up0*Q_down0);
			ans=_max(ans,temp);
		}
	
		if(L_down0!=(int)0x80000000ll){
			temp=0x7FFFFFFFFFFFFFFFll;
			temp=_min(temp,L_down0*Q_max);
			temp=_min(temp,L_down0*Q_min);
			if(Q_up0!=0x7FFFFFFFll) temp=_min(temp,L_down0*Q_up0);
			if(Q_down0!=(int)0x80000000ll)temp=_min(temp,L_down0*Q_down0);
			ans=_max(ans,temp);
		}
	
		if(L_have_0) ans=_max(ans,0);
		if(Q_have_0) ans=_min(ans,0);
		printf("%lld\n",ans);
	}

return 0;
}
```

期望100pts

# 总结

其实我打这道题的思路还是比较傻的，想到一个值就加进去维护，导致代码冗长，但这也是一种好的策略对我来说。毕竟我可能并没有那个时间和能力去一开始就做出来正解，靠着修修补补的方法也算是打过了。毋庸置疑这是极其耗时的方法，就这样打了2h打了出来，也算是有毅力，但打出来总算是好的。

ps.最终v2的代码是去了freopen的考场上的源码。

此致，献给第一次CSP-S——P8818 [CSP-S 2022] 策略游戏题解报告

[1]: https://www.luogu.com.cn/blog/zi-gao/xian-gei-di-yi-ci-csp-s

Last modification：December 19, 2022

大哥给点钱吧~ヽ(･ω･´ﾒ)(微信支付宝 QQ都是一个码哦～

洛谷P8818 题解-献给第一次CSP-S

Zi_Gao • 2022 年 11 月 05 日

# PART.0 前言

本文同时可以在洛谷“[Zi_Gao的博客][1]”上查看，后续更新在此不会贴出来。本部分与学术无关，可以略过。

# PART.1 读题

# PART.2 细化

> **ST表**

> > 解决问题:

> > > 区间**静态**查询最大/最小值等

> > 时间复杂度：

> > > 初始化 **$O(n\log{n})$**

> > > 查询 **$O(1)$**

> **线段树**

> > 解决问题:

> > > 区间**动态**查询/维护最大/最小/和/乘积等

> > 时间复杂度：

> > > 初始化 **$O(n)$**

> > > 查询 **$O(\log{n})$**

> > > 修改 **$O(\log{n})$**

> 树状数组

> > 解决问题:

> > > 区间**动态**查询/维护和/乘积/异或等

> > 时间复杂度：

> > > 初始化 **$O(n)$**

> > > 查询 **$O(\log{n})$**

> > > 修改 **$O(\log{n})$**

显然此题使用**ST表**最优

# PART.3 编码

_ST表不会的同学，出门右转[【模板】ST 表](https://www.luogu.com.cn/problem/P3865)_

## Version 0

根据思路第一版部分分代码诞生

```cpp
#include <cstdio>
#include <algorithm>
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))

struct rmq{
	int f_max[100010][20],f_min[100010][20];
	void build(int n,int *arr){
		register int i,j;
		int k=std::__lg(n);
		for(i=1;i<=n;++i) f_max[i][0]=f_min[i][0]=arr[i];

for(j=1;j<=k;++j)
			for(i=1;i<=(n-(1<<j)+1);++i)
				f_max[i][j]=_max(f_max[i][j-1],f_max[i+((1<<(j-1)))][j-1]),
				f_min[i][j]=_min(f_min[i][j-1],f_min[i+((1<<(j-1)))][j-1]);
		return;
	}

int q_max(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}

int q_min(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}
}L_st,Q_st;

int L_arr[100010],Q_arr[100010];

int read(){
	register int x=0;register char f=0,c=getchar();
	while(c<'0'||'9'<c) f|=(c=='-'),c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return f?-x:x; 
}

int main(){
	register int i,l_1,r_1,l_2,r_2;
	register long long L,Q;
	int n=read();
	int m=read();
	int q=read();

for(i=1;i<=n;++i) L_arr[i]=read();
	for(i=1;i<=m;++i) Q_arr[i]=read();

L_st.build(n,L_arr);
	Q_st.build(m,Q_arr);

for(i=0;i<q;++i){
		l_1=read();
		r_1=read();
		l_2=read();
		r_2=read();
		L=L_st.q_max(l_1,r_1);
		Q=Q_st.q_min(l_2,r_2);

printf("%lld\n",L*Q);
	}

return 0;
}
```

期望40pts

## Version 1

然鹅，这个时候连样例都过不了，顺理成章开启 _面向数据样例_。

```cpp
#include <cstdio>
#include <algorithm>
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))

int q_max(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}

int q_min(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}

int q_have_0(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(have_0[l][k],have_0[r-(1<<k)+1][k]);
	}
}L_st,Q_st;

int L_arr[100010],Q_arr[100010];

int read(){
	register int x=0;register char f=0,c=getchar();
	while(c<'0'||'9'<c) f|=(c=='-'),c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return f?-x:x;
}

int main(){

register int i,l_1,r_1,l_2,r_2;
	register long long L_max,Q_min,ans;
	register char L_have_0,Q_have_0;
	int n=read();
	int m=read();
	int q=read();

for(i=1;i<=n;++i) L_arr[i]=read();
	for(i=1;i<=m;++i) Q_arr[i]=read();

L_st.build(n,L_arr);
	Q_st.build(m,Q_arr);

return 0;
}
```

期望过样例1

## Version 2

```cpp
#include <cstdio>
#include <algorithm>
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))

int q_max(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}

int q_min(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}

int q_down0(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(down0[l][k],down0[r-(1<<k)+1][k]);
	}

int q_up0(int l,int r){
		int k=std::__lg(r-l+1);
		return _min(up0[l][k],up0[r-(1<<k)+1][k]);
	}

int q_have_0(int l,int r){
		int k=std::__lg(r-l+1);
		return _max(have_0[l][k],have_0[r-(1<<k)+1][k]);
	}
}L_st,Q_st;

int L_arr[100010],Q_arr[100010];

int read(){
	register int x=0;register char f=0,c=getchar();
	while(c<'0'||'9'<c) f|=(c=='-'),c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
	return f?-x:x; 
}

int main(){

register int i,l_1,r_1,l_2,r_2;
	register long long L_max,L_min,Q_max,Q_min,L_up0,L_down0,Q_up0,Q_down0,ans,temp;
	register char L_have_0,Q_have_0;
	int n=read();
	int m=read();
	int q=read();

for(i=1;i<=n;++i) L_arr[i]=read();
	for(i=1;i<=m;++i) Q_arr[i]=read();

L_st.build(n,L_arr);
	Q_st.build(m,Q_arr);

return 0;
}
```

期望100pts

# 总结

ps.最终v2的代码是去了freopen的考场上的源码。

此致，献给第一次CSP-S——P8818 [CSP-S 2022] 策略游戏题解报告

[1]: https://www.luogu.com.cn/blog/zi-gao/xian-gei-di-yi-ci-csp-s

洛谷P8818 题解-献给第一次CSP-S

Leave a Comment Cancel reply
快来发言吧(ﾉ´▽｀)ﾉ♪

简短代码实现网站黑化(夜间模式)

handsome魔改备忘1

在微信打开显示遮罩

检测到微信打开提示"请用浏览器打开"

开往-友链接力handsome侧栏添加修改

Zi-Gao / Linux-Detect Linux系统CPU利用率监控程序

使你的网站更安全吧

P4247 [清华集训2012]序列操作题解

使用phpMyAdmin一键替换头图地址

Windows常用安装包合集

洛谷P8818 题解-献给第一次CSP-S

Leave a Comment Cancel reply 快来发言吧(ﾉ´▽｀)ﾉ♪

洛谷P8818 题解-献给第一次CSP-S

Leave a Comment Cancel reply
快来发言吧(ﾉ´▽｀)ﾉ♪