Codeforces Round #772 (Div. 2)

传送门

Codeforces Round #772 (Div. 2)

A

按位考虑,若存在第 k k k 位为 1 1 1 的元素,则可以用这个元素将其余元素的第 k k k 位变为 0 0 0;为满足操作的约束,存在 1 1 1 的每个数位至少需要保留一个元素。故最小和为所有元素的按位或。总时间复杂度 O ( n ) O(n) O(n)。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 1E2 + 5;
int T, N, A[MAXN];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> N;
        for (int i = 0; i < N; ++i)
            cin >> A[i];
        int res = 0;
        for (int i = 0; i < N; ++i)
            res |= A[i];
        cout << res << '\n';
    }
    return 0;
}
B

改变任一元素至多影响其左右元素。当某个元素 a i a_i ai​ 相邻元素都是局部最大时,取 a i ′ = max ⁡ ( a i − 1 , a i + 1 ) a^{\prime}_i=\max(a_{i-1},a_{i+1}) ai′​=max(ai−1​,ai+1​) 即可消去两个局部最大元素;其余情况,取局部最大元素为左右元素的最大值即可。总时间复杂度 O ( n ) O(n) O(n)。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int T, N, A[MAXN];
bool conf[MAXN];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> N;
        for (int i = 0; i < N; ++i)
            cin >> A[i], conf[i] = 0;
        for (int i = 1; i < N - 1; ++i)
            conf[i] = A[i] > A[i - 1] && A[i] > A[i + 1];
        int res = 0;
        for (int i = 0; i < N; ++i)
        {
            if (!conf[i])
                continue;
            if (i + 2 < N && conf[i + 2])
                ++res, conf[i + 2] = 0, A[i + 1] = max(A[i], A[i + 2]);
            else
                ++res, A[i] = max(A[i - 1], A[i + 1]);
        }
        cout << res << '\n';
        for (int i = 0; i < N; ++i)
            cout << A[i] << (i + 1 == N ? '\n' : ' ');
    }
    return 0;
}
C

由于操作涉及的三个元素满足索引值的单调递增性,那么索引值最大的两个元素不能被修改。若 a n − 1 > a n a_{n-1}>a_n an−1​>an​ 则不可能使数组单调非降; 反之,若 a n > = 0 a_n>=0 an​>=0,取所有可以被修改的元素为 a n − 1 − a n a_{n-1}-a_n an−1​−an​ 即可;若 a n < 0 a_n<0 an​<0,则涉及它的操作不可能使数组满足单调非降性,那么将其删除后递归地处理即可。总时间复杂度 O ( n ) O(n) O(n)。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int T, N, A[MAXN];

void solve()
{
    for (int i = N - 2; i >= 0; --i)
    {
        if (A[i] > A[i + 1])
        {
            cout << "-1\n";
            return;
        }
        if (A[i + 1] >= 0)
        {
            cout << i << '\n';
            for (int j = 0; j < i; ++j)
                cout << j + 1 << ' ' << i + 1 << ' ' << i + 2 << '\n';
            return;
        }
    }
    cout << "0\n";
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> N;
        for (int i = 0; i < N; ++i)
            cin >> A[i];
        solve();
    }
    return 0;
}
D

元素 x x x 所生成的元素可以表示为 x x x 的二进制表示后添加数个 1 1 1 或 00 00 00。为了避免重复计数,将可以被数组中其他元素生成的元素删除;具体而言,不断删除元素二进制表示下,末尾的 1 1 1 或 00 00 00,判断余下的位构成的元素是否在数组中即可。时间复杂度 O ( n log ⁡ n log ⁡ max ⁡ ( a i ) ) O\big(n\log n\log\max(a_i)\big) O(nlognlogmax(ai​))

求严格小于 2 p 2^p 2p 的元素个数,则元素为长度至多位 p p p 的任意数字。考虑元素 x x x 及其生成的严格小于 2 p 2^p 2p 的元素个数,设 x x x 二进制表示下长度为 l e n len len,则末尾需要至多长度为 n = p − l e n n=p-len n=p−len 的 1 1 1 或 00 00 00 来补。那么元素的个数为
∑ 0 ≤ j ≤ n , 0 ≤ 2 k ≤ j ( j − k k ) = ∑ 0 ≤ 2 k ≤ n ∑ 2 k ≤ j ≤ n ( j − k k ) \sum\limits_{0\leq j\leq n,0\leq 2k\leq j}\binom{j-k}{k}=\sum\limits_{0\leq 2k\leq n}\sum\limits_{2k\leq j\leq n}\binom{j-k}{k} 0≤j≤n,0≤2k≤j∑​(kj−k​)=0≤2k≤n∑​2k≤j≤n∑​(kj−k​) 代入 i = j − k i=j-k i=j−k 得到
∑ 0 ≤ 2 k ≤ n ∑ k ≤ i ≤ n − k ( i k ) = ∑ 0 ≤ 2 k ≤ n [ ∑ 0 ≤ i ≤ n − k ( i k ) − ∑ 0 ≤ i ≤ k − 1 ( i k ) ] = ∑ 0 ≤ 2 k ≤ n ( n − k + 1 k + 1 ) \sum\limits_{0\leq 2k\leq n}\sum\limits_{k\leq i\leq n-k}\binom{i}{k}=\sum\limits_{0\leq 2k\leq n}\left[\sum\limits_{0\leq i\leq n-k}\binom{i}{k}-\sum\limits_{0\leq i\leq k-1}\binom{i}{k}\right]=\sum\limits_{0\leq 2k\leq n}\binom{n-k+1}{k+1} 0≤2k≤n∑​k≤i≤n−k∑​(ki​)=0≤2k≤n∑​[0≤i≤n−k∑​(ki​)−0≤i≤k−1∑​(ki​)]=0≤2k≤n∑​(k+1n−k+1​)
不同的 l e n len len 仅有 log ⁡ max ⁡ ( a i ) \log\max(a_i) logmax(ai​) 种,统计每一种的元素数量,预处理逆元,就可以 O ( p ) O(p) O(p) 统计答案。

官方题解提供了一种简洁的 D P DP DP 做法。二进制表示末尾添加 1 1 1 或 00 00 00,则数位增加 1 1 1 或 2 2 2,得到形如斐波那契数列的递推式 d p i = d p i − 1 + d p i − 2 dp_i=dp_{i-1}+dp_{i-2} dpi​=dpi−1​+dpi−2​。这样的递推式可以通过矩阵快速幂等方法进行优化,故当 p p p 的数量级增大,也可以高效地解决问题。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5, MOD = 1E9 + 7;
int N, P, A[MAXN], len_num[32];
bool del[MAXN];
ll fac[MAXN], invf[MAXN];

ll qpow(ll x, int n)
{
    ll res = 1;
    x %= MOD;
    while (n)
    {
        if (n & 1)
            res = res * x % MOD;
        x = x * x % MOD, n >>= 1;
    }
    return res;
}

ll C(ll n, ll m)
{
    if (m == 0)
        return 1;
    if (n < m || m < 0)
        return 0;
    return fac[n] * invf[m] % MOD * invf[n - m] % MOD;
}

int get(int x)
{
    int len = 0;
    while (x)
        ++len, x >>= 1;
    return len;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> P;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    sort(A, A + N);
    for (int i = 0; i < N; ++i)
    {
        int a = A[i];
        while (a)
        {
            bool upd = 0;
            if (a & 1)
                a >>= 1, upd = 1;
            else if (!(a & 1) && !(a >> 1 & 1))
                a >>= 2, upd = 1;
            if (!upd)
                break;
            if (*lower_bound(A, A + N, a) == a)
            {
                del[i] = 1;
                break;
            }
        }
    }
    for (int i = 0; i < N; ++i)
        if (!del[i])
            ++len_num[get(A[i])];
    fac[0] = invf[0] = 1;
    for (int i = 1; i <= P; ++i)
        fac[i] = fac[i - 1] * i % MOD, invf[i] = qpow(fac[i], MOD - 2);
    ll res = 0;
    for (int len = 1; len < 32; ++len)
    {
        ll t = 0;
        int n = P - len;
        for (int k = 0; 2 * k <= n; ++k)
            t += C(n - k + 1, k + 1);
        t %= MOD;
        res += t * len_num[len] % MOD;
    }
    cout << res % MOD << '\n';
    return 0;
}
E 补题

题中的两类关系,需要注意的是,无论速度如何,双方都能相遇或不相遇。则关系 1 1 1 只可能为一方在左侧方向为左,一方在右侧方向为右;关系 2 2 2 只可能为一方在左侧方向为右,一方在右侧方向为左。

此时两类关系涉及相对位置关系与各自方向的关系,难以同时处理。不妨先处理方向关系,即判断是否存在合法的赋值,使车辆向左或向右。可以通过并查集或二分图染色进行判断。

赋予车辆一组合法的方向,此时相相对位置关系就容易处理了。对于左侧的车辆,向右侧的车辆连一条有向边,判断是否满足拓扑序即可。总时间复杂度 ( n + m ) (n+m) (n+m)。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int N, M, col[MAXN], deg[MAXN], pos[MAXN];
vector<int> G[MAXN];
struct node
{
    int u, v, type;
} ns[MAXN];

void dfs(int u, int c)
{
    col[u] = c;
    for (auto v : G[u])
        if (col[v] == -1)
            dfs(v, c ^ 1);
}

bool color()
{
    memset(col, -1, sizeof(col));
    for (int u = 0; u < N; ++u)
        if (col[u] == -1)
            dfs(u, 0);
    for (int u = 0; u < N; ++u)
        for (auto v : G[u])
            if (col[u] == col[v])
                return 0;
    return 1;
}

bool topsort()
{
    memset(deg, 0, sizeof(deg));
    for (int u = 0; u < N; ++u)
        for (auto v : G[u])
            ++deg[v];
    queue<int> q;
    vector<int> ps;
    for (int u = 0; u < N; ++u)
        if (!deg[u])
            q.push(u), ps.pb(u);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (auto v : G[u])
            if (!--deg[v])
                q.push(v), ps.pb(v);
    }
    if ((int)ps.size() < N)
        return 0;
    for (int i = 0; i < N; ++i)
        pos[ps[i]] = i;
    return 1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        auto &t = ns[i];
        cin >> t.type >> t.u >> t.v;
        --t.u, --t.v;
        G[t.u].pb(t.v), G[t.v].pb(t.u);
    }
    if (!color())
    {
        cout << "NO\n";
        return 0;
    }
    for (int u = 0; u < N; ++u)
        G[u].clear();
    for (int i = 0; i < M; ++i)
    {
        int u = ns[i].u, v = ns[i].v;
        if (col[u])
            swap(u, v);
        if (ns[i].type == 1)
            G[u].pb(v);
        else
            G[v].pb(u);
    }
    if (!topsort())
    {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (int i = 0; i < N; ++i)
        cout << (col[i] ? 'R' : 'L') << ' ' << pos[i] << '\n';
    return 0;
}
F 补题

对任意位置 i i i 的元素,使 ∣ x i − x j ∣ ⋅ ( w i + w j ) \lvert x_i-x_j\rvert\cdot (w_i+w_j) ∣xi​−xj​∣⋅(wi​+wj​) 最大的 j j j 可能位置,对于同一侧而言,满足随着 ∣ i − j ∣ \lvert i-j\rvert ∣i−j∣ 增大而减小;但对单个 i i i 求解这样的最大值,时间复杂度仍为 O ( n ) O(n) O(n)。

根据对称性,假设 w j ≤ w i w_j\leq w_i wj​≤wi​,则可以排除 w j > w i w_j>w_i wj​>wi​ 的位置;由于目标是求区间最优,若某一些决策元素可以导出更优决策,则可以排除这样的决策,于是可以排除 w j ≤ w i w_j\leq w_i wj​≤wi​ 且 ∣ i − j ∣ \lvert i-j\rvert ∣i−j∣ 并非最小的位置 k k k,因为同一侧满足 w j ≤ w i w_j\leq w_i wj​≤wi​ 且 ∣ i − j ∣ \lvert i-j\rvert ∣i−j∣ 最小的 j j j 与 k k k 构成的点对可以得到更小的值。那么只用考虑 O ( n ) O(n) O(n) 个点对即可,这样的点对可以通过单调栈求解。

问题转化为已知一些带权值的线段,求区间内被完全覆盖的线段权值的最小值。这样的问题可以通过依次处理左右边界约束求解,具体而言,将查询离线,逆序处理,将满足左边界约束的区间,用能够维护前缀信息的数据结构进行维护,然后在这样的数据结构上查询满足右边界约束的信息即可。总时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 3E5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int N, Q;
int X[MAXN], W[MAXN];
vector<int> rs[MAXN];
vector<pair<int, int>> qs[MAXN];
ll bit[MAXN], res[MAXN];
int stk[MAXN], top;

void _min(ll &x, ll y) { x = min(x, y); }

void add(int i, ll x)
{
    while (i <= N)
        _min(bit[i], x), i += i & -i;
}

ll ask(int i)
{
    ll s = INF;
    while (i)
        _min(s, bit[i]), i -= i & -i;
    return s;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> Q;
    for (int i = 0; i < N; ++i)
        cin >> X[i] >> W[i];
    for (int i = 0; i < Q; ++i)
    {
        int l, r;
        cin >> l >> r;
        --l, --r;
        qs[l].pb({r, i});
    }
    for (int i = 0; i < N; ++i)
    {
        while (top && W[stk[top - 1]] > W[i])
            --top;
        if (top)
            rs[stk[top - 1]].pb(i);
        stk[top++] = i;
    }
    top = 0;
    for (int i = N - 1; i >= 0; --i)
    {
        while (top && W[stk[top - 1]] > W[i])
            --top;
        if (top)
            rs[i].pb(stk[top - 1]);
        stk[top++] = i;
    }
    memset(bit, 0x3f, sizeof(bit));
    for (int l = N - 1; l >= 0; --l)
    {
        for (auto r : rs[l])
        {
            ll t = (ll)(W[l] + W[r]) * (X[r] - X[l]);
            add(r + 1, t);
        }
        for (auto &p : qs[l])
        {
            int r = p.first, k = p.second;
            res[k] = ask(r + 1);
        }
    }
    for (int i = 0; i < Q; ++i)
        cout << res[i] << '\n';
    return 0;
}
上一篇:AI 直播合集 | 五位阿里技术大咖共话人工智能的现在与未来


下一篇:开发者社区精选直播合集 | AIoT实践精选合集