题解1071 cf

## 题面翻译 二元组$ (a,b)$,可以变成$ (a,b+1)$或$ (ab,b)$ 你有初始二元组$ (1,0)$,给你区间$ [l,r]$,和一个整数$ p$,在区间内选一个数$ x$,使$ (1,0)$在不超过$ p$步变化后,第一维的值变成$ x$,求$ x$的个数$ (2 #defin ......

CF1239E Turtle 通过观察我们会发现，第一行一定单调递增，第二行一定单调递减，否则不是最优。再次前提下，乌龟的最优方案只有两种，要么一直向右，最后向下，要么先向下，再一直向右。因此，我们将最小的两个数字放在左上角和右下角，然后把余下数字填入剩余位置，并希望下式最小 显然，这是一个背包问题 ......

不妨设 $a$ 单调递增（无重复），显然如果 $n\le 3$ 答案就是 $0$。 显然答案 $k$ 具有可二分性。也就是说，当 $k #define rep(x,y,z) for(ll x=(y);x=(z);x--) #define debug(format...) fprintf(stderr ......

寄！大！了！ Rating -= 124.  （恼） https://codeforces.com/conte ......

一、题目描述： 给你一个长度为 $n$ 的序列 $a$ , 你需要回答 $q$ 次询问。 $求区间\ l\ 到\ r\ 的第\ k\ 小值$ 数据范围：$1 \le n,q \le 5 \times 10^5 ,所有数\ -10^9 \le val \le 10^9$ 二、解题思路： 首先数据离散化 ......

[01Sequence](https://www.luogu.com.cn/problem/AT_abc216_g) ### 题目大意 构造一个满足 $m$ 个形如 $(l,r,x)$ 的限制条件的 $01$ 序列，其中 $(l,r,x)$ 表示区间 $[l,r]$ 的和不小于 $x$，你需要保证序 ......

[Blocked Roads](https://www.luogu.com.cn/problem/AT_abc218_f) ### 题目大意 给定一张 $n$ 个点，$m$ 条边的无向图，每条边的边权均为 $1$。对于每一个 $i\in [1,m]$ 求出从点 $1$ 到 $n$ 的不经过第 $i$ ......

### 1 题目大意 **1.1 题目翻译：** 给定一个值域为 $[1,n]$ 的函数 $f(x)$，让你求出最小的 $k$，其中 $k$ 满足 $f^{(2k)}(x) = f^{(k)}(x)$。 其实我觉得这题你谷翻译十分到位，建议没读懂题的还是去看你谷翻译罢。 **1.2 数据范围：** ......

[题目链接](https://www.luogu.com.cn/problem/AT_dp_o) 来点位运算优化，目前也是拿下了洛谷最优解，比第二名快一倍： ```cpp #include #define int long long #define btp(x) __builtin_popcount ......

[题面](https://www.luogu.com.cn/problem/CF388D) 题意： >给定非负整数 $n$，定义一个自然数集合 $S$ 是好的，当且仅当 $\forall x\in S,x\le n$ 且 $\forall x,y\in S,x\oplus y\in S$，其中 $\ ......

两道题似乎都涉及了一个经典模型： > 在一张有向图上，给定起点 $s$ 和终点 $t$，询问 $s$ 到 $t$ 与 $t$ 到 $s$ 是否均存在一条长度 $=L$ 的路径（$L$ 是一个 $\ge n^3$ 的数）。 首先 $s$ 与 $t$ 必须在同一个 SCC 内（考场上没看到互相可达直接以 ......

感觉不难啊，为什么是 *2800 捏。 先离散化。对每个横坐标开一个 set 存点，插入删除就能做了。查询的时候线段树二分就行了。 更具体地，我们维护区间内纵坐标的最大值，在二分的时候能左就左，不能左就右。 注意这里的右上角是严格大于。 点击查看代码 ``` #include #define int ......

感觉不难啊，为什么是 *2900 捏。 发现这个玩意的本质是最初在 r，每次不动或向左移动一步，进行 l 次操作，求每次停留的格子权值之和的最小值。显然我们只会停留在至多一个格子上，假设停留在 $i$，那么权值之和就是 $\left(l-r+i\right)a_i+\sum\limits_{j=i+ ......

# 题目大意 给出一个长为$2^{K+1}$的序列，每个元素在$[0,4^K)$之间， 在**序列中**找到两个不相交的区间使得二者的异或和相等 $Krk150 因为元素大小是$4^K$级别的，和大小相关的算法（FWT）都没用了，~~所以不如直接随机~~ 发现长度为$2^{K+1}$的序列里有$2^ ......

## 写在前面 感觉题目是一坨。 A愣了一会，BC同开然后半天读不懂题。写出来发现毛算法都没有，div1那边更是大寄。DEF三题过题数个位数根本看都看不来。总结为很烂的一场。 ## [A](https://codeforces.com/contest/1836/problem/A). Destroy ......

参考splay佬的题解写个记录[https://zhuanlan.zhihu.com/p/602721281](原题解链接) 题意：给定两个字符串a, b，可以选择α里面的字符进行替换，但是替换的字符种类最多为k个。其中字符串α字符出现的种类不超过10种。求将替换后，两个字符的相同部分的数量。(相同 ......

CF888F Connecting Vertices 题号很吉利我们把这个正多边形展开成一条线段，转化成经典区间DP问题。毕竟n3的算法也不是很多 然后，对于题目中要求两条连线不能相交，相当于线段上的两个区间要么相离，要么相切，要么包含。对于不能连的两个点，在DP的时候特判一下就行。 #includ ......

CF598E Chocolate Bar 一道简单的DP，虽然用搜索写的。我们用f(i,j,z)表示把X×Y的巧克力分成总大小为Z的小块所需最小代价。每次掰开的方式有两种，横着掰和竖着掰，故有两种转移。 #include<bits/stdc++.h> using namespace std; int ......

# 【题解】[ABC306G] Return to 1 ## 题目链接 [ABC306G - Return to 1](https://atcoder.jp/contests/abc306/tasks/abc306_g) ## 题意概述 本题多测，$T$ 组数据。 对于每组数据，给定一个 $n$ 个 ......

## [A](https://atcoder.jp/contests/abc306/tasks/abc306_a) - Echo ### 题目大意 给定一个字符串，需要把它每个字符重复输出。 ### 解题思路 可以读完整个字符串，也可以按照字符读一个输出两个。 ### AC Code ```cpp ......

[题目链接](https://www.luogu.com.cn/problem/AT_abc168_f) 挺套路的题。如果值域和线段数量同阶，可以预处理不能越过的线段，使用状压四个方向记录每个节点能不能往这个方向走，然后直接爆搜就好了，标记上能走到哪些地方。但这个值域一看就是没有救的，于是就要拿出来 ......

一步都没想到，一定是状态不好吧，一定吧一定吧？ 加训数数！ ## 题意 给定 $n, x, y$，定义好的序列 $\{a_i\}_{i = 1}^n$ 满足 $\sum\limits_{i = 1}^na_i = x, \operatorname{OR}\limits_{i = 1}^na_i = ......

## RC-u4 变牛的最快方法 ### 思路 最短编辑距离+记录路径板子题，不懂最短编辑距离的可以看看网上的博客。不懂为什么官方题解用的bfs写法，然后网上所有的题解就是bfs了。我这里就是双重for循环实现，参考下写法即可。 ### 代码 点击查看代码 ``` #include #define ......

**题目描述** [题目传送门](https://codeforces.com/problemset/problem/1840/C) $T$ 组数据，每组数据给定 $n$，$k$，$q$ 和一个长度为 $n$ 的数组 $a$，求 $a$ 中长度大于等于 $k$ 且最大值小于等于 $q$ 的序列个数。 ......

[Problem](https://www.luogu.com.cn/problem/CF1059B) ### Solution 搜索染色类。 我们发现染色是不可逆的，也就是染成了#后不得染回“.”,所以对于每次染色我们都要尽可能向std上靠拢。 我们可以观察一下std，发现需要尽可能从std上的“ ......

##### JOI 2020 Just Long Neckties 首先一定是贪心将两个从小到大排。然后考虑维护 $a_i-b_i$ 的前缀 max 与 $a_{i+1}-b_i$ 的后缀 max 即可。 https://qoj.ac/submission/113106 ##### JOI 2020 ......

## 题目描述： 策策同学特别喜欢逛公园。公园可以看成一张 $N$ 个点 $M$ 条边构成的有向图，且没有 自环和重边。其中 $1$ 号点是公园的入口，$N$ 号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从 $1$ 号点进去，从 $N$ 号 ......

已经 18 号了捏。 ### [Educational Codeforces Round 150 (Rated for Div. 2)](https://codeforces.com/contest/1841) #### [E. Fill the Matrix](https://codeforces ......

## F.More Holidays ### 题目描述： 给你一个由 `o` 和 `x` 组成的长度为 $N$ 的字符串 $S$，以及整数 $M$ 和 $K$。保证 $S$ 至少包含一个 `x`。 假设 $T$ 是由 $S$ 复制 $M$ 次而成的长度为 $NM$ 的字符串。考虑将 $T$ 中的 $ ......

非常纯正的换根DP，都写在注释里了 题目链接：https://codeforces.com/contest/1796/problem/E 代码链接：https://codeforces.com/contest/1796/submission/209931430 ``` /* 题意：将一棵树划分成若干 ......