前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #Pi (Div. 2)

Codeforces Round #Pi (Div. 2)

作者头像
熙世
发布2019-07-15 16:27:05
3260
发布2019-07-15 16:27:05
举报
文章被收录于专栏:Code思维奇妙屋

上次比完赛就准备写了, 结果懒癌发作了, 拖到了现在。

Problem_A:

题意:

  在一条x轴上有n座城市, 每个城市之间的距离就是它们对应坐标的距离, 现在求出每个城市到其他城市的最近距离和最远距离。

思路:

  最远的必然在最左右端点产生, 因为没有比它们还远的城市了。

  最近的必然在相邻左右端点产生,因为有没比它们还近的城市了。

  比较下即可, 注意处理最左右端点时的情况。

代码:

代码语言:javascript
复制
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 100010
22 #define dd cout<<"debug"<<endl
23 #define p(x) cout<<x<<endl
24 int n;
25 int x[MAXN];
26 
27 int main()
28 {
29     scanf("%d", &n);
30     for(int i = 0; i < n; i ++)
31         scanf("%d", &x[i]);
32     for(int i = 0; i < n; i ++)
33     {
34         if(i == 0)
35             printf("%d ", x[i + 1] - x[i]);
36         else if(i == n - 1)
37             printf("%d ", x[i] - x[i- 1]);
38         else 
39             printf("%d ", min(x[i] - x[i - 1], x[i + 1] - x[i]));
40 
41         if(i == n - 1)
42             printf("%d\n", x[i] - x[0]);
43         else if(i == 0)
44             printf("%d\n", x[n - 1] - x[i]);
45         else 
46             printf("%d\n", max(x[i] - x[0], x[n - 1] - x[i]));
47     }
48     return 0;
49 }

Problem_B:

题意:

  一个图书馆中有一个记录人员进出的机器, 现在你根据这台机器的进出记录计算一下这图书馆能容纳的最小人数。

  图书馆的机器不是24小时开启, 这意味着有可能在它开机之前就有人进入图书馆并且在它开机后出去。

思路:

  计算图书馆进出记录中, 同时有多少人在里面, 如果有人出来, 并且没有进入记录, 那么他在之前就已经进去, 这时候最小容纳人数需 + 1。

代码:

代码语言:javascript
复制
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 1000010
22 #define dd cout<<"debug"<<endl
23 #define p(x) cout<<x<<endl
24 int n;
25 bool in_r[MAXN];
26 
27 int main()
28 {
29     int in = 0, out = 0;
30     int max_in = 0;
31     scanf("%d", &n);
32     getchar();
33     memset(in_r, false, sizeof(in_r));
34     for(int i = 0; i < n; i ++)
35     {
36         char ch;
37         int r;
38         scanf("%c %d", &ch, &r);
39         getchar();
40         if(ch == '+')
41         {
42             in_r[r] = true;
43             in ++;
44             if(in > max_in) max_in = in;
45         }
46         else if(ch == '-')
47         {
48             if(in_r[r] == false)
49             {
50                 max_in ++;
51             }
52             else 
53             {
54                 in_r[r] = false;
55                 in --;
56             }
57         }
58     }
59     printf("%d\n", max_in);
60     return 0;
61 }

Problem_C:

题意:

  给n个数, 一个公比k。

  问数列中有多少个三元集满足 是一个公比为k的等比数列。集合中的顺序不能交换, 即只能根据给定的顺序计算。

思路:

  枚举中值bk, 计算在它之前有多少个b, 在它之后又多少个bk^2, 则这个中值的贡献值为这两个数之积。

  hash,map均可。

代码:

代码语言:javascript
复制
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 200010
22 #define dd cout<<"debug"<<endl
23 #define p(x) cout<<x<<endl
24 int n;
25 LL k;
26 LL ans;
27 LL x[MAXN];
28 LL l_num[MAXN], r_num[MAXN];
29 map<LL, LL> m;
30 void cal_right()
31 {
32     m.clear();
33     for(int i = n - 1; i >= 0; i --)
34     {
35         map<LL, LL>::iterator m_ = m.find(x[i] * k);
36         if(m_ != m.end())
37             r_num[i] = m[x[i] * k];
38         m[x[i]] ++;
39     }
40 }
41 void cal_left()
42 {
43     m.clear();
44     ans = 0;
45     for(int i = 0; i < n; i ++)
46     {
47         if(x[i] % k == 0)
48         {
49             map<LL, LL>::iterator m_ = m.find(x[i] / k);
50             if(m_ != m.end())
51                 l_num[i] = m[x[i] / k];
52         }
53         m[x[i]] ++;
54     }
55 }
56 
57 int main()
58 {
59     scanf("%d %lld", &n, &k);
60     for(int i = 0; i < n; i ++)
61         scanf("%lld", &x[i]);
62     cal_right();
63     cal_left();
64     for(int i = 0; i < n; i ++)
65         ans = ans + l_num[i] * r_num[i];
66     printf("%lld\n", ans);
67     return 0;
68 }

Problem_D:

题意:

  给你一段长度为n的区间, 你在这区间内放置k只船只,每只船只的长度为a, 每两只船不能接触。

  你的朋友告诉你一些点是不能放置船只的, 你来判断你的朋友说的是否为真话。

  如果为假, 则输出你的朋友说出来的第几个点是不满足放置k只船只的。

思路:

  每得到一个点, 就将整个区间的划分数 + 1, 计算每次划分是否满足题意即可。

  划分之后的放置船只数 = 总的划分数 - 这个点所在最小区间的放置数 + 将这个区间划分后所形成的两个新区间的放置数。

代码:

代码语言:javascript
复制
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 1000000
22 #define dd cout<<"debug"<<endl
23 #define p(x) cout<<x<<endl
24 int n, k, a;
25 int m;
26 set <int> s;
27 
28 int main()
29 {
30     scanf("%d %d %d", &n, &k, &a);
31     scanf("%d", &m);
32     s.insert(0);
33     s.insert(n + 1);
34     int ans = (n + 1) / (a + 1);
35     int ans_id = -1;
36     for(int i = 0; i < m; i ++)
37     {
38         int x;
39         scanf("%d", &x);
40         if(ans < k) continue;
41         s.insert(x);
42         set <int>::iterator s_ = s.find(x);
43         int l = *(-- s_);
44         int r = *(++ (++ s_));
45         //p(l),p(r),p(ans);
46         ans = ans - (r - l) / (a + 1);
47         ans = ans + (x - l) / (a + 1) + (r - x) / (a + 1);
48         //p((r - l) / (a + 1)),p((x - l) / (a + 1)),p((r - x) / (a + 1)),p("\n");
49         if(ans < k) ans_id = (i + 1);
50     }
51     printf("%d\n", ans_id);
52     return 0;
53 }

太阳出来了, 看着朝阳升起也是一种不错的体验, very nice.

没有做的题待搞懂做完后再将题解加进来吧~

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-08-11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档