题解colorful p9665 macao

1811D 1814C 1819B 1821D 1770D 题意： Koxia 和 Mahiru 正在玩一个游戏。游戏使用 $a,b,c$ 三个长度为 $n$ 的数组，共进行 $n$ 轮。 每一轮中，Koxia 先在 $a_i,b_i,c_i$ 中选择一个数字，Mahiru 再从未选择的两个数字中选 ......

「BZOJ2144」跳跳棋 个人评价 挺好的一道题，难点在于想到树这个结构和建树 1 题面 跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有 3 颗棋子，分别在 a,b,c 这三个位置。我们要通过最少的跳动把他们的位置移动成 x,y, ......

A Link。 模拟，代码。 B Link。 模拟，代码。 C Link。 我们设 $c$ 为最后相同的字符。 性质：我们一定不会删除字符 $c$。 因此以 $c$ 为最后字符的操作次数就是不包含字符 $c$ 的极大段的最小操作次数的最大值。 对于一个长度为 $l(l\ge 1)$ 的段，它的最小操 ......

P4198 楼房重建 题解 线段树二分 思路 考虑在线段树内维护二信息： 区间斜率最大值 $mx$ 区间最大斜率上升序列长度 $len$ 答案即为根节点的 $len$。 考虑转移信息二： 蓝色部分代表左区间的上升序列，红色是右区间的，绿色折线就是当前区间的上升序列。 🤔稍微思考之后发现，左区间的上 ......

DP。状态设计是点睛之笔。 首先显然有每行或每列只能有至多 $2$ 个棋子。 设状态 $f_{i,j,k}$ 为第 $i$ 行，有 $j$ 列只放了一个棋子，$k$ 列放了两个棋子。 之后直接转移即可。注意边界判断。 code： 点击查看代码 #include<bits/stdc++.h> #def ......

传送门 CF1034D Intervals of Intervals 题目大意 有 $n$ 个线段，第 $i$ 个是 $[a_i,b_i]$。 定义区间 $[l,r]$ 的价值是第 $l$ 个线段到第 $r$ 个线段的并的长度。 找出 $k$ 个不同的区间，使得总价值最大。输出最大总价值。 $1 \ ......

Question Asm.Def 在第一象限内找到了n个可疑点。他需要为导弹规划路径。 如图所示，导弹一开始在(0,0)。它只能朝着一定的方向——即严格夹在图中两条射线间的方向（白色部分）前进。注意，它不能沿着这两条射线前进，当然也不能停在原地。 当导弹到达某个可疑点后，它仍然只能朝着该范围内的方向 ......

题目地址 C.Darkness I 题意：有一个n*n的方格，最开始全是白色，如果白色周围4格有两个黑色格子，1秒后这个白色格子会变成黑色，问如果要使全部格子都变为黑色，最开始最少需要涂黑几个格子 Solution 对于两个黑色格子，只有当满足 $$ |x_1-x_2|+|y_1-y_2|≤2 $$ ......

补题链接：https://codeforces.com/gym/104337 原文链接：https://www.eriktse.com/algorithm/1136.html M. Different Billing 签到题，写几个柿子然后枚举B或C即可。 #include <bits/stdc++ ......

首先先是一步很猛的操作——将三染色视作构造一个矩阵使得相邻元素相差 $1$ 且每个元素 $\bmod 3$ 的值就等于其颜色。证明是显然的，我们按从上到下从左到右的顺序填数，可以归纳证明，对于一个相邻格子颜色互不相同的矩阵的填数方案，处于斜对角的两个格子上写的数要么差 $2$，要么相等，这样待填的这 ......

题意： 有一根长为 $1$ 的巧克力，已经被切了 $m-1$ 刀被分成 $m$ 分，接下来每次在整根长度为 $1$ 的巧克力上均匀随机一个点切一刀，求每一小段巧克力长度均小于一个给定值 $K$ 需要的期望次数。 引理：Irwin-Hall 分布：对于 $n$ 个在 $[0,1]$ 内均匀分布的实数随 ......

4 月 30 日测试题解 T1 ${\color{green}{\text{100pts}}}\text{/100pts}$ 题意 一个无限长宽的棋盘，给出起点 $s$ 和终点 $t$，行走方式是象棋中马的走法，问最少需要走多少步。 对于 $100%$ 的数据，$|x_s|, |y_s|, |x_t ......

题目描述 给出 $n$ 个数 $q_1,q_2, \dots q_n$，定义 $$F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - ......

P5785 [SDOI2012]任务安排 题目描述 分析 很明显是一个dp 我们不妨设$dp[i]$表示枚举到$i$的最小费用 $t[i]$表示加工完第$i$个任务所用的总时间，也就是$T[i]$的前缀和 由于每一批任务前都要一个时间为$s$的开机工作 我们不妨把每一个这样的$s$秒提出来，则这$s ......

前言 题目传送门！ 更好的阅读体验？ 比较好玩的二进制题目。 思路 答案最小，也就是说较高位要尽可能小。所以很容易想到从最高位开始枚举。 第 $i$ 位为 $0$，等价于选出的所有边的第 $i$ 位都为 $0$。同时，由于我们是贪心，如果之前枚举过的第 $j$ 位可以是 $0$，那么这两个条件要同时 ......

洛谷P4715 淘汰赛 题目描述 有 2^n（n≤7）个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。 能力值高的国家和能力值低的国家踢比赛时高者获胜。 1 号国家和 2 号国家踢一场比赛，胜者晋级。 3 号国家和 4 号国家也踢一场，胜者晋级…… 晋级后的国家用相同的 ......

题目传送门 题意：给定 $p\le n$ 个值域为 $1\sim m$ 的数，你需要将其补充到 $n$ 个，每个数都在 $[1,m]$ 内独立随机。求最终第 $K$ 小数的期望值。$n,m\le 2000$ 看到这个问题，就容易想到枚举第 $K$ 位的值，计算概率（或者方案数）。首先将其给定的 $p ......

## 题意： [题目](https://www.luogu.com.cn/problem/P7579) 一道交互题。 有 n 个球，里面有两个假球，假球比普通球的要轻，每次可以询问任意两组球的轻重关系，第一组轻为 < ,第二组轻为 > ,一样重量为 = 。 ......

原题链接 题目大意 巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。 对于每一块巧克力，我们设 $x$ 和 $y$ 为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数 $a$ 和 $b$ ，分别 ......

题目大意 给定$n$个三维空间的平面，由高度$z$、$x$的范围$[xl,xr]$和$y$的范围$[yl,yr]$来表示。有$m$次射击，每次射击点$(x,y)$，摧毁包含此点的$z$值最小的平面，输出此平面编号，若摧毁不了任何平面，输出$0$。 题解 点查平面不好做，于是可以转化为平面查点，先将平 ......

2A. Politics 因为编号为 $1$ 的人一定不会离开，那么最后留下的人一定要和编号为 $1$ 的人的所有参数都一致，所以计数即可。 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext ......

题目传送门 题意：定义毛毛虫为一种特殊的树，形如一条链上挂着若干个叶子。特殊地，在本题中的毛毛虫允许自环但不允许重边。给定一个无向图，每次操作可以合并两个点以及两个点的出边（两个点有相同出边则出现重边，两个点之间有边则出现自环）。求将其变为毛毛虫的最小操作次数。 容易发现，一个环要想最终放到一棵树上 ......

T1 二分一个删除的数字个数 然后考虑删除的数字肯定是从大到小来的，所以预处理一个降序的数组，这样能知道二分的数字个数所对应的数字。 在原数组上跑最大子段和，如果碰到大于二分位置的数字就删了。 最终成绩26分，因为对于二分的个数mid，原数组中a[mid]不止1个的话，无法判断哪些该删，哪些不该删。 ......

题解 CF1817F Entangled Substrings 闲话：这场开始看 A 看错题了，打了好久发现样例都过不了，自闭了，不想打了，然后听 JV 的看 E，感觉 E 很奇怪，于是看 F，本来不打算做了发现 F 好像很可做的样子，于是就写了一发 F，但是最后回来 BC 都没做出来，还是输了/l ......

这是数学题耶！ 题意 给定一个整数 $n$ 和一个长度为 $n$ 的整数序列 $a$，求满足以下要求的三元组个数： $1 \leqslant i < j < k \leqslant n$。 $a_i \ne a_j$，$a_j \ne a_k$，$a_k \ne a_i$。 思路 先想正着做，好，不 ......

ABC212G Power Pair 推柿子题 $\sum\limits_{x}^{P-1}\sum\limits_{y}^{P-1} \exists n \in \mathbb{N}\ x^n \equiv y(\bmod P)$ $1+\sum\limits_{x=1}^{P-1}\sum\li ......

一、题目描述： 你有一个骰子，数字 1~6 可以被等概率扔到。 初始时有一个数 $ans=1$。 当扔到数字 $x$ 时，$ans=ans \times x$。 给你一个数字 $n$ ，求 $ans$ 能等于 $n$ 的概率。 $n<=1e18$。答案对 $998244353$ 取模。 二、解题思路 ......

D. Range and Partition 1800 思维 https://codeforces.com/contest/1631/problem/D 题解：由于严格大于，故其最终前缀和s[n]>=k,而当s[n]>=k，s[0]=0,每步至多下降1，故其中必有至少k个点满足s[i]=x（1<=x ......

luogu P2123 题目描述 皇后有 $n$ 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 $n$ 位大臣颁发奖金，其中第 $i$ 位大臣所获得的奖金数目为第 $i－1$ 位大臣所获得奖金数目与前 $i$ 位大臣左手上的数的和的较大值再加上第 $i$ 位大臣右手上 ......

4 月 27 日测试题解 最短路专场 T1 ${\color{green}{\text{100pts}}}\text{/100pts}$ 题意 给出 $m$ 个变量与 $n$ 个约束，每个约束形如以下三种中的一种； $x_i - x_j \le w$ $x_i - x_j \ge w$ $x_i - ......