题解codeforces round 879

题目链接：https://codeforces.com/problemset/problem/1852/C 题意： 给定一个长度为n的序列和正整数k； 每次可以选取任意一个区间，将区间内每个数减1； 如果出现一个数变成0，那么那个数变成k； 问至少操作多少次可以使得每个数变成k； 分析： 将每个数值 ......

题目链接：https://codeforces.com/contest/1845/problem/E 题意： 给定长度为n且只含0和1的数组，你可以进行以下操作： 交换相邻的0和1； 给正整数k，问经过k次操作后，会有多少种本质不同的结果； 分析： 如果1比0多，我们可以把他们取反（让0比1多，结果 ......

# P5629 【AFOI-19】区间与除法 题解 由于题目中的运算是除法，所以对于一个数字 $x$，最多运算次数不会超过 $\lceil\log_{d}x\rceil$ 就会变成 $0$。 然后我们就可以在 $O(n\log C)$ 的时间复杂度内算出来每一个数字能被哪些原数消灭。 这样处理询问仍 ......

前言 最近学了一种新的数位dp的状态表示，打算应用到以前做过的数位dp的题目。如果我们对数$N$进行数位dp，以前的状态定义$f(i,j)$表示所有数位大小为$i$且最高位是数字$j$的数的个数，如果还有其他约束条件那么再补充相应的状态即可。而新的状态定义则是$f(i,1)$和$f(i,0)$，其中 ......

[销售基因链](https://www.luogu.com.cn/problem/P9196) ### 题目大意 给定 $n$ 个字符串，长度总和为 $m$，进行 $q$ 次询问，每次询问给定两个字符串 $p,s$，问所有的字符串中以 $p$ 为前缀且以 $s$ 为后缀的有多少个。 ### 思路分析 ......

https://ac.nowcoder.com/acm/contest/63869#question ### C https://ac.nowcoder.com/acm/contest/63869/C #### 题意 小美定义一个 01 串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操 ......

今天只有3题，有点遗憾，D题几乎一眼切，但是时间不够，分类讨论没写完，vp结束几分钟后写出来。 A题开始还以为要并查集，后面发现只有一个N不行 B题漏写括号WA一发 C题感觉不好写啊，因为直接计算可能会爆，所以要先从后往前，确定边界，然后就是跟普通的填数差不多，二分一下。 又是找串，还得特别小心会不 ......

# [P2486 [SDOI2011] 染色](https://www.luogu.com.cn/problem/P2486) 神仙树剖题。 ## 题意 给你一棵树，每个点都有颜色，支持下面两种操作： * 路径染色。 * 路径颜色段数量查询。 ## 树剖部分 我们看到树上问题，不好处理，所以想办法给 ......

### 分析： 贪心算法。 有 $n$ 个客人。对于每一位客人，我们都要遍历一遍所有房间，找出最优入住房间编号。 设当前遍历的房间编号为 $j$。 分三种情况： 1. 左右两边的房间皆空，则为最优房间。 2. 左右两边只有一个房间有客人，则愤怒值加 $2$（因为有两个客人所以加 $2$）。 3. 左 ......

让人头大的数位DP。建议评蓝。个人认为不适合放ABC的F。 将三个数二进制拆分，使三个数异或为0相当于每个二进制位三个数中有0或2个是1。 所以考虑数位DP，设 $dp[i][m1][m2][m3][lim1][lim2][lim3]$ 为第 $i$ 位，三个数模 $a$ , $b$ , $c$ 分 ......

题目链接：https://codeforces.com/problemset/problem/1854/C 大致题意： 有一个集合S，和一个上界m； 现在每秒钟可以进行一次如下操作： 1：等概率的选取S中的一个元素x； 2：将x从S中移走； 3：如果x+1不大于m并且x+1不在S中，那么添加x+1在 ......

题目链接：https://codeforces.com/problemset/problem/1848/F 大致题意： 长度为n（n是2的幂次），每轮让a【i】 = a【i】^a【i%n + 1】，（^为异或）问需要操作多少次后可以使得每个数为0； 解题思路： 我们来观察： 第一次相当于：a【i】 ......

题目链接：https://codeforces.com/problemset/problem/1854/B 题目大致题意： 有n张卡牌从上到下堆叠，每张卡片有锁或不锁俩种状态，一开始第一张是不锁的； 对最上面的卡牌，如果他是不锁的状态，那么可以进行俩种操作： 1：从上到下，将v张被锁的卡牌解锁； 2 ......

题目链接：https://codeforces.com/contest/1856/problem/D 大致题意： 这是一道交互题，有1~n的排列p，对于每次询问，你可以花费（R-L）2的代价去得到区间【L，R】之内的逆序对的个数， 你需要在5n2的代价内得到n的位置。 初步思路： 首先我们来思路，在 ......

题目链接：https://codeforces.com/problemset/problem/1849/E 大致题意： 长度为n的序列，求有多少个区间满足区间最大值在区间最小值的右边？ 解题思路： （此题有使用线段树等其他做法，本处使用的是单调栈做法） 我们先求出每个a【i】 的左边的比他小的LMI ......

[题目链接](https://www.luogu.com.cn/problem/P9580) 挺好的博弈论题，这是一个跟官方题解不太一样的做法。 遇到这种组合游戏可以先考虑逆推胜负，把握一下规律，我们先从一个区间的胜负判断开始入手。 考察区间中最后一个数字的从属关系，如果它属于弈，因为 $a_i>0 ......

## 思路 考虑区间 DP。 设 $f_{i, j}$ 表示要刷到 $[i, j]$ 这一段的目标需要的最小次数。 对于 $f_{i, j}$， 如果 $color_i$ 与 $color_j$ 相等，那么再子区间合并的时候就可以少刷一次，即 $f_{i, j} = \min\limits_{k = ......

**A**. $n$ 个长为 $m$ 的字符串，判断存在 $i, j, k, l$ 有 $1 \leq i view ``` #include #define REP(i, A, N) for (int i = (int)A; i = (int)A; --i) typedef long long l ......

## 题意 题目给定了一个长度为$n$序列$a$与$m$个操作，操作一共有3种： 1.给定$x,y$，使$a_x$增加$y$。 2.给定$x$，使$a$中所有数全部乘上$x$。 3.给出k个数$c_1,c_2,...,c_k$，表示这个操作的任务是按照先后顺序执行编号为$c_1,c_2,...,c_ ......

## 思路 设 $f_{i, j, k}$ 表示从原点走到 $(i, j)$ 模 $m$ 后的乘积为 $k$ 的方案数。 状态转移：$f_{i, j, ka_{i, j} \bmod m} = f_{i - 1, j, k} + f_{i, j - 1, k}$ 统计答案：$f_{n, n, k}$ ......

## 思路 我们发现两种操作都不会影响字符之和。 考虑动态规划， 设 $f_{i, j}$ 表示在前 $i$ 位，可以达到和为 $j$ 的方案数。 有 $f_{i, j} = \sum\limits_{k = 0}^{25}f_{i - 1, j - k}$。 最后记得 $-1$，表示去除原始字符串 ......

## 思路 假设 $a_i$ 和 $b_i$ 的最大值是 $maxn$。 可以发现序列 $1,2,3 \cdots maxn$ 一定是要构造的序列的子序列。 那么，这种情况下，一定满足了所有的 $a_ib_i$ 就可以了。 对于所有的 $a_i>b_i$，我们有两种选择，到了 $a_i$ 后，序列往 ......

# AT_agc030_d [AGC030D] Inversion Sum 题解 ## 题目大意 给你一个长度为 $n$ 的数列，然后给你 $q$ 次交换操作，你每次可以选择操作或者不操作，问所有情况下逆序对的总和。（$n, q \le 3000$） ## 分析 很容易想到 $dp$，但是发现不好直 ......

取自我的洛谷博客：https://www.luogu.com.cn/blog/SunnyYuan/solution-at-abc317-g 借鉴了官方题解思路。 ## 思路 首先我们要建立一个二分图。 对于输入的 $a_{i, j}$，我们可以连接 左侧的 $i$ 和 右侧的 $a_{i, j}$。 ......

# 「TAOI-2」Ciallo～(∠・ω 考场上以防万一，我用的双哈希……但好像有点多余。 ```cpp #include #include #include #include using namespace std; const int N = 4e5 + 7, BASE = 131, mod ......

简单题，先二分出直线上 $x$ 最小的点使得这个点在矩形内。 然后不断跳，直到遇到整点。（实际上要用扩欧，但初测能过于是就偷个懒没写） 接着不断跳直到不符合条件。 先 $\sqrt{V}$ 个跳一下，跳完后再一个一个跳就不用写二分了多好。 代码： #include<iostream> #define ......

[原题](https://www.luogu.com.cn/problem/UVA908) ## 1.题意分析 题意就是给你很多组数，对于每组数，有三组小数据。第一组小数据先输入一个n表示顶点数，然后再输入n-1条边表示初始边数。其它组小数据先输入一个数k，表示增加的边的数量，然后再输入k条边，表示 ......

## 思路 我们需要尽量让相邻两个数的和的最大值减最小值最小。 先思考如何让最大值最小。 对于 $n$，两侧最小也必须要放 $1$ 和 $2$。所以最大值至少也是 $n+2$。 同时，我们再思考 $1$ 周围能摆什么，因为不能让最小值太小，我们需要放比较大的，也就是 $n$ 和 $n-1$。 这样来 ......

## 思路 ### Step1.暴力 考虑到数据范围很小，所以可以暴力模拟操作，赛时直接去想更优的情况，倒是没去想模拟，所以这里就不展开了。 ### Step2.有点思维难度的做法 首先发现在过程中，只有乘以 $2$ 和除以 $2$ 的操作，所以向上取整的情况只会出现在细胞数量为 $1$ 的情况。 ......

[题目链接](https://www.luogu.com.cn/problem/P9584) 你说得对，但是不如换根。换根是由原先的树形 DP 简单变换而来，故事发生在这道叫做《城市》的题目中，在这里你妄图求解每个点到树中其它所有节点的距离，即 $f_i = \sum_{j = 1}^n dis_{ ......