Codeforces Round #844 (Div. 1 + Div. 2)

A. Parallel Projection

枚举一下选择的边界点即可。复杂度 \(O(t(w+d))\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 100007

inline void work() {
int w = rd(), d = rd(), h = rd();
int a = rd(), b = rd(), f = rd(), g = rd();
int ans = 1e9;
auto calc = [&](int x, int y) {
ans = min(ans, h + abs(a - x) + abs(b - y) + abs(f - x) + abs(g - y));
};

for (int i = 0; i <= d; ++i) {calc(0, i); calc(w, i);}
for (int i = 0; i <= w; ++i) {calc(i, 0); calc(i, d);}

printf("%d\n", ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

B. Going to the Cinema

\(a_i\) 升序排序,显然去的人会是一个前缀。

枚举去了 \(k\) 个,只需要检查第 \(k\) 个人和第 \(k+1\) 个人。复杂度 \(O(n\log n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 200007

int a[N];

inline void work() {
int n = rd();
for (int i = 1; i <= n; ++i) a[i] = rd();
sort(a + 1, a + 1 + n); a[n + 1] = 1e9;
int ans = (a[1] > 0);
for (int i = 1; i <= n; ++i) {
if (i > a[i] && i < a[i + 1]) ++ans;
}
printf("%d\n", ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

C. Equal Frequencies

枚举用了多少个字符,然后选出现次数最多的那几个即可。好一点的实现可以复杂度 \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 200007

char s[N], t[N];

int n, cnt[26], rem[26], id[26];

vector<char> add;

inline int calc(int m) {
int ret = n;
for (int i = 0; i < m; ++i) ret -= min(n / m, cnt[i]);
return ret;
}

inline void work() {
n = rd();
scanf("%s", s + 1);
for (int i = 0; i < 26; ++i) cnt[i] = rem[i] = 0;
for (int i = 1; i <= n; ++i) ++cnt[s[i] - 'a'];
for (int i = 0; i < 26; ++i) id[i] = i;

sort(id, id + 26, [&](int a, int b) {return cnt[a] > cnt[b];});
sort(cnt, cnt + 26, [&](int a, int b) {return a > b;});
int ans = 1e9, res = 1;
for (int i = 1; i <= 26; ++i)
if (n % i == 0) {
int ret = calc(i);
if (ret < ans) {ans = ret; res = i;}
}

for (int i = 0; i < res; ++i) rem[id[i]] = n / res;
printf("%d\n", ans);
for (int i = 1; i <= n; ++i) {
if (rem[s[i] - 'a']) {--rem[s[i] - 'a']; t[i] = s[i];}
else t[i] = 0;
}
add.clear();
for (int i = 0; i < res; ++i)
if (rem[id[i]]) for (int j = 1; j <= rem[id[i]]; ++j) add.push_back(id[i] + 'a');
for (int i = 1; i <= n; ++i)
if (t[i] == 0) {t[i] = add.back(); add.pop_back();}
t[n + 1] = '\0';
puts(t + 1);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

D. Many Perfect Squares

给定 \(n\ (n\le 50)\) 个数 \(a_1,\dots,a_n\) ,求: \[ \max_{0\le x\le 10^{18}} \sum_{i=1}^n [ \exists t \in \mathbb{N}, x+a_i=t^2] \]

答案至少为 \(1\) ,考虑答案 \(\ge 2\) 时,枚举答案包含的某两个 \(a_i,a_j\ (a_i\le a_j)\) ,则 \(x\) 要满足: \[ \left\{ \begin{array}{l} x+a_i=t_1^2 \\ x+a_j=t_2^2 \end{array} \right. \Rightarrow a_j-a_i=t_2^2-t_1^2=(t_2+t_1)(t_2-t_1) \] 对于一组 \((a_i,a_j)\) 只有因数个数级别的可能,因此总共需尝试的 \(x\) 只有 \(O(n^2 \sqrt[3]{\max a_i-a_j})\) 个数。

复杂度 \(O(n^2\sqrt{\max \Delta}+n^3\sqrt[3]{\max \Delta})\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 57

int a[N], ans;

unordered_map<ll, bool> vis;

inline void work() {
int n = rd();
ans = 1; vis.clear();
for (int i = 1; i <= n; ++i) a[i] = rd();

auto issqr = [&](ll x) {
ll rt = sqrt(x);
for (ll i = rt - 2; i <= rt + 2; ++i)
if (i * i == x) return true;
return false;
};

auto test = [&](ll x) {
int cnt = 0;
for (int i = 1; i <= n; ++i) cnt += issqr(a[i] + x);
return cnt;
};

for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
int x = a[j] - a[i];
int lim = sqrt(x);
for (int d = 1; d <= lim; ++d)
if (x % d == 0) {
int t = x / d - d;
if (t & 1) continue;
t >>= 1;
ll tar = 1ll * t * t - a[i];
if (tar < 0) break;
if (vis[tar]) continue;
vis[tar] = true;
ans = max(ans, test(tar));
}
}
printf("%d\n", ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

E. Rectangle Shrinking

只有一行则面积不会变小:按照左端点排序,依次处理,将左端点增大到此前区间最靠右的位置之后即可。

对于两行,先把高度是 \(2\) 的矩形按照上述方法处理后,不再有交。

然后两行分别考虑,找出来所有该行有覆盖的矩形,按照左端点排序,然后扫描:

如果当前块 \([l_i,r_i]\) 是两行的:

  • 如果在这一行被完全包含,则删掉当前块这一行的部分即可。
  • 否则将前面的所有区间右端点改为 \(<l_i\) 。因为前面的操作保证高度是 \(2\) 的不交,所以只会改高度是 \(1\) 的,而每个块显然至多只会因为这个操作被修改一次,所以复杂度没问题。

如果当前块 \([l_i,r_i]\) 是一行的:

  • 如果被完全包含,直接删掉。
  • 否则将左端点增大到此前区间最靠右的位置之后。

很容易发现面积不会变小,都修改完之后算面积即可。

复杂度 \(O(n\log n)\) 。其实代码大段复制粘贴也不难写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))

inline T rd() {
T x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 200007

vector<int> s;

struct node {int u, d, l, r;} c[N];

inline void work() {
int n = rd();
for (int i = 1; i <= n; ++i) {
c[i].u = rd(); c[i].l = rd(); c[i].d = rd(); c[i].r = rd();
}

// u = 1 && d = 2
s.clear();
for (int i = 1; i <= n; ++i) if (c[i].u == 1 && c[i].d == 2) s.pb(i);
sort(all(s), [&](int a, int b){return c[a].l == c[b].l ? c[a].r < c[b].r : c[a].l < c[b].l;});
int r = 0;
for (auto x : s) {
if (c[x].r <= r) c[x] = (node){0, 0, 0, 0};
else {c[x].l = max(c[x].l, r + 1); r = c[x].r;}
}

// u = 1
s.clear();
for (int i = 1; i <= n; ++i) if (c[i].u == 1) s.pb(i);
sort(all(s), [&](int a, int b){return c[a].l == c[b].l ? c[a].r < c[b].r : c[a].l < c[b].l;});
r = 0;
for (int i = 0, lim = (int)s.size(), ptr = 0; i < lim; ++i) {
int x = s[i];
if (c[x].d == 2) {
if (r >= c[x].r) c[x].u = 2;
else {
for (; ptr < i; ++ptr)
if (c[s[ptr]].r >= c[x].l) c[s[ptr]].r = c[x].l - 1;
r = c[x].r;
}
} else {
if (c[x].r <= r) c[x] = (node){0, 0, 0, 0};
else {c[x].l = max(c[x].l, r + 1); r = c[x].r;}
}
}

// d = 2
s.clear();
for (int i = 1; i <= n; ++i) if (c[i].d == 2) s.pb(i);
sort(all(s), [&](int a, int b){return c[a].l == c[b].l ? c[a].r < c[b].r : c[a].l < c[b].l;});
r = 0;
for (int i = 0, lim = (int)s.size(), ptr = 0; i < lim; ++i) {
int x = s[i];
if (c[x].u == 1) {
if (r >= c[x].r) c[x].d = 1;
else {
for (; ptr < i; ++ptr)
if (c[s[ptr]].r >= c[x].l) c[s[ptr]].r = c[x].l - 1;
r = c[x].r;
}
} else {
if (c[x].r <= r) c[x] = (node){0, 0, 0, 0};
else {c[x].l = max(c[x].l, r + 1); r = c[x].r;}
}
}

int tot = 0;
for (int i = 1; i <= n; ++i) {
if (c[i].u > c[i].d || c[i].l > c[i].r) c[i] = (node){0, 0, 0, 0};
if (c[i].u) tot += (c[i].d - c[i].u + 1) * (c[i].r - c[i].l + 1);
}
printf("%d\n", tot);
for (int i = 1; i <= n; ++i) printf("%d %d %d %d\n", c[i].u, c[i].l, c[i].d, c[i].r);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}