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

青旅半醒 2022-01-09 06:15 291阅读 0赞

Problem A [Bear and Raspberry][]

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

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Problem B [Bear and Strings][]

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

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

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Problem C [Bear and Prime Numbers][]

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

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

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/shu-xiaohao/p/3533242.html

[Bear and Raspberry]: http://codeforces.com/contest/385/problem/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/c80f1133b68140e69532246f0d8ed50d.png
[Bear and Strings]: http://codeforces.com/contest/385/problem/B
[Bear and Prime Numbers]: http://codeforces.com/contest/385/problem/C