Codeforces Round 894 (Div. 3)

第一次div3 ak，虽然是vp的，后三题质量不错

A - Gift Carpet

穷举四个不同列即可，时间复杂度 \(O(M ^ 4)\)

int a[100][100];
void solve()
{       
    memset(a, 0, sizeof a);
    int n,  m;  cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            char x; cin>>x;
            a[j][x - 'a' + 1] = 1;
        }
    bool ok = false;
    for(int i = 1; i <= m; i++)
        for(int j = i + 1; j <= m; j++)
            for(int k = j + 1; k <= m; k++)
                for(int l = k + 1; l <= m; l++)
                    if(a[i]['v' - 'a' + 1] && a[j]['i' - 'a' + 1]
                    && a[k]['k' - 'a' + 1] && a[l]['a' - 'a' + 1])
                        ok = true;
    if(ok)
        cout<<"YES\n";
    else
        cout<<"NO\n";
    return;
}

B - Sequence Game

分两种情况：

1. 对 b 数组 的每个 \(b_{i - 1} > b_i (2 \leq i \leq n )\) ，放 \(2\) 个 \(b_i\) 到答案数组
2. 对 b 数组 的每个 \(b_{i - 1} \leq b_i (2 \leq i \leq n )\) ，放 \(1\) 个 \(b_i\) 到答案数组

const int N = 4e5 + 10;

int a[N];
void solve()
{       

    vector<int> res;
    int m, n = 0;   cin>>m;
    for(int i = 1; i <= m; i++) 
    {
        cin>>a[i];
    }  
    res.push_back(a[1]);
    for(int i = 2; i <= m; i++) 
    {
        if(a[i] >= a[i - 1])
            res.push_back(a[i]);
        else
        {
            res.push_back(a[i]);
            res.push_back(a[i]);
        }

    }
    cout<<res.size()<<'\n';
    for(auto it : res)
        cout<<it<<" ";
    cout<<'\n';
    return;
}

C - Flower City Fence

对于水平放置的篱笆在高度上差分一下，即可求出水平放置的篱笆高度

有的篱笆比 \(n\) 长，要特判一下

const int N = 4e5 + 10;
 
ll n, a[N], b[N];
void solve()
{       
    bool ok = true;
    cin>>n;
    for(int i = 1; i <= n + 1; i++)
        a[i] = b[i] = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        b[1]++, b[min(n + 1, a[i] + 1)]--;
    }
    for(int i = 1; i <= n; i++)
        b[i] += b[i - 1];
    for(int i = 1, j = n; i <= n; i++, j--)
        if(a[i] != b[i])
            ok = false;
    if(ok && a[1] == n)
        cout<<"YES\n";
    else
        cout<<"NO\n";
    return;
}

D - Ice Cream Balls

问的是刚好能组合出有 \(n\) 这个数量，先二分出 \(\dfrac{l \times (l - 1)}{2} \geq n\)， 因为相同冰激凌可以组合起来，且贡献为 \(1\)，则答案：

1. \(\dfrac{l \times (l - 1)}{2} = n\) 答案就为 \(l\)
2. 否则为 \(n - \dfrac{l \times (l - 1)}{2} + l\)

ll n;
bool check(ll x)
{
    x--;
    ll s = (1ll + x) * x / 2;
    if(s >= n)  return true;
    return false;
    return s >= n;
}

void solve()
{       
    cin>>n;
    ll l = 1, r = 1e10;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        if(check(mid))  r = mid;
        else l = mid + 1;
    }
    if(l * (l - 1) / 2 > n) l--;
    cout<<n - (l) * (l - 1) / 2 + l<<'\n';
    return;
}

E - Kolya and Movie Theatre

观察得到，对于任意一种方案，其方案的最后一天看电影是第 \(r\) 天，则 \(\texttt{兴趣减弱的总和} = r \times d\) ，也就是说可以枚举 \(r\) ，求出最大的 \([1, r]\) 的前 \(m\) 大之和即可，发现是个可持久化板子，刚好还存了，交了MLE4， 改了下数组大小就过了

等会看看有没有更简单的方法

F - Magic Will Save the World

由于 \(n\) 的大小无法求其方案，但观察到 \(n = 100\) ， \(s_i \leq 10 ^ 4\)

我们能不能二分天数，以一种能量的总和，对敌人能量做一个 01 背包呢，再对剩下的敌人能量判断是否小于另一种能量

\(\sum_{i = 1}^{n} s_i \leq 10 ^ 6\)

开 $\sum_{i = 1}^{n} s_i $ 的数组大小

每次二分判断转移次数有 \(n \times \sum_{i = 1}^{n} s_i\)

时间复杂度是 \(O(T n \sum_{i = 1}^{n} s_i \log n)\) 看上去很寄，但给了 4s，最终3900ms过了