首页 > 其他分享 >【题解】CF1942C1 Bessie's Birthday Cake (Easy Version)

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

时间:2024-08-14 13:49:22浏览次数:12  
标签:int 题解 差为 Version Easy Birthday include

\(\mathfrak{1st.\ Preamble\ |}\) 前言

题目传送门:CF1942C1 Bessie's Birthday Cake (Easy Version)

蒟蒻在洛谷上第一篇通过的题解。

\(\mathfrak{2nd.\ Reasoning\ |}\) 思路

其实只需要把选中的点组成一个新的多边形,然后我们就可以发现有 \(x\) 个点的多边形可以连出 \(x-2\) 个三角形。此外,两个位置差为 \(2\) 的点也是可以连出一个三角形。

于是我们只需要对点的位置排个序,然后从头到尾遍历一遍,发现差为 \(2\) 的相邻两点就 cnt++,最后输出 \(x-2+cnt\) 就是最终答案了。

注意:首尾点的位置差为 \(n-a_x+a_1\),如果这个为 \(2\) 也得 cnt++

时间复杂度:每组数据 \(O(n \log_2 n)\)。

\(\mathfrak{3rd.\ Code\ |}\) 代码

#include <iostream>
#include <algorithm>
#include <string.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int T,n,x,y,ans,a[N];
int main(){
	//数据较大,关闭同步流加快输入输出速度
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
    	ans=0,memset(a,0,sizeof(a));	//保险起见清空一下
    	cin>>n>>x>>y;
    	for(int i=1;i<=x;i++)cin>>a[i];
    	sort(a+1,a+x+1);	//排序点的位置
    	for(int i=2;i<=x;i++)if(a[i]-a[i-1]==2)ans++;
    	if(n-a[x]+a[1]==2)ans++;	//判断首尾点的位置差
    	cout<<ans+x-2<<endl;
	}
	return 0;
}

标签:int,题解,差为,Version,Easy,Birthday,include
From: https://www.cnblogs.com/Simon-Wu/p/18358827

相关文章

  • 【知识】并查集的单点删除 &【题解】SP5150
    \(\mathfrak{1st.}\)前言-->题目传送门<--原先这道题的难度是紫,我觉得题目翻译看不懂,就去讨论版发了个贴,然后题管更新了题目翻译,并且把难度降到了蓝……\(\mathfrak{2nd.}\)思路赶时间或嫌啰嗦的可以直接跳到『思路归纳』。我们先从普通并查集开始思考对于删除单点\(x\),......
  • 【问题解决】git status中文文件名乱码
    问题复现解决办法在gitbash中直接执行如下命令gitconfig--globalcore.quotepathfalse原因通过gitconfig--help可以查看到以下内容:core.quotePathCommandsthatoutputpaths(e.g.ls-files,diff),willquote"unusual"charactersinthepathnamebyencl......
  • 启动应用程序出现PCLXL.DLL找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个PCLXL.DLL文件(挑选合适的版本文件)把它放入......
  • 项目推荐——音频标注wavesurfer.js用法及相关问题解决
    一、前言上期推荐了文本标注poplar-annotation用法,这期针对音视频标注推荐wavesurfer.js库;Wavesurfer.js是一个基于WebAudioAPI和HTML5Canvas的开源音频可视化库,用于创建可交互、可定制的波形。同时拥有众多插件库。二、demo效果可以实现音视频播放暂停、指定区域......
  • 【实践问题】UART通信问题解决过程
    近期开发了一项通过UART进行读写操作的功能。说起来并不难,但是实际操作起来还是遇到了不少问题,解决问题也费了一番周折。因此记录下来作为积累,也供遇到类似问题的同学参考。问题背景当前的项目需要开发一项功能:BMC通过UART串口与另一设备通信,进行读写操作。听起来并不难,......
  • [CS61A] 学习记录六 Lab2 题解思路分享
    前言观前提示,笔者写的代码答案放在GitHub仓库中,此处仅记录过程与心得。此外,请最好在尝试独立完成该任务后再看本文,否则就很可能失去了体验本项目精华的机会正文Q1:WWPD:LambdatheFree有两个问题有点意思。lambda与参数>>>b=lambdax:lambda:x#Lambdascanr......
  • 洛谷P9573 「TAOI-2」核心共振 题解
    ProblemSolution很容易发现如果\(p\ge2n\)时「共振」的次数一定为\(0\),所以这时随便怎么输出都行。考虑一般情况。首先为\(p\)的倍数的数肯定无法与其他不是\(p\)的倍数的数组,所以先输出是\(p\)的倍数的数。然后可以想到只需要枚举一个\(i\)表示余数,发现只需要枚......
  • CF1393B Applejack and Storages 题解
    ProblemSolution注意到能拼出时必须要存在\(2\)组及以上的四个相同的木棍,或者\(1\)组及以上的四个相同的木棍和除此之外的\(2\)组及以上的两个相同的木棍。同时又注意到\(a_i\)很小,所以可以用桶统计,同时实时更新四个相同木棍的组数和两个相同木棍的组数即可。Code#in......
  • 洛谷P7767 DNA 题解
    ProblemSolution考虑DP。设\(dp_{i,0}\)表示前\(i\)个字符全为A的最小操作次数,\(dp_{i,1}\)表示前\(i\)个数全为B的最小操作次数。考虑转移。若当前位为A则\(dp_{i,0}=\min(dp_{i-1,0},dp_{i-1,1}+1)\),\(dp_{i,1}=\min(dp_{i-1,0}+1,dp_{i-1,1}+1)\);若当前位......
  • 洛谷P9539 「AWOI Round 2 B」树学 题解
    ProblemSolution题目要求字典序最小,所以一定要尽可能多的\(a\),而且要尽可能靠前。所以我们只需修改不是\(a\)的位置为\(a\)即可。但若\(a\)的个数比\(r\)大,我们就需要将多余的\(a\)手动改为\(b\)并在接下来的修改中保持不变,所以定义一个\(vis_i\)表示是否一定......