Problem A Bear and Raspberry
题意：水题。找前一天减后一天的差值最大。然后大于c就减去c，否则为0.
代码如下：
1 //2014-01-24-23.22 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cstring> 7 #include <algorithm> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #define MP(a, b) make_pair(a, b) 14 #define PB(a) push_back(a) 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef pair<int ,int> pii; 20 typedef pair<unsigned int, unsigned int> puu; 21 typedef pair<int ,double> pid; 22 typedef pair<ll, int> pli; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 27 int main() 28 { 29 // freopen("in.txt", "r", stdin); 30 31 int n, m, a[110]; 32 while(scanf("%d%d", &n, &m)!=EOF) 33 { 34 for(int i=0; i<n; i++){ 35 scanf("%d", &a[i]); 36 } 37 int Max = 0; 38 for(int i=0; i<n-1; i++){ 39 Max = max(Max, a[i]-a[i+1]); 40 } 41 if(Max-m>0)printf("%d ", Max-m); 42 else printf("0 "); 43 } 44 return 0; 45 }
Problem B Bear and Strings
题意：让你找一个字符串中有多少个包含bear的子串。
思路：先递推dp[i]表示到i结束的字符串从i前面几个开始包含bear。然后累加求和就行了。
代码如下：
1 //2014-01-24-23.22 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cstring> 7 #include <algorithm> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #define MP(a, b) make_pair(a, b) 14 #define PB(a) push_back(a) 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef pair<int ,int> pii; 20 typedef pair<unsigned int, unsigned int> puu; 21 typedef pair<int ,double> pid; 22 typedef pair<ll, int> pli; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 const int LEN = 100000+10; 27 28 int main() 29 { 30 // freopen("in.txt", "r", stdin); 31 32 int len, tag, dp[LEN]; 33 char str[LEN]; 34 while(scanf("%s", str)!=EOF){ 35 len = strlen(str); 36 tag = -1; 37 dp[0] = dp[1] = dp[2] = -1; 38 for(int i=3; i<len; i++){ 39 if(str[i]=='r' && str[i-1]=='a' && str[i-2]=='e' && str[i-3]=='b'){ 40 tag = 3; 41 }else if(tag>=3) tag++; 42 dp[i] = tag; 43 } 44 ll ans = 0; 45 for(int i=0; i<len; i++){ 46 if(dp[i]!=-1)ans+=(i-dp[i]+1); 47 } 48 printf("%I64d ", ans); 49 } 50 return 0; 51 }
Problem C Bear and Prime Numbers
题意：有一个数组，定义了一个值f（i）i为素数=数组中有多少个元素能除进i。然后问你一个区间段的f值之和。
思路：先求出所有的f值然后查询。f值得求法是先打一张1E7的素数表，然后每个素数去试除，就ok了。
代码如下：
1 //2014-01-24-23.22 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cstring> 7 #include <algorithm> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #define MP(a, b) make_pair(a, b) 14 #define PB(a) push_back(a) 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef pair<int ,int> pii; 20 typedef pair<unsigned int, unsigned int> puu; 21 typedef pair<int ,double> pid; 22 typedef pair<ll, int> pli; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 const int MAX = 10000000+10; 27 const int LEN = 1000000+10; 28 bool isprime[MAX]; 29 int tot; 30 int a[LEN], num[MAX], prime[MAX]; 31 32 void makePrime() 33 { 34 // memset(prime, 0, sizeof prime); 35 tot = 0; 36 for(int i=2; i<=MAX; i++){ 37 if(!isprime[i]) prime[tot++] = i; 38 for(int j=0, k; j<tot && (k=i*prime[j])<=MAX; j++){ 39 isprime[k] = true; 40 if(i%prime[j]==0)break; 41 } 42 } 43 } 44 45 int main() 46 { 47 // freopen("in.txt", "r", stdin); 48 makePrime(); 49 int n, q; 50 while(scanf("%d", &n)!=EOF){ 51 for(int i=0; i<n; i++) scanf("%d", &a[i]); 52 for(int i=0; i<n; i++){ 53 for(int j=0; j<tot; j++){ 54 if(prime[j]*prime[j]>a[i])break; 55 if(a[i]%prime[j]==0){ 56 num[prime[j]]++; 57 while(a[i]%prime[j]==0)a[i]/=prime[j]; 58 } 59 } 60 num[a[i]] += (isprime[a[i]]==true?0:1); 61 } 62 for(int i=1; i<MAX; i++) num[i] += num[i-1]; 63 int q, l, r; 64 scanf("%d", &q); 65 for(int i=0; i<q; i++){ 66 scanf("%d%d", &l, &r); 67 l = min(l, MAX-1); 68 r = min(r, MAX-1); 69 printf("%d ", num[r]-num[l-1]); 70 } 71 } 72 return 0; 73 }