2022-08-12 21:22 江西省上饶市玉山县玉山一中机械设计/制造

关注

【题解】牛客小白月赛 54 题解

统计 & 难度情况

AK 人数：1 人，低于预期。
ADE 相对之前的小白月赛可能偏易，BC 适中，我们注意到了 F 略高的难度。

A

显然每次操作都要让得分为正，且正数用的越多越好。

从大到小排序，扫前缀和并累加，直到前缀和为负为止。

时间复杂度 $O(\sum n)$ 。

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;

typedef long long LL;
const int INF =2147483647;
const int MAXN =2e5+3,MOD=1e7+7;
LL qread(){
    LL w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10ll+c-'0';
    return ret*w;
}
void write(LL t){
    if(t>9ll) write(t/10ll); putchar('0'+t%10ll);
}
LL n,ans,sum,A[MAXN];
void Solve(){
    sum = 0, ans = 0;
    n=qread(); up(1,n,i) A[i]=qread();
    sort(A+1,A+1+n); sum+=A[n]; dn(n-1,1,i){
        sum+=A[i]; if(sum>=0ll) ans=(ans+sum)%MOD; else break;
    }
    write(ans%MOD); puts("");
    return;
}
int main(){
    int T = qread();
    while(T--) Solve();
    return 0;
}

B

题目要求身上不带有一种 debuff 即可。我们可以考虑枚举这个不带有的 debuff，强制不取到它，每次贪心进入尽量多的房间。

则我们考虑，若不取到编号为 $x$ 的 debuff，可以进到哪些房间。显然，对于 $r_i < x$ 和 $l_i > x$ 的房间我们均可以进入，其余的我们均不可以进入。则我们有了 $O(nm)$ 的做法。

由于 $l_i \le r_i$ ，上述做法是不会进入重复的房间的。则我们考虑进行前缀和优化， $pre_x$ 表示 $r_i \le x$ 的房间积分的和， $suf_x$ 表示 $l_i \ge x$ 的房间积分的和。则答案为 $\max \limits_{i=1}^m pre_{i-1} + suf_{i+1}$ 。时间复杂度 $O(n+m)$ 。

#include <bits/stdc++.h>
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define per(i, b, s) for(int i = (b); i >= (s); --i)
#define ll long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define mp make_pair
#define Ld long double
#define pii pair<int, int>
#define mid (l + r >> 1)

using namespace std;

const int N = 1e6 + 5;

int n, m;
int l[N], r[N], s[N];
ll pre[N], suf[N];

int main() {
    ios;
    cin >> n >> m;
    assert(n >= 1 && n <= (int)(1e6));
    assert(m >= 1 && m <= (int)(1e6));
    rep(i, 1, n) cin >> l[i] >> r[i] >> s[i];
    rep(i, 1, n) {
        assert(l[i] >= 1 && l[i] <= m);
        assert(r[i] >= l[i] && r[i] <= m);
        assert(s[i] >= 1 && s[i] <= (int)(1e9));
        pre[r[i]] += s[i];
        suf[l[i]] += s[i];
    }
    rep(i, 1, m) pre[i] += pre[i - 1];
    per(i, m, 1) suf[i] += suf[i + 1];
    ll ans = 0;
    rep(i, 1, m) ans = max(ans, pre[i - 1] + suf[i + 1]);
    cout << ans << endl;
    return 0;
}

C

算法 1

我会开数组！

直接开一个二维数组 $Can$ ， $Can_{i,j}=1:\tt{i:j\ can't\ call}$ 。

对于每一个区间，暴力枚举这个区间内的所有时刻，存储在 $Can$ 数组中。

无法通过此题。

算法 2

我会暴力！

对于每一个询问的 $x,y$ ，枚举 $n$ 个区间，暴力判断 $x:y$ 是否在区间中。

时间复杂度 $O(nq)$ ，无法通过此题。

算法 3

我会找规律！

开两个数组 $H$ 和 $M$ ， $H_i$ 表示第 $i$ 个小时能否通话， $M_{i,j}$ 表示 $i:j$ 能否通话。

对于 $a:b\to c:d$ 的区间，做如下操作：

将 $M_{a:b\to a:(m-1)}$ 标记为不可通话。
将 $M_{c:0\to c:d}$ 标记为不可通话。
将 $H_{(a+1)\to(c-1)}$ 标记为不可通话。

伪代码如下（对于单个区间）：

$\def\b#1{ \textbf{ #1 } } \def\t#1{\text{ #1 }} \def\s{\quad} \def\l{\underline{\kern{300pt}}\\[-10pt]} \def\r{\overline{\underline{\kern{300pt}}}} \begin{aligned} &\r\\&\b{Algoirithm:}\t{School Card}\\[-13pt]&\l\\ &\begin{aligned} \t{1.}&\b{function} \t{Solution}(a,b,c,d,h,m): \\ \t{2.}&\s\b{for} i \b{from} b \b{to} m-1 \b{step} 1\\ \t{3.}&\s\s M[a][i]\gets 1 \\ \t{4.}&\s \b{end for} \\ \t{5.}&\s\b{for} i \b{from} 0 \b{to} d \b{step} 1\\ \t{6.}&\s\s M[c][i]\gets 1 \\ \t{7.}&\s \b{end for} \\ \t{8.}&\s\b{for} i \b{from} a+1 \b{to} c-1 \b{step} 1\\ \t{9.}&\s\s H[i]\gets 1 \\ \t{10.}&\s \b{end for} \\ \end{aligned}\\[-12pt] &\r \end{aligned}$

时间复杂度 $O(n(2\cdot m+h))$ ，以及空间复杂度 $O(hm)$ ，无法通过此题。

算法 4

我会分块！

考虑仍然将 $a:b\to c:d$ 拆分为 $\underline{a:b\to(a+1):0},\underline{(a+1):0\to c:0},\underline{c:0\to c:d}$ 三部分，但对于 $1,3$ 两段，我们仅维护对应小时内左右最大拓展的端点。

同时注意到 $a=c$ 时，需要在该小时内另外维护一个中间段的左右端点 $l,r$ 。

这样一来消去了算法 3 中 $M$ 数组的一维，同时复杂度为 $O(nm)$ ，可以通过此题。

#include <cstdio>

#define N 10010
#define min(a, b) ((a) < (b)) ? (a) : (b)
#define max(a, b) ((a) > (b)) ? (a) : (b)
using namespace std;
inline int rd();
int a, b, c, d, x, y, n, q, h, m;
bool H[N];
int l[N], r[N], p[N], s[N];
int main(){
    n = rd(), h = rd(), m = rd(), q = rd();
    for(int i = 0 ; i < h ; i++) l[i] = s[i] = m, r[i] = p[i] = -1;
    for(int i = 1 ; i <= n ; i++){
        a = rd(), b = rd(), c = rd(), d = rd();
        if(a < c){
            s[a] = min(s[a], b), p[c] = max(p[c], d);
            for(int i = a + 1 ; i < c ; i++)
                H[i] = 1;
        }
        else
            l[a] = min(l[a], b), r[a] = max(r[a], d);
    }
    while(q--){
        x = rd(), y = rd();
        puts((y >= l[x] && y <= r[x])
             || (y <= p[x] || y >= s[x]) || H[x] ? "No" : "Yes");
    }
    return 0;
}
inline int rd(){
    char c;
    bool flag = 0;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag = 1;
    int res = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

D

发现对于每一个单词表里的单词，我们只需要知道其最少多少步可以由 $s$ 变化而来，以及上一步由谁变化而来。而每次仅能改变一个位置的字母。

考虑进行 bfs，每步枚举改变的位置和变成什么字母。对于每一个单词表里的单词以及 $s,t$ ，我们只会让其入队一次，而每次会枚举如何改变。我们用 map 记录每个单词在单词表中的位置，从而时间复杂度是 $O(26nm \log nm)$ 。

#include <bits/stdc++.h>
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define per(i, b, s) for(int i = (b); i >= (s); --i)
#define ll long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define mp make_pair
#define Ld long double
#define pii pair<int, int>
#define mid (l + r >> 1)

using namespace std;

const int N = 5005;

int n, m;
string s[N];
int frm[N];
bool vis[N];
int st[N];
map<string, int> id;

void print(int x) {
    if(x == -1) return ;
    print(frm[x]);
    cout << s[x] << '\n';     
}

void bfs() {
    memset(frm, -1, sizeof frm);
    queue<int> q; q.push(0);
    vis[0] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        string nw = s[u];
        rep(i, 0, m - 1) {
            char lst = nw[i];
            rep(j, 0, 25) {
                nw[i] = (char)('a' + j);
                int idd = id[nw];
                if(id.find(nw) != id.end() && !vis[idd]) {
                    vis[idd] = 1;
                    frm[idd] = u;
                    st[idd] = st[u] + 1;
                    q.push(idd);
                }
            }
            nw[i] = lst;
        }
    }
    cout << st[n] - 1 << endl;
    if(!st[n]) return ;
    print(n);
}

int main() {
    ios;
    cin >> n >> m;
    rep(i, 1, n) cin >> s[i];
    cin >> s[0] >> s[n + 1]; ++n;
    rep(i, 0, n) id[s[i]] = i;
    bfs();
    return 0;
}

E

考虑 dp，设 $dp[i][j][k]$ 表示走到 $(i,j)$ 时已经匹配到 $s$ 的第 $k$ 个字符时能获得的最大答案。

然后可以扫一遍转移，最终答案是 $\max\limits_{i=1}^{|s|}\{dp[n][m][i]\}$ 。

时间复杂度 $O(nm|s|)$ 。

注意 $|s|=1$ 的情况，特意卡了。

#include <bits/stdc++.h>
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define per(i, b, s) for(int i = (b); i >= (s); --i)
#define ll long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define mp make_pair
#define Ld long double
#define pii pair<int, int>
#define mid (l + r >> 1)

using namespace std;

const int N = 105;

int n, m, sz;
string s;
char mz[N][N];
int dp[N][N][N];

int main() {
    cin >> n >> m;
    cin >> s;
    sz = s.size();
    s = ' ' + s;
    rep(i, 1, n) scanf("%s", mz[i] + 1);
    memset(dp, -0x3f, sizeof dp);
    dp[0][1][0] = dp[1][0][0] = 0;
    if(sz == 1 && mz[1][1] == s[1]) dp[1][1][0] = 1;
    rep(i, 1, n) rep(j, 1, m) {
        rep(k, 1, sz) {
            if(s[k] != mz[i][j]) continue;
            if(k == 1 && sz != 1) dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j][0], dp[i][j - 1][0]));
            else dp[i][j][k] = max(dp[i][j][k], max(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]) + (k == sz));
        }

        rep(k, 0, sz) dp[i][j][0] = max(dp[i][j][0], max(dp[i][j][k], max(dp[i][j - 1][k], dp[i - 1][j][k])));
    }
    int ans = 0;
    rep(i, 0, sz) ans = max(ans, dp[n][m][i]);
    cout << ans << '\n';
    return 0;
}

F

考虑先判断无解的情况。

$m < n-1$ ， $\dfrac{n \times (n-1)}{2} < m$

容易发现，前者则无法联通，后者则必有重边。
$d_1 \not= d_n$ ， $\min\limits_{i=1}^n d_i < d_1$

由于限制形如“必须经过点 $i$ ”，则必有 $d_1=d_n=\min\limits_{i=1}^n d_i$ 。

其余的无解会在下面进行说明。在上面的限制下，观察到我们可以构造形如 $(u,v,10^9)$ 的无用边来达到总边数 $=m$ 的目标，则我们只需要最小化满足要求的图 $G$ 的总边数。

接下来我们考虑直接对这张图进行构造。首先我们提出所有 $d_i=d_1$ 的点 $i$ ，并将其连成链。我们将其中一条边的边权设为 $d_1$ ，其余的设为 $0$ 。

对于剩下的 $d_i>d_1$ 的所有 $d_i$ ，我们考虑其奇偶性。

若 $d_i \equiv d_1 (\bmod 2)$ ，我们只对其连一条边 $(1,i, \dfrac{d_i - d_1}{2})$ 。此时由于只有这一条边可以到达 $i$ ，从 $1$ 经过 $i$ 到 $n$ 的最短路方案一定是 $1 \rightarrow i \rightarrow 1 \rightarrow n$ 。
若 $d_i \not\equiv d_1 (\bmod 2)$ ，我们对于所有这样的 $d_i$ 组成的集合 $S=\{d_i\}$ ，找到一个位置 $x$ 使 $d_x = \min(S)$ ，连边 $(1,x,\dfrac{d_x}{2})$ ， $(x,n,d_x - \dfrac{d_x}{2})$ 。对于其余的 $i \not= x$ ，连边 $(i,x,\dfrac{d_i - d_x}{2})$ 。然而对于 $d_1=0, d_x=1$ 的特例是无解的。容易看出，这种情况下 $1 \rightarrow x \rightarrow 1 \rightarrow n$ 和 $1 \rightarrow n \rightarrow x \rightarrow n$ 这两条路径中必有一条长度为 $0$ 。

容易证明，如上的构造一定是最优的。则我们只需要判断上面提到的无解，以及在最优构造方案下边数不够用的情况。

对于无用边的构造，注意满足 $u<v$ 和无重边即可。

时间复杂度 $O((n+m) \log m)$ 。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#include<vector>
using namespace std;

int n,m;
int d[300005];

struct note{
    struct G{
        struct note{
            int x,y,w;
        };
        map<pair<int,int>,bool> vis;
        vector<note> anslist;
        bool insert(int x,int y,int w) {
            if (x>y) swap(x,y);
            if (vis.count({x,y})) return false;
            vis[{x,y}]=true;
            anslist.push_back({x,y,w});
            return true;
        }
        void print() {
            for (auto e : anslist) {
                printf("%d %d %d\n",e.x,e.y,e.w);            
            }
        }
    }g;
    vector<int> ext;
    void insert_ext(int id) {
        ext.push_back(id);
    }
    vector<int> spec;
    void insert_spec(int id) {
        spec.push_back(id);
    }
    void work() {
        g.insert(1,n,d[1]);
        for (auto id : ext) {
            g.insert(1,id,(d[id]-d[1])/2);
        }

        int Min = 2e9, Minid = -1;
        for (auto id : spec) {
            if (Min>d[id]) {
                Min = d[id];
                Minid = id;
            }
        }
        if (Minid != -1) {
            g.insert(1,Minid,d[1]);
            g.insert(Minid,n,d[Minid]-d[1]);    
            if (d[1]==0 || d[Minid]==0) throw -5;
        }
        for (auto id : spec) {
            if (id!=Minid) {
                g.insert(id,Minid,(d[id]-d[Minid])/2);
            }
        }

        int res = m - g.anslist.size();
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++) if (i!=j) {
                if (res==0) return;
                if (g.insert(i,j,1e9)==true) res--;
            }
        if (res) throw -6;
    }
}ans;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&d[i]);
    try {
        if (m<n-1) throw -1;
        if (d[1]!=d[n]) throw -2;
        for (int i=2;i<n;i++) 
            if (d[i]<d[1]) throw -3;
        for (int i=2;i<n;i++) {
            if ((d[i]-d[1])%2==0) {
                ans.insert_ext(i);
            }else{
                if (m<n) throw -4;
                ans.insert_spec(i);
            }
        }
        ans.work();
    }catch(int error) {
        puts("No");
        return 0;
    }
    puts("Yes");
    ans.g.print();
}