竞赛讨论区 > 牛客寒假营第一场题解
头像
嘤嘤世界第一可爱
发布于 02-03 18:01 福建
+ 关注

牛客寒假营第一场题解

牛客寒假营第一场题解

签到：L、K

easy：C、E

mid：B、G、H

hard：A、D、I

防AK：F、J

shit：A、C、E、F、G、K

前言

比较恶心的一场，大部分题都在恶心人，苯环真是罪大恶极！

进场第一眼看A就发现了一坨题，关掉A开B又看到一坨题，所以我多次建议第一场换一套题or换一下题目顺序，但最终都没有执行。

大部分题都是读题地狱or dirt地狱，做起来非常痛苦。

整体没什么太大的问题，难度也比较合理，就是感觉很容易劝退萌新，应该跟第X场交换一下，先把萌新骗进来。

A A+B Problem

概率、模拟

纯shit模拟题，傻逼苯环

读题，写题都很烦，特别是放在第一题，能劝退不少萌新。。。

首先可以发现，每个灯管亮或不亮是独立的，由此可以推出每个数字的出现概率也是独立的。

我们可以预处理每个数字出现的概率，即累乘该亮的灯管亮的概率 a_i ，不该亮的灯管不亮的概率 (1-a_i) 。

之后枚举 a+b=c 的所有 a,b 组合，只需要枚举 a ，移项可得 b=c-a 。

用预处理得到的概率计算出现 a,b 的概率累加即可（由于必须是 4 位数，要记得对 a,b 数字补前导零）。

时间复杂度： O(T \times c) 。

#include<bits/stdc++.h>

using namespace std;

template<const int M = 1e9 + 7>
struct MInt {
    using LL = long long;
    int x;
    MInt(int x = 0) : x(norm(x)) {}
    MInt(LL x) : x(norm(x % M)) {}
    inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
    inline MInt ksm(MInt x, LL y) const {return x ^= y;}
    inline int val() const {return x;}
    inline MInt operator - () const {return MInt(norm(M - x));}
    inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
    inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
    inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
    inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
    inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
    inline MInt& operator ^= (LL y){
        LL ans = 1;
        while(y){
            if(y & 1) ans = ans * x % M;
            x = LL(x) * x % M;
            y >>= 1;
        }
        x = ans;
        return *this;
    }
    inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
    inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
    inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
    inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
    inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
    inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
    inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt<998244353>;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int c;
        cin >> c;
        vector<Z> a(8);
        for(int i = 1; i <= 7; i++){
            cin >> a[i];
            a[i] /= 100;
        }
        vector<string> s(10);
        s[0] = " 1110111";
        s[1] = " 0010010";
        s[2] = " 1011101";
        s[3] = " 1011011";
        s[4] = " 0111010";
        s[5] = " 1101011";
        s[6] = " 1101111";
        s[7] = " 1010010";
        s[8] = " 1111111";
        s[9] = " 1111011";
        vector<Z> p(10, 1);
        for(int i = 0; i < 10; i++){
            for(int j = 0; j <= 7; j++){
                if(s[i][j] == '1') p[i] *= a[j];
                else p[i] *= (1 - a[j]);
            }
        }
        Z ans = 0;
        for(int i = 0; i <= c; i++){
            Z sum = 1;
            auto s = to_string(i) + to_string(c - i);
            for(auto &i : s){
                sum *= p[i - '0'];
            }
            sum *= sum.ksm(p[0], 8 - s.size());
            ans += sum;
        }
        cout << ans << endl;
    }
}

B Card Game

找规律、结论

挺有趣的

多玩几组样例可以发现，如果小苯的最小牌 > 小红的最小牌，小苯一定能出完；比小红最小牌小的牌，小苯一定出不掉。

定义小红的最小牌为 mi ，设小苯的一张牌 x < mi ，那么在 x 之后的所有牌一定会被 x 卡住（因为 x 出不去），全都出不掉。

现在小苯要最大化得分，也就是说在第一个 x 出现之前，所有该出的牌都要出掉。

什么叫该出的牌呢？将小苯的牌从大到小排序后开始游戏可以发现，所有比 mi 大的牌都一定能出掉。

这就意味着，能得到最高分的排列中：在第一个小于 mi 的 x 出现之前，所有大于 mi 的数都要出掉（也就是在 x 前面）。

所以我们可以把小苯的牌分成两类，一类是大于 mi 的（假设有 a 个），另一类是小于 mi 的（假设有 b 个）。

大于 mi 的要放左边，小于 mi 的放右边，两类不交叉，可以分别计算。两类的方案数都是全排列，即 a! \times b! 。

时间复杂度： O(n) 。

#include<bits/stdc++.h>

using namespace std;

template<const int M = 1e9 + 7>
struct MInt {
   using LL = long long;
   int x;
   MInt(int x = 0) : x(norm(x)) {}
   MInt(LL x) : x(norm(x % M)) {}
   inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
   inline MInt ksm(MInt x, LL y) const {return x ^= y;}
   inline int val() const {return x;}
   inline MInt operator - () const {return MInt(norm(M - x));}
   inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
   inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
   inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
   inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
   inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
   inline MInt& operator ^= (LL y){
       LL ans = 1;
       while(y){
           if(y & 1) ans = ans * x % M;
           x = LL(x) * x % M;
           y >>= 1;
       }
       x = ans;
       return *this;
   }
   inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
   inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
   inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
   inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
   inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
   inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
   inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt<998244353>;

int main(){
   int T = 1;
   cin >> T;
   while(T--){
       int n;
       cin >> n;
       vector<int> a(n + 1), b = a;
       for(int i = 1; i <= n; i++){
           cin >> a[i];
       }
       for(int i = 1; i <= n; i++){
           cin >> b[i];
       }
       ranges::sort(b);
       int cnt = 0;
       for(int i = 1; i <= n; i++){
           cnt += a[i] > b[1];
       }
       Z ans = 1;
       for(int i = 1; i <= cnt; i++){
           ans *= i;
       }
       for(int i = 1; i <= n - cnt; i++){
           ans *= i;
       }
       cout << ans << endl;
   }
}

C Array Covering

贪心

出生题，非常无趣，傻逼苯环

一个贪心的想法，我们选最大值作为左端点或右端点各更新一次整个数组即可。

然后题目藏了一个开区间的坑，因此第一个数和最后一个数都无法被修改。

时间复杂度： O(n) 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        auto ans = 1ll * (n - 2) * *ranges::max_element(a) + a[1] + a[n];
        cout << ans << endl;
    }
}

D Sequence Coloring

二分、贪心、DP、双指针、BFS

还行

首先染色花费的时间一定是满足单调性的，因为 t 秒能染完， t+1 秒放着不动也还是染完了，因此我们可以二分染色花费的时间，最小时间为 0 ，最大时间为无穷。

那么怎么判断规定时间 t 秒内能不能染完呢？

很显然第一个白色格子我们必须手动染红，然后第一个白色格子可以扩散 1 秒染红一些格子，这些格子又可以扩散 1 秒染红另一些格子，类似一个 BFS 的过程，由于只能往右扩展，因此可以不用真的去写 BFS 。

t 秒过后有一些格子还未被染红，此时我们一定需要手动染红格子，设第一个格子未被染红的格子为 x ，手动染红第 x 个格子，我们可以在 1 秒后染红 (x, x + a_x] 中的所有格子。

但如果在 x 之前有某一个在第 t 秒被染红的格子 y ，它本来应该在第 t+1 秒将 (y, y + a_y] 染红，但由于时间不够因此没能成功，而我们手动染红第 y 个格子的话，可以在 1 秒后染红 (y, y + a_y] 中的所有格子。

若此时 y + a_y > x + a_x ，我们手动染红 y 显然是更优的，因为可以在 1 秒后染红 (x + a_x, y + a_y] 之间的格子，因此我们需要一个值 ma 维护 ma + a_{ma} 的最大值，当有格子未被染红时，手动染红第 ma 个格子。

最后我们只需要判断手动染红的格子数量是否超过 k ，就知道 t 秒是否可以染红所有格子了。

如果无穷秒都无法完成染色，则无解。

时间复杂度： O(n \times logn) 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n, k;
        cin >> n >> k;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        int l = 1, r = n * 2;
        auto check = [&](int x){
            vector<int> dp(n + 1, 1e9);
            int r = 0;
            int ans = 0;
            int t = 0;
            for(int i = 1; i <= n; i++){
                if(!a[i]) continue;
                if(i + a[i] > t + a[t]) t = i;
                if(dp[i] > x){
                    ans++;
                    dp[t] = 0;
                    if(x){
                        for(int j = i + 1; j <= min(n, t + a[t]); j++){
                            dp[j] = 1;
                        }
                    }
                }
                for(; r + 1 <= min(n, i + a[i]); r++){
                    dp[r + 1] = min(dp[r + 1], dp[i] + 1);
                }
            }
            return ans <= k;
        };
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(l > n) cout << -1 << endl;
        else cout << l << endl;
    }
}

E Block Game

找规律

出生题，傻逼苯环

我们可以将万能方块放在开头，然后结尾的会掉出来变成新的万能方块，然后插入、掉出、插入、掉出……

实际上万能方块并不万能，这些方块的本质相当于一条由方块做成的手链，万能方块两边分别是 a_1 和 a_n 。

而每一次操作就相当于将这条手链转一圈，最后要求的答案也就是手链上相邻两个数字之和。

然后值域有负数，需要注意最小值的初始化。

时间复杂度： O(n) 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        int ans = -1e9;
        for(int i = 0; i <= n; i++){
            cin >> a[i];
            if(i) ans = max(ans, a[i - 1] + a[i]);
        }
        ans = max(ans, a[0] + a[n]);
        cout << ans << endl;
    }
}

F Permutation Counting

计数、数据结构、并查集

出生题，傻逼苯环

首先啊需要发现几个结论：

  1. 对于多个 k 相等的限制的区间， k 必须填在多个区间的交集中，若最终交集为空，则一定无解。
  2. 对于多个 k 相等的限制的区间，比 k 大的数字不能填在多个区间的并集（若有区间不相邻，则交集为空，在上面会被判成无解）。
  3. 没有任何区间包含的位置，可以任意填数字。

如何计算答案呢？

我们从大到小考虑：

若有区间限制 x ，那么 x 必须满足 1 且不能影响结论 2 ，如果有 t 个符合的位置，则可以任选一个，方案数ans := ans \times t ，且有 t-1 个位置将转化成结论 3 （因为从大到小考虑，接下来填的数一定不会违背结论 2 ）。

若没有区间限制 x ，那么 x 必须满足结论 3 ，如果满足结论 3 的位置个数为 t ，则方案数 ans := ans \times t（从大到小考虑，还处于结论 2 的位置一定是填不了的）。

现在我们需要求出结论 1、2、3 的对应的区间或位置： 1、2 结论本质是区间最值或区间赋值，是经典的数据结构问题，由于可以离线，可以使用并查集。 3 实际上就是结论 2 中没有被赋值的位置。

不知道为啥偏要卡 log ，恶心人。

时间复杂度： O(n) 。

#include<bits/stdc++.h>

using namespace std;

template<const int M = 1e9 + 7>
struct MInt {
    using LL = long long;
    int x;
    MInt(int x = 0) : x(norm(x)) {}
    MInt(LL x) : x(norm(x % M)) {}
    inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
    inline MInt ksm(MInt x, LL y) const {return x ^= y;}
    inline int val() const {return x;}
    inline MInt operator - () const {return MInt(norm(M - x));}
    inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
    inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
    inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
    inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
    inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
    inline MInt& operator ^= (LL y){
        LL ans = 1;
        while(y){
            if(y & 1) ans = ans * x % M;
            x = LL(x) * x % M;
            y >>= 1;
        }
        x = ans;
        return *this;
    }
    inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
    inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
    inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
    inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
    inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
    inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
    inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt<998244353>;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector ve(n + 1, array<int, 2>({n + 1, 0}));
        vector ve1(n + 1, array<int, 2>({0, n + 1}));
        vector<int> st(n + 1);
        for(int i = 1; i <= m; i++){
            int l, r, x;
            cin >> l >> r >> x;
            st[x] = 1;
            ve[x][0] = min(ve[x][0], l);
            ve[x][1] = max(ve[x][1], r);
            ve1[x][0] = max(ve1[x][0], l);
            ve1[x][1] = min(ve1[x][1], r);
        }
        auto get = [&](auto &ve){
            vector<int> a(n + 1);
            vector<int> nxt(n + 1);
            for(int i = 0; i <= n; i++){
                nxt[i] = i + 1;
            }
            for(int x = 1; x <= n; x++){
                auto &[l, r] = ve[x];
                if(!st[x] || l > r) continue;
                auto dfs = [&](this auto &&dfs, int u){
                    if(u > r) return u;
                    if(!a[u]) a[u] = x;
                    return nxt[u] = dfs(nxt[u]);
                };
                dfs(l);
            }
            return a;
        };
        auto a = get(ve);
        auto a1 = get(ve1);
        vector<int> b(n + 1), b1(n + 1);
        for(int i = 1; i <= n; i++){
            b[a[i]]++;
            if(a[i] == a1[i]) b1[a[i]]++;
        }
        int sum = b[0];
        Z ans = 1;
        for(int i = n; i >= 1; i--){
            sum += b[i];
            if(st[i]) ans *= b1[i];
            else ans *= sum;
            sum--;
        }
        cout << ans << endl;
    }
}

G Digital Folding

分类讨论

出生题，傻逼苯环

若 l 与 r 相等，答案就是 l 倒过来并去除前导零后的结果。

如果 r 是10的幂，答案就是 r - 1 。

否则，让 ans 变成 10 的幂，位数与 r 对齐，若 ans 小于 l ，则将 ans 变成 l 。然后为了让反过来的数最大，我们需要从后往前让每一位尽可能变成 9 ，因此模拟一下变化即可。

细节非常多，真恶心，太出生了。

时间复杂度： O(T \times log_{10}r) 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        LL l, r;
        cin >> l >> r;
        auto t = to_string(r);
        if(l == r){
            ranges::reverse(t);
            cout << stoll(t) << endl;
            continue;
        }
        if(ranges::count(t, '0') == t.size() - 1 && t[0] == '1'){
            cout << r - 1 << endl;
            continue;
        }
        LL ans = stoll("1" + string(t.size() - 1, '0'));
        ans = max(ans, l);
        auto s = string(18, '0') + to_string(ans);
        for(LL i = 1, j = s.size() - 1; i <= 1e16; i *= 10, j--){
            for(int k = 1; k <= '9' - s[j]; k++){
                if(ans + i <= r) ans += i;
            }
        }
        s = to_string(ans);
        ranges::reverse(s);
        cout << s << endl;
    }
}

H Blackboard

DP、位运算

还行

首先有一个结论，要使得答案最大，必须让连续的或运算的结果等于连续的加运算。

有一个比较常用的结论，以 i 为前缀或者后缀的不同区间或的个数不超过 logA 个，也就是说区间或运算产生不同结果的个数最多只有 32 个。

我们可以设计一个 DP 状态， dp_{i,j} 表示前 i 个数字，最后一些数字区间或是 j 的方案数，第二维可以用类似map的东西或者区间左端点进行维护。

假设新加入的数字是 a_i = x ，状态转移就是：

dp_{i, a_i} = dp_{i, a_i} + \sum_{j=0}^{+\infty} dp_{i - 1, j} //填+号，实际至多只会有 32 个 j 有效

dp_{i, a_i | j} = dp_{i, a_i | j} + dp_{i - 1, j}, (a_i | j) = a_i + j //填|号，实际至多只会有 32 个 j 有效

初始状态是：dp_{1, a_1} = 1 或者 dp_{0,0} = \frac 1 2 。

时间复杂度： O(n \times logA) 。

#include<bits/stdc++.h>

using namespace std;

template<const int M = 1e9 + 7>
struct MInt {
    using LL = long long;
    int x;
    MInt(int x = 0) : x(norm(x)) {}
    MInt(LL x) : x(norm(x % M)) {}
    inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
    inline MInt ksm(MInt x, LL y) const {return x ^= y;}
    inline int val() const {return x;}
    inline MInt operator - () const {return MInt(norm(M - x));}
    inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
    inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
    inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
    inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
    inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
    inline MInt& operator ^= (LL y){
        LL ans = 1;
        while(y){
            if(y & 1) ans = ans * x % M;
            x = LL(x) * x % M;
            y >>= 1;
        }
        x = ans;
        return *this;
    }
    inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
    inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
    inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
    inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
    inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
    inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
    inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt<998244353>;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector dp(n + 1, map<int, Z>());
        dp[0][0] = Z(1) / 2;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            for(auto &[y, cnt] : dp[i - 1]){
                if((x | y) == x + y) dp[i][x | y] += cnt;
                dp[i][x] += cnt;
            }
        }
        Z ans = 0;
        for(auto &[x, y] : dp[n]){
            ans += y;
        }
        cout << ans << endl;
    }
}

I AND vs MEX

数学、找规律

还行

若要答案 mex 不为 0 ，那么集合中必须有 0 。

令 x 为 2 的幂，且 x, x - 1 在区间内：

得到 0 的方法就是 (x + 0) \& (x - 1) = 0

得到 1 的方式就是 (x + 1) \& (x - 1) = 1

得到 2 的方式就是 (x + 2) \& (x - 1) = 2

……

得到 y 的方式就是 (x + y) \& (x - 1) = y

x + y 的最大取值是 r 与 2x - 1 的最小值（ x 首位进位后就无法让首位为 1 了，因此 x 不能进位）。

y 的取值就是 min(r - x,x - 1) ，对于每个在区间内的 2 的幂中我们可以求出最大的 y 。

(x - 1) \& (x - 2) 可以得到 x - 3

(x - 1) \& (x - 4) 可以得到 x - 7

(x - 1) \& (x - 8) 可以得到 x - 15

……

(x - 1) \& (x - 2 ^ i) 存在可以得到 z = x - 2^{i+1} + 1

对于每个在区间内的 2 的幂中我们可以求出最小的 z ，如果 y + 1 \ge z ，那么区间就得到了合并，答案为 r + 1 。

否则答案就是 y + 1 。

时间复杂度： O(T \times logA^2) 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int l, r;
        cin >> l >> r;
        if(l == 0){
            cout << r + 1 << endl;
            continue;
        }
        int ma = -1;
        for(int i = 2; i < 1 << 30; i <<= 1){
            if(l < i && i <= r) ma = max(ma, min(r, i * 2 - 1) - i);
        }
        int mi = l;
        for(int i = 2; i < 1 << 30; i <<= 1){
            int t = i - 1;
            if(l < i && i <= r){
                for(int j = 1; j < 1 << 30; j <<= 1){
                    if(i - 1 - j >= l) t -= j;
                }
                mi = min(mi, t);
            }
        }
        if(ma + 1 >= mi) ma = r;
        cout << ma + 1 << endl;
    }
}

J MST Problem

最小生成树、数据结构

还不错

最小生成树常用的算法有：Prim 和 Kruskal

回忆一下 Prim 的过程是什么呢？

首先有两个点集，左边点集为空，右边点集为所有点，初始时左边点集到右边点集的所有点距离都为无穷。

  1. 将一个点 u 从右边点集拉到左边点集（选择与左边点集距离最小的点，若左边点集为空则任取一个点）。
  2. 用 u 的邻边更新左边点集到右边点集每个点的最小距离。
  3. 重复操作 1 直到右边点集为空。

这个算法的时间复杂度是 n ^ 2 的，因为操作 1 和操作 2 的时间复杂度都是 O(n) ，操作 3 的循环次数是 O(n) 。

操作 1 实际上是全局最小值，在平时我们一般会用一个堆来维护，将操作 1 优化成 logn 级别，当然我们也可以复杂一点用线段树之类的数据结构进行维护全局最值。

操作2实际上是遍历邻边，所有操作 2 的次数加起来实际上是图上的边数，如果图是稀疏的（ n, m 同阶），操作 2 会从 O(n) 均摊优化成 O(1) 。但是这张图是稠密完全图，我们无法像稀疏图一样均摊优化掉，因此时间复杂度的瓶颈就是操作 2 。

由于初始时图是完全图，然后删除一些边，这些被删除的边组成的是稀疏图，然后一个点的两条邻边之间的间隙实际上就是一个区间，区间的个数是稀疏的。

分析一下边权： u, v 的边权是 a_u + a_v ，对点 v 来说，我们只需要知道左边点集中与 v 连接的点中 a_u 的最小值即可。看上去只需要在线段树之类的数据结构上进行一下区间推平最小值即可，但是这样操作 1 的查询并不是很好做。

思考一下区间操作具体细节，似乎每次区间操作的最值在大部分情况是增大的，似乎可以直接在线段树上暴力修改，然后每次用 pushup 更新全局最大的 a_u + a_v ，可以做到 O(n) 修改 O(1) 查询，但是似乎修改的次数是均摊 O(n \times logn) 的。

似乎就可以过了？？？

时间复杂度： O(n \times logn) ，大概？

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        vector ve(n + 1, vector<int>(1));
        for(int i = 1; i <= m; i++){
            int u, v;
            cin >> u >> v;
            ve[u].push_back(v);
            ve[v].push_back(u);
        }
        for(int i = 1; i <= n; i++){
            ve[i].push_back(n + 1);
            ranges::sort(ve[i]);
        }
        vector<array<long long, 2>> mi(n << 2 | 3);
        vector<long long> ma(n << 2 | 3);
        auto pushup = [&](int u){
            int ls = u << 1;
            int rs = u << 1 | 1;
            ma[u] = max(ma[ls], ma[rs]);
            int t1 = mi[ls][1] > 0;
            int t2 = mi[rs][1] > 0;
            if(t1 && t2){
                auto x = mi[ls][0] + a[mi[ls][1]];
                auto y = mi[rs][0] + a[mi[rs][1]];
                if(x <= y) mi[u] = mi[ls];
                else mi[u] = mi[rs];
            }
            else if(t1) mi[u] = mi[ls];
            else mi[u] = mi[rs];
        };
        auto build = [&](this auto &&build, int u, int l, int r)->void{
            if(l == r){
                ma[u] = mi[u][0] = 1e18;
                mi[u][1] = l;
                return;
            }
            int mid = (l + r) >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        };
        build(1, 1, n);
        auto assign = [&](int le, int ri, int x){
            auto dfs = [&](this auto &&dfs, int u, int l, int r)->void{
                if(le <= l && r <= ri){
                    if(x >= ma[u]) return;
                    if(l == r){
                        assert(ma[u] > x && mi[u][0] > x);
                        ma[u] = mi[u][0] = x;
                        if(!x) mi[u][1] = 0;
                        return;
                    }
                }
                int mid = (l + r) >> 1;
                if(le <= mid) dfs(u << 1, l, mid);
                if(ri > mid) dfs(u << 1 | 1, mid + 1, r);
                pushup(u);
            };
            dfs(1, 1, n);
        };
        vector<int> q = {1};
        auto ans = 0ll;
        for(int i = 0; i < q.size(); i++){
            auto u = q[i];
            assign(u, u, 0);
            for(int i = 1; i < ve[u].size(); i++){
                int l = ve[u][i - 1] + 1;
                int r = ve[u][i] - 1;
                if(l <= r) assign(l, r, a[u]);
            }
            auto &[x, y] = mi[1];
            if(y && x <= 1e9){
                ans += x + a[y];
                q.push_back(y);
            }
        }
        if(q.size() != n) ans = -1;
        cout << ans << endl;
    }
}

K Constructive

构造

垃圾苯环

第 3 点要求数组数字互不相同，那意味着数组乘积至少是阶乘这个数量级的。

而数组的和只有 n^2 的数量级，当 n=4 时， n! 就开始大于 n^2 了。

我们只需要考虑 n = 1, 2, 3 的情况，由于 1, 2 在样例中有，因此只需要尝试 3 是否可以构造。

尝试一下即可得到 [1, 2, 3] 的解。

时间复杂度： O(T) 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        if(n == 1 || n == 3){
            cout << "YES" << endl;
            for(int i = 1; i <= n; i++){
                cout << i << " ";
            }
            cout << endl;
        }
        else cout << "NO" << endl;
    }
}

L Need Zero

枚举

个位数是 0 说明一定是 10 的倍数，任意整数乘 10 一定是 10 的倍数。

因此只要从 1 开始枚举到 10 即可。

时间复杂度： O(1) 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int x;
    cin >> x;
    for(int i = 1; i <= 10; i++){
        if(x * i % 10 == 0){
            cout << i << endl;
            break;
        }
    }
}
2026最新求职资料大礼包领取
真题
历年笔试真题附答案
酷家乐2020校园招聘-项目经理卷
小鹏汽车2020秋招Java笔试题目
【2023】腾讯秋招技术岗编程合集
全部 >
面经
面试常考问题整理
22届-国企上岸经验分享
0928携程笔试题解
腾讯三面已上岸
全部 >
内推
员工内推码获取
拼多多内推 拼多多内推
虎牙2026届春季校招内推开始啦！
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(2) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”