首页 > 其他分享 >T403510 平面划分(Hard) 题解

T403510 平面划分(Hard) 题解

时间:2023-12-07 15:24:13浏览次数:37  
标签:直线 题解 LL Hard T403510 平面 2n

Link

T403510 平面划分(Hard)

Question

平面上由 \(n\) 条这样的折线所界定区域的最大的个数 \(Z_n\) 是多少。

image.png

Solution

先思考一个简单的问题

平面上 \(n\) 条直线所界定的区域最大个数 \(L_n\) 是多少?

image.png

我们考虑假设已经有\(n-1\) 条直线,我们需要画一条直线,这条直线最多和 \(n-1\) 条直线相交产生 \(n\) 个新的区域
image.png
所以我们得到了

\[\begin{align*} &L_0=1 \\ &L_n=L_{n-1}+n (n >0) \end{align*}\]

很容易我们可以得出 \(L_n=\frac{n(n+1)}{2}+1,n \ge0\)

然后再来思考原问题

考虑一个折线可以看作两条直线擦掉一半,对于每个折线,我们都失去了 \(2\) 块区域

image.png

所以

\[\begin{aligned} Z_n & = L_{2n}-2n \\ & = \frac{2n(2n+1)}{2}+1-2n\\ & = 2n^2-n+1,n \ge 0 \end{aligned}\]

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=1e9+7;
int main() {
    LL N;
    cin>>N;
    cout<<(2*N*N-N+1)%TT<<endl;
    return 0;
}

标签:直线,题解,LL,Hard,T403510,平面,2n
From: https://www.cnblogs.com/martian148/p/17882101.html

相关文章

  • 【题解】CodeForces 1902F Trees and XOR Queries Again
    传送门:https://codeforces.com/contest/1902/problem/F数据结构题,这里讲两种思路。$ST$表思路:判定“从若干个数中能否取出其中一些,使得异或和为$x$”的问题,第一时间想到线性基,本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性基可以合并,方法为“暴力将......
  • [ARC106E] Medals 题解
    题目链接题目链接题目解法感觉不难啊,怎么想到网络流和\(hall\)定理后面就屁都没想到呢首先一眼网络流先二分答案考虑一个朴素的建图方法是:把每个人拆成\(k\)个点,然后往在的天连边,跑最大流,满流即合法可以发现,跑网络流对这道题还说没有必要,因为只要判是否有完美匹配不难......
  • 【UVA 101】The Blocks Problem 题解(模拟+向量)
    计算机科学的许多领域使用简单、抽象的领域进行分析和实证研究。例如,早期的人工智能规划和机器人研究(STRIPS)使用了一个区块世界,其中机器人arm执行涉及块操作的任务。在这个问题中,您将在某些规则和约束下对一个简单的块世界进行建模。相当地与确定如何达到指定状态相比,您将“编程......
  • Maven无法下载fastdfs-client-java依赖问题解决
    一、分析原因控制台报错具体如下:并且pom.xml中以下依赖爆红:<dependency><groupId>org.csource</groupId><artifactId>fastdfs-client-java</artifactId><version>1.29-SNAPSHOT</version></dependency>原因:因为fastdfs-clien......
  • [CF83E] Two Subsequences 题解
    [CF83E]TwoSubsequences题解思路定义\(overlap(a,b)\)为字符串\(a\)的后缀与\(b\)的前缀的最大相等的长度,有\(|f(a,b)|=|a|+|b|-overlap(a,b)\),下文称匹配为相邻两串的\(overlap\)。观察到每次操作之后,一定有一个序列是以\(a_i\)为结尾的。所以根据这个......
  • CF1900B题解
    原题思路略微思考不难得到,三个数字的数量之差的奇偶性是不会变的。因为一个数的数量减少了$1$,另一个数无论是增加$1$或是减少$1$,两者的差要么不变,要么增加/减少$2$,对奇偶性无影响。同时,如果另外两个数的数量变为$0$,它们数目的差一定是$0$。那么,我们只需要判断另外两个......
  • 【题解】CodeForces 686E Optimal Point
    传送门:https://codeforces.com/contest/686/problem/E前言:本题解来源于作者某天晚上和一位朋友的发电内容(没错,这个作者直接把自己和朋友发电时发的话用markdown排了一下,传上来了),当时本来就比较口语化,加上作者的做法又实在太过离谱,因此可能语言表述不够清晰,对此深感抱歉qwq;离......
  • 【题解】LibreOJ #3051「十二省联考 2019」皮配
    传送门:https://loj.ac/p/3051  首先,对于这样“少部分个体有特殊要求”的题目,我们先考虑,如果没有任何个体有特殊要求怎么做,然后再考虑怎么加上特殊要求;对于这道题,如果$k=0$,即没有学校有不喜欢的导师,那么,设总人数为$al$,城市$i$的人数和为$cit_i$、选择的阵营为$zy_i=0/......
  • UVA753 A Plug for UNIX 题解
    LinkUVA753APlugforUNIXQuestion有\(n\)个插座,\(m\)个设备和\(k\)种转换器,每种转换器有无限多个。转换器可以插着转换器用,每个插座或插头的类型可能不同,求最少剩多少个不匹配的设备Sulotion先考虑转换器连用的情况,用边表\(G[x][y]\)表示\(x\)类型可以转换成\(y......
  • UVA1395 Slim Span 题解
    LinkUVA1395SlimSpanQuestion求所有生成树中最大边权与最小边权差最小的,输出他们的差值Solution因为\(n\le100\)非常小,先把边从小到大排序,那么生成树的边肯定是排序后上的边连续的一块所以,可以枚举连续一块的起点\(L\),\(R\)从\(L\)往后推,判断全图连通性,如果已经完......