牛客周赛 Round 54 (c++题解)

比赛地址 :

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A

输出'o'的个数；

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;inline void solve(){string s ; cin >> s ;int t  = 0 ;for(char c : s) t += (c=='o') ;cout << t << endl ;
}signed main(){IOSint _ = 1;while(_ --) solve();return 0;
}

B

模拟，因为至少买x ，要把x+1,x+2的情况也考虑上 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;inline void solve(){LL a , b , x ; cin >> a >> b >> x ;LL ans =  0 ;LL g = a * 3 ;if(g<=b) ans = 1LL * x * a ;else {LL s1 = 1LL*(x%3)*a + 1LL * b * (x/3) ;LL s2 = 1LL*((x+1)%3)*a + 1LL * b * ((x+1)/3) ;LL s3 = 1LL*((x+2)%3)*a + 1LL * b * ((x+2)/3) ;ans = min(s1,min(s2,s3)) ;}cout << ans << endl ;
}signed main(){IOSint _ = 1;while(_ --) solve();return 0;
}

C

模拟 :

1 . 排序

2 . 对于每一个饲料等级取和上一个较小的数量；

3 . 累加每一级，要求级数从1开始且连续 ;

详细请看代码：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;
typedef long long LL;inline void solve(){int n , m ; cin >> n >> m ;vector<int> a(n) ;int t = 0 ; for(int& x : a) {cin >> x ;if(x==1) t ++ ;}sort(a.begin(),a.end()) ;LL ans = 0 ;int pre = 0 ;int ps = n ;for(int i=0;i<n;i++){int j = i ;while(j<n && a[j]==a[i]) j++ ;int len = j - i  ;if(a[i]-pre==1){pre = a[i] ;ps = min(ps,len) ;ans += ps ;}else{break ;}i = j - 1 ;}cout << ans << endl ;
}signed main(){IOSint _ = 1;// cin >> _;while(_ --) solve();return 0;
}

D

bfs暴力即可 :

#include<bits/stdc++.h>
const int nn = 1e3+5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;ll n;
vector<ll> a(nn),dis(nn,inf);
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];queue<ll> q;dis[1] = 0;q.push(1);while(q.size()){ll v=q.front();q.pop();for(ll j=1;j<=n;j++){if(v==j)continue;if(a[v] % labs(v-j) == 0){if(dis[j]>dis[v]+1){dis[j] = dis[v]+1;q.push(j);}}}}if(dis[n]==inf) cout<<-1;else cout<<dis[n]<<endl;
}
int main() {ios::sync_with_stdio(), cin.tie(), cout.tie();int t=1;while(t--) solve();return 0;
}

但是数据小，dp几次也能过 :

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
const int N = 1e3 + 10 ;LL a[N] ;inline void solve(){int n ; cin >> n ;for(int i=1;i<=n;i++) cin >> a[i] ;vector<int> dp(n+1,n) ;dp[1] = 0 ;// 往左跳// 从前面和后面转移而来// dp[j] = min(dp[j],dp[i]+1) ;for(int k=0;k<15;k++){for(int i=1;i<=n;i++){for(int j=1;j<i;j++){// 判断j是否能跳到i ;int d = i - j ;if(a[j]%d==0) dp[i] = min(dp[i],dp[j]+1) ;}for(int j=n;j>i;j--){int d = j-i ;if(a[j]%d==0) dp[i] = min(dp[i],dp[j]+1) ;}}}cout << dp[n] << endl ;
}signed main(){IOSint _ = 1;while(_ --) solve();return 0;
}

E

dp , 一个线性dp ；

dp[i]代表长度为i个单位的ans ,最后输出dp[n] ;

枚举每个位置，分为使用第i张覆盖和使用i前面的覆盖两种情况；

使用第i张覆盖 : dp[i] = min(dp[i],dp[i-a[i]]+1) ;

不使用第i张覆盖 : 枚举j -> [1,i-1] , dp[i] = min(dp[i],dp[j-p-1]+1) ;

详情想想然后看代码便可理解 :

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;// 01 背包
// dp[i] 使用到第i位的ansinline void solve(){int n ; cin >> n ;vector<int> a(n+1) , dp(n+1,n+1);for(int i=1;i<=n;i++) cin >> a[i] ;if(a[1]<=n) dp[a[1]]=1;dp[0] = 0;for(int i=1;i<=n;i++){// 遍历每个位置// 使用第i张if(i-a[i]>=0&&dp[i-a[i]]!=(n+1)){dp[i] = min(dp[i],dp[i-a[i]]+1) ;}// 不使用第i张 , 使用前面的第j张   for(int j=1;j<i;j++){int d = i - j ;if(a[j]>=d+1){int p = a[j]-(d+1) ;if(j-p-1>=0&&dp[j-p-1]!=(n+1)){dp[i] = min(dp[i],dp[j-p-1]+1) ;}}}}    if(dp[n]==n+1) cout << -1 << endl ;else cout << dp[n] << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}