OJ选题集

OJ选题集
4FGR下列OJ平台仅代表题目信息的一个出处,不一定为OJ平台原创
很少会出现需要数据结构来做的题。基本和数学相关。
每道题下面的均为其中关键的解题思路,题目大意并非完整题目,只出现解题思路中需要的变量。
(因此,基于测试用例t等无关变量将不会出现)
各题出处如下:
Codeforces
Cherry Bomb
Codeforces Round 1020 div.3 C. Cherry Bomb Problem - C - Codeforces
tags: greedy math sortings *1000
题目大意
两个非负整数数组a与b,当我们称其互补时,当且仅当对于每个编号i,均有ai+bi= x, 其中x为一定值。我们希望数组a,b的每个元素均非负且不大于k,并且a与b是互补的。接下来,会给出n和k、完整的数组a,以及不完整的数组b,不完整的地方用-1补齐,请问有多少种填充b的办法满足我们的需要。
Fashionable Array
Codeforces Round 1026 Div.2 A. Fashionable Array
题目大意
给一个数组,问通过每次消灭任意一个元素,如何得到(max+min)%2==0的“时尚”数组。Down with Brackets
Codeforces Round 1026 Div.2 B. Down with Brackets
tags: strings
题目大意
给你一个良好顺序的括号字符串s,你能任意破坏一个左括号和右括号,是否破坏完后能使顺序不良好。良好顺序具体定义如下:1.可以是空集。2.如果A顺序良好,则(A)顺序良好。3.如果A、B顺序良好,则AB顺序良好
我们发现如果存在同等级括号,如 \(ABC\) 型,则从其中任意两个不同的括号集合如 \(AB\) 中分别取括号,那么就破坏了两者的良好性,如果没有干扰,我们知道这不符合定义3,故不良好。
但这实现困难并且存在干扰:如果等级并非最高的,即外面有括号包住,如(\(ABC\)),我们发现取出的括号会被外面的括号补充,这是不行的。
事实上,我们发现只用判断是否第一个括号和最后一个括号相对应即可,真则不能,假则能。
Vladik and fractions
Codeforces Round 384 (Div. 2) C. Vladik and fractions
题目大意:
构造一组互不相同的 \(x,y,z\) ,使得 \(\frac{1}{x} + \frac{1}{y}+\frac{1}{z} = \frac{2}{n}\)
\(n = 1\) 时无解,其它则有通解 \(n、n+1、n(n+1)\)
通解证明简单,带入即可。
Cool Partition
核心:贪心+双map模拟区间
题目大意
将一个区间划为两个区间时,如前一区间的元素全部出现在后一区间,我们称这一次切割为有效切割。试问对于给定的区间,通过有效切割得到的区间个数的最大值。这是一道贪心题,只要最先就能做有效切割就做(即让前一区间元素尽量少),显然开始就把第一个元素当作第一个区间,然后这样遍历(我们设前一区间为mp1,后一区间为mp2,原数组为a):
- 从 \(mp1\) 中删去 \(a[i]\),表示无需再检查这一元素
- 在 \(mp2\) 中加入 \(a[i]\) ,表示后一区间已有该元素
- 如果 \(mp1\) 为空,说明 \(mp2\) 已满足所有前一区间元素,立刻划分,并且 \(mp2\) 成为下一 \(mp1\),并清空 \(mp2\)。
洛谷
开关
[P3870 TJOI2009] 开关 - 洛谷
tags: 线段树 分块
题目大意
有n盏灯排一排,能做两种操作,指定一个区间[a,b],即可以要求输出区间打开的灯数,也可以改变该区间灯的状态(开的关,关的开),灯泡在初始时是关着的。
n,m 表示灯数与操作数
c表示操作种类(c=0为第一种,c=2为第二种),a,b,表示指定区间
这是一个线段树的问题,线段树如何实现这里不做叙述,可见数据结构-线段树 | 4FGR の Blog
关键是如何处理操作1,即如何改变灯泡状态。
考虑到灯泡只有两种状态,要么开,要么关,由于我们要求开着的灯泡数量,于是置开为1,关为0,对区间做操作1,实际上是对区间每个编号的值异或1的结果(1异或1为0,由开为观;0异或1为1,由关为开),注意更新lazy标记的办法也是自异或1(lazy初始为0,01表示是否区间需要翻转)。
跳石头
[P2678 NOIP 2015 提高组] 跳石头 - 洛谷
tags: 贪心 二分
核心:二分答案
题目大意
举办跳石头大赛,从起点到终点的距离是S,其中有N个石头,第i个石头离终点的距离为ai,举办方打算移除M个石头,求出可实现的最短跳跃距离的最大值。 我们看到,答案一定确定在 \([1,S]\), 并且问题是求最小值的最大值,这时候我们求可以用二分答案来求解。
二分答案,顾名思义,依靠对答案的二分解出最后的答案,因此答案序列得是有序的且有界限,一般可用来解最小值的最大值,或者最大值的最小值。我们用 \(judge\) 函数每次评判中间值 \(mid\),如果成功,说明这个答案是合法解,最优解要么是它本身,要么就在它右边,若不合法,答案一定在它左边。随时用 \(ans\) 跟进合法的 \(mid\),显然答案就是最后一个判定为合法的 \(mid\)。
对于这道题而言,(由于我们用 \(l\) , \(r\) 表示左右,因此文中的起点到终点的距离用s表示),答案一定在区间 \([1,s]\) 上,我们每次取中间值 \(mid\),放入评判函数中。\(judge\) 函数如何设置呢?我们遍历每个石头的距离,如果这个距离小于 \(mid\),显然这块石头需要被捡走(不然不满足最短距离为 \(mid\) 的条件),记录石头被捡走的次数,如果这个次数比 \(m\) (我们本应捡走的)要多,说明不是合法解,否则是合法解。
力扣
码蹄集OJ(百度)
[青铜]房间打扫
码蹄杯2022 MC0102房间打扫
核心:寻找等价关系
实际上,最多打扫干净的行数为有着相同字符串,或者说有相同元素的行数的最大值。
[黄金]项链
码蹄杯2022 MC0104项链
核心:数学思维
碰巧做对的思路
每次一最小一最大排列,最后计算美观值。这个实际上是最佳序列的其中一种,它恰好实现了大值加2次,小值减两次,以及个数为奇数情况下的第n/2大个数恰好一加一减被抵消了而已。 我们知道,这道题如果没有绝对值的限制,显然总和为 \(0\) , 因为每个数都恰好地被做了一对加减法。在加了绝对值的情况下,对于美观值答案 \(ans\),我们显然期望两次加的都是更大的,两次减的都是最小的,因此最佳期望的答案是
\[ans = 2*|最大的n/2个数总和-最小的n/2个数总和|\]
这个最佳序列是可以得到的,只要保证这两队数奇偶位置分别放置即可,即保证大值左右两旁有小值,这样大值就被加了两次。
注意,当个数 \(n\) 为奇数时,对于第中间大数 \(a_{n/2}\),由于比它大的数与比它小正好匹配,即比它大的数都加了两次,比它小的数都减了两次,可怜的 \(a_{n/2}\) 只能本身做一次加减法,因此被抵消掉了。
[青铜]白日梦
核心:前缀极值的动态维护
这道题的核心思想非常巧妙,由于我们只做一次来回兑换,显然我们想要换英镑时汇率是大的,这样我们只要在遍历前记录当前最大值并更新 \(ans\) 和最大值 \(mx\) 即可。
[白银]水往低处流
码蹄杯2022 MC0116水往低处流
核心:寻找等价关系
题目大意
有一 n*n 的梯田,可往格子里浇上一桶水,同时它和比它严格低的格子会是“湿润的”,问至少需要多少桶水,使得梯田完全湿润。[白银]子集统计
码蹄杯2022 MC0126 子集统计
核心:位运算、排列组合
有意思的思维题,\(a \& c=c\),意味着凡是 \(a\) 有 \(1\) 的地方都可以随便填,而 \(a\) 有 \(0\) 的地方只可以填 \(0\)(因为与操作要求同一位上两个均为 \(1\) 才能为 \(1\)),同理,\(c\&b=b\)为相反情况,如果 \(b\) 有 \(1\) 的地方只能填 \(0\),如果之前标记了只能填 \(0\),那么显然冲突,无解并退出。否则,用 \(n\) 记录下可以随便填的位数,一位有两种状态 \(0\) 与 \(1\),显然答案为 \(pow(2,n)\)。
[白银]函数的幂Ⅱ
码蹄杯2022 MC0136函数的幂Ⅱ 码蹄集OJ-函数的幂Ⅱ
核心:找规律
题目大意
对于 f(a,b) 存在a=1时,f(a,b) = c*b+d, 否则 f(a,b) = f(a-1,f(a-1,b))。问对给出的a、b、c、d的最终答案的个位数。其中 a 可能高达1e6事实上,还可以通过迭代实现,因为是求个位数,我们知道其实 \(f(a,b)\) 总能化成 \(C_ix+D_i\) 的形式,由于我们只求个位数, \(C\) 、\(D\) 对其的影响也只有其个位上的数字,每次 \(a\) 上升 \(1\) 都是倍增的,于是我们可以这样更新 :
\[C_{i+1} = C_i*C_i \mod10\]
\[D_{i+1} = (C_i*D_i+D_i) \mod 10\]
[白银]快速计算
码蹄杯2022 MC0152快速计算
核心:合并多项操作、预处理
这是比较难的白银题了。要两个要处理的点,一个是所有操作可变成一个线性操作 \(Ax+b\),这里无需赘述。但这远远不够——这些数据也开得太大了吧。对总 \(q\) 个还要做 \(p\) 次操作,还与变量 \(x\) 有关!我们发现,\(p\) 次操作仍只需一阶 \(x\),本来可以化成 \((a^n)x + 一个等比数列和\),但这样我又要搞快速幂和费马小定理,太麻烦了。但由于乘数和加数与 \(x\) 无关,只随 \(p\) 变化而变化,可以算出各个 \(p\) 时的 \(mul\) 与 \(add\),但难不成我还要根据 \(p\) 动态调整?我一看 \(p\) 最多 \(1e6\),管你多大直接预处理,这样我们便得到了最终答案。
[黄金]水渠规划
码蹄杯2022 MC0154水渠规划
核心:数学
若有线段 \(AB\),和点 \(P\),则 \(P\) 到线段 \(AB\) 的最近距离为:
\[ Dis(P, AB) = \begin{cases} |AP|, & \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} < 0 \\ \frac{|\vec{AP} \times \vec{AB}|}{|\vec{AB}|}, & 0 \le \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} \le 1 \\ |BP|, & \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} > 1 \end{cases} \]
- 当 \(\frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} < 0\),即 \(P\) 的垂足不在线段上,投影点在 \(A\) 左边,则到线段的最近距离为 \(|AP|\)。
- 当 \(\frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2} > 1\),即 \(P\) 的垂足也不再线段上,投影点在 \(B\) 右边,则最近距离为 \(|BP|\)。
- 否则,投影点在 \(AB\) 之间, 则到线段的最近距离就是到直线 \(AB\) 的最近距离,可以通过计算得到。
\(\vec{AP} \times \vec{AB}\) 的值恰好为三角形 \(ABP\) 面积的两倍,除以底边 \(AB\) 的长度,即为高的长度。
剪刀石头布
MC0176剪刀石头布
[黄金]世界警察
MC0204 世界警察
核心:双指针+动态维护最后位置
用map或者哈希表(unordered_map) 动态维护元素从0到r最后出现的位置,如果已有重复元素并且包含在区间(通过l<=mp[a[i]]判断),则立马结算(注意区间应为r-1),并更新map,每次循环结束注意更新ans。
[黄金]未来战争
MC0221未来战争
核心: 合并区间|差分
利用差分性质,每次让 差分数组 \(b\) 中的 \(b_l\), \(b_{r+1}\) 分别加 \(1\) 和减 \(1\) ,使得对差分数组做前缀和后,凡是充能区间都为1,最后用 \(ans\) 记录最长连续 \(1\) 即可。
蓝桥杯
[困难]选数异或
给定一个长度为 n 的数列 \(A_1,A_2,⋯,A_n\) 和一个非负整数 \(x\) , 给定 \(m\) 次查 询, 每次询问能否从某个区间 $[l,r] $中选择两个数使得他们的异或等于 \(x\)
核心有两点:
a异或b = x 说明 a异或x = b
对于数组b,时刻记录最近的异或对中最远的那个编号,这个“最近”指的也是这些远端中最近的。这样对于区间的处理,只用判断 \(b[r]\) 是否大于 \(l\) 即可
其他
贪吃蛇
这是我们学校的题 T606586 贪吃蛇
原题应该是棋盘哈密尔顿路径问题 (据AI)
由于是内部校赛的题, 链接无用,下面给出题目
贪吃蛇问题
在贪吃蛇游戏中,玩家能够操控一条蛇,它会不停前进,且只能向上下左右四个方向运动,现在,给你的挑战是: 给定一个n∗n (1≤n≤5000)的棋盘和蛇的起点坐标(x,y),请判断是否存在一种方式,可以使得蛇可以不重复地走过棋盘上的所有的格子(忽略蛇的长度)。 这是一道特判题,事实上,只要是偶数阶方阵对任意出发点一定有解,对于奇数阶方阵,出发点只有一种无解情况:abs(x-y)%2 == 1。
AC代码如下:
1 |
|
逃离方块: 磨坊
同上 T606553 逃离方块: 磨坊
为了提取黑色方块,猫头鹰先生成功将劳拉传送了过来。但是,为了将机器启动,他们还需要输入密码, 机器下方有一串由n位字母构成的文本,而密码就是这段文本中最长的一段连续非回文子文本\(s\)的长度。请你帮乌鸦先生得到启动机器的密码。
回文串定义:\(\forall_{ 1\leq i \leq \frac{m}{2}}s_i = s_{m-i+1}\)(\(m\)是\(s\)的长度)
假定s的长度为m
这道题的思路是:先看是否 \(s\) 为回文串,显然,如果不是的话输出 \(m\) ,而其实别的判断也十分简单。判断是否 \(s\) 所有元素相同,是则返回 \(0\) ,否则返回 \(m-1\),注意单字母如 \(a\) 本身也是回文串,作者当时搞错成返回 \(1\),吃了好多罚时qaq。
之所以如此,是因为我们可以证明,当 \(s\) 为回文串并非所有元素相同时,只用左右两边仍减去一个就为非回文串。首先,显然 \(s_1\) 和 \(s_m\) 是相同的,如果仍减去一个还要是回文串,那么 \(s_1\) 和 \(s_m-1\) , \(s_2\) 和 \(s_{m-2}\)…\(s_{m/2}\) 和 \(s_{m/2-2}\) 就得相同,显然只有 \(s\) 所有元素相同才行,因为我们可以由此得到这样一条式子 \(s_1 = s_m = s_{m-1} = s_2 = s_{m-2} = s_3...\) 如此循环往复。