#牛客周赛 Round 54 （A~E）

前言：

以后会定时更新很多比赛的题解  希望借此让自己坚持赛后补题  
要不然写完就结束 自己水平没有一点提高  本人很菜所以不会更新
太难的题  加油！！！

1. ​清楚姐姐的糖葫芦

题目描述 :
输出字符‘o’个数

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int, int>pii;
const int N = 1e3 +10, MOD= 1e9+7;void solve(){string str;cin >> str;int res = 0;for(int i = 0; i < str.length(); i++){if(str[i] == 'o')res++;}	cout << res << endl;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--) solve();return 0;
}

很简单的签到题 唯一全对的
​

2. 清楚姐姐买竹鼠

题目描述 :
清楚姐姐买竹鼠，a 元可以买一只竹鼠，b 元可以买三只竹鼠，问至少买 x 只竹鼠要花多少钱。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int, int>pii;
const int N = 1e3 +10, MOD= 1e9+7;void solve(){int a, b, x;cin >> a >> b >> x;int ans = 0;if(b < a*3){int t = x/3;int t2 = x%3;ans = t*b+ min(a*t2, b); //如果b的价格小于a*剩余鼠的数量则 可以用b元买三只鼠}else{ans = a*x;}cout << ans << endl;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--) solve();return 0;
}

原题目这么描述的读起来有点怪 导致我就拿了90 他这个买x只鼠 可以多余x只鼠 求至少x只鼠的最小价格

3. 竹鼠饲养物语

题目描述 :
鼠鼠快速成长饲料一共分为 m 个等级，初始时全部竹鼠都是零级竹鼠，投喂一袋“鼠鼠快速成长饲料I ”可以升级为一级竹鼠，继续投喂“鼠鼠快速成长饲料 II ”可以升级为二级竹鼠，……。需要注意的是，你不能越级投喂，例如，向零级竹鼠投喂“鼠鼠快速成长饲料 II ”没有任何效果
清楚一共有 n 袋饲料和无限多的零级竹鼠，问最多可以进行多少次有效投喂。

给定一个数组， 问其中可以连续的累加值是多少

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int, int>pii;
const int N = 1e3 +10, MOD= 1e9+7;void solve(){int n, m;cin >> n >> m;multiset<int>S;for(int i = 0; i < n; i++){int a;cin >> a;S.insert(a);}int ans = 0;int tmp = 1e9;for(int i = 1; i <= m; i++){if(S.find(i) == S.end()) break;tmp = min((int)S.count(i), tmp);ans += tmp;}cout << ans << endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--) solve();return 0;
}

比时 没考虑 如果前面的值的数量少于 他后面下一个值的数量 则有效的时前面较小的数量 而不是一昧着加连续的数量

没解出来的

4. 清楚姐姐跳格子

题目描述 :
从1号格子 走到n号格子， 每个格子有一个数 可以向右或向左走该格子数的因子步 问最少走几步到n
分析 :
由于每个格子上都是正整数， 所以都有因子1， 所以肯定有一种可以一直向右 每次走一个的方法 这样要走n-1步。
最优情况是是什么呢？就是当所在的格子有个因子为（n-1) 这样一部就可以到达终点。
所以在每个格子 可以走到终点的步数一定在1~n-1，
所以可以用bfs来求解此题 从1号格子开始枚举 判断其可以走的步数 到达下一个格子

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>pii;
const int N = 1e3+ 10;bool vis[N];//判断该节点是否已走过//宽搜 
void bfs(int n, vector<int>&a) {queue<pii>q;//宽搜队列  pii第一个存步数， 第二个存到达的节点 q.push({0,1});//首先 把0 和 开始1号节点进队 while(q.size()) {auto tmp = q.front();//取队首元素 q.pop();if(tmp.second == n) { //边界条件 到达n号格子 cout << tmp.first;//输出次数 return;}if(vis[tmp.second]) continue;//已被访问 vis[tmp.second] = true;for(int i = 1; i< n; i++) {//枚举到达终点 在当前格子每次可以走的步数 if(a[tmp.second]%i) continue; //当前步数 不是此格子因子 不能走 if(i + tmp.second <= n && !vis[tmp.second + i]) { //在当前格子可以 向右走的步数q.push({tmp.first+1,i + tmp.second});}if(tmp.second - i >= 1 && !vis[tmp.second - i]) {//同理 向左走 q.push({tmp.first+1,tmp.second-i});}}}
}void solve() {int n;cin >> n;vector<int> a(n+1,0);for(int i = 1; i <= n; i++) {cin >> a[i];}bfs(n,a);
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}

5. 清楚姐姐的布告规划

题目描述 :
在长度为n的墙上贴布告板， 有n个布告板 要求
● 第 𝑖 张布告必须要覆盖掉布告板的第 i 个位置；
● 布告不能够相互重叠，但是可以紧贴。
问至少多少张才能贴满墙

分析 :
一道典型的DP问题 0-1背包 多了点限制
每块布告板可选 可不选 选的前提是满足第i块能把墙的第i个位置覆盖 且布告板不能重叠 所以每次选第i块布告板满足第i块布告板的左端点小于等于i,且第i块的右端点大于等于i. f[i][j] = k~前i块布告板中 能覆盖面积为j (j>=i)的最少块数为k 优化为一维 每次能选第i块的条件是 j >= i and j - a[i] + 1 <= i

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>pii;
const int N = 5e3+ 10;void solve() {int n;cin >> n;vector<int> a(n+1,0);for(int i = 1; i<= n; i++) {cin >> a[i];}vector<int>dp(n+1,1e9);dp[0] = 0;for(int i = 1; i <= n; i++) { //枚举第几块布告板for(int j = n; j >= a[i]; j--) { //枚举墙的总面积if(j >= i && j-a[i] + 1 <= i) //要求第i块布告要盖住第i块位置dp[j] = min(dp[j], dp[j-a[i]] + 1);}}if(dp[n] > n) dp[n] = -1;cout << dp[n] << endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--)solve();return 0;
}