今日学习记录
1. First one-hdu-5358
好久没做出来的题,当时没能做出来,ai 也做不出来,然后就做不出来了,没题解,没人教,所以就先放着了 时隔一个月,我再来看,思考了大概半个小时就想出来,我独自想出来的,至少说明我比一个月前强了不少 那么类似的题不止一个,还有csp的这道题,一模一样的板子,但是不同的规律和处理,大值思考方向和实现是一样的,我原本以为我这道题做出来了后就能解决所以此类问题,但是这类题其实特别难,此题就比 csp 的第四题要简单一点点,真的就一点点,log 的规律容易发现,而 gcd 不容易发现,其实此类题就是在这个核心部分出题,改变题目的处理手段(考察其他数学之类的知识),但是大体框架是一模一样的 **最终代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T; cin >> T;
while(T--){
int n; cin >> n;
int a;
vector<ll> prefix(n + 1, 0);
for(int i = 1; i <= n; i++){
cin >> a;
prefix[i] = prefix[i - 1] + a;
}
ll ans = 0;
for(int i = 1; i <= n; i++){
int j = i;
while(j <= n){
ll sum = prefix[j] - prefix[i - 1];
if(sum == 0){
int k = j;
while(k <= n && prefix[k] == prefix[i - 1]) k++;
k--;
int cnt = k - j + 1;
ans += 1LL*cnt * i + 1LL*(j + k) * cnt / 2;// t=0, 所以(t+1)=1
j = k + 1;
continue;
}
int t = 0;
ll temp = sum;
while(temp > 1){
t++;
temp >>= 1;
}
ll lower = (1LL << t);
ll upper = (1LL << (t + 1)) - 1;
int left = j, right = n, R = j;
while(left <= right){
int mid = (left + right) / 2;
ll sum_mid = prefix[mid] - prefix[i - 1];
if(sum_mid <= upper){
R = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
int cnt = R - j + 1;
ans += (t+1)*(1LL*cnt * i + 1LL*(j + R) * cnt / 2);
j = R + 1;
}
}
cout << ans << "\n";
}
return 0;
}学到的点：
- 三指针 i,对 i 进行分析,映射出要查找的范围,再进行答案匹配和计算