今日学习记录
1. Problem - 2064C - Codeforces
关键词：前后缀
问题分析：
输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5) 和长为 n 的数组a(-1e9≤a[i]≤1e9, a[i]≠0)。
每次操作，你可以选择 a 中的一个数a[i]，得到 |a[i]| 分。
然后：
如果 a[i] < 0，移除 a[i] 及其右边的所有元素。
否则，移除 a[i] 及其左边的所有元素。
操作直到数组为空。
输出最大总得分。
核心思路: 正数从左边开始选,负数从右边开始选 处理就用前后缀,简单
**最终代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
cin>>n;
while(n--){
cin>>m;
vector<long long> arr(m+1);
vector<long long> pre(m+1);
vector<long long> suf(m+1);
for(int i = 1;i<=m;i++){
cin>>arr[i];
pre[i] = pre[i-1]+(arr[i]>=0?arr[i]:0);
}
for(int i = m-1;i>=0;i--) suf[i] = suf[i+1]+(arr[i+1]<0?-arr[i+1]:0);
long long ans = 0;
for(int i = 0;i<=m;i++){
ans = max(pre[i]+suf[i],ans);
}
cout<<ans;
cout<<endl;
}
return 0;
}学到的点：
- 观察力和敏感度不够
2. Problem - 1931D - Codeforces
关键词：同余
问题分析：
输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(2≤n≤2e5) x y(1≤x,y≤1e9) 和长为 n 的数组a(1≤a[i]≤1e9)。
输出有多少个下标对 (i,j) 同时满足：
- i < j。
a[i]+a[j]是 x 的倍数。a[i]-a[j]是 y 的倍数。 核心思路
同余
(a[i]+a[j])%x = 0 -> a[i]%x = (-a[j])%x(a[i]-a[j])%x = 0 -> a[i]%x = (a[j])%x要满足以上两个条件的话,要两个都同时相等 那么就是找对应{a[i]%x,(a[j])%x}键与{a[i]%x,(-a[j])%x}键相等的数量 先记录前者的数量,再每次查找后者的数量并加入到答案中
最终代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,x,y;
int main(){
cin>>T;
while(T--){
cin>>n>>x>>y;
vector<int> arr(n);
map<pair<int,int>,int> mp;
long long ans = 0;
for(int i = 0;i<n;i++){
cin>>arr[i];
ans += mp[pair{(x-arr[i]%x)%x,arr[i]%y}];
mp[pair{arr[i]%x,arr[i]%y}]++;
}
cout<<ans<<endl;
}
return 0;
}学到的点：
- 不知道同余是来干什么的