Codeforces Round#310 div2

C题：这题说的是套娃，如果做题的时候知道是套娃，那就好理解多了

规则1：套娃A可以放到套娃B里面，当且仅当套娃B没有放在其他套娃里面

规则2：套娃A放在套娃B里面，且套娃B没有放在其他套娃里面，那么可以把A从B中拿出来

问我们最少要操作多少次，才能将套娃全部套起来，拆开和组装都算是一次操作

思路：找到序号为1的套娃的哪一组，然后统计该组有多少个套娃是连在1后面，且每次序号都是加1的，那么这些个套娃是不用拆开的。那么剩下的套娃都是要拆开的

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;                   
16 const int INF = 1<<30;
17 /*
18 
19 */
20 int a[100000 + 10];
21 int main()
22 {
23     
24     int n, k, m;
25     int ans;
26     int cnt;
27     while (scanf("%d%d", &n, &k) != EOF)
28     {
29         ans  = cnt = 0;
30         for (int i = 0; i < k; ++i)
31         {
32             scanf("%d", &m);
33             bool flag = false;
34             for (int j = 0; j < m; ++j)
35             {
36                 scanf("%d", &a[j]);
37                 if (a[j] == 1)
38                 {
39                     flag = true;
40                 }
41             }
42             
43             if (flag)
44             {
45                 cnt = 1;
46                 for (int j = 1; j < m; ++j)
47                 {
48                     if (a[j] - 1 == a[j - 1])
49                         cnt++;
50                     else
51                         break;
52                 }
53                 ans += m - cnt;
54                 flag = false;
55             }
56             else
57                 ans += m - 1;
58         }
59         ans += n - cnt;
60         printf("%d
", ans);
61     }
62     return 0;
63 }

View Code

D题：当时的想法是把岛屿按距离下一个的岛屿的距离，从小到大排序，并且将桥的长度也从小到大排序，然后进行贪心，但是问题是

可能贪心的时候，选择了当前的桥A，但是桥B也时候自己（桥A排在桥B前面），但是呢，到下一个岛屿的时候，桥B对它来说，太长了。

例子：三个岛屿，两座桥，按上面那样子贪心是不行的。

1 10

11 16

20 23

10 15

上面的贪心策略，没有考虑到的信息是岛屿自身的长度。仅考虑了岛屿与岛屿之间的距离

我们规定上界是：两个岛屿之间能建立的最长的桥，下界是：最短的桥

我们可以将岛屿按照上界进行排序，然后选择桥的时候，找到第一个大于等于下界的桥即可。这样就不会发生上面所说的那种情况（因为上界是递增的）

还有一点就是STL的lower_bound()函数极端情况下，时间复杂度是O(n)，会超时

可以将桥的长度存到set中，然后用set自带的lower_bound()函数，时间复杂度是O(logn)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;
16 const int INF = 1 << 30;
17 /*
18 
19 */
20 const int N = 200000 + 10;
21 struct Island
22 {
23     LL l, r, upper, lower, id;
24     bool operator<(const Island&rhs)const
25     {
26         return upper < rhs.upper;
27     }
28 }island[N];
29 set<pair<LL, int> > b;
30 int ans[N];
31 int main()
32 {
33     int n, m;
34     LL a;
35     scanf("%d%d", &n, &m);
36     for (int i = 0; i < n; ++i)
37     {
38         scanf("%I64d%I64d", &island[i].l, &island[i].r);
39     }
40     for (int i = 0; i < n - 1; ++i)
41     {
42         island[i].id = i;
43         island[i].lower = island[i + 1].l - island[i].r;
44         island[i].upper = island[i + 1].r - island[i].l;
45     }
46     sort(island, island + n - 1);
47     for (int i = 0; i < m; ++i)
48     {
49         scanf("%I64d", &a);
50         b.insert(make_pair(a, i));
51     }
52     for (int i = 0; i < n - 1; ++i)
53     {
54         set<pair<LL, int> >::iterator iter = b.lower_bound(make_pair(island[i].lower, 0));
55         if (iter == b.end())
56         {
57             puts("No");
58             return 0;
59         }
60         else
61         {
62             if (iter->first <= island[i].upper)
63             {
64                 ans[island[i].id] = iter->second + 1;
65                 b.erase(iter);
66             }
67             else
68             {
69                 puts("No");
70                 return 0;
71             }
72         }
73     }
74     puts("Yes");
75     printf("%d", ans[0]);
76     for (int i = 1; i < n - 1; ++i)
77         printf(" %d", ans[i]);
78     puts("");
79     return 0;
80 }

View Code

E题：

对于向上走的点，那么只有比自己大的x能影响到自己

对于向左走的点，那么只有比自己小的x能影响到自己

用set就行了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;                   
16 const int INF = 1<<30;
17 /*
18 6 5
19 3 4 U
20 6 1 L
21 5 2 U
22 4 3 U
23 2 5 U
24 
25 
26 
27 
28 如果向上走，那么只有比自己大的x[i]向左走能影响到自己
29 如果向左走，那么只有比自己小的x[i]向上走能影响到自己
30 */
31 const int N = 200000 + 10;
32 set<pair<int,int> > s;
33 set<pair<int, int> >::iterator it;
34 int x[N], y[N];
35 int main()
36 {
37     int n, q;
38     char d[2];
39     scanf("%d%d", &n, &q);
40     s.insert(make_pair(0, q+1));
41     s.insert(make_pair(n + 1, q+1));
42     x[0] = y[0] = 0;
43     for (int i = 1; i <= q; ++i)
44     {
45         scanf("%d%d%s", &x[i], &y[i], d);
46         if (d[0] == 'U')
47         {
48             it = s.lower_bound(make_pair(x[i], -1));
49         }
50         else
51         {
52             it = s.upper_bound(make_pair(x[i], q+1));
53             //it-- , 找到比自己小的x
54             it--;
55         }
56         if (it->first == x[i])
57         {
58             printf("0
");
59             continue;
60         }
61         s.insert(make_pair(x[i], i));
62         if (d[0] == 'U')
63         {
64             printf("%d
", y[i] - y[it->second]);
65             //影响是可以传递的
66             y[i] = y[it->second];
67         }
68         else
69         {
70             printf("%d
", x[i] - x[it->second]);
71             x[i] = x[it->second];
72         }
73     }
74     return 0;
75 }

View Code

目标：①div2做4题 ②一次AC，手速快，题意看清