牛客小白月赛101（A~E）

牛客小白月赛101

写在前面

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

A tb的区间问题

思路

考点：模拟

由于每次只能删除第一个元素或者最后一个元素，那么操作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]$ ,有且仅有一个完全平方数，因此我们可以用差分去维护这个区间

我们可以开一个map数组，key存的是sum，value存的是下标，用于差分维护
从左到右进行遍历，然后在开一重$j$循环从1到sum
如果当前 $sum-j\ast 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 ;
}