2021年牛客集训第五场部分签到题

本文主要是介绍2021年牛客集训第五场部分签到题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

K-King of range

题目大意：给我们一组数组，计算有多少个区间的（max-min）> k。本题我打算暴力，结果代码通过率为0···自闭了   

解法：听说用st表和单调队列解决，看了一些大佬的代码发现貌似不难，比如l和r组成的区间合法，那么l向左同时r向右的区间均合法，这样可以省去不少时间

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N],q1[N],q2[N];
int n,m;
long long query(int x){
    int l1 = 1,r1 = 0,l2 = 1,r2 = 0;
    int l = 1;
    long long ans = 0;
    for(int i = 1;i <= n;i++){
        while(l1 <= r1 && a[q1[r1]] <= a[i]) r1--;
        while(l2 <= r2 && a[q2[r2]] >= a[i]) r2--;
        q1[++r1] = i;
        q2[++r2] = i;
        while(l <= i && a[q1[l1]] - a[q2[l2]] > x){
            ans += 1ll * (n - i + 1);
            l++;
            while(l1 <= r1 && q1[l1] <l) l1++;
            while(l2 <= r2 && q2[l2] <l) l2++;
        }
    }    
    return ans;
}
int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    while(m--){
        int x;
        cin >> x;
        printf("%lld",query(x));
　　　　　printf("\n");
    }
    return 0;
}

J.jewels

题目大意：你的坐标是( 0 , 0 , 0 ) (0,0,0)(0,0,0)，有m个宝物，分别坐标是是( x i , y i , z i ) ，你每次获取一个宝物的费用是两者的距离的平方，每秒只能获取一个宝物，从第0 00秒开始，问获取所有宝物的最小费用

解法：看数据小估计用DP？或者DFS，时间复杂度O（n³）左右，三次的没试过所以这题放弃了，看了大佬的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 310;
ll w[N][N];
ll la[N], lb[N];
bool va[N], vb[N];
int match[N];
int n;
ll delta, upd[N];
ll p[N];
ll c[N];
int x[N], y[N], z[N], v[N];

void bfs(int x)
{
    int a, y = 0, y1 = 0;
    for (int i = 1; i <= n; ++ i)
        p[i] = 0, c[i] = INF;
    match[y] = x;
    do {
        a = match[y], delta = INF, vb[y] = true;
        for (int b = 1; b <= n; ++ b) {
            if (!vb[b]) {
                if (c[b] > la[a] + lb[b] - w[a][b])
                    c[b] = la[a] + lb[b] - w[a][b], p[b] = y;
                if (c[b] < delta) //还是取最小的
                    delta = c[b], y1 = b;
            }
        }
        for (int b = 0; b <= n; ++ b)
            if (vb[b])
                la[match[b]] -= delta, lb[b] += delta;
            else c[b] -= delta;
        y = y1;
    } while (match[y]);
    while (y)match[y] = match[p[y]], y = p[y];
}

ll KM()
{
    for (int i = 1; i <= n; ++ i)
        match[i] = la[i] = lb[i] = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j)
            vb[j] = false;
        bfs(i);
    }
    ll res = 0;
    for (int y = 1; y <= n; ++ y) //若匹配失败w[match[y]][y]=INF;
        res += w[match[y]][y];
    return res;
}

ll dis(int x, int y, int z) {
    return 1ll * x * x + 1ll * y * y + 1ll * z * z;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >>x[i] >> y[i] >> z[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i][j] = -1ll * dis(x[j], y[j], z[j] + (i - 1) * v[j]);
    printf("%lld\n",-1ll * KM());
    return  0;
}

上面的代码是参考了CSDN的匿枫大佬的

H.Holding Two

大意：构造01矩阵，使对角线、竖线、横线三个方向都不会出现三个相同的数字，如果不存在输出-1

题解：不可能不存在···构造00110011，下面岔开这种类型的就行，最简便的代码贴下面了，当然自己写的也可

#include <bits/stdc++.h>
using namespace std;
int a[2000][2000]={0},n,m;
int col[4]={1,1,0,0};
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int t=col[i%4];
        for (int j=0;j<m;j++){
            a[i][j]=1-t;
            t=a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cout<<a[i][j];
        }
        cout<<endl;
    }
}

CSDN某大佬看的，觉得很简洁就贴了，当然自己也写得出来（懒）

C.Cheating and Stealing（这种题不可能做得出来，写一下自己以后看看皮毛得了，这种过的人极少，代码这些全是贴的）

题意：

和打兵乓球差不多求题目要求的（自己看吧）

思路：

很显然，至少i 球分出胜负，所以枚举是调和级数O(nlogn),考虑如何O(1)预处理，事实上，我们发现只需要关注两边第i 次得分时候的情况和平局的情况，因为要么在此时决出胜负，要么一直平局到有人赢或无法决出胜负。那就预处理下前缀和和第i 个W/L的位置和在i次平局到什么时候可以分出胜负，就是个简单dp,分类讨论即可，具体来说就是

1.第i 次能赢吗

2.赢不了再加一个能赢吗

3.平局的话能赢吗

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int mod=998244353;
int sumW[maxn],sumL[maxn],cntW,cntL,posL[maxn],posW[maxn];
int equ[maxn],n;
char s[maxn];
int main(){ 
    cin>>n;
    cin>>(s+1);
    for(int i=1;i<=n;++i){ 
        if(s[i]=='W'){ 
            sumW[i]=sumW[i-1]+1;
            sumL[i]=sumL[i-1];
            posW[++cntW]=i;
        }else{
            sumW[i]=sumW[i-1];
            sumL[i]=sumL[i-1]+1;
            posL[++cntL]=i;
        }
    }
    for(int i=n+1;i>=1;--i){ 
        if(i>=n)
            equ[i]=n+1;
        else
            equ[i]=(s[i]==s[i+1])?i+1:equ[i+2];
    }
    int ans=0,win;
    for(int i=1,num=1;i<=n;++i,num=(ll)num*(n+1)%mod){ 
        win=0;
        for(int l=1,r;l<=n;l=r+1){ 
            int nxtW=(cntW-sumW[l-1]>=i)?posW[sumW[l-1]+i]:n+1;
            int nxtL=(cntL-sumL[l-1]>=i)?posL[sumL[l-1]+i]:n+1;
            if(nxtW==n+1&&nxtL==n+1){//分不出
                r=n;
            }else if(nxtW<nxtL){ 
                if(i-(sumL[nxtW]-sumL[l-1])>=2)//第i个已经赢了
                    r=nxtW,win++;
                else if(nxtW==n)//分不出
                    r=n;
                else if(nxtW+1!=nxtL){//加一场就赢了
                    r=nxtW+1,win++;
                }else{ 
                    int pos=equ[nxtW+2];
                    if(pos==n+1)r=n;
                    else r=pos,win+=(s[pos]=='W');//破平局
                } 
            }else{ 
                if(i-(sumW[nxtL]-sumW[l-1])>=2)
                    r=nxtL;
                else if(nxtL==n)
                    r=n;
                else if(nxtL+1!=nxtW)
                    r=nxtL+1;
                else{ 
                    int pos=equ[nxtL+2];
                    if(pos==n+1)r=n;
                    else r=pos,win+=(s[pos]=='W');
                }
            }
        }
        ans=(ans+(ll)win*num%mod)%mod;
    }
    cout<<ans;
    return 0;
}

原文链接：https://blog.csdn.net/weixin_45539557/article/details/119301046

这篇关于2021年牛客集训第五场部分签到题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！