文章目录
- 写在前面
- A tb的区间问题
- 思路
- code
- B tb的字符串问题
- 思路
- code
- C tb的路径问题
- 思路
- code
- D tb的平方问题
- 思路
- code
- E tb的数数问题
- 思路
- code
牛客小白月赛101
写在前面
最近几天没怎么刷题,昨天晚上打的这场牛客月赛打的很烂,隔几天不刷题感觉自己的思维都钝化了,看来每天得刷几题找找手感,不然直接打训练赛容易暴毙
A tb的区间问题
思路
考点:模拟
由于每次只能删除第一个元素或者最后一个元素,那么操作k次后,剩余的序列一定是连续的
我们可以运用滑动窗口的思想,从左到右遍历,如果当前的窗口的个数超出 n − k n-k n−k 个,将最前面的元素减去即可
code
int a[N];
void solve(){int n,k;cin >> n >> k;for(int i=1;i<=n;++i) cin >> a[i];int sum=0;int ans=0;for(int i=1;i<=n;++i){sum+=a[i];if(i>=n-k){sum-=a[i-(n-k)];ans=max(ans,sum);}}cout << ans;return ;
}
B tb的字符串问题
思路
考点:单调栈
遍历字符串,如果当前字符和栈顶字符可以进行匹配(即"fc"或者"tb"),将栈顶出队
反之,将当前字符加入栈中
最后输出栈的大小即可
code
void solve(){int n;cin >> n;string s;cin >> s;stack<char> st;for(int i=0;i<s.size();++i){if(st.empty()) st.push(s[i]);else{if(st.top()=='f' && s[i]=='c' || st.top()=='t' && s[i]=='b'){st.pop();}else st.push(s[i]);}}cout << st.size() << endl;return ;
}
C tb的路径问题
思路
考点:找规律
把玩一下不难发现,每次进行传送的格子都是当x等于2的时候进行传送
- 当n大于等于4时,如果n为偶数,输出4
- 如果n为奇数,输出6
小于4的情况直接打印出来即可,一道很简单的规律题
code
void solve(){int n;cin >> n;if(n==1){cout << 0 << endl;}else if(n==2) cout << 2 << endl;else if(n==3) cout << 4 << endl;else{if(!(n & 1)) cout << 4 << endl;else cout << 6 << endl;}return ;
}
D tb的平方问题
思路
考点:差分
对于一个区间的问题,一般都需要用到差分
对于一个区间 [ l , r ] [l,r] [l,r] ,有且仅有一个完全平方数,因此我们可以用差分去维护这个区间
我们可以开一个map数组,key存的是sum,value存的是下标,用于差分维护
从左到右进行遍历,然后在开一重 j j j循环从1到sum
如果当前 s u m − j ∗ j sum-j*j sum−j∗j 在数组出现过,则用差分进行维护
最后进行前缀和处理,每次询问输出当前下标的值即可
code
int a[N],c[N];
void solve(){int n,q;cin >> n >> q;for(int i=1;i<=n;++i) cin >> a[i];int sum=0;map<int,int> m;m[0]=0;for(int i=1;i<=n;++i){sum+=a[i];for(int j=1;j*j<=sum;++j){if(m.count(sum-j*j)){c[m[sum-j*j]+1]++;c[i+1]--;}m[sum]=i;}}for(int i=1;i<=n;++i) c[i]+=c[i-1];while(q--){int x;cin >> x;cout << c[x] << endl;}return ;
}
E tb的数数问题
思路
考点:模拟
题目说的很清楚了,如果一个数的所有因子不在数组里,那这个数就不是好数字
首先需要进行特判,如果数组里面没有1,那么直接输出0(1作为因子是最基本的)
由于数据范围不大,因此可以从1遍历到数组中最大的数
如果当前数没被标记,则将它以及它之后的倍数都标记为0
最后统计被标记的数字即可
code
int a[N],vis[N],f[N];//vis标记数组,f操作数组(被操作过的数不需要在进行操作)
void solve(){int n;cin >> n;int flag=0,mx=0;for(int i=1;i<=n;++i){cin >> a[i];if(a[i]==1) flag=1;mx=max(mx,a[i]); vis[a[i]]=1;} if(flag==0){cout << 0 << endl;return ;}for(int i=2;i<=mx;++i){if(!vis[i] && !f[i]){for(int j=i+i;j<=mx;j+=i){vis[j]=0;f[j]=1;}}}int ans=0;for(int i=1;i<=mx;++i){if(vis[i]) ans++;}cout << ans;return ;
}