AT_abc444_c[ABC444C] AtCoder Riko

思路

这道题细节比较多，导致很多人赛时没切掉。
一步一步来：
首先我们知道每根饼干最多分裂一次，也就是说对于每一种初始长度，若分裂出的其中一根饼干的长度确定，则也可以得出另一根的长度就是总长减第一根。
由此我们就可以得出计算一种初始长度是否可行的方法。
只要遍历一遍每种存在的长度，判断一下与其对应的长度存在的饼干数量是否和它相等即可。
而对于长度恰好为初始长度一半的，判断其数量 $x$ 是否 $\equiv 0\pmod 2$，因为它对应的是自己，一定要两两一组。
对于长度等于初始长度的，直接跳过，它不需要和长度为 $0$ 的饼干拼接。
在发现验证某初始长度是否成立的方法后，易得到一个结论：成立的初始长度只有可能是最长的长度或者最长的长度加上最短的长度。
我们设长度为 $len$，最长为 $mx$，最短为 $mi$，分类讨论一下：

$len<mx$：无法得到长度最大的，一定不行；
$mx<len<mx+mi$：最大的就算加上最小的仍然大于初始长度，无法得到，一定不行；
$mx+mi<len$：最小的就算加上最大的仍然小于初始长度，一定不行。

综上所述，可能的答案只有 $mx$ 和 $mx+mi$。

代码

#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=3e5+5;
int n,a[N];
vector<int>ans;
unordered_map<int,int>mp;
bool cmp(int a,int b){
	return a>b;
}
void work(int x){
	for(auto i:mp){
		int v=i.fir;
		if(v==x)continue;
		if(mp[v]!=mp[x-v])return;
		if(v==x-v&&mp[v]%2!=0)return;
	}
	print(x);putchar(' ');
}
signed main(){
	read(n);
	rep(i,1,n)read(a[i]),mp[a[i]]++;
	sort(a+1,a+n+1);
	ans.emplace_back(a[n]);
	ans.emplace_back(a[1]+a[n]);
	fep(i,0,ans.size()){
		int x=ans[i];
		work(x);
	}
}