寒假集训营题解

欢宴的独奏家‌

2026-02-09 15:12:55

发布于：浙江

4阅读

0回复

0点赞

求区间和：

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010],pre[100010];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
}
while(m--){
int l,r;
cin>>l>>r;
cout<<pre[r]-pre[l-1]<<endl;
}
return 0;
}

像2017的数：

#include <bits/stdc++.h>
using namespace std;
int q,a[100010],pre[100010];
bool p(int x){
if(x<2) return 0;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0) return 0;
}
return 1;
}
int main(){
for(int i=1;i<=q;i++){
cin>>a[i];
}
for(int i=1;i<=100010;i++){
if(p(i) && p((i+1)/2)){
a[i]=a[i-1]+1;
}
else{
a[i]=a[i-1];
}
}
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cout<<a[r]-a[l-1]<<endl;
}
return 0;
}

最大子段和：

#include <bits/stdc++.h>
using namespace std;
int n,a[100010],pre[100010];
int main(){
cin>>n;
int mn=0;
int s=-1e9;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
s=max(s,pre[i]-mn);
mn=min(mn,pre[i]);
}
cout<<s;
return 0;
}

数组最值问题：

#include <bits/stdc++.h>
using namespace std;
int n,a[100010],pre[100010];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
//pre[i]=pre[i-1]+a[i];
pre[i]=max(pre[i-1],a[i]+i);
}
int ans=-1e9;
for(int j=2;j<=n;j++){
ans=max(ans,pre[j-1]+a[j]-j);
}
cout<<ans;
return 0;
}

异或前缀和：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,q,a[N],pre[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>q;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]^a[i];
}
while(q--){
int s=0,l,r;
cin>>l>>r;
s=pre[r]^pre[l-1];
cout<<s<<" ";
}

return 0;

}

异或为0的子数组：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6;
int n,a[N],pre[N],b[M];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long ans=0;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]^a[i];
if(pre[i]==0) ans++;
ans+=b[pre[i]];
b[pre[i]]++;
}
cout<<ans<<endl;
return 0;
}

神奇的元音精灵：

#include<bits/stdc++.h>
using namespace std;
int pos[32]; // 记录每个状态p第一次出现的位置，32是因为5位二进制最多32种状态(0~31)
string s; // 存储输入的字符串
int ans,p; // ans：最终答案（最长子串长度）；p：当前元音奇偶状态（初始值默认0）
int main(){
cin>>s;
// 初始化pos数组：所有状态的首次位置设为-1（表示未出现过）
for(int i=0;i<32;i++){
pos[i]=-1;
}
pos[0]=0; // 初始状态p=0（所有元音都是偶数次，0次），出现在位置0（字符串前的虚拟位置）
for(int i=0;i<s.size();++i){
// 核心：根据当前字符更新状态p（异或^=：翻转对应位的奇偶性）
if(s[i]'a') p^=1; // a对应第0位，异或1翻转该位
else if(s[i]'e') p^=2; // e对应第1位，异或2翻转
else if(s[i]'i') p^=4; // i对应第2位，异或4翻转
else if(s[i]'o') p^=8; // o对应第3位，异或8翻转
else if(s[i]=='u') p^=16; // u对应第4位，异或16翻转
// 非元音字符：p不变（因为不影响元音奇偶）
// 关键逻辑：判断当前状态p是否出现过
if(pos[p]!=-1){
// 出现过：计算当前位置(i+1)和首次位置(pos[p])的距离，更新最长长度
ans=max(ans,i+1-pos[p]);
}else{
// 没出现过：记录当前状态p的首次位置（i+1是因为字符串下标从0开始，位置从1算）
pos[p]=i+1;
}
}
cout<<ans; // 输出最长子串长度
return 0;
}