Codeforces Round 1009 (Div. 3)¶

比赛时间: 2025-03-11

比赛链接: https://codeforces.com/contest/2074

本来 carrot 预测的是差不多加到我差几分上绿。但是一早上醒来发现我前面好多人被 hack 了，中午的时候我排名升了 50名。然后晚上重测完之后，排名有上升了一百多，总共升了150多... 太多人 FST 了吧。

于是我幸运的再次回到了蓝名。

赛时其实 D 题很久都没思路，然后我以为我 div. 3 会和 div. 2 一样的题数，有点难受了。于是没抱很大希望去看一下 E 题，然后以为就直接模拟就行，于是随便交一发， TLE ，然后改了又 TLE ，之后想着看能不能混过去用了 rand( ) ，毫无疑问过了，而且这还真就是正解。。。

最后看到 D 题的小提示，也成功 AC 了。就是慢了点。不过尽管如此，这场比赛是我 CF 打过的 rank 最好的一场比赛，rated里的 550 名。继续加油吧。而且写完这篇博客，最近的基本就补得差不多了。。。还有AtCoder的，，，感觉真是写不完的博客，补不完的题目啊。

前三题比较基础就不详细解释了。

A¶

void ChatGptDeepSeek()
{
    array<int, 4>a;
    for(int i=0;i<4;i++)
        cin>>a[i],a[i]=abs(a[i]);
    sort(a.begin(),a.end());
    if(a[0]==a[3])
        cout<<"YES\n";
    else
        cout<<"NO\n";
}

B¶

void ChatGptDeepSeek()
{
    int n;
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        sum+=x;
    }
    cout<<sum-(n-1)<<'\n';
}

C¶

void ChatGptDeepSeek()
{
    int x;
    cin >> x;
    // x+y>=x^y
    // 111
    // 101
    // 010
    for (int i = 30; i >= 1; i--) {
        if (x >> i & 1) {
            int y = (1 << i) - 1;
            int z = x ^ y;
            if ((x != y) && z < x + y && x + z > y && y + z > x) {
                cout << y << '\n';
                return;
            }
        }
    } // 11
    // 01
    // 10
    cout << "-1\n";
}

D¶

本以为这场 div. 3 将会耻辱地只写出 3 题，这个 D 题给我看傻了。

最后写完 E 题回来看，注意了一句之前没怎么注意的话。。。

∗Is this information really useful? Don't ask me; I don't really know.

因为感觉这个有点意思，所以就多看了两眼，发现原来这个这么有用。。。

\(\sum r=m\) 意味着所有的横坐标，最多只会有 \(2m\) 个，所以直接对于每一个横坐标枚举即可。

void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vector<int> l(m * 2 + 1), x(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> r[i];
    set<pair<int, int>> st;
    auto Insert = [&](int X, int Y) {
        auto it = st.lower_bound({ X, 0 });
        if (it == st.end() || it->first != X) {
            st.insert({ X, Y });
        } else {
            if (Y > it->second) {
                st.erase(it);
                st.insert({ X, Y });
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        for (int j = x[i] - r[i]; j <= x[i] + r[i]; j++) {
            //(j-x[i])*(j-x[i])+y*y<=r*r
            // 可以知道y的范围
            int y = sqrt(1LL * r[i] * r[i] - 1LL * (j - x[i]) * (j - x[i]));
            Insert(j, y);
        }
    }
    long long sum = 0;
    for (auto [X, Y] : st) {
        sum += 2 * Y + 1;
    }
    cout << sum << '\n';
}

E¶

如果不限制次数，肯定就是一直问 \((1,2,x)\) 这样，但是有可能最多需要问 \(n\) 次。

由于这题不允许 \(hack\) ，所以尝试用随机数来混过去。。。

但这就是正解，每次在中心有点后，随机两个顶点和这个点组成新的三角形。这样每次点的数量平均会减少 \(\frac{2}{3}\) ，所以其实非常非常大的概率是询问次数很小就行了。

也是我第一次通过跟 rand() 有关的题目了。

int ask(int a, int b, int c)
{
    cout << "? " << a << " " << b << " " << c << endl;
    int x;
    cin >> x;
    return x;
}
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    int x = 1, y = 2, z = 3;
    for (int i = 1; i <= 75; i++) {
        int X=ask(x,y,z);
        if(!X){
            cout<<"! "<<x<<" "<<y<<" "<<z<<endl;
            return;
        }
        int Y=rand();
        if(Y%3==0) x=X;
        else if(Y%3==1) y=X;
        else z=X;
    }
}

F¶

本来连题目都没看懂来着，，感觉看着有一点难受。

看了两种思路。

楜桃林的 Codeforces 题解 ¶

先用小的正方形来填充，若是可以用更大的正方形，那么一定可以把这个正方形替换成4个小一号的正方形。

所以可以先全部用小的正方形，若是能用大的正方形，则用的正方形的数量可以减少3倍的大正方形的数量。

void ChatGptDeepSeek()
{
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    long long ans = 1ll * (r1 - l1) * (r2 - l2);
    for (int i = 1; i < 30; i++)
    {
        int s = 1 << i;
        int L1 = (l1 + s - 1) / s * s;
        int L2 = (l2 + s - 1) / s * s;
        int R1 = r1 / s * s;
        int R2 = r2 / s * s;
        if (L1 >= R1 || L2 >= R2)
            continue;
        ans -= 3LL * (R1 - L1) / s * (R2 - L2) / s;
    }
    cout << ans << '\n';
}

ksun48的思路 ¶

比如 \(k=1\) 时，若 \(l1 , r1,l2,r2\) 为奇数，则必须使用 \(k=0\) 的正方形来填充。我们可以先把这一部分加上，之后 \(l1,r1,l2,r2\) 一定会全是偶数了，并且再也不会使用 \(k=1\) 的三角形了。

于是我们可以把这四个数字除以二，于是可以一直重复之前的操作了。

void solve(){
    ll lx, rx, ly, ry;
    cin >> lx >> rx >> ly >> ry;
    ll ans = 0;
    while(true){
        if(lx == rx || ly == ry) break;
        if(lx & 1){
            ans += (ry - ly);
            lx += 1;
        }
        if(rx & 1){
            ans += (ry - ly);
            rx -= 1;
        }
        if(ly & 1){
            ans += (rx - lx);
            ly += 1;
        }
        if(ry & 1){
            ans += (rx - lx);
            ry -= 1;
        }
        lx /= 2; rx /= 2; ly /= 2; ry /= 2;
    }
    cout << ans << '\n';
}

G¶

tag: 区间DP

好好好，这么会区间DP。好像还真是比较基础的区间DP，然而我是看题解做的。虽然看起来这个是一个环，但是其实并不需要特别处理。

\(dp_{i,j}\) 表示区间 \([i,j]\) 的最大答案。那么 \(dp_{l,r}=max(dp_{l,r},dp_{l+1,m-1}+dp_{m+1,r-1}+a_la_ma_r)\)

但是也可能中间已经有更好的方案，所以再加一个 \(dp_{l,m}+dp_{m+1,r}\)

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int len = 3; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            for (int m = l + 1; m < r; m++)
                dp[l][r] = max(dp[l][r], dp[l + 1][m - 1] + dp[m + 1][r - 1] + a[l] * a[m] * a[r]);

            for (int m = l; m + 1 <= r; m++)
                dp[l][r] = max(dp[l][r], dp[l][m] + dp[m + 1][r]);
        }
    }
    cout << dp[1][n] << '\n';
}

End¶

2025-03-25

时隔两周，终于把这场Div. 3补完了。并且只有FG需要补且都是今天写的。。。且都看了题解。

但是无论如何终于把这一套给结束了，需要补的题总是少了一点的。今晚又有一场Div. 3，而且这次我可以 unrated 了，爽了。

好像我总共都没有 unrated 打过几场比赛。。因为比赛少且掉分比较快。。。慢慢来吧，虽然要补的题也会越来越多。但是无论如何我的写题量也会越来越多，实力也会提高的。

提升水平才是真正的目的。

Codeforces Round 1009 (Div. 3)¶

A¶

B¶

C¶

D¶

E¶

F¶

楜桃林的 Codeforces 题解¶

ksun48的思路¶

G¶

End¶

楜桃林的 Codeforces 题解 ¶

ksun48的思路 ¶