题解1203 div cf

好神奇的 dp 题。 description 给定数组 \(a\)，求其有多少个排列满足 \(y_i=\max(a_1,a_2,\dots,a_{i-1})\) \(\forall i\in [1,n]\cap\mathbb{Z},2a_i\leq y_i ~\texttt{OR}~ 2y_i\le ......

ABC209E Shiritori 题解 原题：洛谷AT_abc209_e 分析 博弈，可重复选，一眼图论，将每个单词的前三个字符向后三个字符连边，并用后三个字符代表这个单词。 看一下样例。 5 eaaaabaa 1 2 eaaaacaa 1 3 daaaaaaa 4 5 eaaaadaa 1 4 ......

给一个 \(n \times m\) 的矩阵和 \(n \times m\) 个数，你需要把这些数填入矩阵。保证 \[\sum_{i=1}^n \sum_{j=1}^m \left ( \mathop{max}\limits_{1 \leq x \leq i, 1 \leq y \leq j} a_ ......

给一个堆 \(n\) 个石子，如果可以分裂为整数，它将分裂为 \(\frac{1}{3} n\) 和 \(\frac{2}{3} n\) 的两堆石子。并且新石堆会继续分裂。 询问过程中是否出现过大小为 \(m\) 的石堆。 显然记忆化 \(dfs\) 即可。 记忆数组一般开全局。容易观察到值域很大， ......

给定两个长为 \(n\) 的数组 \(a\) 和 \(b\) 。你需要将 \(a\) \(b\) 归并成一个数组 \(c\) 。询问所有归并方法中，连续数相同的子段最长为多少。\(1 \leq a_i, b_i \leq 2n\) 。 显然归并在 \(a\) 可以任选一段 \([l_1, r_1]\ ......

原题 ++ 题目背景 题目描述 给定一个 \(n\) 个节点（编号为 \(1\) 到 \(n\)）和 \(n-1\) 条边构成的无向连通图。 构造一张新图： 新图的点集与原图相同 在新图中 \(u,v\) 之间有无向边 是 在原图中 \(dis(u,v) \ge k\) 的充分必要条件 （\(k\) ......

定义正整数 \(C = \overline{c_1c_2 \cdots c_k} = c_1 \cdot 10^{k-1} + c_2 \cdot 10^{k - 2} + \cdots + c_1\) 。 假设有两个正整数 \(X = \overline{x_1x_2 \cdots x_n}, Y ......

题目链接 Game Bundles 分析 很神奇的一道题目 先想想如何计算一个集合和为60的子集个数 可以想到通过 \(DP\) 求解： 记 \(f[i][j]\) 为前 \(i\) 个数字，和为 \(j\) 的子集个数 则 \(f[i][j]+=f[i-1][j-a[i]]\) \(f[i][a[ ......

这题首先上来会发现题目中的很多信息都是假的，核心就是问要构造一个\(x\)个点的完全图至少要多长的序列 我们把序列中相邻的两个元素看作图上的一条边，则可以把问题转化为：给一个\(x\)个点的完全图，问至少要走多长的路径才可以遍历图中的所有边至少一次 简单讨论下会发现当\(x\)为奇数时，此时图中每个 ......

原题 挺好的树形 dp ，正好 dp 不太熟练，练习一下 赛时只想到了暴力和\(X \leq 7\) 的链的部分分，过于 naive 不说了 先考虑链的情况，既然是二进制考虑按位拆分。设 \(g_{i,j,0/1}\) 表示以 \(i\) 为根，从 \(i\) 点连通块的疑惑和第 \(j\) 位为 ......

双指针、二分法、数学、分治、摩尔投票、Hash存储、队列、栈、博弈论、动态规划、模拟、排序、贪心、滑动窗口、单调栈、深度优先搜索、Mirrors遍历、Manacher、回溯剪枝 ......

小清新贪心+分类讨论，因为边的数组开小了WA了好久…… 首先我们贪心地选出不包含\(s,t\)的边，用这些边尽量地将除了\(s,t\)外的\(n-2\)个点连通 接下来考虑每个连通块，由于题目保证图初始连通，因此只有三种情况，即要么其中仅有和\(s\)相连的边；仅有和\(t\)相连的边；或者同时有向 ......

刚开始想复杂了，后面再细想了下发现是个傻逼题 考虑一下构造策略，每次从两种颜色集合中分别取出一个数\(u,v\)，考虑连边\(u\leftrightarrow v\)，边权为\(\min(s_u,s_v)\) 并在每次操作后将\(s_u,s_v\)中较小的那个直接删掉，并把较大的那个值减去\(\mi ......

也是一个很经典的优化最短路的题，感觉在暑假前集训做过类似思想的题来着 首先发现我们可以把所有有路灯的点以及终点看作关键点，很显然我们只关心关键点之间的边权以及最短路 不难发现对于两个关键点\(i,j\)，如果\(i,j\)相邻，则它们之间有边权为\(0\)的边；否则若\(|x_i-x_j|\le 2 ......

挺有意思的一个构造题，不过这种排列置换相关的套路感觉都太明显了 首先考虑把原图的每个置换环求出来，稍作观察会发现所有长度为奇数的置换环都可以很容易地构造出对应的\(q\)数组 但长度为偶数的置换环就不能单独构造了，但我们发现可以把两个长度相同且为偶数的置换环交错着合并来得到一个合法的\(q\)数组 ......

Description 给你 \(n\) 种颜色的球，每种颜色的球有 \(k\) 个，把这 \(n\times k\) 个球排成一排，把每一种颜色的最左边出现的球涂成白色（初始球不包含白色），求有多少种不同的颜色序列，答案对 \(10^9+7\) 取模。 \(1\leq n, k\leq 2000\ ......

给一个字符串 \(s\) 包含 \(0, 1, ?\) 。 定义一个 \(01\) 串 \(s\) 的 \(cost\) 为：选择 \(s\) 的任意一个子段 \([l, r]\) 并 \(reverse\) 。将 \(s\) 变为一个非降序序列时的 \(reverse\) 最小次数即 \(cost ......

解题思路 若车 \(A\) 限制车 \(B\) 离开，则 \(A\) 先于 \(B\) 离开，所有的限制条件构成了一个拓扑结构。 若 \(A\) 限制 \(B\)，\(A\) 向 \(B\) 连边，最终可以使用拓扑排序求解。 而查找每个车辆的约束车辆时间复杂度为 \(\mathcal{O}(n\ti ......

Codeforces Round 901 (Div. 2) 比赛链接 "考古"啦！之前没有做，现在补上 A. Jellyfish and Undertale 题目链接 思路： 按理说用模拟应该也是可以做到的，但是我应该没有写好，因为我们要找的是最大时间，所以我们每次加上的是min(a-1,x[i]) ......

分析 大概是强连通分量里面最水的一道紫题，不过细节挺多的，做题的时候给蒟蒻震惊到了。 题目要求是从 \(1\) 走到某个点，然后再走回 \(1\) 号点，中途可逆行一次，问最多能经过几个点。 有一个明显的思路是存两个图，一个正图一个反图，正图是为了求 \(1\) 到各个点的距离，反图是为了求各个点到 ......

分析 简单排序题。 首先 Petya 可以通过跨过一个台阶和两个台阶保证不经过脏台阶，但是不可以通过跨过三个台阶来保证不经过脏台阶，所以只要看有没有连续的三个脏台阶即可。 同时，如果第一个台阶和最后一个台阶至少一个是脏台阶那么就不可以达成。 Accepted Code /*Code By Manip ......

哈人*3400，是不是贺过了个 1F (? 单点编号 \(\to max + 1\)，动态维护 prufer 序列删除了哪些点。 看似不可做，但是不难发现我们一个点被更改其他点的相对次序不会改变，反而 \(x \to max\) 这条链的删除次序到了最后面。 然后我们以权值最大点为根，不难发现每次只 ......

简单题。CF 评分才 *1600。 可以直接先把 \(Q\) 拆成两部分。 \[\begin{aligned} \large a&=\oplus^n_{i=1}p_i\\ \large b&=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (i\bmod j)\\ \large ......

见到有单调性、有限制的区间问题，很自然地就会想到用尺取去做。 先按工资升序排序，然后套上尺取就行了。 不会尺取的可以根据这道题去学。 时间复杂度 \(O(n\log n)\)。 #include<cstdio> #include<algorithm> #define ll long long usi ......

发现还没有和我一样的做法。 觉得 B 比 A 好想的多。 令 \(A_i\) 为 \(a_i\) 变成 \(A\) 的倍数最少次数，\(B_i,C_i,AB_i,AC_i,BC_i,ABC_i\) 同理。 那么我们就有 \(A_i=(A-A\bmod {a_i})\bmod A\)，其他同理。 这一 ......

略带一点思维吧。 个人认为比 B 难想。 先来考虑弱化版的题面： Case 1 如果 \(X\) 串和 \(Y\) 串都没有字母 C，如何判断是否有解？ 观察操作，我们能发现这个操作的本质实际上是让一个位于前面的字母 A 挪到其后面的任意的位置，并且前后两个 A 的相对位置不会发生改变。 所以，如果 ......

思路 发现如果一个字符串中有长度大于等于 \(2\) 回文子串，必定有长度为 \(2\) 的回文子串或长度为 \(3\) 的回文子串，并且形如：aa 和 aba。 所以考虑用线段树这两种情况。维护一段区间的最左、次左、最右、次右的元素，同时用两个标记变量 \(f_1,f_2\) 分别表示这个区间中是 ......

Abnormal Permutation Pairs (hard version) 两个限制：字典序小、逆序对大，一个显然的想法就是确保一对关系，统计另一对关系。 确保哪一对呢？我们想了想，决定确保字典序小，因为字典序是可以贪心的。 具体而言，我们考虑两个排列自第 \(i\) 位开始出现了不同。这样 ......

[ABC207F] Tree Patrolling 弱智 DP 题，设 \(f(i,j,0/1/2)\) 表示在点 \(i\)，子树中有 \(j\) 个点被覆盖，且 \(i\) 点自身状态是未被覆盖/被自身覆盖/被某个儿子覆盖，然后树上背包更新就行了。 代码： #include<bits/stdc+ ......

木 弱智 DP 题，直接设 \(f_i\) 表示 \(i\) 子树内染色的方案数，然后每次合并一个点与它的儿子即可（具体而言，因为儿子间独立，所以方案数就是二项式系数）。 需要注意的是因为第一条边可以在任意位置，所以要以每个点为根各 DP 一次。但是这样每条边会被算两次，所以乘以 2 的逆元即可。 ......