牛客周赛Round57

ABC挺送，但C比较细节，D也是比较细节，E不太好写，F纯板子加个前缀和迷惑人

A

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans=0;
    for(int i=1;i<=5;i++)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            ans=i;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

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
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    map<pair<int, int>, int> mp;
    int ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        mp[{x, y}] = 1;
    }
    for (auto &[x, y] : mp)
    {
        int a = x.first;
        int b = x.second;
        if (s[a] == s[b])
        {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

C

这个注意到n-1表示n一定是11。特判123即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    //有两个k进制的数字
    //找到使得表示他们都是1的数字
    //由于一定可以输出一个2
    //因此只需要找到1个就可以
    ll n;
    cin>>n;
    if(n==2)
    {
        cout<<"NO"<<'\n';
    }
    else if(n==1)
    {
        cout<<"YES"<<'\n';
        cout<<2<<' '<<3<<'\n';        
    }
    else if(n==3)
    {
        cout<<"YES"<<'\n';
        cout<<2<<' '<<3<<'\n';
    }
    else
    {
        cout<<"YES"<<'\n';
        cout<<2<<" "<<ll(n-1)<<'\n';
    }
 
 
    return 0;
}

## D

找两边，记录在直线上的。

  • 先把两边较小的一边用了
  • 另外就尽量用较大的一边抵去直线上的。
  • 最后剩下的+1配即可。
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    // 找到在一边的，找到在另一边的即可
    int n, k, b;
    cin >> n >> k >> b;
    vector<int> ans_1(2 * n + 1);
    vector<int> ans_2(2 * n + 1);
    vector<int> ans_3(2 * n + 1);
    int cnt_1 = 0;
    int cnt_2 = 0;
    int cnt_3 = 0;
    int ans = 0;
    int cnt = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        int x, y;
        cin >> x >> y;
        int t = k * x + b;
        if (t > y)
        {
            ans_1[cnt_1++] = i;
        }
        else if (t < y)
        {
            ans_2[cnt_2++] = i;
        }
        else
        {
            ans_3[cnt_3++] = i;
        }
    }
    if (abs(cnt_1 - cnt_2) >= cnt_3)
        cout << min(cnt_1, cnt_2) + cnt_3 << '\n';
    else
        cout << n << '\n';
    if (cnt_1 > cnt_2)
    {
        for (int i = 0; i < cnt_2; i++)
        {
            cout << ans_1[i] << ' ' << ans_2[i] << " " << 'Y' << '\n';
        }
        if (cnt_1 - cnt_2 >= cnt_3)
        {
            for (int i = 0; i < cnt_3; i++)
            {
                cout << ans_3[i] << " " << ans_1[cnt_2 + i] << ' ' << 'Y' << '\n';
            }
            for (int i = cnt_2 + cnt_3; i < cnt_1; i += 2)
            {
                cout << ans_1[i] << ' ' << ans_1[i + 1] << " "
                     << "N" << '\n';
            }
        }
        else
        {
            for (int i = 0; i < cnt_1 - cnt_2; i++)
            {
                cout << ans_3[i] << " " << ans_1[cnt_2 + i] << ' ' << 'Y' << '\n';
            }
            for (int i = cnt_1 - cnt_2; i < cnt_3; i += 2)
            {
                cout << ans_3[i] << ' ' << ans_3[i + 1] << " "
                     << "Y" << '\n';
            }
        }
    }
    else
    {
        swap(ans_1, ans_2);
        swap(cnt_1, cnt_2);
        for (int i = 0; i < cnt_2; i++)
        {
            cout << ans_1[i] << ' ' << ans_2[i] << " " << 'Y' << '\n';
        }
        if (cnt_1 - cnt_2 >= cnt_3)
        {
            for (int i = 0; i < cnt_3; i++)
            {
                cout << ans_3[i] << " " << ans_1[cnt_2 + i] << ' ' << 'Y' << '\n';
            }
            for (int i = cnt_2 + cnt_3; i < cnt_1; i += 2)
            {
                cout << ans_1[i] << ' ' << ans_1[i + 1] << " "
                     << "N" << '\n';
            }
        }
        else
        {
            for (int i = 0; i < cnt_1 - cnt_2; i++)
            {
                cout << ans_3[i] << " " << ans_1[cnt_2 + i] << ' ' << 'Y' << '\n';
            }
            for (int i = cnt_1 - cnt_2; i < cnt_3; i += 2)
            {
                cout << ans_3[i] << ' ' << ans_3[i + 1] << " "
                     << "Y" << '\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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 500005;
int T, n, m, a[N];
int ans;
 
bool check(int x)
{
    while (x)
    {
        if (x % m > 1)
            return 0;
        x /= m;
    }
    return 1;
}
 
void dfs(int x)
{
    // cout<<x<<'\n';
    if (ans || x > 1e18 || x < 0)
        return;
    if (check(x) && x > 1)
    {
        ans = x;
        return;
    }
    dfs(x * n);
    dfs(x * n + 1);
}
void solve()
{
    cin >> n >> m;
    if (n < m)
        swap(n, m);
 
    dfs(1);
    if (ans)
    {
        cout << "YES\n";
        cout << ans << '\n';
    }
    else
        cout << "NO\n";
}
 
signed main()
{
    T = 1;
    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
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int t, x, y, q, a[N], m[N], s[N], tree[N], n;
int build(int i, int l, int r)
{
    if (l == r)
        return tree[i] = a[l];
    return tree[i] = min(build(i * 2, l, (l + r) / 2), build(i * 2 + 1, (l + r) / 2 + 1, r));
}
int query(int i, int l, int r)
{
    if (y < l || r < x)
        return 0x7f7f7f7f;
    if (x <= l && r <= y)
        return tree[i];
    return min(query(i * 2, l, (l + r) / 2), query(i * 2 + 1, (l + r) / 2 + 1, r));
}
int modify(int i, int l, int r)
{
    if (l == r && l == x)
        return tree[i] = y;
    if (x < l || r < x)
        return tree[i];
    return tree[i] = min(modify(i * 2, l, (l + r) / 2), modify(i * 2 + 1, (l + r) / 2 + 1, r));
}
int main()
{
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> m[i];
        s[i] = s[i - 1] + m[i];
        for (int j = 1; j <= m[i]; j++)
            cin >> a[++n];
    }
    memset(tree, 0x7f, sizeof(tree));
    build(1, 1, n);
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int i, j;
            cin >> i >> j >> y;
            x = s[i - 1] + j;
            modify(1, 1, n);
        }
        else
        {
            int i;
            cin >> i;
            x = 1, y = s[i];
            cout << query(1, 1, n) << "\n";
        }
    }
}