牛客周赛 Round 46

A

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,m;
    cin>>n>>m;
    if((n/2)>=m) cout<<n+m<<endl;
    
    else cout<<n/2+n<<endl;
    return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int n,x;
int a[100010];
int mx,cnt;
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==x)
            a[i]=-1;
        mx= max(mx,a[i]);
    }
    for(int i=1;i<=n;i++)
        if(a[i]==mx)
            cnt++;
    cout<<cnt;
    return 0;
}

C

这是一道枚举因子的题目

很简单的枚举一下因子就可以了。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 100;
ll a[N];
void solve()
{
    ll n, x; cin >> n >> x;
    ll ans = 0;
    ll cnt=x;
    for(ll i=1;i<=n&&i*i<=x;i++)
    {
        if(x%i!=0)continue;
        if(i*i==x)
        {
            ans++;
            break;
        }
       ans++;
        if(x/i<=n)ans++;    
    }
    if (ans % 2 == 0)cout << "OFF";
    else cout << "ON";
 
}
int main()
{
    ios::sync_with_stdio, cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

D

这是一道需要进行一下讨论的题目

注意如果k>2，并且没有出现过就一定是不可以的，显然不满足题意。

其他只需要注意一步步进行讨论既可。

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
#include <bits/stdc++.h>
using namespace std;
int t;
int a,b,c,k;
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>t;
    while(t -- )
    {
        map<int,int>mp;
        cin>>a>>b>>c>>k;
        mp[a] ++;
        mp[b] ++;
        mp[c] ++;
        if(k > 2 && !mp[k]) cout<<-1<<'\n';
        else if(mp[k]) cout<<0<<'\n';
        else {
            if(k == 0)
            {
                if(mp[0]) cout<<0<<'\n';
                else cout<<1<<'\n';
            }else if(k == 1)
            {
                if(mp[1]) cout<<0<<'\n';
                else if(mp[0]) cout<<1<<'\n';
                else cout<<2<<'\n';
            }else if(k == 2)
            {
                if(mp[2]) cout<<0<<'\n';
                else if(mp[0] && mp[1]) cout<<1<<'\n';
                 else if(mp[0] || mp[1]) cout<<2<<'\n';
                else cout<<3<<'\n';
            }
        }
    }
    return 0;
}

E

记录一个前缀和和一个后缀和

每次找到那个刚好用完的，采用二分进行搜索即可。

这样子前面的就都是用完的，后面的就是全部可以使用K次的，因此两个前缀和的含义也是不一样的。

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
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5+5;
 
struct P {
    long long a=0, b=0;
};
 
P lst[N];
 
int n, q, k;
long long sum1[N], sum2[N];
 
bool cmp(P a1, P a2) {
    return a1.b < a2.b;
}
 
int bs(int k) {
    int l = 1, r = n, mid;
    while (l < r) {
        // 找第一个大于k的值
        mid = (l+r) >> 1;
        if (lst[mid].b > k) r = mid;
        else l = mid+1;
    }
     
    if (lst[l].b > k) return l;
    return n+1;
}
 
int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> lst[i].a;
    for (int i=1; i<=n; i++) cin >> lst[i].b;
     
    sort(lst+1, lst+n+1, cmp);
     
    for (int i=1; i<=n; i++) sum1[i] = sum1[i-1] + lst[i].a*lst[i].b;
    for (int i=n; i>=1; i--) sum2[i] = sum2[i+1] + lst[i].a;
    cin >> q;
     
    while (q--) {
        cin >> k;
        int t = bs(k);
         
        cout << sum1[t-1] + sum2[t]*k << '\n';
    }
    return 0;
}