XP03B - day01
2026-08-03 10:12:26
发布于：广东
76阅读
0回复
0点赞
寻找舞伴 同向双指针
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[110],b[110];
int main(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++)cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int i = 1, j = 1,ans = 0;
while(i<=n && j<=m){
if(abs(a[i]-b[j])<=1){
i++;
j++;
ans++;
}else{
if(a[i]<b[j])i++;
else j++;
}
}
cout<<ans;
return 0;
}
滑动窗口 最长无重复区间
// 最长连续区间
// 使得该区间内任意两个数都不相同
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int cnt[N];//统计每个数出现次数
int a[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int l = 1,r = 1,ans = 0;
while(r<=n){
cnt[a[r]]++;// 统计右端点结尾数的出现次数
while(l<=r && cnt[a[r]]>1){
cnt[a[l]]--;
l++;
}
ans = max(ans,r-l+1);
r++;
}
cout<<ans;
return 0;
}
反向双指针
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int n,m,k;
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
int l=1,r=m,ans = 0;
while(l<=n && r>=1){
if(a[l]+b[r]>k)r--;
else if(a[l]+b[r]<k)l++;
else{
cout<<l-1<<" "<<r-1;
break;
}
}
return 0;
}
判断子序列
#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010];
int main(){
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int j=1;j<=m;j++) cin >> b[j];
int i=1,j=1,ans=0;
while(j<=m){
if(a[i]==b[j]){
i++;
j++;
ans++;
}
else{
j++;
}
}
if(ans==n) cout << "Yes";
else cout << "No";
}
区间和计数
//pre[r] - pre[l-1] = k
//pre[l-1] = pre[r] - k
//求pre[r] - k的前缀和的数量
// 普通的计数数组 2*10^14
// cnt[x]++;
// mp[x]++;
#include<bits/stdc++.h>
using namespace std;
long long a[200009],pre[200009];
map<long long,int> mp;
int main(){
int n;
cin>>n;
long long k;
cin>>k;
long long ans = 0;
mp[0] = 1;
for(int r=1;r<=n;r++){
cin>>a[r];
pre[r]=pre[r-1]+a[r];
ans += mp[pre[r]-k];
mp[pre[r]]++;
}
cout<<ans;
return 0;
}
map笔记
Map 与哈希表笔记
map 和 unordered_map 用来保存：
键 → 对应的值
例如统计前缀和出现次数：
unordered_map<long long,long long> q;
q[5]++;
q[-3]++;
表示前缀和 5、-3 分别出现了多少次。
区别：
map：有序，单次操作 O(log n)
unordered_map：无序，平均 O(1)
前缀和统计区间和为 k：
q[0]=1;
sum+=x;
ans+=q[sum-k];
q[sum]++;
原理：
所以：
注意必须先查询，再记录当前前缀和，否则 k=0 时会统计空区间。
区间倍数问题
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k, x;
long long cnt[N];
long long sum, ans;
int main(){
cin >> n >> k;
cnt[0] = 1;
for (int i = 1; i <= n; i++){
cin >> x;
sum += x;
sum%=k;
ans += cnt[sum];
cnt[sum]++;
}
cout << ans;
return 0;
}
异或前缀和
#include <bits/stdc++.h>
using namespace std;
int n,q,a[500005],p[500005];
int main(){
cin>>n;
for(int i = 1;i<=n;i++)cin>>a[i];
for(int i = 1;i<=n;i++){
p[i] = p[i-1] ^ a[i];
}
cin>>q;
for(int i = 1;i<=q;i++){
int l,r;
cin>>l>>r;
cout<<(p[r]^p[l-1])<<' ';
}
return 0;
}
接雨水
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N];
int l[N],r[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)l[i] = max(l[i-1],a[i]);//前缀最值
for(int i=n;i>=1;i--)r[i] = max(r[i+1],a[i]);//后缀最值
long long ans = 0;
for(int i=1;i<=n;i++){
ans += max(0,min(l[i-1],r[i+1]) - a[i]);
}
cout<<ans;
return 0;
}
考试 T4
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,a[N],b[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int i=n,j=n,ans = 0;//判断子序列 思维题
while(i>=1){
if(b[j] == a[i]){
j--;
i--;
ans++;
}else i--;
}
cout << n - ans;
return 0;
}
考试 T5
考试T6
考试T7
考试T8
#include<bits/stdc++.h>
using namespace std;
// 1. 完全平方数 奇数个因子
// 2. 异或和为偶数因子的子数组数量
// 3. 正难则反 总数 - 异或和奇数因子
// n 1+2+3+...+n = (1+n)*n/2;
// 4. 异或和为0的子数组数量
// pre[l-1] == 完全平方数 ^ pre[r]
const int N=2e5+10;
int pre[N];//前缀异或
int a[N];//原数组
int cnt[2*N]; //统计异或值为i的数量
int main(){
long long n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]^a[i];
}
long long ans=0;
cnt[0]=1;
//pre[l-1] == 完全平方数 ^ pre[r]
for(int r=1;r<=n;r++){
//枚举完全平方数
for(int i=0;i*i<=n;i++){
ans += cnt[pre[r]^(i*i)];
}
cnt[pre[r]]++;
}
cout<< n*(n+1)/2 - ans;
return 0;
}
考试T8 枚举约数数量
#include<bits/stdc++.h>
using namespace std;
int f[300009];
int pre[500009];
unordered_map<int,int> mp;
vector<int>a;
int main(){
f[0]=1;
for(int i=1;i<=300005;i++){
for(int j=1;j*i<=300005;j++){
f[i*j]++;
}
}
for(int i=0;i<=300005;i++){
if(f[i]%2==1){
a.push_back(i);
}
}
long long n;
cin>>n;
long long ans=0;
mp[0]=1;
for(int i=1;i<=n;i++){
int x;
cin>>x;
pre[i]=pre[i-1]^x;
for(int j=0;j<a.size();j++){
ans+=mp[a[j]^pre[i]];
}
mp[pre[i]]++;
}
ans=n*(n+1)/2-ans;
cout<<ans;
return 0;
}
2025 csp-j 异或和
#include<bits/stdc++.h>
using namespace std;
int cnt[1<<20]; // cnt[i] 异或和为i的点下标
int n,k;
int main(){
cin>>n>>k;
int sum = 0;//求异或前缀
for(int i=0;i<1<<20;i++)cnt[i]=-1;
int ans = 0;
int r = -1;
cnt[0] = 0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
sum^=x;
if(cnt[sum^k]!=-1 && cnt[sum^k]>=r){
ans++;
r = i;
}
cnt[sum] = i;
}
cout<<ans;
return 0;
}
奶茶热量
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
long long a[N],b[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
sort(a+1,a+n+1);
long long ans = 0;
for(int i=1;i<=m;i++){
int r = lower_bound(a+1,a+n+1,b[i])-a;
int l = r-1;
long long mn = 1e18;
if(r<=n)mn = a[r]-b[i];
if(l>=1)mn = min(mn,b[i] - a[l]);
ans+=mn;
}
cout<<ans;
return 0;
}
全部评论 5
补一个挑战题
//本题其实可以理解为线段上的区间覆盖问题（很经典的贪心题），通过前缀异或求得区间后贪心即可 //贪心的思路是优先选右端点小的，如果相同再选左端点大的 #include<bits/stdc++.h> using namespace std; int pre[500009];//前缀异或数组 unordered_map<int,priority_queue<int>> mp;//priority_queue自动降序排序左端点 int main(){ int n,k; cin>>n>>k; int ans=0; mp[0].push(0); int last=0;//初始化 for(int i=1;i<=n;i++){ int x; cin>>x; pre[i]=pre[i-1]^x;//输入+运算 if(!mp[pre[i]^k].empty() && mp[pre[i]^k].top()>=last){//寻找可行的左端点 ans++;//可行，则将答案+1，并更新上一个右端点 last=i; } mp[pre[i]].push(i); } cout<<ans; return 0; }2026-08-03 来自 广东
0
有帮助，赞一个