OJ选题集

4FGR2025-05-232025-05-28

OJ选题集

下列OJ平台仅代表题目信息的一个出处，不一定为OJ平台原创

很少会出现需要数据结构来做的题。基本和数学相关。

每道题下面的均为其中关键的解题思路，题目大意并非完整题目，只出现解题思路中需要的变量。

（因此，基于测试用例t等无关变量将不会出现）

Codeforces

Codeforces Round 1020 div.3 C. Cherry Bomb Problem - C - Codeforces

tags: greedy math sortings *1000

题目大意

两个非负整数数组a与b，当我们称其互补时，当且仅当对于每个编号i，均有a_i=b_i。我们希望数组a,b的每个元素均非负且不大于k,并且a与b是互补的。接下来，会给出n和k、完整的数组a，以及不完整的数组b，不完整的地方用-1补齐，请问有多少种填充b的办法满足我们的需要。

我们假设 $a_i+b_i$ 互补时的结果为 $x$

显而易见，由于 $b$ 是不完整的，我们所做的其中一点就是保证不完整的地方非负且不大于 $k$ 。当 $x$ 一定时，显然我们就确定了 $b$ 的范围，若 $a$ 的范围为 $[mina,maxa]$，则b的范围就为 $[x-maxa,x-mina]$，我们显然不用担心 $x-maxa$ 为负数，我们唯一担心的就是 $x-mina$ 的结果超过了 $k$。

注意到 $x>=maxa+minb$ 。显然，如果 $x$ 的下界$-mina$ 大于 $k$ ，则 $x$ 的个数为 $0$ 。

如果 $x$ 确定，则 $minb=x-maxa$ ，我们于是知道当数组 $a$ 确定时，一个 $x$ 唯一确定 $minb$ 。

到了这里，相信你已经知道如何算出 $x$ 的个数了，即 $minb$ 可取的值域大小 $[0,k-(maxa-mina)]$（ $minb$ 上界要照顾到 $mina$ 或者说 $maxb$ ）

上界的得出有两种想法：

一种想法是不能使 $x-mina>k$ , $x$ 对应 $maxa+minb$ ，带入即可得出其上界，同时注意到 $minb$ 为整数，因此可以化开区间为闭区间
另一种想法是 $maxa-mina = maxb-minb$ , 因为 $maxb$ 上界为 $k$ （事实上，基准值 $x$ 绝不会超过 $k+mina$ ，因此所有元素 $b_i$ 一定能通过加上一个比 $k$ 小的值得到基准值)，所以 $minb$ 的上界应该是 $k-(maxb-minb)$ ，即 $k-(maxa-mina)$

当然你也可直接通过 $x$ 的值域 $[maxb,k+mina]$ 来得到 (如果你知道上述 $minb$ 区间的由来，这里你应该就能理解了)

因此，$x$ 的个数为 $k-(maxa-mina)+1$ 。

同时注意对个数为 $0$ 的判断(如果存在至少完整的一个元素，结果要么为 $0$ ，要么为 $1$ )：

多个完整的 $b$ 中元素存在，但与 $a$ 中对应元素相加的结果不一致
相加结果 $x$ 一致，但依据 $x$ 得出的其他 $b$ 的元素大于 $k$ 或者小于 $0$
$maxa-mina==k+1$

注意到题中 $0\leq a \leq k$ ，故条件3无需判断。

Codeforces Round 1026 Div.2 A. Fashionable Array

Problem - A - Codeforces

题目大意

给一个数组，问通过每次消灭任意一个元素，如何得到(max+min)%2==0的“时尚”数组。

对数组排序，可证明要么开始成功，要么只用从左往右，或者从右往左，找到第一个与 $max$ 或 $min$ 奇偶性不同的值，最大次数是遍历到 $min$ 或 $max$ （消除到只剩一个）。其中奇偶性不同的判断为 $(a+b)\%2=1$ ，结果对从左往右和从右往左搜索的结果取最小值。

Codeforces Round 1026 Div.2 B. Down with Brackets

Problem - B - Codeforces

tags: strings

题目大意

给你一个良好顺序的括号字符串s，你能任意破坏一个左括号和右括号，是否破坏完后能使顺序不良好。良好顺序具体定义如下：1.可以是空集。2.如果A顺序良好，则(A)顺序良好。3.如果A、B顺序良好，则AB顺序良好

我们发现如果存在同等级括号，如 $ABC$ 型，则从其中任意两个不同的括号集合如 $AB$ 中分别取括号，那么就破坏了两者的良好性，如果没有干扰，我们知道这不符合定义3，故不良好。

但这实现困难并且存在干扰：如果等级并非最高的，即外面有括号包住，如（$ABC$），我们发现取出的括号会被外面的括号补充，这是不行的。

事实上，我们发现只用判断是否第一个括号和最后一个括号相对应即可，真则不能，假则能。

洛谷

[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表示是否区间需要翻转)。

力扣

其他

这是我们学校的题 T606586 贪吃蛇

原题应该是棋盘哈密尔顿路径问题 （据AI）

由于是内部校赛的题，链接无用吗，下面给出题目

贪吃蛇问题

在贪吃蛇游戏中，玩家能够操控一条蛇，它会不停前进，且只能向上下左右四个方向运动，现在,给你的挑战是：给定一个n∗n (1≤n≤5000)的棋盘和蛇的起点坐标(x,y)，请判断是否存在一种方式，可以使得蛇可以不重复地走过棋盘上的所有的格子（忽略蛇的长度）。

这是一道特判题，事实上，只要是偶数阶方阵对任意出发点一定有解，对于奇数阶方阵，出发点只有一种无解情况：abs(x-y)%2 == 1。

AC代码如下:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int x,y,n;
    cin >> n >> x >> y;
    if(n%2==0) cout <<"YES";
    else if(n%2==1 && abs(x-y)%2==1){
        cout << "NO";
    }else cout << "YES";
}

同上 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...$ 如此循环往复。