题解：CF1942C1 Bessie's Birthday Cake (Easy Version)

· · 题解

找能划分成几个三角形，题目的意思是从边入手，边构成了多少个三角形，而我们数边是通过数点来完成的，所以我们从点入手。 其实这个图形是几边形无所谓，只有 x 的值对我们是有用的，首先我们把点排序，然后组成一个新的图形来看，然后我们要数一下有几条不相交的对角线，很明显是 x-3 条，但是会隔成 x-2 个三角形，但是，数对角线的时候，我们把所有的点考虑成了相邻的，假如不相邻，就像 case3 一样，如果 v [ i ] =v[ i-1 ]+2 ，那么相邻的边也可以组成一个三角形，所以需要相加，但别忘了，点是环状的，所以最后一个点单独拿出来考虑。

代码时间到！

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n,x,y;
    cin>>n>>x>>y;
    vector<int>v(x);
    for(int i=0;i<x;i++) cin>>v[i];
    sort(v.begin(),v.end());
    int ans=x;
    for(int i=1;i<(int)v.size();i++)
        if(v[i]==v[i-1]+2) ans++;
    int a=v.size(),b=v[a-1]+2;
    if(b>n) b-=n;
    if(b==v[0]) ans++;
    cout<<ans-2<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}
//各位大佬给个面子，点个赞吧