牛客周赛 Round 56

A

简单的模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,y;
    cin>>n>>x>>y;
    if(n+x<=y)
    {
        cout<<"YES"<<'\n';
    }
    else
    {
        cout<<"NO"<<'\n';
    }
}

B

简单模拟即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    int n,m ,k;
    cin>>n>>m>>k;
    vector<int>a(n+1);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sum/=k;
    if(sum>=m+1)
    {
        cout<<m+1<<'\n';
    }
    else
    {
        cout<<sum<<'\n';
    }
    return 0;
}

C

注释那里解释了一下奇数和偶数异或1之后各自的变化。

但是1和1e9是需要进行一下特殊判断的。

只需要找两个数异或是1即可，2和3显然符合要求。

1e9的话我的选择是打表，打个表去找一下就可以了。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    //如果是奇数和1异或的话，会减去1
    //如果是偶数和1异或的话，会加上1
    int t;
    cin>>t;
    while(t--)
    {
        ll x;
        cin>>x;
        if(x==1)
        {
            cout<<2<<' '<<3<<'\n';
        }
        else if(x==1000000000)
        {

            cout<<1000000000-1<<' '<<1023<<'\n';
        }
        else if(x&1)
        {
            cout<<1<<' '<<x-1<<'\n';
        }
        else 
        {
            cout<<1<<' '<<x+1<<'\n';
        }
    }
    return 0;
}

D

自觉得的一个贪心做法， 没想到就是正解了。

只需要排序，然后直接按照从大到小的去选择即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
 
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<ll>a(n+1);
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a.begin()+1,a.end());
        ll ans=0;
        for(int i=n;i>=3;i--)
        {
            for(int j=i-2;j>=1;j--)
            {
                if(a[i]>=a[j]+a[j+1])
                {
                    break;
                }
                ans=max(a[i]+a[j]+a[j+1],ans);
            }
        }
        if(ans==0)
        {
            cout<<-1<<'\n';
        }
        else
        {
        cout<<ans<<'\n';
        }
    }
 
 
    return 0;
}

E

模拟题，见题解区域。

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
#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n, m;
    std::cin >> n >> m;

    auto cal = [&] (std::string s) -> int {
        int h = 0, m = 0;
        h = (s[0] - '0') * 10 + (s[1] - '0');
        m = (s[3] - '0') * 10 + (s[4] - '0');
        return h * 60 + m;
    };

    std::vector<int> vis(200, 0);
    for (int i = 1; i <= n; i++) {
        std::string s1, s2;
        std::cin >> s1 >> s2;
        
        int tmp1 = cal(s1), tmp2 = cal(s2);
        if (tmp1 >= tmp2) {
            for (int i = 0; i <= std::min(120, tmp2); i++) {
                vis[i] = 1;
            }
            for (int i = tmp1; i <= 120; i++) {
                vis[i] = 1;
            }
        }
        else {
            for (int i = tmp1; i <= std::min(120, tmp2); i++) {
                vis[i] = 1;
            }
        }
    }

    std::map<std::string, int> mp;
    for (int i = 1; i <= m; i++) {
        std::string s;
        std::cin >> s;
        mp[s] = 1;
    }

    int q;
    std::cin >> q;
    while(q--) {
        std::string s;
        std::cin >> s;
        int tmp = cal(s);
        std::string s1, s2, s3;
        std::cin >> s1 >> s2 >> s3;

        if (tmp >= 120 || !vis[tmp]) {
            std::cout << "Loser xqq" << '\n';
            continue;
        }

        int tmp1 = cal(s1), tmp2 = cal(s2);
        if (tmp1 > tmp2 || !mp.count(s3)) {
            std::cout << "Joker xqq" << '\n';
            continue;
        }

        std::cout << "Winner xqq" << '\n';
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
 
const int P = 13331;
const i64 hash_mod = 1610612741;
 
void solve()
{
    int n;
    cin >> n;
 
    string s, t;
    cin >> s >> t;
    s = ' ' + s, t = ' ' + t;
    vector<i64> h1(n + 1), h2(n + 1), h3(n + 1), p(n + 1);
 
    p[0] = 1, h1[0] = 0, h3[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * P % hash_mod;
        h1[i] = (h1[i - 1] * P + s[i]) % hash_mod;
        h3[i] = (h3[i - 1] * P + t[i]) % hash_mod;
    }
    h2[0] = 0;
    reverse(s.begin() + 1, s.end());
    for (int i = 1; i <= n; i++)
    {
        h2[i] = (h2[i - 1] * P + s[i]) % hash_mod;
    }
 
    auto get = [&](int l, int r, vector<i64> &h) -> i64
    {
        return ((h[r] - h[l - 1] * p[r - l + 1]) % hash_mod + hash_mod) % hash_mod;
    };
 
    int mx = 0, pos = 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = n;
        while (l <= r)
        {
            int mid = l + r >> 1;
            i64 tar = get(1, mid, h3);
            i64 num = 0;
            if (mid > i)
            {
                num = get(i + 1, mid, h1);
                num = (num + get(n - i + 1, n, h2) * p[mid - i]) % hash_mod;
            }
            else
            {
                num = get(n - i + 1, n - i + mid, h2);
            }
 
            if (tar == num)
            {
                l = mid + 1;
                if (mid > mx)
                {
                    mx = mid;
                    pos = i;
                }
            }
            else
            {
                r = mid - 1;
            }
        }
    }
 
    cout << mx << ' ' << pos << '\n';
}
 
signed main()
{
 
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}