第一题：给定n个元素，求：

$$\sum_{1 \le i < j \le n}^{} (a_i+a_j)^2$$

其中，$n \le 200000$。 这道题可以双重枚举，但是显然时间不够。所以，我们想到了数学优化。

原式 $ =\sum (a_i^2+a_j^2+2*a_i*a_j)= (n-1)*\sum a_i^2 + \sum (2*a_i*a_j) $

所以，需要优化后面式子，将$a_i$和$a_j$分离。

因为，$\sum (2*a_i*a_j) = (\sum a_i)^2- \sum a_i^2$

所以，原式 $= (n-2)*\sum a_i^2+(\sum a_i)^2$

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
const int mod=1e9+7;
int n,a[maxn],sum1=0,sum2=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++) sum1+=a[i],sum1%=mod;
	for(int i=1;i<=n;i++) sum2+=(1ll*a[i]*a[i])%mod,sum2%=mod;
	
	int ans=(1ll*(n-1)*sum2)%mod;
	ans+=1ll*sum1*sum1%mod;ans%=mod;
	ans-=sum2,ans=(ans+mod)%mod;
	printf("%d\n",ans);
	return 0;
}

当我们在比赛的过程中，遇到类似这样的数学题时，可以将代数式简化，分离不同项，合并同类项，时间复杂度会降低。

第二题：这道题可以使用二分的思路进行解决，对答案进行二分枚举。

答案是具有单调性的，即当答案 $i$ 满足时，$i-1$也满足题目条件，即可满足二分的条件。

对于每一个确定的答案，去查看其是否满足条件。可以去枚举长度为i的子串，看其是否满足条件。

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
int n,k;
char s[maxn];

bool check(int i){
	int t=0,ans=0;
	for(int j=1;j<=i;j++){
		if(s[j]=='1') t++;
	}
	if(t<=k){
		return true;
	}
	for(int j=i+1;j<=n;j++){
		if(s[j]=='1') t++;
		if(s[j-i]=='1') t--;
		if(t<=k){
			return true;
		}
	}
	return false;
}
int main(){
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)/2;
		if(check(mid)==1) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
	return 0;
}

这个思路比较朴素，时间复杂度为 $O(nlogn)$ ，有很多可以优化的地方。大家可以去看一下老师的代码，时间复杂度为 $O(n)$。

第三题：这道题是一道十分朴素的贪心题目。

首先，两个数组的顺序没有相互的影响，因此可以将两个数组分别排序。

其次，关于贪心的策略，可以是用最小的钱买价值最小的物品，也可以是用最大的钱买价值最大的物品。两种策略任选其一即可，我选择了第一种策略。

如果不能用最小的钱买价值最小的物品，那这个最小的钱数就不能再买价值更大的物品了，因此可以跳过该钱数，使用下一个钱数来跟当前物品的价值做对比。可以简单地证明，该贪心策略最优。

关于策略二，同学们可以去看一下老师的题解，是用物品去配钱数。

#include<bits/stdc++.h>
using namespace std;

const int maxn=3e5+5;
int n,m,a[maxn],c[maxn];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	sort(a+1,a+1+n);
	sort(c+1,c+1+m);
	
	int j=1,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=c[j] && j<=m) j++,cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

同学们要仔细甄别二分与贪心的关系，仔细区别不同题目的算法。事实上，有些贪心的思路可以转换为二分算法。

第四题：题目给出了两个数组：$t_i$ 和 $w_i$。

因为不等式 $|t_i-t_j| \ge w_i+w_j$ 中，$t$ 的运算含有绝对值，所以容易想到，将$t$数组的元素大小表示在一个数轴上。要求，任两个点之间的距离都不小于两个点的权值之和。

先告诉大家结论，可以对每一组$t_i$和$w_i$，在数轴上表示出线段$[t_i-w_i,t_i+w_i]$，再最大化求不相交的线段数量即可。

如果只简单地思考，看似合理。那为什么这两个结论会等价呢？下面进行证明。

当满足不等式$|t_i-t_j| \ge w_i+w_j$的时候，当$t_i > t_j$的时候（当$t_i \le t_j$同理可证）。所以，$t_i-w_i \ge t_j+w_j$，再结合$t_i > t_j$，可得这两条对应的线段不相交，充分性证明。

当$[t_i-w_i,t_i+w_i]$与$[t_j-w_j,t_j+w_j]$线段不相交的时候，当$t_i > t_j$的时候（当$t_i \le t_j$同理可证）。所以，$t_i-w_i \ge t_j+w_j$，即$t_i-t_j \ge w_i+w_j$，再结合 $t_i \le t_j$，可得$|t_i-t_j| \ge w_i+w_j$,必要性证明。

所以，这两个命题是充分必要条件，即它们是等价的，所以该问题就转换为了最大化线段数量，使得线段两两不相交。

这里有一个经典的贪心算法，我们可以将线段的右端点排序，再贪心地去取左端点，具体代码如下所示。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=1e6+5;
int n;
ll t[maxn],w[maxn];
pair<ll,ll> p[maxn];

bool cmp(pair<ll,ll> x,pair<ll,ll> y){
	return x.second<y.second;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
	
	for(int i=1;i<=n;i++){
		p[i]=make_pair(t[i]-w[i],t[i]+w[i]);
	}
	sort(p+1,p+1+n,cmp);
	
	ll lst=p[1].second,cnt=1;
	for(int i=2;i<=n;i++){
		if(p[i].first>=lst) lst=p[i].second,cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

在我们做题的过程中，我们不能只追求分数，而是要全面考虑题目地内容，去真正地理解题目。

第五题：给定$n$个一维坐标，从中选取$k$个，使得两两之间的最小距离最大。

我们可以使用贪心的算法，对于每一个枚举的答案，去算出最多能选取多少个坐标，再跟$k$比较，判断答案是否满足。

由于答案满足单调性，所以可以使用二分求解。这是一道典型的二分答案的题目。

#include<bits/stdc++.h>
using namespace std;

const int maxn=3e5+5;
int n,p,a[maxn];

bool check(int x){
	int l=a[1],cnt=1;
	for(int i=2;i<=n;i++){
		if(a[i]-l>=x) l=a[i],cnt++;
	}
	return cnt>=p;
}
int main(){
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	
	int l=1,r=1e9;
	while(l<r){
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	
	printf("%d\n",l);
	return 0;
}

第六题：有$n$类人，每一类人有$a_i$个。请将这些人进行分组，每一组有$m$人，每一组不能出现相同类的人。有的人可以不参与分组，请问最大的分出多少组来。

我们讨论，如果要分出$k$组来，那么$a$数组需满足的条件。

首先，“每一组不能出现相同的人”，那么在所有需要被分组的人中，不能出现多于$m$个同一类的人。所以，每一种类型的人最多提供$m$个人，总共最少需要$m*k$个人。

接下来，我们就要讨论，“大于等于$m*k$个人”这个条件的充分性。可以构造$mid$个抽屉，根据抽屉原理，至少有一种方案，使得抽屉内，不会有两个同类人。

最后，我们只需要二分枚举$k$即可得到答案。 不要忘记了，答案可能超过$int$范围，所以要计算答案的上线，避免不必要的超时。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int n,m,a[maxn];
long long s;

bool check(long long x){
	long long sum=0;
	for(int i=1;i<=n;i++) sum+=min(1ll*a[i],x);
	return sum>=1ll*m*x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),s+=a[i];
	
	long long l=1,r=s/m;
	while(l<r){
		long long mid=(l+r+1)/2;
		if(check(mid)==1) l=mid;
		else r=mid-1;
	}
	printf("%lld\n",l);
	return 0;
}

通过这些题，我们发现：看似这些题十分困难，但是其都是一些简单算法的集合，所以我们需要培养灵活使用算法的能力。