题解p9669 jinan order

原题链接 解题思路 这是一道经典的动态规划题目。 如果尝试使用深度优先搜索（dfs）或广度优先搜索（bfs）做就会获得 TLE （注意数据范围）。于是我们想到了更为高级的动态规划（Dynamic Programming, dp）。 简略介绍动态规划算法的核心思想：把原问题分解为相对简单的子问题的方式 ......

[原题](https://www.luogu.com.cn/problem/P9570) [更好的阅读体验](https://www.luogu.com.cn/blog/356277/p9570-glaciaxion-ti-xie) 直接遍历字符串，如果当前字符为 `N` ,就判断编号 $1 \si ......

[原题](https://www.luogu.com.cn/problem/P1371) 题目要求的很简单，就是问一个任意加了 $ N,O,I $ 三个字母中的任意一个打的字符串里面能组成几个 $ NOI $ 。 先考虑不加字母的情况，直接枚举每一个 $ O $ 的前后 $ N $ 和 $ I $ ......

题目给出两个数列 $a$,$b$，均按不降序排序，要求 $a$ 数列中的数在 $b$ 数列中出现多少次。 刚开始是想用一个数组来记录 $b$ 数列中的数出现的次数，然后再枚举 $a$ 数列中的每个数是否在 $b$ 数列中出现来累计答案，但是后面看到 $ 1 \leq n, m \leq 10^7 $ ......

~~蒟蒻第一次发题解qwq~~ $$ S=a_1 \times a_2+a_1 \times a_3+a1 \times a_n+a_2 \times a_3+···+a_n-2 \times a_n-1+a_n-1 \times a_n $$ 从样例来看 4 1 3 6 9 这道题就是要求 $$ ......

模拟退火的题解。 题目的难点在于如何计算点到所有线段的距离。 我们可以通过求线段的直线解析式，然后计算与其垂直的直线的斜率，将随机出来的点带入求得直线解析式，然后求两直线交点，判断是否在线段上进行分讨即可，但是我可能写挂了，所以改成用的向量。 ![](https://cdn.luogu.com.cn ......

看到这题，自然的想到 DP 啦！ 如果设 $f_{i,j}$ 为到第 $i$ 个位置前面的都合法且最后一段和为 $j$ 是否可行，那么转移十分显然，但是状态会炸。 此时我们考虑在状态上进行优化来减少时间，把 $f_i$ 设为到第 $i$ 个位置分段数量最多的情况下且最后一段和最少的和，以及能分成几段 ......

题意很清晰，直接跑 SPFA 求最短路。 只是我们在松弛操作时，需要注意从 $u$ 是否可以到达 $v$。 怎么判断呢？ 请移步下面三个部分。 ## Part 1 先解释一下，下面点 $i$ 的信息分别为以下变量： + `color` 表示颜色， `1` 表示蓝色，`0` 表示紫色 + `num` ......

## Div2 A 容易发现最后要存活下来一定要每次和 $1$ 号做出相同的选择，直接数就好了. ## Div2 B 容易发现当 $n$ 为奇数的时候无解。 考虑 $n$ 为偶数的情况怎么构造，有一种方案是在 $a_i=i$ 的基础上调整，交换一下 $a_{2i-1}$ 和 $a_{2i}$，证明考 ......

## 思路 题目给我们一个数组 $a$，那么我们可以算出其异或前缀和 $sum$。 我们知道，算出 $[l, r]$ 的异或和可以这样计算：$sum_r \oplus sum_{l - 1}$。 那么问题就转换为了 $sum_{0\sim n}$ 这 $n + 1$ 个数字两两异或之和（当然 $su ......

```cpp #include using namespace std; using pii = pair; constexpr int N = 3e5 + 5, S = 2e3 + 5, K = 1e2 + 5, INF = 0x3f3f3f3f; int n, m, T, poi[N]; int ......

## 思路 如果 $k$ 和每个订单都是固定的，那所有的生产和剩余的货物都是固定的，那直接模拟就好。 可以提前对订单按照天数排序，对于排序后第 $i$ 个订单，可以提前累加前面所有订单所需的货物，再与天数乘以 $k$ 判断能否完成。 ## AC 代码 ```cpp #include using na ......

## 题面 给定 $x, y$，求 $$\sum\limits_{a = 1}^{x} \sum\limits_{b = 1}^{y} \left[\left\lfloor\dfrac{a}{b}\right\rfloor = a \bmod b\right]$$ （$1 \le x, y \le ......

### [P3089](https://www.luogu.com.cn/problem/P3089) 令 $f_1[i][j]$ 表示向右跳，从 $j$ 跳到 $i$ 的最大总得分，有状态转移方程： $$ f_1[i][j]=\displaystyle\max_{k1&&x[j]-x[k-1] u ......

[link](https://www.luogu.com.cn/problem/P3165)。 #### 题意 对序列进行 $n$ 次 reverse 操作，第 $i$ 次操作的左端点为 $i$，问如果最终要使序列有序，每次操作选择的右端点是什么。 #### 解法 由于每次左端点为 $i$，很容易想 ......

### 题目颜色为洛谷难度 # [$\color{#F39C11}{A}$](https://vjudge.csgrandeur.cn/contest/576896#problem/A) [洛谷上](https://www.luogu.com.cn/problem/P2952) ## 思路 容易发现 ......

### 题目颜色大致对标洛谷难度 # [$\color{#F39C11}{A}$](https://vjudge.csgrandeur.cn/contest/576896#problem/A) ## 思路 容易发现这是一道双端队列的模板题，所以直接模拟就好。 我使用的是手工队列（忘了 STL 的双端 ......

[link](https://www.luogu.com.cn/problem/P2572)。 对平衡树的懒标记的应用题，其实和线段树也差不多。 如果不考虑取反操作，那维护操作 $5$ 就需要知道当前区间答案，当前区间前缀和后缀，因为在 push_up 时我们当前区间的答案肯定等于左区间的答案，右区 ......

A 最后一次插入的数的值与位置一定相同 考虑倒着做 每次从左往右扫一遍 当遇到 a[i]==i 时将此数删除并跳出 B 当 n 为 5 时 构造出的图如下 （图形编辑器 (csacademy.com)） 那么我们猜想当 n 为奇数时将 n 与其他点连边 i 与除了 n-i 的其他点连边 证明： n ......

# P2757 [国家集训队\] 等差子序列 题解 首先简化题目之后，发现如果序列之中存在一个长度 $\ge 3$ 的子序列，一定存在一个子序列的子序列长度为 $3$，所以只需要统计有没有长度为 $3$ 的子序列即可。 对于这种长度为 $3$ 的统计问题，第一想法就是从中间的那个点入手，由于排列的性 ......

[题目链接](https://www.luogu.com.cn/problem/AT_xmascon19_h) 经典一个系列四道题，其他三道都是 trash。给定一个有一些位置初始被染色的矩阵，每次可以选择一行将一个公差为**奇素数**的等差序列位置染色，求最少操作多少次使得整个矩阵被染上色。 首先 ......

## 题意 给定 $l, r$，求 $$\prod\limits_{i = l}^{r} \prod\limits_{j = l}^{r} \operatorname{lcm}\left(i, j\right)^{\operatorname{lcm}\left(i, j\right)} \bmod ......

[传送门](https://luogu.com.cn/problem/p7911) 早期题解，转自博客 QwQ 本蒟蒻为数不多过了的黄题，祝贺！！！  # 题面 # [CSP-J 2021 ......

## 前言 *~~附加任务~~* 这道题也是一个简单模拟题。 [传送门](https://luogu.com.cn/problem/p1540) ## 解析 这道题就是一个简单的模拟题，简单来说就是如果内存里面没有这个单词（其实是一个数）的话就从外存入队，如果内存容量不够，出队即可。 对了，每次查询 ......

## 「JLOI2014」松鼠的新家 ### 前言 这道题倒也不是很难，只是有一些小坑需要避一下，可以看作半个 LCA 树上差分裸题。 ### 解析 考虑维护一个树，点 $u$ 表示每个房间需要的糖果数 $s_u$，而维尼在参观房间时从 $a$ 到 $b$ 就需要在 $(a,\to b)$ 的路径上 ......

转自博客。 [传送门](https://luogu.com.cn/problem/p5661) 一道`橙题`，但是会T。 # 题面 # [CSP-J2019] 公交换乘 ## 题目描述 著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案： 1. 在搭乘一次地铁后 ......

# 前言 转自博客，早期黑历史作品。 这是本蒟蒻の第一篇题解qwq,发在博客上,还请多多关照. 这道题是一道橙题,难度没有太大的问题,对于大犇们来说自然是一遍过的,本蒟就只能调调再交了. # 题面 [传送门](https://www.luogu.com.cn/problem/P1055) ## 题目 ......

### 题解 [传送门](https://luogu.com.cn/problem/at_abc176_d) #### 题目大意 给出一个序列 $A$ ，求 $A_l \oplus A_{l+1} \oplus \dots \oplus A_r = A_l + A_{l + 1} +\dots+ A ......

## 前言 [传送门](https://www.luogu.com.cn/problem/P1042) 远古TJ!!! *~~这道题题解是老师喊我写的！！！~~* ## 题面 ### 题目背景 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 $11$ 分 ......

# P3168 [CQOI2015\] 任务查询系统 题解 因为题目给定的是若干区间，所以考虑差分一下，把区间左端点挂上一个标记，表示到这里的时候多了一个任务，把区间右端点加一挂上一个标记，表示到这里的时候任务消除了。 接着看到第 $k$ 大，考虑主席树，可以用一排在序列上的主席树维护优先级的前缀和 ......