题解1203 div cf

赛后补题请到 洛谷比赛。 A 考虑分类讨论。显然当 $a=0,b=0$ 时，答案等于 $0$。 当 $a=0$ 或 $b=0$ 时，直接将等于 $0$ 的数乘以一个很大的数字，将不等于零的数除以一个很大的数字，答案为 $v$。 当 $a,b$ 均不为 $0$ 时，可以选择先将一个数字减到 $0$，或 ......

C. Scoring Subsequences 思路：我们想要找到满足的最大值的长度最长的的区间，因为单调不减，所以更大的数一定在最大值的里面包含，所以我们用两个指针维护这样一个满足当前i的最大值区间，当新来一个数，这时我们答案里面一定要包含这个数，我们看能否保持这个长度，能不能保持需要看j指针所指 ......

一个区间的权值为最大的三个数的和-区间长度，求最大的权值。 首先我们注意到，两个端点肯定是max，考虑反证法，假设当前选的是l,r区间，若两端不是max，则可以通过增大l，减小r来增加答案。（然而好像并没有什么用？） 我们可以设$f[i][1/2/3]$，表示到了第i个点，我们当前选了几个的最大贡献 ......

Part I Preface 原题目(Luogu) Part II Sketch 求出若干组排列 $a,b,c$，使得 $a:b:c = 1:2:3$。 Part III Analysis 暴力 $9$ 层循环即可。 Part IV Code #include <iostream> using na ......

CF1826E 这个题比赛的时候基本做出来了，就是不会用 bitset 导致最后寄了。这已经是第三次很有希望做出 E 最后没有做出来了 /ll 好几个月了一直卡在四题，吐了 首先如果对于一个模特，她在 $i$ 城市的所有分数都分别小于 $j$ 城市的，那么就 $i\rightarrow j$ 连一条 ......

Part I Preface 原题目(Luogu) Part II Sketch 给定一个正整数 $L$，表示独木桥长度。 给定一个正整数 $N$，表示桥上士兵的数量。 给定 $N$ 个整数，分别表示每个士兵的坐标。 规定走到 $0$ 坐标或 $L+1$ 的位置为下桥，两个士兵相遇时不能走过去，他们 ......

题意 给你一个长度为 $n$ 的序列 $b$，求下面这个式子的值： $$ \max_{1 \le l \le i \lt j \lt k \le r \le n}(b_i + b_j + b_k -(r - l)) $$ $n \le 10^5$。 思路 官方题解给出的做法使用了单调栈，这里给出一种 ......

Part I Preface 原题目(Luogu) Part II Sketch 给定一个正整数 $n$，表示地毯张数。 接下来 $n$ 行，每行 $4$ 个整数，$a,b,g,k$，分别表示一个地毯的左下角和右上角的坐标。 最后一行，$x,y$，表示查询的点。 求出这个点上面覆盖的最上面的地毯编号 ......

Part I Preface 原题目(Luogu) 原题目(AtCoder) Part II Sketch Part III Analysis 观察这道题，我们很容易想到，必须推导出 $x1, y1, x2, y2$ 与 $x3, y3, x4, y4$ 之间的关系。 我们观察下图。 可以发现： $ ......

Part I Preface 原题目(Luogu) 原题目(CodeForces) Part II Sketch 给定一个整数 $n$。 将 $n$ 拆分成一个数列 $a_1,a_2,a_3,\dots,a_m$。 使得 $\sum\limits_{k = 1}^{m}a_k = n$，每个 $a_ ......

Part I Preface 原题目(Luogu) 原题目(CodeForces) Part II Sketch 设有一个 $2 \times 2$ 的棋盘，上面可以填入 $1-9$ 的数字。 给出 $6$ 个数字，为每行每列以及每个对角线上的数字之和，求相应的摆放方式，无解输出 $-1$。 Par ......

这次写的也是比较快！rank305 虽然D简单，但是写出来了就算胜利！ A. Trust Nobody 题意：给出n个人，他们会说多少人是说谎的，你要找出这个人数 思路： n最多只有100个，我枚举说谎的人有i个，对说话小于等于i的做前缀和，这个几个人都是说真话，记录前缀和sum，n-sum就是说谎 ......

题意：给定一个仅包含左右括号的字符串，求其中合法的括号子串种数。 一眼看上去没思路，先从简单的问题看起。 如何判断一个括号序列是合法的？ 将左括号变成 $1$ ，右括号变成 $-1$ ，然后得到前缀和数组 $pre$。如果 $pre$ 中没有负数说明括号序列合法。 怎么求合法的括号子串个数？ 考虑枚 ......

C. Make It Permutation 我们希望尽可能少地进行操作可以使代价最小，我们如果要排列的话，那些重复的元素我们无论如何都要进行删除的，所以我们可以先把去重的代价计算出来，然后依次枚举排列的位数是多少，也就是枚举去重后的数组，其中的代价我们可以一次计算出来，当我们枚举第i个a时，前面1 ......

首先将将 $b_i$ 的定义改为 $b_i$ 在 $a$ 中出现的位置 $pos$，那么询问操作就是询问 $b_{[l_b,r_b]}$ 中有几个数的值在 $[l_a,r_a]$ 中。 因为时间有 $\texttt{6.00 S}$ 且 $n,m\le 2\times 10^5$，所以~~考虑分块~ ......

题目传送门 一道小根堆模板题。 在做这道题之前，我们先介绍一下小根堆是什么。 我们定义小根堆是一种对于任何一个父结点的权值总是小于或等于子节点权值的完全二叉树。因此，不难看出，一个小根堆的堆顶（这棵树的根节点）应该是这个堆（树）中权值最小的结点。 简单介绍完了小根堆，我们再介绍下如何存储。 存储 我 ......

思路 一道很好的复习数据结构的题。 对于第 $1$ 个问答（既第 $2$ 种操作），我用一个小根堆（优先队列，$\text{priority_queue}$）来储存第 $i$ 个盒子的卡牌。 对于第 $2$ 个问答（既第 $3$ 种操作），我用一个 $\text{set}$ 来储存编号为 $i$ 个 ......

题目传送门 一道模拟题。 先看数据范围，$x,y,z \le 10^9$ 显然会超时。不难看出，顺时针或逆时针旋转 $4$ 次和镜面对称 $2$ 次后会恢复原样，所以我们先对 $x,y,z$ 进行取余。 $$x\bmod 4,z\bmod4,y\bmod2$$ 然后我们观察一个矩阵顺时针旋转后坐标的 ......

A. Ian and Array Sorting 思路：首先我们可以从前往后做一遍，把除了最后一个元素其他所有数都变成和第一个数一样的数，然后假如前n-1个数个数为偶数，这样我们分组进行操作，一定可以把所有数变成无限小，也就是说一定会有解，也就是说n为奇数一定有解，我们考虑n为偶数的情况，n为偶数， ......

简要题意 给定两个次数为 $d$ 的多项式 $A, B$ 在 $0, 1, 2, \dots, d$ 处的点值对 $10^9+7$ 取模，保证 $B(x) \equiv A(x+s) \pmod {10^9+7}$。求 $s \bmod 10^9+7$。 数据范围：$1\le d\le 2.5\ti ......

problem 一个长为 $m$ 的数组 $a$，每个数的取值为 $[1,n]$ 的正整数；另外有一个长为 $m$ 的数组 $b$，初始全零；另外有一棵 $n$ 个点的树，求树上两点距离的函数为 $dist$。请支持三种操作： 输入 $l,r,c$，枚举 $i\in [l,r]$，使得 $b_i\g ......

地址：https://www.cnblogs.com/FReQuenter5156/p/shuxingyilaidp.html/ 简介 这类背包本质上是分组背包问题。 将一个节点的每一棵子树看作一组，进行分组背包。所谓分组背包，即在选择物品的时候，一开始将物品分为好几组，在选择时，可以从每一组中至多 ......

一、题目描述： 这是一道交互题，你需要猜出一个 $1$~$n$ 的全排列 $p_1,p_2,p_3...p_n$ 。 有 $t$ 组数据，每组数据有一个整数 $n$ 表示数组的大小。 假设一开始有一个只有 $n$ 个点，没有边的图。你有 $2\times n$次询问机会，两种询问方式： 第一种：$+ ......

CF338D GCD Table 个人评价：还好 算法 扩展CRT 题面 给了一张$n\times m$的矩阵，第i行j列的权值是gcd(i,j),现在有一个长度为k的序列A，问是否存在(i,j)使得$gcd(i,j+l-1)=a_l(1\leq l\leq k)$ 问题分析 我们将对应行设为x,对 ......

传送门 前言： 很久之前做的一道题目了，当时并没有想出来怎么做，随便猜了个结论交上去发现过了。（~~好像还是第一道自己做出来的绿~~） 简要题意： 你有一个长度为 $n$ 的序列 $a$ ，一个区间$[l, r]$的价值定义为当前区间的极差减去区间长度，求出最大的价值。 $Solution$： 看了 ......

Part I Preface 原题目(Luogu) 原题目(CodeForces) Part II Sketch 给定一个正整数 $n$，表示汽车数量。 给定一个 $n \times n$ 阶矩阵 $A$，第 $i$ 行 $j$ 列上的数字表示 $i$ 车与 $j$ 车的对撞情况。 $\begin{ ......

Part I Preface 原题目(Luogu) 原题目(CodeForces) Part II Sketch 给定一个正整数 $n$，表示汽车数量。 给定一个 $n \times n$ 阶矩阵 $A$，第 $i$ 行 $j$ 列上的数字表示 $i$ 车与 $j$ 车的对撞情况。 $\begin{ ......

妙妙题，但是感觉评不到紫。 题目链接。 题意 luogu 题意。 有 $n$ 个人，贿赂第 $i$ 个人的代价为 $a_i$。这些人中，贿赂代价为 $-1$ 的是你的朋友。现在，你可以两两配对，使得编号小的被淘汰，但是，如果你贿赂了编号大的，那么编号大的被淘汰，而编号小的留下。问：使得你朋友夺得冠军 ......

前言 题目传送门！ 更好的阅读体验？ 题解区的方法思维难度都过大（？），提供一种极其容易的方法。 思路 题目就是求 $\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}$。所以很容易想到先算 $\sum\limits_{j=y_1}^{ ......

A. Constructive Problem 题意：给定一个长度为n的非负数组a，我们可以进行一次操作，操作是将l~r这个区间内的所有数变为k（k >= 0），得到b，能不能使mex（a）+ 1 = mex（b） 思路：我是先排了个序，去了一下重，然后得到的这个数组其实只有两种情况 一种每两个数之 ......