T3

题意 给定一张有向图，问你反转一条边后是否对 \(scc\) 有变化。 \(n \le 1500, m \le 10^6\) Sol 先对图跑一边 \(tarjan\)，考虑对每条边进行分讨。 在同一强连通分量里。如果反转后依然有一条 \(u \to v\) 的路径，那么 \(scc\) 不变，否则 ......

简要题意 求一个抽象函数，满足 \(∀𝑥 ∈ ℤ, 𝑓(𝑥) + 𝐶 = 𝑓(2𝑓(𝑥) − 𝑥 + 1)\)，给定 \(n\) 个点，使得 \(\sum |f(x_i)-y_i|\) 最小，输出最小值 思路 对这个函数进行一次迭代，可以得到 \(f(x+2C)=f(x)+2C\) ......

逆天。 题意 给定一个带 ? 的 01 串，求所有填法下，后缀自动机节点的期望。\(1\le n\le 36\) 解法 后缀自动机节点数等于反串后缀树节点个数。这道题中，后缀树是一棵二叉树，记 \(a, b, c\) 表示其中有 \(0, 1, 2\) 个儿子的点个数。注意到 \(c = a - 1 ......

题意 给定一个序列 \(a\)，将之划分为两个子序列，使得两个序列前缀最大值的和之和最小。 \(1\le n\le 5\times 10^5, 1\le a_i\le 10^9\) 做法 首先 DP 很容易做到平方：考虑前 \(i\) 个数，其中一个子序列当前的最大值当然是前 \(i\) 个数的最大 ......

非常简单的一道题。要好好反思为什么没有做出来。 题意 给定一棵点带权的树，强制在线询问一条链上取恰好 \(m\) 个数按位与的最大值。\(1\le n\le 10^6, 1\le q\le 10^5, 1\le m\le 10, 0\le V< 2^{62}\)。 解法 考虑一个暴力：取出树链上所有 ......

作为能源电力、工业自动化领域的国产中坚力量，全志T3/A40i处理器国产平台一直深受广大客户的喜爱，甚有“国产工业鼻祖处理器”之称。自创龙科技推出T3/A40i全国产工业核心板（SOM-TLT3/A40i，国产化率100%，提供“中国赛宝实验室”国产化率认证报告），满足了广大客户智能电力终端（例如D ......

首先要把 A 和 B 分别按顺序排序，然后有一个显然的思路是记录 $dp_{i,j,k,l,0/1,0/1}$ 表示 A 做到 $i$，B 做到 $j$，当前时刻是 $a_k+l\times T$，是 $a_k$ 还是 $b_k$，上一个走的 A 还是 B 的最小答案，转移比较简单，复杂度 $O(n ......

题意 给定一个序列，你需要维护下面两种操作： 将所有 \(i mod k \in [l, r]\) 的 \(a_i\) 加上 \(x\) 求 \(\sum_{i = l} ^ r a_i\) Sol 考场代码挂成 \(35\) 了，数组全开两倍就直接过了/cf 初始化加强版，把单修改成了区修。 类似 ......

恶魔的低语，会送来天堂的福音。 题意 有一个 \(n\) 个点的有向无环图，第 \(i\)（\(1 \le i \le n\)）个点有 mi 条有序的出边 \(e_{i,1}, e_{i,2}, . . . , e_{i,m_i}\)。每个点要么是黑点，要么是白点。有 \(k\) 个程序，第 \(i ......

第3题 步数(原始) 查看测评数据信息 有一个二维网格，从上往下，行的编号从1至n，从左往右，列的编号是1至m。 第i行第j列的格子编号为(i,j)，如果 a[i][j]为 '@',表示格子(i,j)有障碍物， 如果a[i][j]为'.'则表示格子(i,j)可通行。 奶牛bessie当前在 格子(r ......

强制 \(X_1 < Y_1\)（若不满足，交换 \(X\) 和 \(Y\) 即可）。 把问题抽象为在一个 \(n \times m\) 的 八连通 网格图上，满足 \(X_i \ge Y_j\) 的点 \((i, j)\) 处有障碍，问 \((1, 1)\) 和 \((n, m)\) 是否连通。 ......

第3题 删除区间 查看测评数据信息 开始给你N个元素的数组（下标从1开始），数组里的数是1,2,3,…,N，然后执行D次删除操作。每次删除操作给一个区间[lo, hi]，要求删除下标位置从lo到hi的数，数组里的数据个数会减少hi-lo+1个。 例如，N=8，第1次删除操作区间是[3 4]，结果为” ......

题意 给定长度为 \(n\) 的数列 \(a\)。以及字符串 \(S\)。 你需要在每一个数字之间插入一个字符 \(x \in S\)。 求使得最终表达式的值最大的方案。 \(S \in [+, -, *]\) Sol 考虑分讨。 当 \(|S| = 1\) 时，直接填入即可。 当 \(S \in ......

题意 给定 \(n\) 个数，求将她们收尾拼接形成 \(11\) 的倍数的方案数。 Sol 数数题。 众所周知，是 \(11\) 的倍数意味着将该数错位相减 \(mod 11 = 0\)。 注意到偶数位数的数与奇数位数的数的贡献是不同的。 考虑将她们分开计算，然后合并。 设 \(f_{ijk}\) ......

2023NOIP A层联测32 T3 sakuya 虚伪的期望，彬彬赛时都能 A 的数学题。 思路 考虑算出来总的花费，再除以 \(m!\) 求期望。 对于某个排列的花费为：\(\sum\limits_{i=2}^m dis(a_{i-1},a_i)\)。 但考虑一下，这个式子重要吗？ 我们的目的是 ......

题意 给定 \(n\) 个形如 \(f(x) = (x - m) ^ 2 + k\) 的二次函数。 \(1, m, k\) 表示加入一个顶点位 \((m, k)\) 的二次函数。 \(2, x, t\) 表示删除所有 \(f(x) \le t\) 的二次函数。 求每次操作结束后还剩余几个二次函数。 ......

2023NOIP A层联测28 T3 大眼鸹猫 比赛做出来了，但是文抄…… 思路 分析每一个 \(i\)，发现其一定需要上升或下降 \(|a_i-b_i|\)。 如果求出最小操作次数，然后在此基础上，将上升或下降操作分成多次，减小对答案的贡献即可。 最小操作次数 从后向前考虑，若 \(a_i\) 需 ......

2023NOIP A层联测26 T3 tour 有意思的树上主席树。 思路 首先考虑一个点 \(p\) 能计入答案的情况，就是 \(dis(x,p)-a_p \ge a_p\)。 我们把 \(x \to y\) 的路径拆成 \(x \to lca,lca \to y\) 两条。 记录一个点 \(x\ ......

NOIP2023模拟9联测30 T3 高爸 三分啊，三分…… 思路 设现在的平均力量值为 \(x\)，大于 \(x\) 力量值的龙有 \(n\) 条，小于等于的龙有 \(m\) 条，花费为： \[a(n \times x-\sum_{i=1}^{n+m} p_i (p_i>x))+b(\sum_{i ......

ERROR: Cannot unpack file C:\Users\17482\AppData\Local\Temp\pip-unpack-9g93t3zt\simple.html (downloaded from C:\Users\17482\AppData\Local\Temp\pip-req ......

T3 结构体 考完试后补题，才发现这玩意不难搞出来。 这篇题解用了较多代码块，可以依需要看每一部分的代码。 题面好长看不懂，看提示。 【提示】 对于结构体类型的对齐要求和大小，形式化的定义方式如下： 设该结构体内有 \(k\) 个成员，其大小分别为 \(s_1,...,s_k\)，对齐要求分别为 \ ......

2023NOIP A层联测16 T3 货物运输 题目描述说这是一个仙人掌图，通常将问题转换为环和树的问题在使用圆方树来解决。 树解法 令 \(a_i=s_i-\frac{\sum s_i}{n}\) ，最终令 \(a_i=0\)。 通过树形 dp，从叶子节点向上转移，叶子节点要么向父亲拿资源，要么向 ......

CSP模拟58联测20 T3 注视一切的终结 题面及数据范围 Ps：链接为衡水中学OJ。 去除重边以后是树，而我们需要使一个点到另外一个点的简单路径上相邻边的颜色尽可能不相同。 发现如果一条边有 \(3\) 种或以上的颜色，那么该边肯定可以与相邻边不同，所以把 \(\geq3\) 的情况均看为 \( ......

零一串 (string) 题目描述 给定一个长度为 \(n\) 的 01 串，你需要将它划分成若干段，每一段的长度都不超过 \(m\)，且满足以下两种条件之一： 这个段中全部为 \(0\) 或全部为 \(1\). 这个段中 \(0,1\) 数量之差不超过 \(k\). 你需要求出该 01 串合法的划 ......

P5987 [PA2019] Terytoria / 2023NOIP A层联测13 T3 全球覆盖 题面及数据范围 对于一个点对，可以降维为线段，转化为 1 维的问题。 如图： 我们可以在横着的方向和竖着的方向个选择一种颜色的线段，任意一种选择可以构成一个合法的矩形。 我们需要求最大重叠面积，可以 ......

题目链接 题意： 时间轴上分布着$n$位乘客（$1\le n\le 500$），$i$号乘客的位置为$t_i$（0\le t_i\le 4\times 10^6），用互相距离不小于$m$的车次将时间轴分为若干部分，并管辖以自己为右端点的这个区间（除了第一趟车包括$0$，其他车次左开右闭），求最小费用 ......

乱杀 题目描述 乐孤星和 WA90 准备联合参加下一次的 NOB(National Olympiad in Badminton)。 他们想要在一场比赛中击回对手打出的所有球从而赢得比赛，因为 WA90 非常强，所以可以预先知道对手打出的每一个球的位置，他们想要计算一下打败对手需要多认真。 形式化的， ......

sudo apt install make gcc bc u-boot-tools bzip2 fakeroot gawk mkbootimg busybox 问题1： usr/bin/ld: scripts/dtc/dtc-parser.tab.o:(.bss+0x50): multiple de ......

树上询问 你有一棵 \(n\) 个节点的树 \(T\) ，回答 \(m\) 个询问，每次询问给你两个整数 \(l,r\) ，问存在多少个整数 \(k\) 使得从 \(l\) 沿着 \(l->r\) 的简单路径走 \(k\) 步恰好到 \(k\) ，\(n,m\le 10^6\)。 解题思路 分析一下 ......

Mystia 的居酒屋 题目背景 小麻雀 Mystia 开了一间居酒屋，每天清晨她都要跨过门前的河流去收集食材。 题目描述 Mystia 想搭一座跨过河的桥，来方便她取得食材。 河是一条无限长的宽度为 \(W\) 的直线，所有在坐标系中符合 \(0≤y≤W\) 的点都属于这条河流。 河面上有 \(N ......