【政治】规划 题解

· · 题解

楼下那个官方题解也是可以……

这才是官方题解!

题目大意：

给你a_1条直线，a_2个圆，a_3个正三边形，a_4个正四边形，a_5个正五边形......a_n个正n边形，问这些图形最多能把一个平面分成多少块。

首先，我们看一下只有直线的情况：

直线数：1\quad2\quad3\quad4\quad5

平面数：2\quad4\quad7\quad11\quad16\quad

发现没有？如果有a_1条直线，那么就可以分割成\large\frac{a_1*(a_1+1)}{2}+1个区间。

于是代码如下：

if(i == 1){
    ans = 1 + a * (a + 1) / 2;
    sum += a * 2;//sum1以后会有用 
    ans %= mod;//注意要mod 
}

那么，直线搞定后，我们再来康康圆。

如果刚开始没有直线，那么a_2个圆可以分割成2+a_2*(a_2-1)个区间。

为什么？

下面来证明一下：

易知一个圆时可以分成2个部分，那此时多加一个圆，这个圆跟刚开始的那一个圆会有2个交点，那么它就会把原来的圆分成2个部分。分成2个部分后，它就会多分割出两个平面，于是就变成了四个平面。

同理，3个，4个直到a_2个也是如此。

我们可以列一个表格来康康：

圆的总共个数：1\quad2\quad3\quad4\quad

新增交点个数：0\quad2\quad4\quad6

新增段数个数：0\quad2\quad4\quad6

新增块数个数：0\quad2\quad4\quad6

平面总共块数：2\quad4\quad8\quad14

那么，加上直线怎么做呢？

同样，一条直线和一个圆最多会有两个交点，于是一条直线和一个圆可以多分成两块，于是ans还要加上a_1*a_2*2。但此时第一个圆会与直线有交点，所以最终只需要每两个圆进行处理即可，于是又要加上C^2_{a_2}*2=a_2*(a_2-1)

于是第二部分的代码就出现啦QAQ

else if(i == 2){
    ans += sum * a;//sum的用处就在这 
    if(!sum) ans = 2 + a * (a - 1);//没有直线的情况 
    else ans += a * (a - 1);//有直线的情况 
    b = a;//b是圆的个数，以后也会有用 
    ans %= mod;
}

那么，按照这个思路，正n边形的就好打了。

一个正n边形与一条直线有2个交点，与一个圆有2n个交点，与一个正3边形有6个交点，……与一个正n-1边形有2(n-1)个交点。

那么，ans就要加上sum*a_n+b*a*i*2

其中sum=2*a_1+6*a_3+8*a_4+...+2*(n-1)*a_{n-1}，b就是圆的个数。

还有这a_n个正n边形两两之间有2n个交点，于是ans还要加上C^2_{a_n}*2*n=a_n*(a_n-1)*n

于是第三部分的代码就大功告成啦~

else{
    ans += sum * a + b * a * i * 2;//与前面图形的块数 
    if(!sum && !b) ans = 2 + a * (a - 1) * i;//还是要特判QAQ 
    else ans += a * (a - 1) * i;//两两之间的块数 
    sum += i * a * 2;//sum要加上去 
    ans %= mod;
}

综合以上三段代码，这道题就结束啦~~

CODE: 
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, a, sum, ans, b;
signed main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &a);
        if(!a) continue;//没有就直接continue掉 
        if(i == 1){
            ans = 1 + a * (a + 1) / 2;
            sum += a * 2;//sum1以后会有用 
            ans %= mod;//注意要mod 
        }
        else if(i == 2){
            ans += sum * a;//sum的用处就在这 
            if(!sum) ans = 2 + a * (a - 1);//没有直线的情况 
            else ans += a * (a - 1);//有直线的情况 
            b = a;//b是圆的个数，以后也会有用 
            ans %= mod;
        }
        else{
            ans += sum * a + b * a * i * 2;//与前面图形的块数 
            if(!sum && !b) ans = 2 + a * (a - 1) * i;//还是要特判QAQ 
            else ans += a * (a - 1) * i;//两两之间的块数 
            sum += i * a * 2;//sum要加上去 
            ans %= mod;
        }
    }
    printf("%lld", ans == 0 ? 1 : ans);//最后的特判QAQ 
    return 0;
}

这道题不算难，主要考察大家的思维能力，代码也很短，为了考验大家就限制了空间。

End