codeforces B. Ilya and Queries 解题报告

题目链接:http://codeforces.com/problemset/problem/313/B

题目意思:给出一个只有 "."  和  "#" 组成的序列s,问当给定一个区间 [li,?ri] 时,si?=?si?+?1(".." 或者 "##")的个数。(li?≤?i?<?ri

 

  直接做绝对会超时,所以需要离线处理。开一个不比?105小的数组,存储当前得到的最多si?=?si?+?1的数量。感觉上有点像DP的思想......

      最后根据给定的 l  和 r,数组下标为 r-1 的数量 - 数组下标为 l-1 的数量即可(数组下标从0开始)

    

codeforces   B. Ilya and Queries  解题报告
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 1e5 + 10;
 8 int cnt[maxn];
 9         
10 int main()
11 {
12     int i, m, l, r, c;
13     string s, tmp;
14     cin >> s;
15     l = s.size();
16     memset(cnt, 0, sizeof(cnt));
17     c = 0;
18     for (i = 0; i+1 < l; i++)
19     {
20         tmp = s.substr(i, 2);
21         if (tmp == ".." || tmp == "##")
22             c++;
23         cnt[i+1] = c;
24     }
25     scanf("%d", &m);
26     for (i = 0; i < m; i++)
27     {
28         scanf("%d%d", &l, &r);
29         printf("%d\n", cnt[r-1]-cnt[l-1]);      
30     }    
31     return 0;
32 }
33     
codeforces   B. Ilya and Queries  解题报告

codeforces B. Ilya and Queries 解题报告

上一篇:AngularJS的核心对象angular上的方法全面解析(AngularJS全局API)


下一篇:根据日期推算星期和历法由来