首页 > 代码库 > Codeforces Round #419 (Div. 2)

Codeforces Round #419 (Div. 2)

1.题目A:Karen and Morning

题意:

给出hh:mm格式的时间,问至少经过多少分钟后,该时刻为回文字符串?

思路:

简单模拟,从当前时刻开始,如果hh的回文rh等于mm则停止累计。否则,根据rh和mm的大小来累计sum,然后hh+1,不断尝试。

技术分享
 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int hh,mm;
 6     char c;
 7     while (cin >> hh >> c >> mm)
 8     {
 9        int sum = 0;
10        bool firsthour = true;
11        while (1)
12        {
13            int rh = hh % 10 * 10 + hh / 10;
14            if (rh == mm) break;
15            else
16            {
17                    if (rh < 60)
18                    {
19                        if (firsthour)
20                        {
21                            firsthour = false;
22                            if (rh >= mm)
23                            {
24                                sum += rh - mm;
25                                break;
26                            }
27                            else
28                            {
29                                sum += 60 - mm;
30                                mm = 0;
31                                hh = (hh + 1) % 24;
32                            }
33                        }
34                        else
35                        {
36                            sum += rh;
37                            break;
38                        }
39                    }
40                    else
41                    {
42                        if (firsthour) sum += 60 - mm,mm=0,firsthour=false;
43                        else sum += 60;
44                        hh = (hh + 1) % 24;
45                    }
46                
47            }
48        }
49        cout << sum << endl;
50     }
51     return 0;
52 }
A. Karen and Morning

2.题目B: Karen and Coffee

题意:

给出n个已知区间,然后询问q个区间,问询问区间中至少被k个已知区间包含的点为几个。

思路:

一开始想着对每个已知区间中的值累加,然后对每次询问[l,r],遍历l——r,妥妥超时~~

然后看了些大神的代码,首先不必要对每个已知区间中的值累加,只要在已知区间的开始和结束的位置做标记,然后对于查询,可以预处理用前缀和来记录1~i满足条件的数目,然后O(1)便能得出答案。还有的巨巨用线段树来维护,至少比O(n)的时间少,应该是O(logn)吧。。。

下面给出巨巨的链接:

线段树实现

前缀和实现

 

Codeforces Round #419 (Div. 2)