Solution - Codeforces Round 1009 (Div. 3)

Posted on Edited on

Codeforces Round 1009 (Div. 3)

A Draw a Square

Solution

原点到四个角的长度相等即可。

Code

Show Code 
1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
signed main(){
    int t; cin >> t;
    while (t--){
        int l, r, d, u;
        cin >> l >> r >> d >> u;
        cout << (l == r && r == d && d == u ? "YES" : "NO") << endl;
    }
    return 0;
}

B The Third Side

Solution

假设选中了aa和bb（a<ba<b），则xx的取值范围是[b−a+1,a+b−1][b-a+1, a+b-1]，由于a>0a>0，所以xx总是有取值，所以贪心地选取最大的x=a+b−1x=a+b-1即可。答案是∑i=1nai−(n−1)\sum_{i=1}^n a_i - (n - 1)。

时间复杂度O(n)O(n)。

Code

Show Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, A[N], sum;
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        sum = 0;
        for (int i = 1; i <= n; ++i) cin >> A[i], sum += A[i];
        sum -= n-1;
        cout << sum << endl;
    }
    return 0;
}

C XOR and Triangle

Solution

由于异或运算可以看做不进位的加法，或者不退位的减法，所以只要x+yx + y不进位，或者x−yx - y不退位（二进制），那么x⊕yx\oplus y就会和以上两个中某个相等，导致不能构成三角形。而由于不进位和不退位的性质，我们有x−y≤x⊕y≤x+yx - y\leq x\oplus y\leq x + y，所以只要x+yx+y能进位，x−yx-y能退位，就一定能构成三角形。

进位的充要条件是：存在某个xx为11的位，yy的这一位也为11；退位的充要条件是：存在某个xx为00的位，yy的这一位为11。

所以我们只要找到最小的能使x+yx+y进位，x−yx-y退位的yy，并验证是否比xx小就好了。

从低到高遍历xx的数位，遇到第一个00和第一个11设为11，其他设为00即可。

时间复杂度O(log⁡x)O(\log x)。

这个是第一个方法。我们继续观察存在yy的条件，可以发现只要y≠2ky\neq 2^k（第一个11填上就比xx大了）且y≠2k−1y\neq 2^k - 1（第一个00填上就比xx大了）就一定是可以的，且此时只要把比xx最高位小的所有位都设为11即可。

时间复杂度依然是O(log⁡x)O(\log x)。

Code

Show Code 
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
#include<bits/stdc++.h>
#define int unsigned
using namespace std;
const int N = 32;
// int C[N][N];
inline int bitcnt(int x){
    int cnt = 0;
    while (x){
        x -= (x & -x);
        ++cnt;
    }
    return cnt;
}
inline int larger(int x){
    for (int i = 0; i < 32; ++i){
        if (x <= (1 << i)){
            return ((1 << i - 1) - 1);
        }
    }
    assert(true);
}
// inline void init(){
//     for (int i = 0; i < N; ++i){
//         for (int j = 0; j <= i; ++j){
//             if (i == 0 || j == 0 || i == j) C[i][j] = 1;
//             else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
//             printf("C %d %d = %d\n", i, j, C[i][j]);
//         }
//     }
// }
signed main(){
    // init();
    int t; cin >> t;
    while (t--){
        int x; cin >> x;
        // cout << ":::";
        if (bitcnt(x) == 1 || bitcnt(x + 1) == 1){
            cout << -1 << endl;
        }else{
            cout << larger(x) << endl;
        }
    }
    return 0;
}

D Counting Points

Solution

发现m≤2e5m\leq 2e5，所以横坐标可以枚举。开一个map，记录每个横坐标对应的纵坐标最大值即可。

时间复杂度O(mlog⁡m)O(m\log m)。

Code

Show Code 
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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 2e5 + 1;
int n, m;
struct node{
    int x, r;
} G[N];
map<int, int> mp;
signed main(){
    int t; cin >> t;
    while (t--){
        LL ans = 0;
        cin >> n >> m;
        mp.clear();
        for (int i = 1; i <= n; ++i){
            cin >> G[i].x;
        }
        for (int i = 1; i <= n; ++i){
            cin >> G[i].r;
        }
        for (int i = 1; i <= n; ++i){
            for (int x = G[i].x - G[i].r, y = 0; x <= G[i].x + G[i].r; ++x){
                while (LL(y + 1) * (y + 1) + LL(x - G[i].x) * (x - G[i].x) <= LL(G[i].r) * G[i].r)
                    ++y;
                while (LL(y) * y + LL(x - G[i].x) * (x - G[i].x) > LL(G[i].r) * G[i].r)
                    --y;
                // printf("x = %d, y = %d, i = %d, x0 = %d, r = %d\n",x,y,i,G[i].x,G[i].r);
                if (mp[x] < y * 2 + 1){
                    ans += y * 2 + 1 - mp[x];
                    mp[x] = y * 2 + 1;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

E Empty Triangle

Solution

难得的交互题，我还以为有什么玄机。。

开局先随便问一个三角形，每次中间给一个点，那么我们就获得了三个小的三角形，每个三角形期望上都有1/31/3的点。所以我们每次随机选择两个外点和中间那个点询问，期望上只要O(log⁡3n)O(\log_3 n)次就可以问出来了，他给我们问75次，稳得很呐。

Code

Show Code 
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
#include<bits/stdc++.h>
using namespace std;
signed main(){
    int t; cin >> t;
    while (t--){
        srand(time(0));
        int n; cin >> n;
        int x = rand() % (n-2) + 1;
        int y = rand() % (n-x-1) + x + 1;
        int z = rand() % (n-y) + y + 1;
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        cout.flush();
        while (true){
            int now; cin >> now;
            if (now == 0){
                cout << "! " << x << ' ' << y << ' ' << z << endl;
                break;
            }
            int tag = rand() % 3;
            if (tag == 0) x = now;
            else if (tag == 1) y = now;
            else if (tag == 2) z = now;
            cout << "? " << x << ' ' << y << ' ' << z << endl;
        }
    }
    return 0;
}

F Counting Necessary Nodes

Solution

我们先找到最大的可以塞进去的块，发现会把矩形分成9个部分。其中中间的已经处理好了，四个角有两边是贴边的（最大块一定会贴这两个边），四个边有三边都是贴边的（若干个最大块一定会贴住这三个边排放）。

1类块{width=50%}

对于2类块，再次取最大块最多会把它分成一个2类块和两个3类块。

2类块{width=50%}

对于3类块，再次取最大块最多会再产生一个三类块。

3类块{width=50%}

计算并找到最大块是O(log⁡n)O(\log n)的，而且每次递归最大块起码会减少1（我们每次都找到所有最大块），所以3类块的计算复杂度是O(log⁡2n)O(\log^2 n)的，所以2类块的计算复杂度是O(log⁡n×log⁡2n)=O(log⁡3n)O(\log n\times \log^2 n) = O(\log^3 n)的。故总复杂度为O(log⁡3n)O(\log^3 n)，约为80008000，而且跑不满，很稳。

以上只是便于分析复杂度，具体实现方面，我们不需要区别某个块到底属于哪一类，直接每次分成9部分递归处理即可。寻找最大块可以采用沿x, y轴分别寻找再乘起来的方法。

Code

Show Code 
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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 1e6 + 1;
struct node{
    int l, r, len;
    node(int x, int y, int z){
        l = x, r = y, len = z;
    }
};
inline node find(int l, int r){
    int len = 0;
    for (int i = 0; i < 32; ++i){
        if (r - l < (1 << i)){
            len = i - 1;
            break;
        }
    }
    int ll = l, rr = r;
    // printf("find ::: l = %d, r = %d, len = %d\n",l,r,len);
    while (l % (1 << len) != 0) l += (l & -l);
    while (r % (1 << len) != 0) r -= (r & -r);
    if (r - l != (1 << len)){
        --len;
        l = ll, r = rr;
        while (l % (1 << len) != 0) l += (l & -l);
        while (r % (1 << len) != 0) r -= (r & -r);
        if (r - l != (1 << len)) r -= (1 << len);
    }
    // printf("find ::: l = %d, r = %d, len = %d\n",l,r,len);
    return node(l, r, len);
}
inline int Work(int l1, int r1, int l2, int r2){
    // printf("Work %d %d %d %d\n",l1,r1,l2,r2);
    if (l1 == r1 || l2 == r2) return 0;
    if (r1 - l1 == 1) return r2 - l2;
    if (r2 - l2 == 1) return r1 - l1;
    node a = find(l1, r1), b = find(l2, r2);
    if (a.len > b.len){
        swap(a, b);
        swap(l1, l2);
        swap(r1, r2);
    }
    // printf("a = %d %d %d, b = %d %d %d\n",a.l,a.r,a.len,b.l,b.r,b.len);
    int res = 1 << (b.len - a.len);
    res += Work(l1, a.l, l2, b.l);
    res += Work(l1, a.l, b.l, b.r);
    res += Work(l1, a.l, b.r, r2);
    res += Work(a.l, a.r, l2, b.l);
    res += Work(a.l, a.r, b.r, r2);
    res += Work(a.r, r1, l2, b.l);
    res += Work(a.r, r1, b.l, b.r);
    res += Work(a.r, r1, b.r, r2);
    return res;
}
signed main(){
    int t; cin >> t;
    while (t--){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << Work(l1, r1, l2, r2) << endl;
    }
    return 0;
}

G Game With Triangles: Season 2

Solution

题目暗示4003400^3，这一看就是想让我们dp。

首先，我们发现每次选完一个三角形相当于把环分成三个子环，对三个子环进行递归处理，我们理论上来讲就可以dfs计算出最优解，但是这样应该是会超时的（没试过记忆化搜索能不能混过去）。

为了方便，我们调整一下编号，按0,1⋯n−10, 1\cdots n - 1编号。确定头和尾，按照顺时针的方向，我们就可以确定一个子环。比如说n=5n=5时，i=3,j=4i=3,j=4确定3,43, 4构成的子环，而i=4,j=3i=4,j=3确定4,0,1,2,34,0,1,2,3构成的子环。

考虑区间dp。f[i][j][1/0][1/0]f[i][j][1/0][1/0]表示i,ji,j确定的子环中，ii选/不选，jj选/不选条件下的最大值。定义max⁡(f[i][j])\max(f[i][j])为max⁡p,q∈{0,1}(f[i][j][p][q])\max_{p, q\in\{0, 1\}}(f[i][j][p][q])。

这里所有关于下标的运算都认为是模意义下的运算。

考虑转移，首先显然有：

f[i][j][0][0]=max⁡(f[i+1][j−1])f[i][j][0][1]=max⁡(f[i+1][j][0][1],f[i+1][j][1][1])f[i][j][1][0]=max⁡(f[i][j−1][1][0],f[i][j−1][1][1])\begin{aligned} f[i][j][0][0] &= \max(f[i+1][j-1])\\ f[i][j][0][1] &= \max(f[i+1][j][0][1], f[i+1][j][1][1])\\ f[i][j][1][0] &= \max(f[i][j-1][1][0], f[i][j-1][1][1]) \end{aligned}

对于f[i][j][1][1]f[i][j][1][1]，有两种情况：

  1. i,ji,j在一个三角形内，则枚举i,ji,j确定子环中的kk，有：

f[i][j][1][1]=max⁡k∈[i+1,j−1]{max⁡(f[i+1][k−1])+max⁡(f[k+1][j−1])+aiajak}f[i][j][1][1] = \max_{k\in [i+1, j-1]}\{\max(f[i+1][k-1])+\max(f[k+1][j-1])+a_ia_ja_k\}

  1. i,ji,j在两个三角形内，则枚举ii所在三角形中最靠近jj的点kk，有：

f[i][j][1][1]=max⁡k∈[i+2,j−3]{f[i][k][1][1]+max⁡(f[k+1][j][0][1],f[k+1][j][1][1])}f[i][j][1][1] = \max_{k\in [i+2, j-3]}\{f[i][k][1][1]+\max(f[k+1][j][0][1],f[k+1][j][1][1])\}

按j−i+1j-i+1从33枚举到nn，枚举ii，再枚举kk，复杂度O(n3)O(n^3)。

Code

Show Code 
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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 401;
int n, A[N];
LL f[N][N][2][2];
inline int mod(int x){
    while (x < 0) x += n;
    while (x >= n) x -= n;
    return x;
}
inline LL g(int x, int y, int z, int t){
    return f[mod(x)][mod(y)][z][t];
}
inline LL maxn(int x, int y){
    return max(max(g(x, y, 0, 0), g(x, y, 1, 0)), 
               max(g(x, y, 0, 1), g(x, y, 1, 1)));
}
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 0; i < n; ++i){
            cin >> A[i];
        }
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
        for (int z = 0; z < 2; ++z) for (int t = 0; t < 2; ++t)
            f[i][j][z][t] = 0;
        for (int len = 3; len <= n; ++len){
            for (int i = 0; i < n; ++i){
                int j = mod(i + len - 1);
                f[i][j][0][0] = maxn(i + 1, j - 1);
                f[i][j][0][1] = max(g(i + 1, j, 1, 1), g(i + 1, j, 0, 1));
                f[i][j][1][0] = max(g(i, j - 1, 1, 1), g(i, j - 1, 1, 0));
                for (int k = mod(i + 1); k != j; k = mod(k + 1)){
                    LL res = A[i] * A[j] * A[k];
                    if (mod(i + 1) != k) res += maxn(i + 1, k - 1);
                    if (mod(k + 1) != j) res += maxn(k + 1, j - 1);
                    f[i][j][1][1] = max(f[i][j][1][1], res);
                    // printf("i = %d, j = %d, k = %d, dd = %lld\n", i, j, k, res);
                }
                for (int k = mod(i + 1); k != j; k = mod(k + 1)){
                    if (mod(k - i) < 2) continue;
                    if (mod(j - k) < 3) break;
                    LL res = g(i, k, 1, 1) + max(g(k + 1, j, 0, 1), g(k + 1, j, 1, 1));
                    f[i][j][1][1] = max(f[i][j][1][1], res);
                }
                // printf("f %d %d = %lld, %lld, %lld, %lld\n", i, j
                //     , g(i, j, 0, 0), g(i, j, 0, 1), g(i, j, 1, 0), g(i, j, 1, 1));
            }
        }
        LL ans = 0;
        for (int i = 0; i < n; ++i) ans = max(ans, maxn(i, i - 1));
        cout << ans << endl;
    }
    return 0;
}/*
3
27
366 942 665 91 390 908 915 531 325 781 51 898 979 867 178 914 742 485 135 530 311 258 517 808 176 914 187
6
1 1 1 1 1 1
6
2 1 2 1 1 1

*/