牛客周赛 Round 54

A

直接计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
 
signed main(){
    string s;
    cin>>s;
    int ls=s.size();
    int cnt=0;
     
    for(int i=0;i<ls;i++){
        if(s[i]=='o')cnt++;   
    }
    cout<<cnt;
}

B

先康康三个买是不是比一个买更加实惠。如果更加实惠，那么肯定优先买3个，剩下的小于3的部分可以买3也不一定买3，因此需要讨论一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll a,b,x,sum;
    cin>>a>>b>>x;
    if(b>=3*a)
        sum=x*a;
    else
    {
        ll sum1=x/3*b+x%3*a;
        ll sum2=x/3*b+b;
        sum=min(sum1,sum2);
    }
    cout<<sum<<endl;
    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
36
37
38
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio();cin.tie();cout.tie();
 
using namespace std;
const int N = 1e6 + 10;
 
void solve(){
    int n, m;
    cin >> n >> m;
 
    map<int, int> mp;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        mp[x]++;
    }
 
    int ans = 0;
    int cnt = mp[1];
    ans += cnt;
 
    for(int i = 2;i <= m;i++){
        cnt = min(cnt, mp[i]);
        if(cnt == 0) break;
        ans += cnt;
    }
 
    cout << ans << endl;
}
 
signed main(){
    int _ = 1;
    while(_--){
        solve();
    }
    return 0;
}

D

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
#include<bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const int maxn = 1e3+3;
using ll = long long;
ll a[maxn],vis[maxn];
int dis[maxn];
 
void solve()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    queue<pair<int,int>> q;
    int x,y;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0,vis[1]=1;
    q.emplace(0,1);
    while(!q.empty())
    {
        x=q.front().first;
        y=q.front().second;
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(i==y) continue;
            if(a[y]%abs(y-i)==0&&!vis[i])
            {
                dis[i]=x+1;
                vis[i]=1;
                q.emplace(x+1,i);
            }
        }
    }
    cout<<dis[n]<<endl;
    return ;
}
 
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; T=1;
    while(T--) solve();
    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
#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n+1),dp(n+1,5006);
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[0] = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=n;j>=a[i];j--)
        {
            if(dp[j-a[i]]!=5006)
            {
                if(i<=j&&i>j-a[i])
                    dp[j] = min(dp[j],dp[j-a[i]]+1);
            }
        }
    }
    if(dp[n]==5006) cout<<-1<<"\n";
    else cout<<dp[n]<<"\n";
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
       
        solve();
    }
    return 0;
}

F

摆!