CF每日5题(1500-1600)
545C 贪心 1500
题意：给 n 棵树在一维数轴上的坐标 x i x_i xi ，以及它们的长度 h i h_i hi。现在要你砍倒这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然也不能覆盖其他的树原来的位置，现在求最大可以砍倒的树的数目。
一眼以为是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
分析：
- 连续元素的和 考虑前缀和
- ∑ i = l ra i = s u m r − s u m l − 1= r − ( l − 1 ) s u m r − r = s u m l − 1− ( l − 1 ) \\sum^r_{i=l}a_i=sum_r-sum_{l-1}=r-(l-1) \\\\ sum_r-r=sum_{l-1}-(l-1) ∑i=lrai=sumr−suml−1=r−(l−1)sumr−r=suml−1−(l−1)
所以求出所有 t p i = s u m i − i tp_i=sum_i-i tpi=sumi−i,相等的两个 t p i tp_i tpi可以组成一个好数组
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;}
