题解：CF2153C Symmetrical Polygons

include13_fAKe · 2025-10-14 15:01:13 · 题解

来不及写就被我妈要求回去睡觉了。

考虑对称图形的性质：

• 有 \ge 3 条边。
• 边两两配对，只剩下 0/1/2 条边。

只剩下 0 条边是好处理的，但是要注意必须至少有两对相等边。

剩下 1 条边需要使其小于其他边的总和。

剩下 2 条边要求较长边小于其他边的总和（包括另外一条剩余边）。

用 map 实现的，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline ll read(){
    ll a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(ll x){
    write(x),putchar(' ');
} 
inline void write2(ll x){
    write(x),putchar('\n');
}
ll n;
ll a[5*114514]; 
ll b[5*114514];
map<ll,ll> c;
void solve(){
    ll tag=0;
    n=read();
    ll include13=0;
    for(ll i=1;i<=n;i++){
        a[i]=read();
        c[a[i]]++;
        if(c[a[i]]==2){
            include13+=a[i]*2;
            tag++;
            c[a[i]]=0;  //解除效应！  
        }
    }
    ll idx=0;
    for(ll i=1;i<=n;i++){
        if(c[a[i]]){
            b[++idx]=a[i];
            c[a[i]]=0;
        }
    } 
    sort(b+1,b+idx+1);
    ll include13_fAKe=include13;    //include13_fAKe 才是真正的最后答案  
    if(tag<=1)  include13_fAKe=0;
    for(ll i=1;i<=idx;i++){
        if(b[i]<include13){
            include13_fAKe=max(include13+b[i],include13_fAKe);
        } 
        if(i!=idx){
            if(b[i+1]-b[i]<include13){
                include13_fAKe=max(include13+b[i+1]+b[i],include13_fAKe);
            }
        }
    }
    write2(include13_fAKe);
} 
int main(){
    ll T=read();
    while(T--)  solve();
    putchar('\n');
    return 0;
} //还是不习惯你不在 这身份转变太快