T3 分拆题解

WYXkk · 2020-03-18 19:09:38 · 题解

upd：修改了一处笔误，感谢 TheShadow 指出。请管理重新审核。

$\text{Subtask}\;2$：正常的爆搜应该能过。（当然你爆搜写的是假的（指正确性）就过不了） $\text{Subtask}\;3$：~~爆搜找规律~~ 数学推导。我们来分情况讨论。 $n=4k+1$：取一个 $n$，$2k$ 个 $1$，$2k$ 个 $-1$ 即可。 $n=4k+2$：假设可以，设 $(a_1,a_2,\cdots,a_n)$ 是 $n$ 的一个「良好的分拆」。既然 $\prod a_i=4k+2$，那么 $a_1,a_2,\cdots,a_n$ 中必定恰好有一个偶数，再根据 $\sum a_i=4k+2$，可得 $4k+1$ 个奇数和一个偶数的和是偶数，不可能。故此时 $n$ 没有「良好的分拆」。 $n=4k+3$：假设可以，设 $(a_1,a_2,\cdots,a_n)$ 是 $n$ 的一个「良好的分拆」。既然 $\prod a_i=4k+3$，那么 $a_1,a_2,\cdots,a_n$ 中必定有奇数个 $4k+3$ 型数和偶数个 $4k+1$ 型数。无论是有 $4k+1$ 个 $4k+3$ 型数和 $4k+2$ 个 $4k+1$ 型数，还是有 $4k+3$ 个 $4k+3$ 型数和 $4k$ 个 $4k+1$ 型数，其和都不是 $4k+3$ 型数。故此时 $n$ 没有「良好的分拆」。 $n=4k$：要分类讨论。 - $n=4$：没有，读者自证不难（ - $n=8k$：一个 $4k$，一个 $2$，$6k-2$ 个 $1$，$2k$ 个 $-1$。 - $n=8k+4$：一个 $4k+2$，一个 $-2$，$6k+3$ 个 $1$，$2k-1$ 个 $-1$。按照上面的方式构造即可。（很好奇比赛的时候有没有人找规律找出来 $\texttt{code:}

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
    T f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
    x*=f;
    return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

void out(int n)
{
    if(n%4==1)
    {
        puts("YES");
        if(n==1) printf("1\n1 1\n");
        else printf("3\n1 %d\n%d 1\n%d -1\n",n,n/2,n/2);
    }
    else if(n%4==2) puts("NO");
    else if(n%4==3) puts("NO");
    else
    {
        if(n%8==0)
        {
            puts("YES");
            printf("4\n1 %d\n1 2\n%d 1\n%d -1\n",n/2,n-n/4-2,n/4);
        }
        else
        {
            if(n==4) puts("NO");
            else
            {
                puts("YES");
                printf("4\n1 %d\n1 -2\n%d -1\n%d 1\n",n/2,n/4-2,n-n/4);
            }
        }
    }
}
int main()
{
    int T=rd();
    while(T--) out(rd());
    return 0;
}

T3 分拆 题解

T3 分拆题解