题解：P16434 [APIO 2026 中国赛区] 蛋糕

· · 题解

场上会了 56 后没有继续思考了，有点遗憾。

sub1：我写的插入 1 到 100，每次相邻比较即可。

sub2 我写的插入 2, 2, 2 讨论下即可，等等是不是因为这个我没被提示到正解。

sub3 就是简单二进制一下就行。

sub4 首先你发现 3^7 = 2187 > 2000。

考虑放入 1,2,3,4,5...3^7 插入 d 之后会有对于 < d 的有 a_i = i + 1 而对于 \ge d 的有 a_i = i 所以考虑怎么利用这个信息在 [L, R] 中定位 d 呢。

我们考虑将区间均分成三份 m_1, m_2。此时我们要是可以有真正的 x = m_1 + m_2 + 1 就可以和这两端点加起来比较 a_{m_1} + a_{m_2}

那么刚刚好通过三个符号可以确定三种位置关系，且区间减小至三分之一，非常对，现在就是要处理下每次的 x 怎么提前得到。这个其实非常简单，当 x > MX 时，直接用 MX 即可，小于的时候用两个数凑一下，正确性比较显然。

#include <bits/stdc++.h>
#include "cake.h"
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
int c;
const int Mx = 1 << 29;
std::vector<int> bake_cakes(int N, int W, int K)
{
    if(K == 100) 
    {
        c = 1; vector<int> v;
        rep(i, 1, 100) v.push_back(i);
        return v;
    }
    else if(N == 3)
    {
        c = 2; return {2, 2, 2};
    }
    else if(N == 40)
    {
        c = 3; vector<int> v; v.push_back(1);
        int x = 1;
        while(x <= Mx)
        {
            v.push_back(x); x <<= 1;
        }
        return v;
    }
    else
    {
        c = 4; vector<int> v;
        rep(i, 1, 2026) v.push_back(i);
        return v;
    }
}
int qmi(int x, int y)
{
    int res = 1;
    while(y)
    {
        if(y & 1) res = res * x;
        x = x * x; y >>= 1;
    }
    return res;
}
int find_tastiness(int m, int W, int K)
{
    if(c == 1)
    {
        rep(i, 1, 100)
        {
            if(compare_tastiness({i}, {i - 1}) == 0) return i;
        }
    }
    else if(c == 2)
    {
        int op = compare_tastiness({1, 2}, {0, 3});
        if(op == 0) return 2;
        else if(op == 1) return 1;
        else return 3; 
    }
    else if(c == 3)
    {
        int k = 0; int res = 0;
        repf(i, 30, 1)
        {
            vector<int> v;
            rep(j, 0, i - 1) v.push_back(j);
            if(compare_tastiness(v, {i}) == 0) { k = i + 1; break; }
        }
        vector<int> y; y.push_back(k - 1);
        repf(i, k - 2, 1)
        {
            y.push_back(i); int op = compare_tastiness(y, {k});
            if(op == 0) break;
            else if(op == 1) y.erase(-- y.end());
            else continue;
        }
        for(int x : y) res += qmi(2, x - 1);
        return res;
    }
    else
    {
        int l = 1, r = 2000;
        while(l < r)
        {
            int len = r - l + 1;
            if(len == 2)
            {
                if(compare_tastiness({l}, {l - 1}) == 0) return l;
                else return l + 1;
            }
            int S1 = len / 3 + (len % 3 > 0 ? 1 : 0);
            int S2 = len / 3 + (len % 3 > 1 ? 1 : 0);
            int m1 = l + S1 - 1;
            int m2 = m1 + S2;
            vector<int> s2;
            if(m1 + m2 + 1 <= 2026) s2.push_back(m1 + m2 + 1);
            else s2.push_back(2026), s2.push_back(m1 + m2 - 2026);
            int op = compare_tastiness({m1, m2}, s2);
            if(op == -1) r = m1;
            else if(op == 0) { l = m1 + 1; r = m2; }
            else l = m2 + 1;
        } return l;
    }
}