竞赛讨论区 > 【题解】牛客小白月赛 54 题解
头像
CSP_Sept
发布于 08-12 21:22
+ 关注

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

统计 & 难度情况

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

A

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

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

时间复杂度

#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,强制不取到它,每次贪心进入尽量多的房间。

则我们考虑,若不取到编号为 的 debuff,可以进到哪些房间。显然,对于 的房间我们均可以进入,其余的我们均不可以进入。则我们有了 的做法。

由于 ,上述做法是不会进入重复的房间的。则我们考虑进行前缀和优化, 表示 的房间积分的和, 表示 的房间积分的和。则答案为 。时间复杂度

#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

我会开数组!

直接开一个二维数组

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

无法通过此题。

算法 2

我会暴力!

对于每一个询问的 ,枚举 个区间,暴力判断 是否在区间中。

时间复杂度 ,无法通过此题。

算法 3

我会找规律!

开两个数组 表示第 个小时能否通话, 表示 能否通话。

对于 的区间,做如下操作:

  • 标记为不可通话
  • 标记为不可通话
  • 标记为不可通话

伪代码如下(对于单个区间):

时间复杂度 ,以及空间复杂度 ,无法通过此题。

算法 4

我会分块!

考虑仍然将 拆分为 三部分,但对于 两段,我们仅维护对应小时内左右最大拓展的端点

同时注意到 时,需要在该小时内另外维护一个中间段的左右端点

这样一来消去了算法 3 中 数组的一维,同时复杂度为 ,可以通过此题。

#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

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

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

#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,设 表示走到 时已经匹配到 的第 个字符时能获得的最大答案。

然后可以扫一遍转移,最终答案是

时间复杂度

注意 的情况,特意卡了。

#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

考虑先判断无解的情况。

  • 容易发现,前者则无法联通,后者则必有重边。

  • 由于限制形如“必须经过点 ”,则必有

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

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

对于剩下的 的所有 ,我们考虑其奇偶性。

  • ,我们只对其连一条边 。此时由于只有这一条边可以到达 ,从 经过 的最短路方案一定是

  • ,我们对于所有这样的 组成的集合 ,找到一个位置 使 ,连边 。对于其余的 ,连边 。然而对于 的特例是无解的。容易看出,这种情况下 这两条路径中必有一条长度为

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

对于无用边的构造,注意满足 和无重边即可。

时间复杂度

#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();
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐