rounding maximum 1857b cf

好神奇的 dp 题。 description 给定数组 \(a\)，求其有多少个排列满足 \(y_i=\max(a_1,a_2,\dots,a_{i-1})\) \(\forall i\in [1,n]\cap\mathbb{Z},2a_i\leq y_i ~\texttt{OR}~ 2y_i\le ......

给一个 \(n \times m\) 的矩阵和 \(n \times m\) 个数，你需要把这些数填入矩阵。保证 \[\sum_{i=1}^n \sum_{j=1}^m \left ( \mathop{max}\limits_{1 \leq x \leq i, 1 \leq y \leq j} a_ ......

给一个堆 \(n\) 个石子，如果可以分裂为整数，它将分裂为 \(\frac{1}{3} n\) 和 \(\frac{2}{3} n\) 的两堆石子。并且新石堆会继续分裂。 询问过程中是否出现过大小为 \(m\) 的石堆。 显然记忆化 \(dfs\) 即可。 记忆数组一般开全局。容易观察到值域很大， ......

给定两个长为 \(n\) 的数组 \(a\) 和 \(b\) 。你需要将 \(a\) \(b\) 归并成一个数组 \(c\) 。询问所有归并方法中，连续数相同的子段最长为多少。\(1 \leq a_i, b_i \leq 2n\) 。 显然归并在 \(a\) 可以任选一段 \([l_1, r_1]\ ......

定义正整数 \(C = \overline{c_1c_2 \cdots c_k} = c_1 \cdot 10^{k-1} + c_2 \cdot 10^{k - 2} + \cdots + c_1\) 。 假设有两个正整数 \(X = \overline{x_1x_2 \cdots x_n}, Y ......

这题首先上来会发现题目中的很多信息都是假的，核心就是问要构造一个\(x\)个点的完全图至少要多长的序列 我们把序列中相邻的两个元素看作图上的一条边，则可以把问题转化为：给一个\(x\)个点的完全图，问至少要走多长的路径才可以遍历图中的所有边至少一次 简单讨论下会发现当\(x\)为奇数时，此时图中每个 ......

小清新贪心+分类讨论，因为边的数组开小了WA了好久…… 首先我们贪心地选出不包含\(s,t\)的边，用这些边尽量地将除了\(s,t\)外的\(n-2\)个点连通 接下来考虑每个连通块，由于题目保证图初始连通，因此只有三种情况，即要么其中仅有和\(s\)相连的边；仅有和\(t\)相连的边；或者同时有向 ......

刚开始想复杂了，后面再细想了下发现是个傻逼题 考虑一下构造策略，每次从两种颜色集合中分别取出一个数\(u,v\)，考虑连边\(u\leftrightarrow v\)，边权为\(\min(s_u,s_v)\) 并在每次操作后将\(s_u,s_v\)中较小的那个直接删掉，并把较大的那个值减去\(\mi ......

也是一个很经典的优化最短路的题，感觉在暑假前集训做过类似思想的题来着 首先发现我们可以把所有有路灯的点以及终点看作关键点，很显然我们只关心关键点之间的边权以及最短路 不难发现对于两个关键点\(i,j\)，如果\(i,j\)相邻，则它们之间有边权为\(0\)的边；否则若\(|x_i-x_j|\le 2 ......

挺有意思的一个构造题，不过这种排列置换相关的套路感觉都太明显了 首先考虑把原图的每个置换环求出来，稍作观察会发现所有长度为奇数的置换环都可以很容易地构造出对应的\(q\)数组 但长度为偶数的置换环就不能单独构造了，但我们发现可以把两个长度相同且为偶数的置换环交错着合并来得到一个合法的\(q\)数组 ......

给一个字符串 \(s\) 包含 \(0, 1, ?\) 。 定义一个 \(01\) 串 \(s\) 的 \(cost\) 为：选择 \(s\) 的任意一个子段 \([l, r]\) 并 \(reverse\) 。将 \(s\) 变为一个非降序序列时的 \(reverse\) 最小次数即 \(cost ......

Codeforces Round 901 (Div. 2) 比赛链接 "考古"啦！之前没有做，现在补上 A. Jellyfish and Undertale 题目链接 思路： 按理说用模拟应该也是可以做到的，但是我应该没有写好，因为我们要找的是最大时间，所以我们每次加上的是min(a-1,x[i]) ......

哈人*3400，是不是贺过了个 1F (? 单点编号 \(\to max + 1\)，动态维护 prufer 序列删除了哪些点。 看似不可做，但是不难发现我们一个点被更改其他点的相对次序不会改变，反而 \(x \to max\) 这条链的删除次序到了最后面。 然后我们以权值最大点为根，不难发现每次只 ......

简单题。CF 评分才 *1600。 可以直接先把 \(Q\) 拆成两部分。 \[\begin{aligned} \large a&=\oplus^n_{i=1}p_i\\ \large b&=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (i\bmod j)\\ \large ......

见到有单调性、有限制的区间问题，很自然地就会想到用尺取去做。 先按工资升序排序，然后套上尺取就行了。 不会尺取的可以根据这道题去学。 时间复杂度 \(O(n\log n)\)。 #include<cstdio> #include<algorithm> #define ll long long usi ......

思路 发现如果一个字符串中有长度大于等于 \(2\) 回文子串，必定有长度为 \(2\) 的回文子串或长度为 \(3\) 的回文子串，并且形如：aa 和 aba。 所以考虑用线段树这两种情况。维护一段区间的最左、次左、最右、次右的元素，同时用两个标记变量 \(f_1,f_2\) 分别表示这个区间中是 ......

Abnormal Permutation Pairs (hard version) 两个限制：字典序小、逆序对大，一个显然的想法就是确保一对关系，统计另一对关系。 确保哪一对呢？我们想了想，决定确保字典序小，因为字典序是可以贪心的。 具体而言，我们考虑两个排列自第 \(i\) 位开始出现了不同。这样 ......

Longest Increasing Subsequence LIS 问题有两种主流 \(O(n\log n)\) 解法，最常见的树状数组法，以及不那么常见的二分法。然后考虑本题，发现一个神奇的思路就是求出 LIS 后倒序复原出数组。 进一步思考后发现，因为本题是 LIS（Longest Incre ......

用桶存，做一遍前缀和，令 \(b_{x,y}\) 表示序列 \(x\) 包含 \(1\sim y\) 的数字个数。考虑枚举第一个序列保留的前缀 \(1\sim i\)，对于第三个序列，如果其保留了后缀 \(j\sim n(i<j)\)，考虑哪些数需要被移掉，那么答案就是： \[b_{1,n}-b_{ ......

A题直接拆成 1 1 n-2 <=4时bob，否则alice B题直接模拟一下就行 C题开始想复杂了，我们直接枚举是哪个字符转成哪个字符即可，如果是变大，一定是放在最左，如果是变小，一定是放在最右，爆算即可。 D题，显然N^2dp，但是还是想错一些细节，假设按右端点排序后，当前考虑第i个区间，假设我 ......

一道简单的博弈论。 思路 我们可以先记录每张牌的个数，如果这个牌的个数为奇数，则 Conan 胜利，如果全部为偶数，Agase 胜利。 证明 如果说所有牌为偶数，那么无论 Conan 取哪张牌，Agasa 都可以和他取一样的，最终让 Conan 失败。 如果不满足，那么 Agasa 会无法操作。 A ......

你有连续的 \(n\) 天假期，第 \(i\) 天的温度为 \(a_i\) 。你计划在这 \(n\) 天中选择连续的若干天去旅游，至少为 \(k\) 天。给定一个 \(q\) ，你需要确保你出去旅游的时间中每天的温度都 \(\leq q\) 。询问你有多少种计划旅游的方案。 不难用双指针找出所有连续 ......

数组 \(a = [a_1, a_2, \cdots, a_n]\) 被称为是美丽的，如果可以将 \([1, x]\) 段移到 \([x + 1, n]\) 段后面，\(x \geq 0\) ，数组可以构成非降序。 现在有一个数组 \(a\) （一开始为空）和 \(q\) 个询问，第 \(i\) 个 ......

给一个正整数 \(n\) ，你需要构造一个 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\) 。对于排列 \(p\) 的每个子段 \([l, r]\) ，\(mex_{i = l}^{r} a_i\) 的结果为质数的次数尽可能多。 此处的 \(mex\) 最小排除值最低为 \( ......

一个塔防游戏。 一共有 $n$ 个塔按 $1 \sim n$ 的顺序排成一列，每座塔都有魔力容量 $c_i$ 和魔力恢复速率 $r_i$。对于一座塔 $i$，每过一秒它的魔力 $m_i$ 会变为 $\min(m_i+r_i, c_i)$。每座塔初始时满魔力。 一共有 $q$ 个怪物，每个怪物有两... ......

On the Bench 题面翻译 给定一个序列 \(a(a_i\le 10^9)\)，长度为 \(n(n\le 300)\)。 试求有多少 \(1\) 到 \(n\) 的排列 \(p_i\)，满足对于任意的 \(2\le i\le n\) 有 \(a_{p_{i-1}}\times a_{p_i} ......

什么一眼构造题 首先要卡Floyd的关键就是存在某两个点\(x,y\)，满足这两个点之间的所有最短路经过的点中（除\(x,y\)本身）至少有一个非关键点 因此很容易想到如下构造法，先随便找一个关键点\(K\)，然后把所有非关键点和\(K\)连边（当然如果所有点都是关键点就显然无解） 接下来先随便连边 ......

什么大力爆搜题 不妨考虑枚举要拿掉的位置，考虑怎么检验它是某两个点之间必经之点 简单手玩一下会发现如果存在这么一条路径，那么我们一定可以把该路径的端点定为与要拿掉的点距离为\(1\)的点上（即与要拿掉的点上下左右前后\(6\)连通） 因此我们把这些点找出来后爆枚点对，判断路径是否唯一就直接爆搜即可 ......

首先先把原图中的连通信息求一下，不妨设其中有\(tot\)个连通块，每个连通块的大小为\(sz_i\) 考虑第二步操作时我们需要连\(tot-1\)条边使得图连通，而每个连通块中只有\(\min(sz_i,k)\)个点可以参与连边 因此如果\(\sum_{i=1}^{tot} \min(sz_i,k ......

好经典的题，因为暑假前集训做过类似的思想的题所以知道怎么处理 这题由于要求最多的删去的边数，则等价于求最少保留几条边，很显然留下的边一定是最短路上的 但问题是如果两条路不相交的话很简单，可事实是两条路径可以重叠一些部分，这些边用了两次可能可以使答案变优 关于这种图上两条路径的题有一个经典结论，即两条 ......