500pt:
链接：http://codeforces.com/problemset/problem/385/A
分析：找前一个减后一个差最大的就行
代码：
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
using namespace std;
#define ll long long
const int N = 1000010;
int arr[N];
int n,m;
int main() {
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int maxR = 0;
for(int i =0;i<n-1;i++)
maxR = max(maxR,arr[i]-arr[i+1]);
int ret = 0;
ret = max(ret,maxR-m);
cout<<ret<<endl;
}
return 0;
}
1000pt:
链接：http://codeforces.com/problemset/problem/385/B
分析：找到"bear“，然后计算前后有多少字母，就可以求出有多少组合数，注意要减去重复计算的，复杂度为O(n)
代码：
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
using namespace std;
#define ll long long
int main() {
string s;
while(cin>>s)
{
int n = s.length();
int ret = 0;
int lastb = -1;
for(int i=0;i<n-3;i++)
{
if(s.substr(i,4)=="bear")
{
ret+=(n-(i+3));
ret+=(n-(i+3))*(i-lastb-1);
lastb = i;
}
}
cout<<ret<<endl;
}
return 0;
}
链接：http://codeforces.com/problemset/problem/385/C
分析：在计算质数的时候，可以把f也顺便求出来，如2是质数，那么4,6,8都不是质数，但是如果输入中有4,6,8的话，那么他们就可以被2这个质数整除
另外，像这种有m个query的题目，题目给定left和right，一般都处理成[0,i]的的结果，这样在求答案的时候只要[0.right]-[0,left]就行，而不用再去遍历求解，复杂度降低了
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
const int maxN = 10000010;
bool prime[maxN];
int cnt[maxN];
int inputNumber[maxN];
int n,m;
void solve()
{
memset(prime,true,sizeof(prime));
prime[0]=prime[1]=0;
for(int i=2;i<maxN;i++)
{
if(prime[i])
{
for(int j=i;j<maxN;j+=i)
{
cnt[i]+=inputNumber[j];
prime[j]=false;
}
}
}
for(int i=2;i<maxN;i++)
cnt[i]+=cnt[i-1];
}
int main() {
cin>>n;
int a;
memset(inputNumber,0,sizeof(inputNumber));
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++)
{
cin>>a;
inputNumber[a]++;
}
solve();
int m;
cin>>m;
while(m--)
{
int li,ri;
cin>>li>>ri;
if(li>maxN)
li = maxN-1;
if(ri>maxN)
ri = maxN-1;
cout<<cnt[ri]-cnt[li-1]<<endl;
}
return 0;
}