蓝桥杯备赛 Day9 构造

构造

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){ //输入和输出都为ll
	return (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; //break
		for(j=i-1;j>=1;j--){
			k=j-1;
			if(a[i]+a[j]+a[k]<maxn)	break;  //break
			for(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;
}