codeforces global round5 ABCD题解

A. Balanced Rating Changes

Description

codeforces global round5  ABCD题解

 

 给一个长度位n总和为0的一个序列,要求每个值除以2,对于奇数可以向上取整也阔以向下取整,且最终和依然为0

Solution

codeforces global round5  ABCD题解
 1 #include <algorithm>
 2 #include <cctype>
 3 #include <cmath>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cstring>
 7 #include <iostream>
 8 #include <map>
 9 #include <numeric>
10 #include <queue>
11 #include <set>
12 #include <stack>
13 #if __cplusplus >= 201103L
14 #include <unordered_map>
15 #include <unordered_set>
16 #endif
17 #include <vector>
18 #define lson rt << 1, l, mid
19 #define rson rt << 1 | 1, mid + 1, r
20 #define LONG_LONG_MAX 9223372036854775807LL
21 #define pblank putchar(' ')
22 #define ll LL
23 using namespace std;
24 typedef long long ll;
25 typedef long double ld;
26 typedef unsigned long long ull;
27 typedef pair<int, int> P;
28 int n, m, k;
29 const int maxn = 1e5 + 10;
30 template <class T>
31 inline T read()
32 {
33     int f = 1;
34     T ret = 0;
35     char ch = getchar();
36     while (!isdigit(ch))
37     {
38         if (ch == '-')
39             f = -1;
40         ch = getchar();
41     }
42     while (isdigit(ch))
43     {
44         ret = (ret << 1) + (ret << 3) + ch - '0';
45         ch = getchar();
46     }
47     ret *= f;
48     return ret;
49 }
50 template <class T>
51 inline void write(T n)
52 {
53     if (n < 0)
54     {
55         putchar('-');
56         n = -n;
57     }
58     if (n >= 10)
59     {
60         write(n / 10);
61     }
62     putchar(n % 10 + '0');
63 }
64 template <class T>
65 inline void writeln(const T &n)
66 {
67     write(n);
68     puts("");
69 }
70 int main(int argc, char const *argv[])
71 {
72 #ifndef ONLINE_JUDGE
73     freopen("in.txt", "r", stdin);
74     // freopen("out.txt", "w", stdout);
75 #endif
76     n = read<int>();
77     int f = 0;
78     for (int i = 0; i < n; i++)
79     {
80         int x = read<int>();
81         if (x & 1)
82         {
83             if (f)
84                 writeln(x >> 1);
85             else
86                 writeln((x + 1) >> 1);
87             f ^= 1;
88         }
89         else
90             writeln(x >> 1);
91     }
92     return 0;
93 }
View Code

 

B. Balanced Tunnel

Description

给两个长度为n的隧道汽车序列,以第一序列为基准,第二序列里有多少汽车超了车。

Solution

将第一序列里元素的顺序映射到第二序列,对于第二序列里的每一个值,判断其后是否有小于它的值,如有则证明其超了车。

使用一个数组记录右端的最小值,如果v[i]==rmin[i],代表没有超车。

codeforces global round5  ABCD题解
 1 #include <algorithm>
 2 #include <bitset>
 3 #include <cctype>
 4 #include <cmath>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <map>
10 #include <numeric>
11 #include <queue>
12 #include <set>
13 #include <stack>
14 #if __cplusplus >= 201103L
15 #include <unordered_map>
16 #include <unordered_set>
17 #endif
18 #include <vector>
19 #define lson rt << 1, l, mid
20 #define rson rt << 1 | 1, mid + 1, r
21 #define LONG_LONG_MAX 9223372036854775807LL
22 #define pblank putchar(' ')
23 #define ll LL
24 using namespace std;
25 typedef long long ll;
26 typedef long double ld;
27 typedef unsigned long long ull;
28 typedef pair<int, int> P;
29 int n, m, k;
30 const int maxn = 1e5 + 10;
31 template <class T>
32 inline T read()
33 {
34     int f = 1;
35     T ret = 0;
36     char ch = getchar();
37     while (!isdigit(ch))
38     {
39         if (ch == '-')
40             f = -1;
41         ch = getchar();
42     }
43     while (isdigit(ch))
44     {
45         ret = (ret << 1) + (ret << 3) + ch - '0';
46         ch = getchar();
47     }
48     ret *= f;
49     return ret;
50 }
51 template <class T>
52 inline void write(T n)
53 {
54     if (n < 0)
55     {
56         putchar('-');
57         n = -n;
58     }
59     if (n >= 10)
60     {
61         write(n / 10);
62     }
63     putchar(n % 10 + '0');
64 }
65 template <class T>
66 inline void writeln(const T &n)
67 {
68     write(n);
69     puts("");
70 }
71 int v[maxn], a[maxn], rmin[maxn];
72 int main(int argc, char const *argv[])
73 {
74 #ifndef ONLINE_JUDGE
75     freopen("in.txt", "r", stdin);
76     // freopen("out.txt", "w", stdout);
77 #endif
78     n = read<int>();
79     int res = 0;
80     for (int i = 1; i <= n; i++)
81         v[read<int>()] = i;
82     for (int i = 1; i <= n; i++)
83         a[i] = v[read<int>()];
84     rmin[n] = a[n];
85     for (int i = n - 1; i >= 1; i--)
86         rmin[i] = min(rmin[i + 1], a[i]);
87     for (int i = 1; i <= n; i++)
88         if (a[i] != rmin[i])
89             ++res;
90     writeln(res);
91     return 0;
92 }
View Code

 

C1. Balanced Removals (Easier)

Description

给出三维空间中的n个点坐标,每次删掉两个点,输出一个删减序列满足每次删掉的两点构成的立方体内不包含其他未删除的点。

Solution

C1数据范围较小,暴力过的。真的很暴力。O(n^4)

codeforces global round5  ABCD题解
  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 using namespace std;
 24 typedef long long ll;
 25 typedef long double ld;
 26 typedef unsigned long long ull;
 27 typedef pair<int, int> P;
 28 int n, m, k;
 29 const int maxn = 1e5 + 10;
 30 template <class T>
 31 inline T read()
 32 {
 33     int f = 1;
 34     T ret = 0;
 35     char ch = getchar();
 36     while (!isdigit(ch))
 37     {
 38         if (ch == '-')
 39             f = -1;
 40         ch = getchar();
 41     }
 42     while (isdigit(ch))
 43     {
 44         ret = (ret << 1) + (ret << 3) + ch - '0';
 45         ch = getchar();
 46     }
 47     ret *= f;
 48     return ret;
 49 }
 50 template <class T>
 51 inline void write(T n)
 52 {
 53     if (n < 0)
 54     {
 55         putchar('-');
 56         n = -n;
 57     }
 58     if (n >= 10)
 59     {
 60         write(n / 10);
 61     }
 62     putchar(n % 10 + '0');
 63 }
 64 template <class T>
 65 inline void writeln(const T &n)
 66 {
 67     write(n);
 68     puts("");
 69 }
 70 struct point
 71 {
 72     int x, y, z, idx;
 73     point() {}
 74     point(int xx, int yy, int zz, int i) : x(xx), y(yy), z(zz), idx(i) {}
 75 };
 76 vector<point> vec;
 77 inline int judge(const point &now, int cur[][2])
 78 {
 79     if (now.x >= cur[0][0] && now.x <= cur[0][1] && now.y >= cur[1][0] && now.y <= cur[1][1] && now.z >= cur[2][0] && now.z <= cur[2][1])
 80         return 1;
 81     return 0;
 82 }
 83 int vis[maxn];
 84 int main(int argc, char const *argv[])
 85 {
 86 #ifndef ONLINE_JUDGE
 87     freopen("in.txt", "r", stdin);
 88     // freopen("out.txt", "w", stdout);
 89 #endif
 90     n = read<int>();
 91     for (int i = 0; i < n; i++)
 92         vec.emplace_back(read<int>(), read<int>(), read<int>(), i + 1);
 93     for (int u = 1; u <= n >> 1; u++)
 94     {
 95         int sz = vec.size(), f = 0;
 96         for (int i = 0; i != sz && !f; i++)
 97         {
 98             if (vis[i])
 99                 continue;
100             for (int j = i + 1; j != sz && !f; j++)
101             {
102                 if (vis[j])
103                     continue;
104                 int cur[3][2];
105                 cur[0][0] = min(vec[i].x, vec[j].x);
106                 cur[0][1] = max(vec[i].x, vec[j].x);
107                 cur[1][0] = min(vec[i].y, vec[j].y);
108                 cur[1][1] = max(vec[i].y, vec[j].y);
109                 cur[2][0] = min(vec[i].z, vec[j].z);
110                 cur[2][1] = max(vec[i].z, vec[j].z);
111                 int flag = 1;
112                 for (int k = 0; k < sz && flag; k++)
113                     if (k != i && k != j && !vis[k])
114                     {
115                         if (judge(vec[k], cur))
116                             flag = 0;
117                     }
118                 if (flag)
119                 {
120                     write(vec[i].idx), pblank, writeln(vec[j].idx);
121                     f = 1;
122                     vis[i] = vis[j] = 1;
123                 }
124             }
125         }
126     }
127     return 0;
128 }
View Code

 

 

C1. Balanced Removals (Hard)

Description

同上,数据范围加到5e4

Solution

挖坑

 

 

D. Balanced Playlist

Description

给出一个长度为n的循环序列,一个点的答案定义为从当前点开始可以最多往后走多少个点,当且仅当$2a[j] \geq max(a[i],a[i+1],a[j-1])$时才可往下走

Solution

模拟发现可以走完到2*n-1则证明可以无限走。

使用set记录最大值,由于权值并非不同,使用multiset维护。类似滑动窗口

codeforces global round5  ABCD题解
 1 /*
 2     单调队列
 3 */
 4 #include <algorithm>
 5 #include <cctype>
 6 #include <cmath>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 #include <iostream>
11 #include <map>
12 #include <numeric>
13 #include <queue>
14 #include <set>
15 #include <stack>
16 #if __cplusplus >= 201103L
17 #include <unordered_map>
18 #include <unordered_set>
19 #endif
20 #include <vector>
21 #define lson rt << 1, l, mid
22 #define rson rt << 1 | 1, mid + 1, r
23 #define LONG_LONG_MAX 9223372036854775807LL
24 #define pblank putchar(' ')
25 #define ll LL
26 using namespace std;
27 typedef long long ll;
28 typedef long double ld;
29 typedef unsigned long long ull;
30 typedef pair<int, int> P;
31 int n, m, k;
32 const int maxn = 1e5 + 10;
33 template <class T>
34 inline T read()
35 {
36     int f = 1;
37     T ret = 0;
38     char ch = getchar();
39     while (!isdigit(ch))
40     {
41         if (ch == '-')
42             f = -1;
43         ch = getchar();
44     }
45     while (isdigit(ch))
46     {
47         ret = (ret << 1) + (ret << 3) + ch - '0';
48         ch = getchar();
49     }
50     ret *= f;
51     return ret;
52 }
53 template <class T>
54 inline void write(T n)
55 {
56     if (n < 0)
57     {
58         putchar('-');
59         n = -n;
60     }
61     if (n >= 10)
62     {
63         write(n / 10);
64     }
65     putchar(n % 10 + '0');
66 }
67 template <class T>
68 inline void writeln(const T &n)
69 {
70     write(n);
71     puts("");
72 }
73 multiset<int> s;
74 int a[maxn << 2];
75 inline int mx()
76 {
77     return *s.rbegin();
78 }
79 int main(int argc, char const *argv[])
80 {
81 #ifndef ONLINE_JUDGE
82     freopen("in.txt", "r", stdin);
83     // freopen("out.txt", "w", stdout);
84 #endif
85     n = read<int>();
86     for (int i = 1; i <= n; i++)
87         a[i] = a[i + n] = a[i + 2 * n] = read<int>();
88     for (int i = 1, j = 1; i <= n; i++)
89     {
90         if (s.empty())
91             s.emplace(a[i]), j++;
92         while (j - i < 2 * n - 1 && mx() <= 2 * a[j])
93             s.emplace(a[j]), ++j;
94         int res = (j - i >= 2 * n - 1) ? -1 : j - i;
95         write(res), pblank;
96         s.erase(s.find(a[i]));
97     }
98     return 0;
99 }
View Code

 

上一篇:围在栅栏中的爱


下一篇:字符统计2