little 1333a artem cf

### 思路 提供一种比较容易想到的做法。 拿到题看数据范围发现都很小，所以放心大胆地暴力。 容易发现 $s_i$ 中 `AC` 的个数等于 $s_{i-2}$ 中 `AC` 的个数加 $s_{i-1}$ 中 `AC` 的个数再加上两者拼接处可能有的一个 `AC`。 所以 $s_1$ 和 $s_2$ ......

## 题面 给定一个长度为 $n$ 数列 $a$，保证每项都不为 $0$。初始时 $x=0$，然后对于 $1\le i\le n$，按顺序进行如下操作： - 如果 $x\ge k$，则 $x\rightarrow \max(k, x+a_i)$，否则 $x\rightarrow x+a_i$。 你需 ......

## 题意 有一个长为 $n$ 的杆，上面有 $m$ 条绳子，每条绳子可以让蜗牛从 $l_i$ 爬到 $r_i$（中途不能离开），保证 $r_i$ 各不相同。蜗牛也可以自然下落。 现在有 $q$ 次询问，询问 $x$ 出发，途中高度不能低于 $x$ 或高于 $y$，问最高能爬到的位置。 $n,m,q ......

## 题意 给定 $n$ 个长度为 $m$ 的数组，每个数组可以向别的数组转移**最多**一个数字，任意一个数组都可以接受无穷多的数字，最大化每个数组的最小值之和。 ## 做法 考虑贪心。 我们记第 $i$ 个数组的第 $j$ 个数字为 $a_{i, j}$。 我们先对每一个数组按照**升序**进行 ......

## 思路 我们实际上发现它计算的就是 $p_i \cdot i$ 的和再减去一个 $p_i \cdot i$ 中的最大值。 那我们可以枚举这个最大值 $p_x \cdot x$，这个值就是最后和中需要删除的数值。 这里我们可以使用贪心。 我们可以从 $n \sim 1$ 枚举除 $p_i$ 的每个 ......

## 题意 给定一个数组 $a$，然后将 $a$ 分到数组 $b$ 和 $c$ 中，使得 $c$ 和 $b$ 都不为空且 $c$ 中的任何一个数字都不是 $b$ 中任何一个数字的因数。 ## 思路 我们知道，在正整数中，一个数字 $x$ 只要大于数字 $y$，那么 $x$ 一定不是 $y$ 的因数， ......

一道值得思考的数学题。 计算可知，做一块披萨的时间是 2.5 分钟，这在 3 个购买方案中一致。故此只需考虑怎样用 6，8，10 这 3 个数字**组合出大于等于 $n$ 且最小的数**。 可以证明，**这 3 个数可以组合成不小于 6 的所有偶数**。证明如下： - 对于不小于 6 的任意偶数 $ ......

过了abc，卡在了d ## A 将数组a拆分乘数组b和c，使得满足任意c[i]不是b[j]的因子，b和c中至少存在一个数。 如果不能输出-1 **法一：** 巧妙构造： 因为一个大的数不可能是一个小的数的因子，所以我把最大的数(最大的数数量可能有很多个，需要全都放在c里面，因为两个相等的数之间也互为 ......

## A [题面](https://www.luogu.com.cn/problem/CF1849A) 分类讨论 $b+c$ 和 $a$ 的大小即可。 点击查看代码 ``` #include #define ull unsigned long long #define ll long long #d ......

赛时没做出来一直在往随机想。 题意挺明确。发现到 $n \times n$ 这个条件，联想到做过的 CF1172D，递归去掉一行一列的基本想法就有了。 那么让两个棋子从右下开始，走完多出的一行一列，然后走进剩余的 $(n-1) \times (n-1)$。 真可以？这就是 `*2400` 的构造？这 ......

而且怎么感觉 E,F 比 D 要简单很多，大概是因为比较套路吧[惊恐] ## A.Coins ### 题目描述： **本题一共有 $t$ 组数据。** 每组数据包含两个整数 $n$ 和 $k$，如果存在两个非负整数 $x,y$，满足 $2\times x+k\times y=n$，输出 `YES`， ......

## CF992E 题解 [传送门](https://www.luogu.com.cn/problem/CF992E) [更好的阅读体验](https://www.cnblogs.com/Xttttr/p/17627033.html) 简化题意：单点修改，设序列的前缀和序列是 $s_i$，查询是否存 ......

# CF1422F Boring Queries ## 题意 询问区间 $lcm$，强制在线。 ## 题解 首先考虑每个质因子对于答案的贡献。 对于一个质因子 $p_i$ 来说其对于区间 $[l,r]$ 的贡献是其最高次幂。 首先考虑离线做法，扫描线，线段树维护答案。 将当前加入的数 $a_i$ 分 ......

[洛谷链接](https://www.luogu.com.cn/problem/CF452C)&[CF 链接](http://codeforces.com/problemset/problem/452/C) ## 题目简述 有 $m \times n$ 张牌，有 $n$ 个种类，每个种类有 $m$ ......

## 做完这道题大大提升了我对主席树的认知。 · 传送门:[here](https://www.luogu.com.cn/problem/CF1422F) 给定一个长度为 $n$ 的序列 $a$ 以及 $q$ 次询问 。 每次询问包含 $2$ 个整数 $l,r$ ，你需要求出区间 $[l,r]$ 的 ......

[题目链接](https://www.luogu.com.cn/problem/CF1076D) 既然题目让我们求保留 $k$ 条边的最大好点数量，那我们首先思考这样的问题：什么情况下删一条边必定会删一个点。 显然，只有树才会出现这样的情况，而在一个连通图还没有删成树之前，删边对于点的数量是没有影响 ......

## Problem [原题链接](https://www.luogu.com.cn/problem/CF650A) ## Meaning 求曼哈顿距离和欧氏距离相等的坐标组数量。 ## Solution 这道题用枚举复杂度较高，我们考虑探究当两点的曼哈顿距离与欧氏距离相等时，它们横纵坐标的关系。 ......

[题面传送门](https://www.luogu.com.cn/problem/CF643F) 感觉这个从信息的角度去考虑比较高妙。 首先取 $p=\min(p,n-1)$。 我们来考虑每个桶对应喝的熊，这样会有一个长度为 $n$ 的数组，假设有 $t$ 天，那么每个位置会写一个 $[1,t+1] ......

（[题目传送门](https://www.luogu.com.cn/problem/CF1082G)） 一道最大权闭合子图的模板题 把所有点当作负权点，所有边当作正权点。 考虑一条边 $e=(x,y,z)$ 能选择的条件，当 $x,y$ 均被选择时就可以选，那对应到最大权闭合子图的模型中，就可以将 ......

# CF1848 ## C 看到形如对 $a,b$ 进行任意操作，将 $a,b$ 替换成 $a,b$ 的线性组合，进行到 $0$，显然需要考虑 $\gcd$ ~~但我没考虑~~ $\gcd$ 不变，考虑同时除以 $\gcd$，最后情况必然是 $(0,d)\rightarrow(d,d)\righta ......

自己做出来了 A-E，F 算是搞懂 GF 后第一道符合我这个菜鸡水平的实战，可惜的是根本没意识到可以 GF。 ## A.Matching ### 题目描述： 整数模板是**每位均为数字或问号**的字符串。 如果可以用数字**替换**模板中的每个问号，从而获得该**正整数（严格大于 $0$）** 的十 ......

### [原题传送门](https://www.luogu.com.cn/problem/CF833B) 题意：将一个长度为 $n$ 的序列划分成连续的 $k$ 段，每一段的价值为段内不同的数字的数量，求最大价值。$(n\leq35000,k\leq50)$ 划分问题，可以考虑 $dp$ 。设 $d ......

半个月前做的题，这段时间一直在颓所以没写题解，今天突然想起来才准备补上。 考虑枚举最大值 $n$ 的位置 $i$，那么排列就被分成 $2$ 个段 $[1,i-1]$ 和 $[i+1,n]$，而且 $\forall k\in [i+1,n]$，$k$ 不可能是前缀最大值；$\forall k\in [ ......

## A.New Palindrome ### 题目描述： 给你一个由小写字母组成的回文字符串，问你是否能在重排其之后构造出另一个与原串不同的回文字符串。 多测，$t \le 1000,2 \le |s| \le 50$ ### 题目分析： 考虑其实就是前 $\lfloor \frac{n}{2} ......

#### [[CF1848F] Vika and Wiki](https://www.luogu.com.cn/problem/CF1848F) shaber 题没想出来，紫砂了。 这种题的经典方法是考虑贡献，注意到顺着想贡献不容易我们倒过来想，设 $f_{i,j}$ 表示 $i$ 轮后 $j$ 的 ......

首先，考虑把数列递推写作矩阵乘法的形式。 $$\begin{pmatrix} 0&1\\ s_n&s_{n+1} \end{pmatrix}\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}=\begin{pmatrix} F_{n+2}\\ F_{n+1} ......

## Problem 给出一个 $n \times m$ 的矩阵，有一些点不能选。 现在按顺序给出 $k$ 次操作，每次都让一个点变成不可选（每次操作都有后效性，将一个点变为不可选后就会一直不可选），每次都问当前可选的最大**正方形**。 ## Input 一行三个整数 $n,m,k$，表示矩阵大小 ......

WA 了十几发，清醒了之后发现自己是个 sb。 首先肯定贪心选，让每条链尽量长即可。 最后直接跑个欧拉回路即可（两个点的欧拉回路(ˉ▽ˉ；)...）。 分析一下，发现两个点的度数一定满足要求，无非就是是否联通。 那么如果两个点之间没有连边并且两个点都有自环，那么就会不连通。 只需要考虑这种特殊情况就 ......

一个非常显然的事情是：总方案数即为每条边方案数之积。 树边已经确定，考察每条非树边 $(u,v)$ 可以怎么取。给定的树 $T$ 是唯一最小生成树，这意味着非树边 $(u,v)$ 要么不存在，要么权值大于 $T$ 上 $(u,v)$ 之间任意一条边的权值。设 $T$ 上 $(u,v)$ 间的最大边权 ......

[题面](https://codeforces.com/problemset/problem/1857/B) ## 题目大意 给定 $T$ 组数据，每组数据一个自然数 $n$，可以多次选择第 $k$ 位数进行四舍五入，求出四舍五入后该数的最大值。 ## 分析思路 思想：**贪心**。 这里给定了两种 ......