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;
}