发布这些文章的目的很简单:
1.作者自己也是c++刚起手没多久的小白,深知自学一门学校不开设课程的语言的难处,(为了改错到处求人问路,看了好多没有真正帮助自己学习知识盲区,掌握新知识的教学视频,自己理解有偏差不能及时改正的困难)尽可能地帮助广大姐妹哥们儿们,我保证博文中的每句话,我都是查好确定了才会编辑在这里面,如有错误谢谢包容,谢谢指出!
2.我学习有点急躁,想一下学会很多,但看得懂并不代表学会了,还要实操才行,把我会的讲出来,讲的同时发现自身的知识盲区,能够更好地使我改正错误并提升自己,也能够使我耐下心来,督促我自己更改错题。(只有把不会的真正学会了,才叫进步。)
话不多说进入正题:
AAAAA
#include<iostream>
using namespace std;
int main(){
string s;
cin>>s;
int num=0;
for(int i=0;i<s.length();i++){
if(s[i]=='o')
num++;
}
cout<<num;
return 0;
}
BBBBB
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll a,b,x;
cin>>a>>b>>x;
ll sum1=a*x;
ll sum2=(x%3)*a+x/3*b;
//ll sum3=(x+2)/3*b;
ll sum3=x/3*b+b;///和上面的公式等价,多买了竹鼠,但是少花了钱
cout<<min({sum1,sum2,sum3});
return 0;
}
CCCCC
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll n, m;
cin >> n >> m;
map<ll, ll> cnt;
// 用于存储每个等级的数量,这里为什么用map,而不用multiest,vector下面有详解
for (ll i = 1; i <= n; i++) {
ll x;
cin >> x;
if (x <= m) {
cnt[x]++; // 统计每个等级的数量
}
}
ll pre = n + 1;///将饲料可能出现的最多次数加一,来初始化这个pre
ll sum = 0;
for (ll i = 1; i <= m; i++) {
if (cnt[i] == 0) break; // 如果该等级不存在,直接跳出循环
//等价于if(!cnt.count(i)) break;下面会有详细介绍
pre = min(pre, cnt[i]);
//不等价于if(cnt[i]<=cnt[i-1])下面有详解
sum += pre;
}
cout << sum << endl; // 输出最大有效投喂次数
return 0;
}
1.这里为什么用map,而不用multiest,vector?
map适合处理稀疏的数据分布(即可能有的数据不连续,或者数据值较大但数量稀疏)。
vector,适合处理密集的等级分布(即从 1 到 m 的等级都有可能出现)
2.if (cnt[i] == 0) break;等价于if(!cnt.count(i)) break;
cnt.count(i) 的含义: cnt 是一个 map,它存储了每个竹鼠等级出现的次数(也就是每个等级的竹鼠数量)。 cnt.count(i) 的作用是检查 map 中是否存在键 i,即检查是否有等级为 i 的竹鼠。 如果存在键 i,则 cnt.count(i) 返回 1。 如果不存在键 i,则 cnt.count(i) 返回 0。
3.pre = min(pre, cnt[i]);不等价于if(cnt[i]<=cnt[i-1])?
我学STL容器也好一段时间了,但是其中的很多细节还没有学到,(这些细节要靠我们自己发掘的)其实这道题对于小白来说挺容易错的,(也可能是作者自己才疏学浅了哈哈)其实我第一反应是用multiset,因为他自动升序,可以允许有重复元素,但是在遍历过程中出现了问题......后来又尝试用vector,但是仍然错了,是在容器创建过程中.......(不是我说牢底,我这下面放的可有好几个细节,听君一席话胜读十年书,细节决定成败,good good study,day day up,我相信我就是天我相信明天!Oh,我就是,传说中的SuperStar,哥的造型,真是犀利......)
第一次错误(multiset)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll n, m;
cin >> n >> m;
multiset<ll> a; //自动升序饲料
for (ll i = 0; i < n; i++) {
ll x;
cin >> x;
a.insert(x);
}
ll num[m] = {0}; 1 1 1 1 2 2 3 4 5 7 8
///因为等级是覆盖式的,并且不可越级,
//所以饲料等级如果不连续,就直接跳出循环,此时即为最多有效次数
ll sum = 0;
for(auto it=a.begin();it!=a.end();it++){
num[(*it-1)]++;
}
for (ll i = 0; i < m; i++) {
sum += num[i];
if (num[i] == 0 && i<n) {//虽然求的是最多有效次数,要减去多加的这一次,其实不用管sum减去当前num[i]的事,因为此时num[i]=0;
break; //因为此时num[i]=0,所以没有写sum=sum-num[i],
}
}
cout << sum << endl;
return 0;
}
错误原因1(初始化问题)
错误原因2 (索引越界)
第二次错误(vector)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll n, m;
cin >> n >> m;
vector<ll> num(m + 1, 0); // 用于存储每个等级的数量
for (ll i = 1; i <= n; i++) {
ll x;
cin >> x;
if (x <= m) {
num[x]++; // 统计每个等级的数量
}
}
ll pre = n + 1;
ll sum = 0;
for (ll i = 1; i <= m; i++) {
if (num[i] == 0) break; // 如果该等级不存在,直接跳出循环
pre = min(pre, num[i]);
sum += pre;
}
cout << sum << endl; // 输出最大有效投喂次数
return 0;
}
错误原因
OK啦!家人们结束,Let's next one!Go,go,go
DDDDD
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int NUM = 2000;
ll visited[NUM];///用于记录每个格子的访问状态(以及到达该格子时所需的步数)
vector<ll> g[NUM];///用于存储每个格子的相邻格子列表。
int main() {
ll n;
cin >> n;
vector<ll> a(n + 1); // 注意这里大小为 n+1 因为题目是从 1 到 n
for(ll i = 1; i <= n; i++) cin >> a[i];
// 构建邻接表
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= n; j++){//j 从 1 开始的原因是,
//我们需要遍历所有格子 j,不论 j 在 i 的左侧还是右侧,以确保不遗漏任何可能的跳跃。
if(i != j && a[i] % abs(j - i) == 0){
//如果从格子i到格子j的距离abs(i - j)是a[i]的因子,则将格子j加入到格子i的邻接列表中。
g[i].push_back(j);
}
}
}
// BFS
queue<ll> q;
q.push(1);
visited[1] = 1;
while(!q.empty()){
ll temp = q.front();
q.pop();
for(auto i : g[temp]){//为什么是g[temp],而不是g,下面有详解
if(!visited[i]){
visited[i] = 1;
visited[i]=visited[temp]+1;
q.push(i);
}
}
}
cout << visited[n] - 1 << endl; // 输出从1号格子到n号格子的最小步数
return 0;
}
(1)典型的BFS,这个文章不方便解释清楚的,需要学的自己去搜网课哦!我简单说一下BFS迷宫模板:
1.创建三个容器,一个盛装需要输入的数据,一个装每个格子相邻的格子,一个盛装到达当前格子需要的步数。
2.读入数据后,将符合条件的当前格子的邻居格子放入存格子的容器中。
3.创建一个队列用来模拟走迷宫,遍历符合条件的格子同时记录步数。
4.输出题目需要的输出结果。
(2)现在解决上面注释中提到的问题:
EEEEE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[6000],dp[6000];
void solve(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll i=0;i<=n;i++) dp[i]=1e18;//不能初始化为dp[j]=1e19或者dp[j]=1e9之类的,下面有详解;
dp[0]=0;//必须有这句,下面有详解
for(ll i=1;i<=n;i++){
for(ll j=i+a[i]-1;j>=max(i,a[i]);j--){//从此步开始往前遍历
dp[j]=min(dp[j],dp[j-a[i]]+1);
}
}
cout<<(dp[n]==1e18?-1:dp[n])<<endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _=1;
cin>>_;
while(_--){
solve();
}
return 0;
}
基础的动态规划问题,下面来解决上面注释中提到的问题:
1.不能初始化为dp[j]=1e19或者dp[j]=1e9之类的
这个差异主要在于不同大小的初始值。如果使用 1e9,可能在某些测试数据下,dp[j] 的值会错误地认为已经有了更小的步数,而实际上它没有被正确覆盖。
因为 1e9 和 1e18 是不同的阈值,所以右边代码在某些情况下会错误地认为解是有效的,或者反过来。
2.dp[0]=0,必须要有这句
表示动态规划的初始位置,没有它的话,程序中的逻辑无法正确地推导出到达其他位置所需的最小步数,导致 dp 数组中未被更新的值依旧是初始化的 1e18,因此最终的输出会错误(出现乱码)。
FFFFF
这个题的难度不言而喻了吧,哈哈,量力而行哈,谢谢观看,再见,晚安,玛卡巴卡。
标签:cnt,Round54,格子,int,ll,ABCDE,long,牛客,dp From: https://blog.csdn.net/2302_80195998/article/details/141157866