牛客周赛 Round 51

牛客周赛 Round 51

A-小红的同余_牛客周赛 Round 51 (nowcoder.com)

分类讨论：

只要$x$是奇数，我们就让$x+1$就可以得到$(x+1)modx$=$1$

如果是偶数就永远都不可能是$1$

void solve()
{
    int n;
    cin>>n;
    cout<<(n+1)/2<<endl;
    
}

B-小红的三倍数_牛客周赛 Round 51 (nowcoder.com)

小学数学题，把每一位加起来只要能被3整除就一定能被3整除

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string t;
        cin>>t;
        for(int j=0;j<t.size();j++)
             s+=t[j]-'0';
    }
    if(s%3==0)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

C-小红充电_牛客周赛 Round 51 (nowcoder.com)

阅读理解题

void solve()
{
    cin>>x>>y>>t>>a>>b>>c;
    double v;
    if(x<=t)v=(100-x)*1.0/c;
    else
    {
        v=(100-x)*1.0/b;
        double g=(x-t)*1.0/y;
        v=min(v,g+(100-t)*1.0/c);
    }
    printf("%.6lf",v);
}

D-小红的 gcd_牛客周赛 Round 51 (nowcoder.com)

D不太会

E-小红走矩阵_牛客周赛 Round 51 (nowcoder.com)

很经典的最大最小的问题，遇到这类问题直接二分答案。

二分完以后只要跑个dfs就行了，也就是如果遇到这个点数值比二分的大就不用走就行

void dfs(int mid,int x,int y,int cnt)
{
    st[x][y]=true;
    if(x==n&&y==n)
    {
        res=min(cnt,res);
        return;
    }
    if(cnt>res)return;
    for(int i=0;i<4;i++)
    {
        int tx=dx[i]+x,ty=dy[i]+y;
        if(tx<=0||ty<=0||tx>n||ty>n)continue;
        if(a[tx][ty]>mid)continue;
        if(st[tx][ty])continue;
        cnt=max(cnt,a[tx][ty]);
        dfs(mid,tx,ty,cnt);
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
                cin>>a[i][j];
     int l=0,r=1e9+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        res=1e9+10;
        memset(st,0,sizeof st);
       dfs(mid,1,1,a[1][1]);
        if(res<=mid)r=mid;
        else l=mid;
    }
    cout<<l+1<<endl;
}

F-小红的数组_牛客周赛 Round 51 (nowcoder.com)

线段树求最大子段和的模板题，无非就多要维护一个最小子段和，然后让区间最大子段和，还有区间最小子段和之间取个$max$就行了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 500010;

struct Node {
    int l, r;
    long long tmax, rmax, lmax, sum;
    long long tmin, rmin, lmin, sum_min;
} tr[4 * N];

int n, m;
int w[N];

void pushup(Node& u, Node& l, Node& r) {
    u.sum = l.sum + r.sum;
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
    
    u.sum_min = l.sum_min + r.sum_min;
    u.rmin = min(r.rmin, r.sum_min + l.rmin);
    u.lmin = min(l.lmin, l.sum_min + r.lmin);
    u.tmin = min(min(l.tmin, r.tmin), l.rmin + r.lmin);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r) {
        long long value = w[r];
        tr[u] = { l, r, value, value, value, value, value, value, value, value };
    } else {
        tr[u] = { l, r };
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

void modify(int u, int x, long long v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u] = { x, x, v, v, v, v, v, v, v, v };
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        Node res = query(1, x, y);
        long long max_abs_sum = max(abs(res.tmax), abs(res.tmin));
        printf("%lld\n", max_abs_sum);
    }
    return 0;
}