Luogu

题目链接 题意：单点修改；给定区间，查询有多少子区间的 \(\gcd>1\)。 考虑只查询一次。这种子序列计数问题容易想到分治。 设当前递归到 \([l,r]\)，设要找的是有多少满足条件的 \([L,R]\in[l,r]\)。我们只需要计数跨区间的（因为 \(L,R\) 都在一个区间的可以递归求解 ......

这道题其实很简单 要让两数和为 \(k\) 的倍数，需要满足以下两条件之一： 两数都是 \(k\) 的倍数 两数的余数和为 \(k\) 因此，我们可以先统计出余数 再按上述条件算出共有多少组，即可得到答案 注意： 当 \(k\) 为偶数时，余数为 \(k/2\) 的数要两两配对，不要多算 这里统计的 ......

这题其实不难。 两人最佳的方案就是先说对方会的词。 不难证明，设先手会说 \(n\) 个单词，后手会说 \(m\) 个单词， 若 \(n>m\)，则先手胜，若 \(n<m\)，则后手胜。 那如果 \(n=m\) 呢？ 假设两人都会说的单词数为 \(k\)， 那么一番推理发现，当两人说了 \(k-1\ ......

这题其实不难 但如果用暴力，肯定过不了 所以我们得想另一种办法 我们发现，只有 \(1\) 异或 \(0\) 的值为 \(1\) 例如： \(1\) , \(0\) , \(1\) 两两异或的和为 2 其实就是每个 \(0\) 与每一个 \(1\) 异或时，\(sum\) 要加 \(1\) 所以，我 ......

这是让我最崩溃的一道橙题了。 整整 11 次提交才 AC。 这道题有几个要点必须注意： 判断日期是否合理。 按顺序输出。 判断重复的日期。 首先，我们来看怎么判断日期是否合理。 我们知道大月有 \(31\) 天，小月有 \(30\) 天，二月看平年闰年。 所以，我们可以写出这样的代码： bool c ......

这道题其实不难。 \(\gcd(i,j)=1\)，其实就是 \(i\) 与 \(j\) 互质。 如果 \(i\) 与 \(j\) 不互质，那么我们一定要让 \(a_i\) 与 \(a_j\) 相同，只有这样，才能使 \(a\) 序列中的最大值最小化。 所以，我们可以使用埃氏筛法，当筛到质数时，给它和 ......

这道题其实并不难。 题目大意是这样的：已知两个序列 \(r\) 和 \(b\)，求出合并后的最大前缀和。 很好发现：答案就是 \(r\) 和 \(b\) 各自的最大前缀和之和。 但要注意：\(r\) 和 \(b\) 可以什么都不取，因此 \(maxa\) 和 \(maxb\) 初始要赋值为 \(0\ ......

这道题其实不难。 \(\gcd(i,j)=1\)，其实就是 \(i\) 与 \(j\) 互质。 如果 \(i\) 与 \(j\) 不互质，那么我们一定要让 \(a_i\) 与 \(a_j\) 相同，只有这样，才能使 \(a\) 序列中的最大值最小化。 所以，我们可以使用埃氏筛法，当筛到质数时，给它和 ......

由于第二张图片是分期制作的，所以两次爬头像时，粉丝列表顺序可能会有微小的变动（比如取关会让后面的人往前一位），这就导致了有极少数粉丝被漏掉了。在此，我对大家道歉 所有粉丝头像 第一张图是动图，第二张图是一个 \(1600\times1800\) 的图片 第一张图片加载可能比较慢 封禁用户不在图片里 ......

分析 树形 dp。 定义状态 \(dp_{~i,~0}\) 为在以 \(i\) 为根节点的子树中，不选第 \(i\) 个人的最大快乐值，\(dp_{~i,~1}\) 为在以 \(i\) 为根节点的子树中，选第 \(i\) 个人的最大快乐值。 寻找根节点，然后从根节点开始 dfs，当前节点 \(u\) ......

分析 排列组合题目，但是 dp 做法。 存储当前列的高度 \(h_i\)，这里反着存，更好转移。 定义状态 \(f_{i,k}\) 为在前 \(i\) 列放置 \(k\) 个车的方法数。初始状态 \(f_{i,0} = 1\)。 分析状态转移方程： 当前列不放置车时：方法数为 \(f_{i-1,j} ......

目录题目链接思路分析代码 题目链接 P4819 思路分析 首先考虑这道题的连通性。容易发现这种类型的题目会容易产生环形的状态转移。假设我们知道了其中的一个点是否是黑白点，那么我们就可以知道所有点是否是黑白点。容易陷入一个误区：我们只能通过一个点知道他所相邻的最直接的点，如何确定相邻的点的状态？注意本 ......

抢到最优解了，UOJ 校验码上 80pts 过不去。/kk 这里是官方题解的简化。 首先考虑 \(n=1\) 怎么做，相当于对 \(m\le 10^{10}\) 筛出 \(f\) 的前缀和。由于 \(f(p)=p\)，直接构造函数 \(g(n)=n\) 然后 PN 筛 \(O(\sqrt m)\) ......

在洛谷中查看 前言 将边权转化到点权的树剖，很好理解，但我就说说线段树部分。 原本想做 P1505 [国家集训队] 旅游 的，但是发现它需要边权转化点权，所以先做了这题，于是代码里维护了 \(minn\)、\(maxn\)、\(sum\)。 线段树怎么写 先试着自己写一写 我们肯定要有两个标记： c ......

[USACO12FEB] Nearby Cows G 题目描述 给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 输入格式 第一行两个正整数 \(n,k\)。 接下来 \(n-1\) 行，每行两个正整数 \(u,v\)，表示 \(u ......

[CTSC1997] 选课 题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 \(N\) 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学 ......

# luogu P2322 [HNOI2006] 最短母串问题 [题目链接](https://www.luogu.com.cn/problem/P2322) 思路比较的简单的 dp 题。 首先看数据范围，$n \leqslant 12,len\leqslant50$ 应该是状压没跑了。 考虑设 $f ......

### [题目链接](https://www.luogu.com.cn/problem/P1419) ## description 给定一个长度为 $n$ 的序列（值域为 $[-10^4,10^4]$）和正整数 $st,ed$。 求一个区间，使得其长度 $\in [st,ed]$ 且平均值最大，输出 ......

# Description 现有一个长度为 $n$ 的非负整数数组 $\{a_i\}$ 。小 L 定义了一种神奇变换： $$f_k=\left(\sum_{i=1}^na_i^k\right)\bmod 998244353$$ 小 L 计划用变换生成的序列 $f$ 做一些有趣的事情，但是他并不擅长算 ......

# Luogu P5290 [十二省联考 2019] 春节十二响 [题目链接](https://www.luogu.com.cn/problem/P5290) ## 题目大意 一颗有根树, 有点权, 把点分成若干个集合, 要求每个集合内不包含祖先关系, 求集合的最大值的和的最小值. ## 做题思路 ......

# [NOIP2014 提高组] 联合权值 ## 题目描述 无向连通图 $G$ 有 $n$ 个点，$n-1$ 条边。点从 $1$ 到 $n$ 依次编号,编号为 $i$ 的点的权值为 $W_i$，每条边的长度均为 $1$。图上两点 $(u, v)$ 的距离定义为 $u$ 点到 $v$ 点的最短距离。对 ......

[Link](https://www.luogu.com.cn/problem/P7706) 一道很有意思的线段树题。 **第一步分析**，我们要求最大的 $a_i+a_k-\min{(b_j)}$，事实上我们可以直接省去这个 $\min$ 因为要最大化这个东西，选出来的 $b_j$ 必然是最小的， ......

写了 $358$ 行，$11.94 \mathrm{KB}$，有这么几个地方写挂了： - 反猪决斗一定选主猪。 - 游戏结束判定是主猪死亡或全部反猪死亡。 - 决斗可能被反杀，之后不能再出牌。 点击查看代码 ```cpp #include using namespace std; int n,m; ......

# [BJOI2019] 排兵布阵 ## 题目描述 小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。 如果一名玩家向第 $i$ 座城 ......

[Problem](https://www.luogu.com.cn/problem/P2285) ### Analysis 我们初始可以任意决定机器人的位置，状态很多，暴力显然会寄掉。 不妨先贪心的思考一下。我们肯定希望机器人初始在最先出现鼹鼠的洞，因为出现在没有鼹鼠的洞是无效的。 题目保证输入数 ......

[Problem](https://www.luogu.com.cn/problem/P4933) ### Description 给定一个长度为 $n$ 的数组 $h$，你可以从中选取若干数字，使得你选择的数组组成一个等差数列。特别地，单一的数字和只有两个数字也算作等差数列。求你可选择的方案数。答 ......

[Problem](https://www.luogu.com.cn/problem/P1064) ### Analysis 我们发现如果忽略主从关系，那这道题就是一个裸的 01 背包问题。 主从关系处理也非常简单，借鉴 [P2014 选课](https://www.luogu.com.cn/pro ......

[Problem](https://www.luogu.com.cn/problem/P2679) ### Description 我们可以换个思路。 从字符串 $A$ 中拿出 $k$ 个字串使其变成 $B$。求有几种不同的方案？ ### Analysis 我们发现 $A$ 中的一个字符取或者不取影 ......

[Problem](https://www.luogu.com.cn/problem/P1144) ### Analysis 求最短路我们都会求，但是求最短路径条数呢？ 不难发现 bfs 是按层搜的，所以它一定能求出从一个点到图上任意一个点的最短路。 若设 $x$ 为当前点， $x-y$ 为一条边， ......

[Problem](https://www.luogu.com.cn/problem/P9562) ### Analysis 不妨先忽略图论，考虑在一条链上选多组点使得每一组点 $i,j$ 均满足 $i-j=a_i-a_j$ 。由于没有规定我们选多少组，因此 $a_i+a_j > 0$ 均对答案产生 ......