Codeforces 1183F - Topforces Strikes Back

Div. 3的题，竟然卡了好久，自闭.jpg

好像我的思路不太一样呢QAQ

首先注意到，如果一个数是另一个的因子，那它肯定不会出现在答案中。

我们先把所有数排序，然后对每个数，我们要往前再找两个数（或者一个，都差不多，就不区分了）和它凑个答案，那我们暴力往前扫，如果碰到它的因子，就直接将这个因子从数列中删掉；如果不是它的因子，就加到答案里，凑满3个就break。

Q：那这样做找到的前面两个数万一有倍数关系咋办？

A：不存在的，因为我们之前就把所有数的因子删掉了。

Q：那怎么删啊？set？map？

A：删除的话，用类似链表的东西维护下就好了。

Q：你这个辣鸡做法好暴力啊，复杂度？

A：扫到每个数的时候，它要么被删掉，要么被统计到答案里了，所以每组是 \(O(n)\) 的，再加sort的 \(O(nlogn)\)

#include<bits/stdc++.h>

#define LL long long

#define re register

#define fr(i,x,y) for(int i=(x);i<=(y);i++)

#define frz(i,x,y) for(int i=x,z=y;i<=z;i++)

#define rf(i,x,y) for(int i=(x);i>=(y);i--)

#define frl(i,x,y) for(int i=(x);i<(y);i++)

using namespace std;

const int N=200003;

int n,a[N],p[N];

inline void read(int &x){

	char ch=getchar();x=0;int w=0;

	for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';

	if (w) x=-x;

}

int main(){

	//init();

	int T;

	read(T);

	while(T--){

		read(n);

		fr(i,1,n) read(a[i]);

		sort(a+1,a+1+n);

		int ans=0;

		fr(i,1,n) p[i]=i-1;

		fr(i,1,n){

			int sum=a[i],s=1,x=i;

			while(s<3&&x){

				if (a[i]%a[x]) s++,sum+=a[x];

				while(p[x]&&a[i]%a[p[x]]==0) p[x]=p[p[x]];

				x=p[x];

			}

			ans=max(ans,sum);

		}

		printf("%d\n",ans);

	}

	return 0;

}