Codeforces Round #226 (Div. 2) 解题报告

Problem A Bear and Raspberry

题意:水题。找前一天减后一天的差值最大。然后大于c就减去c,否则为0.

代码如下:

Codeforces Round #226 (Div. 2) 解题报告
 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\n", Max-m);
42         else printf("0\n");
43     }
44     return 0;
45 }
View Code

Problem B Bear and Strings

题意:让你找一个字符串中有多少个包含bear的子串。

思路:先递推dp[i]表示到i结束的字符串从i前面几个开始包含bear。然后累加求和就行了。

代码如下:

Codeforces Round #226 (Div. 2) 解题报告
 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\n", ans);
49     }
50     return 0;
51 }
View Code

Problem C Bear and Prime Numbers

题意:有一个数组,定义了一个值f(i)i为素数=数组中有多少个元素能除进i。然后问你一个区间段的f值之和。

思路:先求出所有的f值然后查询。f值得求法是先打一张1E7的素数表,然后每个素数去试除,就ok了。

代码如下:

Codeforces Round #226 (Div. 2) 解题报告
 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\n", num[r]-num[l-1]);
70         }
71     }
72     return 0;
73 }
View Code

Codeforces Round #226 (Div. 2) 解题报告

上一篇:error LNK2001: unresolved external symbol ___CxxFrameHandler3


下一篇:Connecting Physics Bodies