HLOJ-DAY 4

[一些闲话]

很好淘汰赛又是挂的。

很好没有昨天挂的那么狠。

享 受 每 一 天 吧！

[T1]

原题削弱版

是这样的，出题人考虑的很少，而选手考虑的就有很多了。

比如 cnt_{max}>\frac{n}{2} 的时候。

然后被这一个点硬控了一个小时。

最后莫名其妙过了。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,a[N],cnt[M];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    if(n&1)
    {
        puts("-1");
        return 0;
    }
    int Max=0;
    for(int i=1;i<M;i++)Max=max(Max,cnt[i]);
    if(Max>n/2)
    {
        int res=1e9;
        for(int i=1;i<M;i++)
        {
            if(cnt[i]<Max)res=min(res,abs((n/2)-cnt[i]));
        }
        printf("%d\n",res);
    }
    else
    {
        int Min1=1e9,Min2=1e9;
        for(int i=1;i<M;i++)
        {
            int s=(n/2)-cnt[i];
            if(Min1>s)
            {
                Min2=Min1;
                Min1=s;
            }
            else if(Min2>s)Min2=s;
        }
        printf("%d\n",Min1+Min2);
    }
    return 0;
}
//1 1 4 5 5 2
//0 1 2

[T2]

原题(但不完全一样)
对于 (n-1)&1=1 的情况，直接构造 2 n-3 。
否则暴力枚举。
CODE:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
void work()
{
    scanf("%lld",&n);
    if((n-1)&1)
    {
        if(n-3>=3)printf("2 %lld\n",n-3);
        else puts("-1");
        return;
    }
    //n&1
    for(LL i=3;i<=n&&i<n-i-1;i+=2)
    {
        LL j=n-i-1;
        if(__gcd(i,j)==1)
        {
            printf("%lld %lld\n",i,j);
            return;
        }
    }
    puts("-1");
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

为什么这么快就九点半了
剩下的明天晚自习补吧……