CF每日5题(1500-1600)

545C 贪心 1500

题意：给 n 棵树在一维数轴上的坐标 $x_i$ ，以及它们的长度 $h_i$。现在要你砍倒这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然也不能覆盖其他的树原来的位置，现在求最大可以砍倒的树的数目。
一眼以为是dp，但是感觉处理左右转移很麻烦，瞟了眼题解…是很易懂的贪心…
分析：

• 两边的树向两边倒，不妨碍中间的树
• 中间的树只考虑左右相邻的距离，直观考虑一边倒的情况较好，互不干扰
  • 统一向左倒
  • 不能向左，向右有两种情况
    • 右边的树可以向左倒，倒就完了，我全都要
    • 右边的树不能倒，或可以向右倒，本次的树是否向右倒不影响这俩树的贡献，倒就完了

struct tr
{
	int x,h;
};
void solve(){
	int n;cin>>n;
	vector<tr>t(n+1);
	forr(i,1,n){
		cin>>t[i].x>>t[i].h;
	}
	if(n==1)return cout<<1<<endl,void();
	//t[1]和t[n]向两边倒 一定有贡献
	int ans=0;
	forr(i,2,n-1){
		if(t[i].x-t[i].h>t[i-1].x){
			ans++;//向左倒
			// cout<<i<<'l'<<endl;
		}
		else if(t[i].x+t[i].h<t[i+1].x){//向右倒
			t[i].x+=t[i].h;
			ans++;
			// cout<<i<<'r'<<endl;
		}
	}
	cout<<ans+2<<endl;
}

550C 思维 枚举 1500

100位数，只能用string存
先考虑啥样的数能被8整除
8 16 24 32 40 48… 1000…
发现千位的数一定能被8整除，只考虑低三位数能不能被整除，取s中的数枚举组合，计算量1e6，能过。

void solve(){
	string s;cin>>s;
	int l=s.size();
	string ans;
	forr(i,0,l-1){
		int a=(s[i]-'0');
		forr(j,i+1,l-1){
			int b=(s[j]-'0');
			forr(k,j+1,l-1){
				int c=(s[k]-'0');
				int tp=a*100+b*10+c;
				if(tp%8==0)return cout<<"YES"<<endl<<tp<<endl,void();
			}
			int tpp=(a*10+b);
			if(tpp%8==0)return cout<<"YES"<<endl<<tpp<<endl,void();
		}
		if(a%8==0)return cout<<"YES"<<endl<<a<<endl,void();
	}
	cout<<"NO"<<endl;
}

580B 双指针 1500

简单尺取法水题

struct fri
{
	int m,s;
};

void solve(){
	int n,d;cin>>n>>d;
	vector<fri>f(n+1);
	forr(i,1,n){
		cin>>f[i].m>>f[i].s;
	}
	sort(f.begin()+1,f.end(),[](fri x,fri y){
		return x.m<y.m;
	});
	int sum=0;
	int l=1,r=1,ans=0;
	while (r<=n)
	{
		if(f[r].m-f[l].m<d)
		{
			sum+=f[r].s;
			ans=max(sum,ans);
			// cout<<ans<<endl;
			r++;
		}else sum-=f[l].s,l++;
	}
	cout<<ans<<endl;
}

1398C 前缀和 找规律 1600

分析：

• 连续元素的和 考虑前缀和
• $$\begin{gathered} {\sum }_{i=l}^r{a}_i=su{m}_r-su{m}_{l-1}=r-(l-1) \\ su{m}_r-r=su{m}_{l-1}-(l-1) \end{gathered}$$
  所以求出所有$t{p}_i=su{m}_i-i$,相等的两个$t{p}_i$可以组成一个好数组

void solve(){
	int n;cin>>n;
	string s;cin>>s;
	vector<int>a(n+1),sm(n+1,0),tp(n+1);
	forr(i,1,n){
		a[i]=s[i-1]-'0';
	}
	forr(i,1,n){
		sm[i]=a[i]+sm[i-1];
		tp[i]=sm[i]-i;
	}
	map<int,int>m;
	m[0]=1;
	int ans=0;
	forr(i,1,n)
		ans+=(m[tp[i]]++);//注意两两组合是怎样计数的
	cout<<ans<<endl;
}

550A 思维 暴力 1500

情况要想得全一点
ABA no
AXBXA no
ABBA yes
ABABA yes
BABAB yes
BABA no
分析：

• 先找到AB，枚举每一个AB在的地方，把AB替换成X，再找有没有BA（但是这样会超时
• BABAB发现找两个AB的位置就可以

void solve()
{
    string s;
    cin>>s;
    int len=s.size();
    int ab=s.find("AB");
    if(ab!=-1)//暴力枚举ab
    {
        string tp=s;
        tp.replace(ab,2,"X");
        int ba=tp.find("BA");
        if(ba!=-1)return cout<<"YES"<<endl,void();
    }
    ab=s.rfind("AB");
    if(ab!=-1)//暴力枚举ab
    {
        string tp=s;
        tp.replace(ab,2,"X");
        int ba=tp.find("BA");
        if(ba!=-1)return cout<<"YES"<<endl,void();
    }
    cout<<"NO"<<endl;
}