题解-[P5377]鸽鸽的分割

Tangent233 · 2021-01-01 22:22:33 · 题解

蒟蒻没想到这么简单就AC了我第一个紫，我简单讲讲我事怎么找规律的（居然和题解都不一样www）。

我们就以n=7的情况举例吧。

我们先画一个圆，然后顺时针给每个点标上序号。

我们先从1号点开始给别的点连线，表示切了一刀，然后计算这一刀给答案做的贡献，也就是切完这一刀后增加了多少块区域

（由于在图上做太过混乱，于是我整理到了表格上）

没啥感觉？那我们再从2号点开始给别的点连线吧。

老天，看看这等差数列。你是不是有些摸到门道了？我们再从三号点出发。

看到这，我们或许有一个大胆的猜想。

从第i个点出发，到其他的点所连成的线对答案的贡献所组成的数列是一个首项为1,项数为n-i,公差为i-1的等差数列！

真的是这样的吗？我们可以把剩下的点都统计完……

看起来是这样的呢（至于为什么最后面再解释吧……）。我们知道这一点那么程序就不难写了吧？

#include<bits/stdc++.h>
using namespace std;
int qh(int s,int e,int gc)
{
    int answ=0,tmp=1;
    for(int i=s;i<=e;i++)
    {
        answ+=tmp;
        tmp+=gc;
    }
    return answ;
}//超级暴力的做法
int ans(int n)
{
    int answer=0;
    for(int i=1;i<n;i++)
        answer+=qh(i+1,n,i-1);
    return answer;
}
int main()
{
    int n;
    while(cin>>n) cout<<ans(n)+1<<endl;//别忘了我们一直统计的都是对答案的贡献，最后还要加上本身圆的一个区域
    return 0;
}

好的，到这里就可以100pts到手啦！

规律的解释（为了让题解能过……）：

首先我们得先知道一个线段增加划分区域的个数为它经过区域的个数，这不难理解，你每经过一个区域都会把这个区域分为两半，自然会把划分区域+1.

那么解释这个规律的关键就在于每个线段它经过了多少个区域，也可以看作是穿过线段数加1（因为一个区域不相交的n条线段会划分出n+1个区域）

如果按照我们探究规律时连接线段的顺序的话，那么对于任意一条从s连接到e（s<e）的线段，有两种可能

• 要么e=s+1,也就是两个点相邻，此时经过线段数为0,穿过区域为1（这就是为什么首项为1）
• 要么e>s+1,那么我们设中间的点数为k=e-s-1.不难理解按照我们连接的顺序，此时中间的每个点已经和其他点连接了s-1条线段，于是经过线段数为k*(s-1)，穿过区域为k*(s-1)+1（这就是为什么公差为i-1)

那么为什么项数为n-i呢？因为我们按照顺序不重复连边的话，从i号点至多能连出n-i条边（联想一下无向图……）

若有什么解释不清楚的话可以在评论问，私信问都可以。