构造
1.要点
考察总结归纳能力，没有固定解法
2.题目
2023平方差
(1)找到规律先存到set里面，然后要考虑最大开到1e6，然后暴力能得70分
(2)再观察规律，y为奇数或者偶数,z为奇数或者偶数，可以得到满足条件的为奇数和4的倍数，但是遍历会超时，可以类似于前缀和思想，求[1,r]满足条件总和-[1,l-1]满足条件总和，奇数个数为(x+1)/2(例如1,3,5,7,x=7+1=8/2=4,x=8+1=9/2=4),4的倍数个数为x/4(例如4,8,x=8/4=2,x=9/4=2)
代码;
#include <bits/stdc++.h>using namespace std;typedef long long ll;
ll l,r;ll get_num(ll x){ //输入和输出都为llreturn (x+1)/2+x/4;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>l>>r;ll cnt=get_num(r)-get_num(l-1);cout<<cnt;return 0;
}
2018倍数问题
学习:
(1)先暴力，不过要尽可能加多一点break条件，避免超时
#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e5+10;
ll a[N],n,K,i,j,k,maxn;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>K;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);for(i=n-1;i>=2;i--){j=i-1,k=i-2;if(a[i]+a[j]+a[k]<maxn) break; //breakfor(j=i-1;j>=1;j--){k=j-1;if(a[i]+a[j]+a[k]<maxn) break; //breakfor(int k=j-1;k>=0;k--){if((a[i]+a[j]+a[k])%K==0){maxn=max(maxn,a[i]+a[j]+a[k]);}if(a[i]+a[j]+a[k]<maxn) break; //break}} }cout<<maxn;return 0;
}