题解1328e cf

一道简单的题目 先考虑 `0 0 ` 的情况 很显然，有两种情况： 1. $y$ 不是 $x$ 的倍数 1. $\Large \frac{y}{x}$ 无法被分解成 $b$ 的乘方 如果不满足上述两种情况，我们只需要将 $b$ 从 $1$ 遍历到 $\Large \frac{y}{x}$ ，找到解输 ......

很简单的题 可以先初始化一下，把所有单词放进一个 `map` 里，最后输入时用 `map` 映射即可。 一个坑点，注意每一个单词的两个字母不相同。 ```cpp #include #include #include #include using namespace std; map mp; void ......

有意思的题目。 还是比较好想的。 先考虑 `-1` 的情况，可以想到，如果 $t$ 的长度不为 $1$，并且 $t$ 里面还有 `a` 的话，那么这个新的 `a` 又能被下一个 $t$ 替换，无限套娃。 剩下的，还是有两种情况： 1. 如果 $t$ 只有一个字符 `a` ，那么 $s$ 无论怎么被替 ......

**题目大意：** 将给定的$n(1\le n\le10^{5})$个字符分配为$k$个字符串（不能有空串），求此操作得到的字典序最大的字符串最小的情况。 我们先将给定的字符按照字典序从小到大排序，然后逐个分配给字符串。我们要让字典序最大的字符串尽可能小，所以将第$i$个字符安排在第$i$字符串的头 ......

可能是我第一篇被通过的题解 好一道图论水题！（虽然因为没有审题交了两遍才过 这题好长啊，一句话题意： `求无向图中的完全图的最大点权和` 那就很简单了 对读入的图存为两种形式：邻接矩阵和邻接表 邻接矩阵是为了更快的判断两点之间有没有边 邻接表是为了更快的枚举每一个点所连的每一条边（虽然没有这个必要， ......

真没啥好说的，纯模拟 ```cpp #include int n,m; int q[2000][2000]; int a[2000]; int ans; int cnt; inline int read() { int x=0,f=1; char ch=getchar(); while(ch'9') ......

[原题传送门](https://www.luogu.com.cn/problem/P4956) 这道题我们想：$52$周所挣的钱都是一样的，我们可以先算出其中一周要多少钱。在**一周**中，Davor挣的钱数是： $$ \large \begin{aligned} money&=(x)+(x+k)+ ......

当然，这道题**不**是我出的题目 ~~(滑稽保命~~ [原题传送门](https://www.luogu.com.cn/problem/P1451) # 一、审题 首先，我们看看，这道题是让我们求连在一起数字大于0的部分的数量 # 二、想思路 这道题是一道搜索题（废话），我喜欢用dfs的暴搜（真香 ......

[原题传送门](https://www.luogu.com.cn/problem/P1087) 好久没写题解了QwQ 这道题我的代码感觉很像线段树(?) 我们先把这道题拆成两个部分：建树、遍历 # part.1 建树 我们可以每一次传入三个值：当前的结点和当前结点所对应的串的左右端点的下标 当然，我 ......

第一次做站外题的题解/jd [题目传送门](http://noi.openjudge.cn/ch0113/41/) 为什么要写这一篇题解呢，是因为它卡了我很久，好不容易AC了（我太蒟，大佬勿喷） 我们开始吧！ ## 一.审题 题目描述很清楚了，大家自己看吧 ## 二.代码&讲解 这里我会给大家上几个 ......

[原题](https://codeforces.com/contest/1824/problem/C) [翻译](https://www.luogu.com.cn/problem/CF1824C) 我们定义$f(l,r,x)=\sum_{j=1}^{x}{\sum_{i=l}^{\min{(j,r) ......

# [Sum](https://codeforces.com/problemset/problem/1442/D) You are given $n$ non-decreasing arrays of non-negative numbers. Vasya repeats the following ......

## 题目描述 You are given $ n $ intervals and $ m $ points on the number line. The $ i $ -th intervals covers coordinates $ [l_i,r_i] $ and the $ i $ -th ......

Let $ c $ be some positive integer. Let's call an array $ a_1, a_2, \ldots, a_n $ of positive integers $ c $ -array, if for all $ i $ condition $ 1 \l ......

## 题意 给定一个长度为 $n$ 的排列 $a$ 和 $m$ 个形如 $\left(x,y\right)$ 的操作，每次操作可以选择是否交换 $a_x, a_y$，求最终所有形成的排列的逆序对总数。 （$1 \le n,m \le 3000$）。 ## 题解 考虑转化题意，考虑求出最终总的期望逆序 ......

## 题意 给定两个正整数 $n, k$，将 $n$ 个元素排成一个序列并按 $1 \rightarrow n$ 编号，每次轮流从前 / 后开始每隔 $k$ 个未删除元素删除一个元素，求最终剩余的一个元素的编号。 ## 题解 因为 $k$ 的取值很少，考虑对于每个 $k$ 进行递推。 在已钦定 $k ......

## ARC142 A-E ### A Reverse and Minimize 憨的。 ### B Unbalanced Squares 构造。考虑一行之内大小交错，行间则单调排列。这样可以使得每个点上下大小关系抵消，左右的又保持一样，于是就合法了。 ### C Tree Queries 处在 $ ......

# A. Gift Carpet ### 题意 最近，特马和维卡庆祝了家庭日。他们的朋友 Arina 送给他们一块地毯，这块地毯可以用拉丁文小写字母的$n \cdot m$表来表示。 维卡还没看过礼物，但特马知道她喜欢什么样的地毯。如果维卡能在地毯上读出自己的名字，她一定会喜欢的。她从左到右逐列阅读 ......

首先，设$1$有$c_1$个，$0$有$c_0$个 $01$串中数字间只有四种关系，分别是$00$，$01$，$10$，$11$ 不难发现，第一种和第四种的数量是固定的，为$ \frac { c_0 \times ( c_0 - 1 ) }{2} $ 和 $ \frac {c_1 \times ( ......

## 思路 题目要求 $m \le 2\times n$，而 $a_i$ 被取出来，只需要 $a_{i-1}\le a_i$ 即可，$a_i$ 被取，只关系于 $a_{i-1}$ 的大小。 因为第一个数是必取的，所以我们可以每两个数之间加一个数，以满足除了 $b_1$ 以外的其他 $b_i$ 会被取 ......

## 思路 原题中已经告诉了我们一种快速判断的方法，我们可以用这个方法来判断。 观察一下横着摆的方式，第一列的高度为 $a_i\ge 1$ 的个数，第二列的高度为 $a_i\ge 2$ 的个数 $\cdots$。 所以我们只需要逐列判断两种方式的高度是否一样就行了。 因为题目中给定了数组 $a$ 是 ......

## 思路 容易发现如果长度为 $x$ 的序列 $a$ 中每个数都不一样，那么无论数是什么，方案数总是一样，这种情况下方案数是 $\frac{x\times (x-1)}2$。 我们再对序列 $a$ 添加一些已经存在的数，如果添加了一个 $k$，则会方案数会加 $1$，也就是多了一个 $\{k,k\ ......

## 思路 假设我们选择了第 $p_1,p_2 \cdots p_x$ 场电影，那么减去的舒畅值是 $d\times(p_1+p_2-p_1+\cdots+p_x-p_{x-1})=d\times p_x$ 所以减去的舒畅值，只与最后一场电影的天数有关。 所以我们可以枚举最后一场电影在第几天，假设在 ......

## 思路 假设总共耗时是 $s$ 秒，那么最多可以消灭的总生命值是 $s\times(w+f)$。 所以我们可以先求出所有怪物的生命值之和 $sum$，那么，至少需要时间 $t=\lfloor \frac{sum}{w+f} \rfloor$。 然后我们可以算出用这些时间最多可以用水魔法消灭的生命 ......

## 思路 发现一个进阶回文序列仅包含三个部分：$x$ 个连续的 $a$，$y$ 个连续的 $b$，$x$ 个连续的 $a$。 对于一个 $a$，我们一定会取最外面的两个 $a$，如果不取，则答案一定不小或不变，所以我们枚举到 $a$ 的时候，一定是确定了最外围的两个 $a$ 的位置。 接下来再枚举 ......

[原题](https://codeforces.com/contest/1824/problem/C) [翻译](https://www.luogu.com.cn/problem/CF1824C) 首先考虑一个朴素的 $dp$ ，我们设$dp_{i,j}$表示以$i$为根的子树全部变成$b_j$最少 ......

## 题意 给定一个长度为 $n$ 的排列 $a$ 和 $m$ 个形如 $\left(x,y\right)$ 的操作，每次操作有 $50\%$ 的概率交换 $a_x, a_y$，求最终排列的期望逆序对数。 （$1 \le n,m \le 5000$）。 ## 题解 首先转化答案 $$\text{An ......

## 1.题目大意 [题目传送门](https://www.luogu.com.cn/problem/SP34012) ## 2.思路 因为每条道路长均为 $1km$，所以我们可以在建边时就加上走这条路的初始成本，即对于每条边的两端 $a,b$ 和通行费 $w$，我们直接 $add (a,b,w+1 ......

又是一道独立（基本上是）做出的黑，好耶！注：下文为了简洁除法用 `/` 代替分数。 前置知识：伯努利数求自然数幂和。 伯努利数：$B_0=1,\sum\limits_{i=0}^n\dbinom{n+1}{i}B_i=0(n\ge1)$，于是可以 $O(n^2)$ 预处理前 $n$ 个伯努利数。 有 ......

[原题](https://codeforces.com/contest/1824/problem/B2) [翻译](https://www.luogu.com.cn/problem/CF1824B2) 首先根据~~猜结论~~数学归纳法可以想到在$k$为奇数时答案依然是$1$ 因此我们只考虑$k$是偶 ......