首页 > 其他分享 >AT_agc017_b 题解

AT_agc017_b 题解

时间:2023-07-26 14:00:46浏览次数:55  
标签:输出 agc017 题解 times le 遍历 区间

洛谷链接&Atcoder 链接

本篇题解为此题较简单做法,请放心阅读。

题目简述

一共有 \(n\) 个格子,给定两个整数 \(A,B\) 分别位于第 \(1\) 和第 \(n\) 格,中间有 \(n−2\) 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 \([C,D]\) 之间。

依次输入 \(n,a,b,c,d\)。

若能,输出 YES;反之输出 NO

思路

遇事不决先看数据范围,发现数据范围 \(3 \le N \le 5 \times 10^5\),那么时间复杂度在 \(O(N)\) 以内就可以接受,本篇题解就详细解释一下 \(O(N)\) 的算法。

首先可以想到 \(O(N)\) 的复杂度就是遍历 \(N\),可以想到枚举在 \(A,B\) 之间填了 \(i\) 个数,从 \(0 \sim N-2\) 遍历即可,遍历时进行判断,如果满足要求可直接输出 YES,否则遍历完后输出 NO

接着可以先把区间 \([C,D]\) 转化为区间 \([0,D-C]\),那么判断条件就需要判断 \(C\) 的合法性及可行性

\[B - (2 \times (i + 1) - N) \times C \]

接着可写出判断条件的边界条件,首先是最大值即右区间,通过右区间 \(D-C\) 很容易得出:

\[A + i \times (D - C) + D \]

以及左区间

\[A + (N - 2 - i) \times (C - D) + C \]

如果合法的 \(C\) 在此区间内则输出 YES,否则在遍历后输出 NO

注意:因为均为闭区间所以需是 \(\le\) 而不是 \(<\)

经过以上分析及转化,很容易即可得出代码了。

提交记录

\[\text{The End!} \]

标签:输出,agc017,题解,times,le,遍历,区间
From: https://www.cnblogs.com/So-noSlack/p/17582280.html

相关文章

  • AT_arc149_a 题解
    洛谷链接&Atcoder链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述求满足以下条件的小于\(10^n\)数最大是多少?每一位数字均相同;是\(m\)的倍数。数据范围:\(1\len\le10^5\),\(1\lem\le10^9\)。思路首先每位数字都相同很好满足,仅需......
  • 题解:【ICPC WF 2021 L】 Where Am I?
    题目链接这年WF较为简单的一道了,直接模拟即可。首先可以预处理出它顺时针螺旋轨迹的移动步数,方便过会算距离直接查表。我偷懒直接用map记录的距离表,这样不用处理复数下标的问题。注意到\(X\)的数量不会超过\(100\)个,所以我们可以反过来从标记点上入手。找出所有的标记点,......
  • 洛谷 P2894 [USACO08FEB] Hotel G 题解
    题目链接P2894[USACO08FEB]HotelG-洛谷|计算机科学教育新生态(luogu.com.cn)分析考虑用线段树维护区间信息维护sum(最大连续空房间数)如何合并?sum1为max(sum2,sum3)(1的两个子区间)但我们发现若区间为100001(0表示空房间)sum1=4而max(sum2,sum3)=2所以再维护suml(从左开始的......
  • 网络并发每日习题解释版
    网络并发每日习题解释版1.软件开发架构类别软件开发架构类别:软件开发架构是指在软件设计和开发过程中,用于组织和管理软件系统的基本结构。常见的软件开发架构类别包括:分层架构(LayeredArchitecture):将软件系统划分为多个相互独立的层,每个层都有特定的功能和责任。客户端......
  • 【题解】Educational Codeforces Round 150(CF1841)
    赛时过了A-E,然后就开摆了,为什么感觉C那么无厘头[发怒][发怒]排名:25thA.GamewithBoard题目描述:Alice和Bob玩游戏,他们有一块黑板。最初,有\(n\)个整数\(1\)。Alice和Bob轮流操作,Alice先手。轮到时,玩家必须在棋盘上选择几个(至少两个)相等的整数,擦除它们,然后写一个......
  • 题解 BZOJ4543【[POI2014] HOT-Hotels】
    长链剖分优化DP板子题了,但是虽然是板子这个转移方程也很难想。problem树。求\(\sum_{1\leqi<j<k\leqn}[dist(i,j)=dist(i,k)=dist(j,k)].\)。\(n\leq10^5\)。solution与重链剖分相似,长链剖分是将树剖成很多条长链。我们定义长儿子,为一个点的儿子中子树深度最大的一个儿......
  • Codeforces 1852A Ntarsis' Set 题解
    题目传送门:Codeforces1852ANtarsis'Set题意给定一个集合,里面初始有\(1,2,3...10^{1000}\),告诉你每天会拿掉其中的第\(a_1,a_2,a_3...a_n\)个,询问这样的\(k\)天之后剩下的最小的数是多少。分析思考如果\(x\)在这天没有被删掉,那么哪些被删掉的位置会对它产生什么......
  • CF1776M Parmigiana With Seafood 题解
    先将所有的叶子取\(\max\)贡献给答案,以下讨论的所有点中不考虑叶子。首先可以考虑先手能否删到\(n\):不难发现当\(2\midn\)的时候可以,然后我们就排除了一半的\(n\),于是以下令\(2\not\midn\)。接下来,考虑先手能否删掉\(n-1\),那么把\(n-1\ton\)的路径当成一个大点,......
  • 洛谷 P9221 「TAOI-1」Pentiment 题解
    Description给定\(n\timesm\)的矩阵,从第\(1\)行任意格子出发,每次向下、左、有走一步,有\(q\)个障碍不能经过,求走到第\(n\)行任意格子的方案。对于所有数据,\(1\leqn,m\leq10^9\),\(1\leqq\leq10^5\)。link:https://www.luogu.com.cn/problem/P9221Solution算法一考......
  • 题解 LGP2300【合并神犇】
    Problem随机\(n\)个正整数组成序列。将序列分尽量多的段数,使得前一段的和不大于后一段的和。求能分成多少段。输出\(n-ans\)。\(n\leq10^5\),值域不重要。Solution状态设计为:\(f_i=1+\min_{sum_i-sum_j\geqg_j}f_j\)表示前\(i\)个数字划分的最多段数,\(g_j\)定义为\(f_......