T278239 蛋糕师

2022/10/2 题解数论

考试推了半天最后没来得及写完。

应该算是半道数论了，由于是按照和升序排序，所以我们先考虑求出目标位置三个数之和为多少。

题解给出的方法是组合数学，~~但正经人谁写组合数学啊，~~ 还不如写个暴力找规律

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,cnt,SUM;
struct node{int a,b,c,sum;}p[1000010];
inline bool cmp(node x,node y)
{
    if(x.sum!=y.sum) return x.sum<y.sum;
    if(x.a!=y.a) return x.a<y.a;
    if(x.b!=y.b) return x.b<y.b;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)p[++cnt]={i,j,k,i+j+k};
    sort(p+1,p+1+cnt,cmp);
    int tot=0;
    for(int i=1;i<=cnt;i++)
    {
        if(p[i].sum==p[i-1].sum) tot++;
        else printf("%d %d %d\n",p[i-1].sum,tot,i-1),tot=1;
    }
    printf("%d %d %d\n",p[cnt].sum,tot,cnt),tot=1;
    return 0;
}

得到（在等于时，不重要）

	三元组和为的个数	三元组和的个数
0（这行没用）	0	0
3	1（+1）	1
4	3（+2）	4
5	6（+3）	10
6	10（+4）	20
7	15（+5）	35
8	21（+6）	56
9	28（+7）	84
10	36（+8）	120
11	45（+9）	165
12	55（+10）	220
13	63（+8）	283
14	69（+6）	352
15	73（+4）	425
16	75（+2）	500
17	75（+0）	575
18	73（-2）	648
19	69（-4）	717
20	63（-6）	780
21	55（-8）	835
22	45（-10）	880
23	36（-9）	916
24	28（-8）	994
25	21（-7）	965
26	15（-6）	980
27	10（-5）	990
28	6（-4）	996
29	3（-3）	999
30	1（-2）	1000

那这个规律就很好找了。~~实际上找了将近一个小时~~

设表示所有三元组和的个数，表示所有三元组和的个数

可能我们可以看一下没那么劝退的代码

for(int i=3;i<=3*n;i++)
{
    if(i<=n+2) pre+=(i-2),sum+=pre;
    else if(i<=2*n+2) pre+=(3*n-2*i+4),sum+=pre;
    else pre+=(i-3*n-2),sum+=pre;
    if(m<=sum)
    {
        DO(i,sum-pre);
        return 0;
    }
}

考场上其实已经推出了以上部分

我们得到了三个数（设为）的和（设为），那么接下来就好说了，只需要枚举每个的值，便可以得到的取值范围和对应的的值

最小值为和均取时，即

然后从最小值依次枚举

重点:

最小值为取时，即 ,最大值为取时，即

所以在这个下，有种情况。我们设一个为当第一个数为时，最后一个三元组的编号，则为第一个数为时，最后一个三元组的编号，当这个编号小于所要求的时，继续枚举下一个。

当这个编号大于等于所要求的时，说明答案的第一位就是，且三个数和为的第个三元组，则，即 , 那。

inline void DO(int tmp,long long num)
{
    int x,y1,y2;
    x=max(tmp-2*n,1);
    for(;;x++,num+=(y2-y1+1))
    {
        y1=max(tmp-x-n,1),y2=min(tmp-x-1,n);
        if(num+(y2-y1+1)>=m) break;
    }
    printf("%d %d %d\n",x,(int)(y1+m-num-1),(int)(tmp-x-y1-m+num+1));
    return ;
}

就这样

LOADING...

T278239 蛋糕师