P15139 [SWERC 2025] Expansion Plan 2 题解

题目传送锚点

在博客园食用更佳

思路

首先，求 \((x,y)\) 和求 \((|x|,|y|)\) 没区别。

所以我们可以先用前缀和处理出 \([l,r]\) 这一段中 \(4\) 和 \(8\) 的个数，再最大化 的使用，最后判断剩下的步数能不能处理掉。

思路有点抽象，不太懂的话是我的问题，不过具体实现可以参考代码注释。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;int n,m,l,r,x,y,z,q,p,a[200001],b[200001];
string s;
signed main()
{ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>n>>m>>s;s=" "+s;//----------前缀和处理-----------for(int i=1;i<=n;++i){a[i]=a[i-1];b[i]=b[i-1];if(s[i]=='4') ++a[i];else ++b[i];}//----------处理询问-------------for(int i=1;i<=m;++i){cin>>l>>r>>x>>y;q=a[r]-a[l-1];		//4的个数p=b[r]-b[l-1];      //8的个数x=abs(x);y=abs(y);if(x>y) swap(x,y);  //使x<y，好处理z=min(x,p);         //最大化8的使用x-=z;               //走了z个对角，所以x-zy-=z;               //y同理p-=z;               //得出剩余的p的个数q+=p;               //现在能走的4联通数if(x+y<=q) cout<<"yes\n";else cout<<"no\n";}return 0;
}