自学内容网 自学内容网

牛客小白月赛101(A~E)

牛客小白月赛101

写在前面

最近几天没怎么刷题,昨天晚上打的这场牛客月赛打的很烂,隔几天不刷题感觉自己的思维都钝化了,看来每天得刷几题找找手感,不然直接打训练赛容易暴毙

A tb的区间问题

思路

考点:模拟

由于每次只能删除第一个元素或者最后一个元素,那么操作k次后,剩余的序列一定是连续的
我们可以运用滑动窗口的思想,从左到右遍历,如果当前的窗口的个数超出 n − k n-k nk 个,将最前面的元素减去即可

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 sumjj 在数组出现过,则用差分进行维护
最后进行前缀和处理,每次询问输出当前下标的值即可

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 ;
}

原文地址:https://blog.csdn.net/wh233z/article/details/142413356

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!