题解 U534154 【正三角形】

发表于 更新于 分类于 ， 阅读次数： 本文字数： 722 阅读时长 ≈ 3 分钟

题目链接：正三角形。

关于题目：作为 T1，巨水的签到题。

应用算法：模拟？

\(\ \ \ \ \ \ \)作为签到题，这道题就是“查数”，只要查明白了每种正三角形的个数就好。

\(\ \ \ \ \ \ \)首先，我们知道所有的正三角形分为正的和倒的，那么就请分类讨论。

  • 一、正的三角形：

    • 1.一层的三角形：单独的面积为 \(1\times 1=1\)，共有 $ {2} $ 个，则面积和为 \(\dfrac {n(n+1)} {2} \times 1^2\)。

    • 2.两层的三角形：单独的面积为 \(2\times 2=4\) ，共有 \(\dfrac {(n-1+1)(n-1)} {2}\) 个，则面积和为 \(\dfrac {(n-1+1)(n-1)} {2} \times 2^2\)。

    • 3.总结来说，对于 \(i(1 \leqslant i \leqslant n)\) 层的三角形，单独的面积为 \(i\times i=i^2\)，共有 $ {2} $ 个，则面积和为\(\dfrac {(n-i+2)(n-i+1)} {2} \times i^2\)。

  • 二、倒的三角形：

    • 1.一层的三角形：单独的面积为 \(1\times 1=1\)，共有 \(\dfrac{(n-1+1)(n-1)} {2}\) 个，则面积和为 \(\dfrac{(n-1+1)(n-1)} {2} \times 1^2\)。

    • 2.两层的三角形：单独的面积为 \(2\times 2=4\)，共有 \(\dfrac {(n-3+1)(n-3)} {2}\) 个，则面积和为\(\dfrac {(n-3+1)(n-3)} {2} \times 2^2\)。

    • 3.总结来说，对于 \(j(1 \leqslant j \leqslant \dfrac {n} {2})\) 层的三角形，单独的面积为 \(j\times j=j^2\)，共有 \(\dfrac {(n-2j+2)(n-2j+1)} {2}\) 个，则面积和为 \(\dfrac {(n-2j+2)(n-2j+1)} {2} \times j^2\)。

  • 三、总面积：\(S=\sum\limits_{i=1}^n \dfrac {(n-i+2)(n-i+1)} {2} \times i^2+\sum\limits_{j=1}^{\left\lfloor\dfrac{n}{2}\right\rfloor}\dfrac {(n-2j+2)(n-2j+1)} {2} \times j^2\)

\(\ \ \ \ \ \ \)其次，几个小细节需要注意一下：

  • 一、这道题的空间限制为 3.00MB，如果用普通的数组递推的话会 MLE（相信大家都不会在这里犯错，毕竟题面上有那么明显的提示……）。
  • 二、这道题的模数为 \(10^8+9\) ，并不是常用的 \(10^9+9\) ，这点还是要注意一下的，本人自测以 \(10^9+9\) 作为模数的话只能得 20 分。

\(\ \ \ \ \ \ \)最后，上代码，相信大家都能看懂（码风不喜勿喷）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
#define M 100000009
using namespace std;
int n,ans;
//每个数组或变量的含义详见处理过程。
in int qread()
//快读
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
//快写
{
	if(x<0)
	{
		putchar('-');
		x=-x;
		qwrite(x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
}
signed main()
{
	n=qread();
	//读入
	for(re int i=1;i<=n;i++)    
	{        
		ans+=((n-i+2)*(n-i+1))/2*i*i;
		//正的正三角形
		ans%=M; 
		if(n>=2*i)        
		{            
			ans+=((n-2*i+2)*(n-2*i+1))/2*i*i;
			//倒的正三角形
			ans%=M;
		}    
	}    
	qwrite(ans);
	putchar('\n');
	//输出
	return 0;
}
U4jNcQ.png