Codeforces Round 1009 (Div.3)

3月11日 Codeforces 实战记录。

A. Draw a Square

构成正方形，四个数相等。

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    vector<int>a(4);
    for(int i = 0; i < 4; i++) cin >> a[i];

    cout << (*max_element(a.begin(), a.end()) == *min_element(a.begin(), a.end()) ? "Yes" : "No") << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. The Third Side

最优策略，每次选取两条边 $a,b$ 构造最长的第三边 $a + b - 1$ 即可，与操作顺序无关。

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    cout << accumulate(a.begin(), a.end(), 0ll) - (n - 1) << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

C. XOR and Triangle

当 $x$ 的二进制形式为 10...0 或 11...1 时，没有对应的 $y$ 满足条件。

否则，对应构造 01...1 即可。

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int x; cin >> x;

    if(!(x & (x - 1)) || !(x & (x + 1))){
        cout << -1 << '\n';
        return;
    }

    cout << (1 << (31 - __builtin_clz(x))) - 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

D. Counting Points

给出了关键信息：半径之和为 $10^5$ 量级。

那么直接维护每一个 $x$ 坐标对应多少个整点即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, m; cin >> n >> m;
    vector<int>x(n), r(n);
    for(int i = 0; i < n; i++) cin >> x[i];
    for(int i = 0; i < n; i++) cin >> r[i];

    map<int, int>mp;
    for(int i = 0; i < n; i++){
        for(int u = - r[i]; u <= r[i]; u++){
            mp[x[i] + u] = max(mp[x[i] + u], (int)sqrt(r[i] * r[i] - u * u));
        }
    }

    int res = 0;
    for(auto &[k, y] : mp){
        res += 1 + 2 * y;
    }
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

E. Empty Triangle

交互题。

当我们询问三角形 $abc$ 后，假设返回一个 $d$ 点，我们知道，三角形 $abd,\ adc,\ dbc$ 将原来的三角形分为了 3 个部分。我们随机选取一个，就能近似将内含的点数缩小到原来的 $\frac13$，75 次询问，剩下的点的个数期望为 $1500\times(\frac{1}{3})^{75}$，大概在 $10^{-33}$ 量级。基本上可以认为一定能找到 empty triangle 了。

（不准确的估算推导，单从数量级上认为方案完全可行。）

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;

    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, 2);
     
    vector<int>a(3);
    for(int i = 0; i < 3; i++) a[i] = n - i;

    auto query = [&](char op){
        cout << op;
        for(auto &i : a){
            cout << ' ' << i;
        }
        cout << '\n';
        cout.flush();
    };

    query('?');
    int np; cin >> np;
    while(np) {
        a[dis(gen)] = np;
        query('?');
        cin >> np;
    }
     query('!');
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

F. Counting Necessary Nodes

考虑分别从 $x$ 轴方向，$y$ 轴方向，将询问矩形划分为长度区间均满足 $[a\cdot2^k,(a+1)\cdot2^k]$ 的区间。

划分后，对于一块区域，若 $x$ 轴方向上长为 $u$，$y$ 轴方向上长为 $v$。由于 $u, v$ 均为 2 的幂次，按小的为正方形区块边长，就能划分出 $\dfrac{\max(u,v)}{\min(u,v)}$ 个区块了。

时间复杂度 $O(\log^2n)$。

#include<bits/stdc++.h>
using namespace std;

vector<int>lenx, leny;

void query(int l, int r, int d, int u, vector<int>&len){
    if(l <= d && r >= u){
        len.emplace_back(u - d);
        return;
    }
    if(l >= u || r <= d){
        return;
    }
    int m = d + u >> 1;
    query(l, r, d, m, len);
    query(l, r, m, u, len);
}

void solve(){
    lenx.clear(); leny.clear();
    int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;

    query(l1, r1, 0, 1 << 20, lenx);
    query(l2, r2, 0, 1 << 20, leny);

    int res = 0;
    for(auto &i : lenx){
        for(auto &j : leny){
            res += max(i, j) / min(i, j);
        }
    }
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

G. Game With Triangles: Season 2

区间dp，根据最优子结构优化，专门写一篇讲讲。

$O(n^5)$ 解法：

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<int>>dp(n + 2, vector<int>(n + 2));
    for(int len = 3; len <= n; len++){
        for(int l = 1, r = len; r <= n; l++, r++){
            for(int i = l; i + 2 <= r; i++){
                for(int j = i + 1; j + 1 <= r; j++){
                    for(int k = j + 1; k <= r; k++){
                        dp[l][r] = max(dp[l][r], 
                            dp[l][i - 1] + dp[i + 1][j - 1] + 
                            dp[j + 1][k - 1] + dp[k + 1][r] + a[i] * a[j] * a[k]);
                    }
                }
            }
        }
    }	
    cout << dp[1][n] << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

正解 $O(n^3)$

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<int>>dp(n + 2, vector<int>(n + 2));
    for(int len = 3; len <= n; len++){
        for(int l = 1, r = len; r <= n; l++, r++){
            // 使用 l, i, r 构建三角形, 从 [l + 1, i - 1] 和 [i + 1, r - 1] 转移
            for(int i = l + 1; i < r; i++){
                dp[l][r] = max(dp[l][r], dp[l + 1][i - 1] + dp[i + 1][r - 1] + a[l] * a[i] * a[r]);
            }
            // 直接分为部分, 从 [l, i] 和 [i + 1][r] 转移
            for(int i = l; i + 1 <= r; i++){
                dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
            }
        }
    }	
    cout << dp[1][n] << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}