2021-10-30 10:50 af C++

关注

牛客练习赛 90 题解

Solution

$T_1 :$ 梦想赛道

直接考虑到，这棵生成树的边肯定会被保留到我们生成的图中，可以考虑把这棵生成树中边权最大的那条边在新的图中再放一条权值为 $1$ 的重边，如果这个边权最大的边的权值仍然为 $1$ 则直接输出无解即可。

$T_2:$ 寒冬信使

设给定的 01 串为 $S$ ， $x = \displaystyle \sum_{i = 1}^n S_{i} \times i$ ，当 $x$ 为奇数时先手必胜，否则后手胜。

$T_3:$ 盾与战锤

设 $f_{i,j}$ 表示回复战盾间隔为 $i$ 的时候，选中的子序列长度为 $j$ 的时候能够造成的最大伤害。

把原序列从大到小排序后求一个前缀和 $S$ ，我们会发现， $f_{i,j}$ 一定是选择前 $j$ 大的数是最优的。

同时又可以证明，假如 $\lceil \frac{x}{i} \rceil = \lceil \frac{y}{i} \rceil \& x > y$ 那么选择 $f_{i,x}$ 一定比选择 $f_{i,y}$ 更优。

还有一个性质就是，最优方案中，在每一次怪物回复战盾之后到下一次回复战盾这段时间内，都是造成了大于战盾值的伤害的，这个的证明也很简单，如果不能造成伤害的话直接把这一段给删掉即可。

于是可以考虑对于 $k = i$ 的情况，我们直接枚举 $k$ 的倍数 $d$ 求 $f_{i,d}$ 然后再求 $\max$ 即可，根据上面提到的性质可以直接令 $f_{i,d} = S_d - (k / i) \times s$ 。

故时间复杂度： $O(n \ln n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Lep(i, r, l) for(int i = r ; i >= l ; i --)
#define Rep(i, l, r) for(int i = l ; i <= r ; i ++)
inline LL read() {
    LL x = 0, flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = x * 10 + ch - '0';
    return x * flag;
}
const int MAXN = 1e6 + 50;
int n, LOG[MAXN];
LL K, f[MAXN], A[MAXN];
bool cmp(LL a, LL b) { return a > b; }

int main() {
    n = read(), K = read();
    Rep(i, 1, n) A[i] = read();
    sort(A + 1, A + 1 + n, cmp);
    Rep(i, 1, n) f[i] = f[i - 1] + A[i];
    for(int i = 1 ; i <= n ; i ++) {
        LL Ans = 0;
        for(int j = i ; j <= n + i ; j += i) 
            Ans = max(Ans, f[min(j, n)] - K * (j / i));
        printf("%lld\n", Ans);
    }
    return 0; 
}

$T_4$ ：妄想集合

其实这道题比 $T_3$ 简单很多，毕竟不怎么要脑子。

我们考虑到，对于 $10^9$ 以内的数，倘若现在有超过 $44$ 个数的话，那么就一定能够从中挑出三个数构成三角形，证明的话即为极限情况就是这些数形成 $Fibonacci$ 数列的形式。

于是假如查询的集合中的数的数量是 $> 44$ 个的，就直接输出 YES。

经过了上面的判断，现在查询的区间 $[l,r]$ 一定长度不超过 $44$ , 否则就会被上面给判掉。

然后对于每一个位置考虑用一个 vector<int> 维护目前的数有哪些，对于询问的话，我们就直接暴力的扫区间 $l,r$ 内所有点的 vector，同时如果此刻目前的容器中有了 $44$ 个数以上了就直接 break，否则就继续。可以发现最后的 vector 要么有 $45$ 个数，要么只有小于等于 $44$ 个数。

对于 $45$ 个数的情况直接输出 YES，否则就用小学数学判断一下能否构成三角形即可。

对于修改操作，我们维护一个 set，表示的是此刻集合内还没有 44 个数的位置有哪些。

对于修改就暴力的找 set 中在区间 $[l, r]$ 内的位置改就行了，因为当集合内达到 $44$ 个数之后这个位置就会直接被删除，因此一个位置能够贡献的复杂度为 $O(\log n \times 44)$ ，于是维护修改的总复杂度为 $O(n \times \log n \times 44)$ 。

至此此题被解决。

Code

#include <bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
inline int read() {
    int x = 0, flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = x * 10 + ch - '0';
    return x * flag;
}
const int MAXN = 3e5 + 50;
int n, m;
vector <int> V[MAXN], Ans;
set <int> S;
char op[60];

int main() {
    n = read(), m = read();
    for(int i = 1 ; i <= n ; i ++) V[i].pb(read()), S.insert(i);
    for(int i = 1 ; i <= m ; i ++) {
        scanf("%s", op + 1);
        int l = read(), r = read(), k;
        if(op[1] == 'Q') {
            k = read(); int now = l - 1;
            while(now <= r) {
                set <int> :: iterator it = S.upper_bound(now);
                if(it == S.end() || *it > r || *it < l) break;
                now = *it, V[now].pb(k); 
                if(V[now].size() >= 46) S.erase(now);
            }
        }
        else {
            Ans.clear();
            if(r - l >= 46){ puts("YES"); continue; }
            for(int i = l ; i <= r ; i ++) {
                for(int j = 0 ; j < V[i].size();  j ++) 
                Ans.pb(V[i][j]);
                if(Ans.size() >= 46) break; // 怕挂判的 46
            }
            if(Ans.size() >= 46) { puts("YES"); continue; }
            if(Ans.size() <= 2) { puts("NO"); continue; }
            sort(Ans.begin(), Ans.end());
            int flag = 0;
            for(int i = 2 ; i < Ans.size() ; i ++) 
                if(Ans[i - 1] + Ans[i - 2] > Ans[i]) flag = 1;
            if(flag) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}