[C++知识库]C. Binary String（二分）C. Rooks Defenders(set + 二分)

Binary String

题意：

给定一个01字符串，从头删任意个字符，从末尾删任意个字符，问max(剩下的0的数量，删除的1的数量）最小是多少

思路：

首先想到，枚举留下的字符串区间 [ l, r ] ，?对于每个l,枚举r利用前缀和与后缀和求出枚举区间剩下的0的数量和删除的1的数量，求最小，

很显然这样会超时，考虑如何优化，仔细观察可以看出，在枚举r的过程中，如果此时 剩下的0的数量>删除的1的数量，那么我们此时的r如果再向右扩展的话，剩下的0的数量只可能增加，删除的1的数量只可能减少，那么答案显然就不是最优的了，反之，如果此时 剩下的0的数量>删除的1的数量，r向左扩展答案也不是最优的。因此，根据这一性质对于每个 l 我们二分查找最优的r

注意二分写法

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e5+7;
ll pre0[N],pre1[N],hou[N];
ll solve(){
	string s;
	ll sum0=0,sum1=0;
	cin>>s;
	s=' '+s;
	ll n=s.size()-1;
	for(ll i=1;i<=n;i++){
		if(s[i]=='0') sum0++;
		else sum1++;
		pre0[i]=sum0;
		pre1[i]=sum1;
	}
	sum1=0;
	for(ll i=n;i>=1;i--){
		if(s[i]=='1') sum1++;
		hou[i]=sum1;
	}
	hou[n+1]=0;
	ll l,r,mid,ans=N*N;
	for(ll i=1;i<=n;i++){
		l=i-1,r=n; 
		while(l<r){ 
			mid=(l+r)/2;  
			if(pre0[mid]-pre0[i-1]>=pre1[i-1]+hou[mid+1]) //求第一个满足该条件的r  
				r=mid;
			else
				l=mid+1;
		}
		//等同于第一种，l为终点 
//		while(l<r){   
//			mid=(l+r+1)/2;  
//			if(pre0[mid]-pre0[i-1]>pre1[i-1]+hou[mid+1])  
//				r=mid-1;
//			else
//				l=mid;
//		}
		
		ans=min(ans,max(pre0[r]-pre0[i-1],pre1[i-1]+hou[r+1]));
	}
	return ans;
	
	
	
}
int main()
{
	ll t;
	cin>>t;
	while(t--){
		cout<<solve()<<endl;
	}
	
	
	return 0;
} 

Rooks Defenders

题意; 有一个n*n的矩阵，q次询问，询问有三种类型，

1， 在（x1,y1) 处放置车（保证此前无车），

2，撤销（x1,y1)处的车 （保证此前有车）

3， 若对于每一个(x,y)都被攻击到则输出Yes,否则输出No（其中?x1 < = x <= x2 , y1 <= y <= y2 ）?

（车可以攻击同行同列的网格）

题解：首先想到对于要判断的子矩阵，若所有的行都被攻击或所有的列都被攻击，则所以的网格都被攻击完，反之则没有，

考虑如何优化，设置两个set集合别存未被攻击到的行和列，然后二分查找第一个大于x1的s1，若

s1 > x2?则说明 x1 - x2之间的行都会被攻击到，列也是如此

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+7;
set<ll>st1,st2;
ll cnt1[N],cnt2[N];
int main()
{
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	ll n,q,t,m,num,x1,y1,x2,y2,s1,s2;
	cin>>n>>q;
	for(ll i=1;i<=n+1;i++){
		st1.insert(i);
		st2.insert(i);
	} 
	while(q--){
		cin>>t;
		if(t==1){
			cin>>x1>>y1;
			if(!cnt1[x1]) st1.erase(x1);
			if(!cnt2[y1]) st2.erase(y1);
			cnt1[x1]++;
			cnt2[y1]++;
		}
		else if(t==2){
			cin>>x1>>y1;
			cnt1[x1]--;
			cnt2[y1]--;
			if(!cnt1[x1]) st1.insert(x1);
			if(!cnt2[y1]) st2.insert(y1); 
		}
		else{
			cin>>x1>>y1>>x2>>y2;
			s1=*st1.lower_bound(x1);
			s2=*st2.lower_bound(y1);
			if(s1>x2||s2>y2) puts("Yes");
			else puts("No");
		}
	} 
	
	return 0;
} 

注意: 不加?std::ios::sync_with_stdio(false); std::cin.tie(nullptr);? 用 cin 会超时...

????????????