3931bdbac26e683cd6862b2bd575a38

----- 我稍微，去改变一下未来。

牛客周赛 Round 51

A

image-20240715001243582

观察一下。

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin>>x;
    cout<<(x+1)/2;
}

B

image-20240715001317862

可以整除3的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin>>x;
    long long ans=0;
    while(x--)
    {
        string s;
        cin>>s;
        for(auto c:s)
        {
            ans+=c-'0';
            ans%=3;
        }
    }
    if(ans%3==0)
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
        }
}

C

image-20240715001348183

本题很自然就会想到超级充电和不玩充电，但往往会忽略一种情况，就是先玩一会然后进行超级充电。

只要考虑了这个就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main()
{
    double x,y,t;
    double a,b,c;
    cin>>x>>y>>t;
    cin>>a>>b>>c;
    double ans=0;
    double j=100;
    if(x<=t)
    {
        ans=(j-x)/c;
    }
    else
    {
        ans=min((j-x)/b,(x-t)/y+(100-t)/c);
    }
    printf("%.8lf",ans);
}

D

image-20240715001444164

Ruby做法

1
2
3
4
5
a,b=gets.to_i,gets.to_i
while b>0
    a,b=b,a%b
end
print a

C++做法

只需要边做边取模即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    long long b,num=0,sum=0;
    cin>>s>>b;
    for(int i=0;i<s.size();i++)
    {
        num=s[i]-'0';
        sum=(sum*10+num)%b;
    }
    cout<<__gcd(sum,b);
}

E

image-20240715001644099

E可以猜出来二分加bfs，然后就可以做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool is(const vector<vector<int>>& matrix, int n, int mid) 
{
    if (matrix[0][0] > mid) 
    {
        return false;
    }
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;

    while (!q.empty()) 
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n - 1 && y == n - 1)
        {
            return true;
        }

        for (int i = 0; i < 4; ++i) 
        {
            int nx = x + d[i][0];
            int ny = y + d[i][1];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && matrix[nx][ny] <= mid) 
            {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    return false;
}

int Path(const vector<vector<int>>& matrix, int n) 
{
    int l = matrix[0][0];
    int r = matrix[0][0];

    for (const auto& row : matrix) 
    {
        for (int val : row) 
        {
            l = min(l, val);
            r = max(r, val);
        }
    }

    while (l < r) 
    {
        int mid = l + (r - l) / 2;
        if (is(matrix, n, mid)) 
        {
            r = mid;
        } 
        else 
        {
            l = mid + 1;
        }
    }

    return l;
}

int main() 
{
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            cin >> matrix[i][j];
        }
    }
    cout << Path(matrix, n) << endl;
}

F

image-20240715001735907

F其实比较水，一个最大子段和的板子更改一下而已，绝对值也一定是在最大值最小值里面取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=500005;

#define int ll

struct Tree{
    ll l,r;
    ll sum,lmax,lmin,rmax,rmin,ans;
}tr[N*4];

ll n,q,a[N];

void pushup(Tree &a,Tree &b,Tree &c){
    a.sum=b.sum+c.sum;
    a.lmax=max(b.lmax,b.sum+c.lmax);
    a.rmax=max(c.rmax,c.sum+b.rmax);
    a.lmin=min(b.lmin,b.sum+c.lmin);
    a.rmin=min(c.rmin,c.sum+b.rmin);
    a.ans=max(max(abs(b.ans),abs(c.ans)),max(abs(b.rmax+c.lmax),abs(b.rmin+c.lmin)));
}

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

Tree query(int u,int x,int y){
    int l=tr[u].l,r=tr[u].r,mid=(l+r)/2;
    if(x<=l&&y>=r)return tr[u];
    
    if(y<=mid)return query(u<<1,x,y);
    else if(x>mid)return query(u<<1|1,x,y);
    else{
        auto b=query(u<<1,x,y);
        auto c=query(u<<1|1,x,y);
        Tree a;
        pushup(a,b,c);
        return a;
    }
}

void build(int u,int l,int r){
    if(l==r)tr[u]={l,r,a[l],a[l],a[l],a[l],a[l],abs(a[l])};
    else{
        tr[u]={l,r};
        int mid=(l+r)/2;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    
    cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        auto t=query(1,l,r);
        cout<<t.ans<<"\n";
    }
}

signed main(){
    solve();
    return 0;
}