6月2号训练（Codeforces Round 306 (Div. 2)）（待补）

前言：

昨天晚上的训练，昨天下午刚刚打了百度的编程之星大赛，~~已经被题目橄榄了，~~榜上清一色的都是搞oi的中学生大佬，而我想了一下午也才只写了一道题，只能说路阻且长啊。晚上去洗了个澡，就没怎么认真写训练，所以今天来把自己能写的都写了一遍，话不多说，放代码吧。

正文：

比赛链接：Dashboard - Codeforces Round 306 (Div. 2) - Codeforces

A - Two Substrings：

#include<bits/stdc++.h>
using namespace std;
string s;
int a[100005],b[100005];
int main(){int cnt1=0,cnt2=0;cin>>s;for(int i=0;i<s.size()-1;i++){if(s[i]=='A'&&s[i+1]=='B')a[++cnt1]=i;if(s[i]=='B'&&s[i+1]=='A')b[++cnt2]=i;}for(int i=1;i<=cnt1;i++){for(int j=1;j<=cnt2;j++){//	cout<<a[i]<<" "<<b[j]<<endl;if(abs(a[i]-b[j])>1){cout<<"YES";return 0;}}}cout<<"NO";return 0;
}

题目大意就是在字符串中找到不重叠的AB与BA，我们从头到尾扫一遍，标记下每个AB与BA的位置，最后枚举他们的位置，如果存在两个位置差值绝对值大于1就满足，否者就不满足。

B - Preparing Olympiad：

#include <bits/stdc++.h>
typedef long long LL;
LL a[20],b[20];
using namespace std;int main()
{int n,l,r,x,ans=0;LL num,nn,mm;cin>>n>>l>>r>>x;for(int i=1;i<=n;i++)cin>>a[i];for(int i=0;i<(1<<n);i++){num=0;mm=0;nn=0;memset(b,0,sizeof(b));for(int j=0;j<n;j++){if(i&(1<<j)) {num+=a[j+1];b[j+1]=a[j+1];}}sort(b+1,b+1+n);mm=b[n];for(int k=1;k<=n;k++){if(b[k]!=0) {nn=b[k];break;}}if(num<=r&&num>=l&&mm-nn>=x){ans++;//cout<<"num="<<num<<endl<<mm<<endl<<nn<<endl;}}cout<<ans<<endl;return 0;
}

二进制枚举。

C - Divisibility by Eight：

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){cin>>s;for(int i=0;i<s.size();i++){int a=s[i]-48;if(a%8==0){cout<<"YES"<<endl;cout<<a;return 0;	}}for(int i=0;i<s.size();i++){for(int j=i+1;j<s.size();j++){int a=(s[i]-48)*10+(s[j]-48);if(a%8==0){cout<<"YES"<<endl;cout<<a;return 0;	}}}for(int i=0;i<s.size();i++){for(int j=i+1;j<s.size();j++){for(int k=j+1;k<s.size();k++){int a=(s[i]-48)*100+(s[j]-48)*10+(s[k]-48);//cout<<a<<endl;if(a%8==0){cout<<"YES"<<endl;cout<<a;return 0;}}}}cout<<"NO"<<endl;return 0;
}

题目大意是说一串位数最多为100的数（不包含前导零），你可以任意删去一些数，如果你可以通过操作得到能被8整除的数就输出YES，否者输出NO。其实我们只要考虑最多三个数就行了（8*125=1000），只要我们能保证一个数前3（2，1）位能被8整除那么这个数就一定能被8整除。