做题记录 2025/6/11

complexor · 2025-06-12 18:48:57 · 个人记录

题意简述

给定 n，将 2,3,\dots,3n+1 划分成 n 组 (a_i,b_i,c_i)，使得每组中的三个正整数构成钝角三角形的三边长。

## 做法 from 🐍🐍，比官解好。观察 $n$ 小的情况： $$ n=1:(2,3,4)\\ n=2:(2,4,5),(3,6,7)\\ n=3:(2,5,6),(3,7,8),(4,9,10) $$ 提出猜想：将后 $2n$ 个数 $n+2\sim 3n+1$ 相邻两两分组，然后依次找前 $n$ 个数 $2~n+1$ 配三角形。但当 $n=4$ 时出现 $(5,12,13)$ 不是钝角三角形。考虑调大后 $2n$ 个数的分组差，具体的选取一个 $x$，得到 $x$ 组边长 $(3n+1-x-i,3n+1-i),i=0,1,\dots,x-1$ 然后找前 $n$ 个数中最大的 $x$ 个配三角形即：$(n+1-i,3n+1-x-i,3n+1-i),i=0\sim n-1$。考虑这样要满足什么条件： 1. 三角形：$(n+1-i)+(3n+1-x-i)>3n+1-i

钝角：(n+1-i)^2+(3n+1-x-i)^2<(3n+1-i)^2

第一个条件取 i=n-1 限制最严，得到 x\leq\lfloor\frac{n}{2}\rfloor。

对于第二个条件，我们需要一个引理：

对于一组钝角三角形三边长 a<b<c，即 a+b>c\wedge a^2+b^2<c^2，则 (a-1)^2+(b-1)^2<(c-1)^2（不过有可能 a+b=c）。

证明将平方展开即可。

这告诉我们第二个条件取 i=0 最严，即 x(6n+2-x)>(n+1-i)^2，不难发现 x=\lfloor\frac{n}{2}\rfloor 且 n\geq 2 时必然满足。

那么我们取出这 \lfloor\frac{n}{2}\rfloor 个三角形，记 m=n-\lfloor\frac{n}{2}\rfloor=\lceil\frac{n}{2}\rceil，则还剩下 3m 个数：2\sim2+m-1,n+2\sim n+1+2m。

再有一个引理：

对于一组钝角三角形三边长 a<b<c，(a,b+1,c+1) 也是钝角三角形三边长。

平方差公式易证。

所以可以加强题目要求：将 2~3n+1 分成 n 组，每组中一个 2\sim n+1 中的数、两个 n+2\sim 3n+1 的数，且每组都是钝角三角形三边长。

这样就可以直接递归到 2\sim 3m+1 的情况，然后将 m+2\sim 3m+1 中的数加上 n-m 即可。

递归边界 n=1。

code:

#include <bits/stdc++.h>
int main()
{
    int n; scanf("%d", &n);
    int x = 2, y = n + 2;
    for (int m = n / 2; m; n -= m, m = n / 2)
        for (int i = 1; i <= m; i++)
            printf("%d %d %d\n", x + n - i, y + n * 2 - m - i, y + n * 2 - i);
    printf("%d %d %d\n", x, y, y + 1);
    return 0;
}