搜索结果
查询Tags标签： 题解，共有 1043条记录-
P1029 最大公约数和最小公倍数问题(普及?) 题解
题目传送门 想要做这题，我们要先了解一下最大公约数。 最大公因数，也称最大公约数、最大公因子，指两个或多 个整数共有约数中最大的一个。a，b的最大公约数记为 （a，b），同样的，a，b，c的最大公约数记为（a，b， c），多个整数的最大公约数也有同样的记号。求最大公…
2023/11/26 1:32:54 人评论 次浏览 -
splay + 垃圾回收 知识点与例题的简要讲解
splay 简要讲解 前置芝士:普通二叉树 splay tree是一个越处理越灵活的数据结构,通过splay(伸展)操作,使整棵树的单次查询时间复杂度接近于O(log n),整棵树的高度也接近于log n 根据上面的这句话,很明显能看出splay与普通二叉树的区别 普通二叉树经过多次处理后,很容易退化…
2023/10/25 1:02:58 人评论 次浏览 -
[AGC055A] ABC Identity 题解
[AGC055A] ABC Identity 题解 题目描述 给定长度为 \(3n (1 \le n \le 2e5)\) 的序列，其中字母 A,B,C 各有 \(n\) 个。 一个合法序列 \(T\) 满足以下条件：其长度为 \(3k (1 \le k \le n)\)。\(T_1 = T_2 = ... = T_k\)\(T_{k + 1} = T_{k + 2} = ... = T_{2k}\)\(T_{2k …
2023/6/14 18:22:17 人评论 次浏览 -
[AGC055B] ABC Supremacy 题解
[AGC055B] ABC Supremacy 题解 题目描述 给定两个长度为 \(n\) 的字符串 \(a\)，\(b\)。 你可以进行若干次以下操作：若 \(a\) 中的一个子串为 ABC，BCA 或 CAB，那么可以将这个子串替换为 ABC，BCA 或 CAB。求能否将 \(a\) 变成 \(b\)，输出 YES 或 NO。 解析 不难发现，…
2023/6/9 14:22:11 人评论 次浏览 -
[ABC268C] Chinese Restaurant
[ABC268C] Chinese Restaurant 声明：以下的所有操作都会再做一次 \(\% n+n) \% n\)，比如 \(i - 1\) 会变成 \(((i-1)\%n+n)\%n\) 题意 有 \(n\) 个人和 \(n\) 个盘子，每个人如果能拿到 \(i - 1\) 或 \(i\) 或 \(i + 1\) 号盘子那么他会很开心，现在每个人的站位是 \(p_…
2023/5/19 1:22:05 人评论 次浏览 -
[ABC270F] Transportation
[ABC270F] Transportation 题意 有 \(n\) 个点，有 \(m\) 条可以加上的边，如果两个点同时建立了一种东西，那么也算连了一条边，每条边都有个代价，每个点建一个东西也有不同的代价，问想要让图连通，最少需要多少代价。 思路 显然是最小生成树，但是由于可以见两种东西，…
2023/5/18 1:22:19 人评论 次浏览 -
[ABC270D] Stones
[ABC270D] Stones 题意 有两个人玩游戏，有 \(n\) 个石子，和一个长度为 \(k\) 的序列，每次可以取 \(a_i\) 个但前提是剩下来的石子数有 \(a_i\) 个，第一个人先取，问两边都是用最优策略时，第一个人最多能得多少个石子。 思路 可以设计状态 \((x, y, f)\) 表示第一个人…
2023/5/18 1:22:15 人评论 次浏览 -
【学习笔记】【题解】树形依赖 DP 选做
地址：https://www.cnblogs.com/FReQuenter5156/p/shuxingyilaidp.html/ 简介 这类背包本质上是分组背包问题。 将一个节点的每一棵子树看作一组，进行分组背包。所谓分组背包，即在选择物品的时候，一开始将物品分为好几组，在选择时，可以从每一组中至多选择一件物品，问…
2023/5/6 1:22:20 人评论 次浏览 -
题解【P5004 专心OI - 跳房子】
本题的找规律题解到此为止。 为防止新人受到误导，不再接受新的此类题解。 以前的保留不会删除，但请不要再提交。题目传送门。 矩阵加速模板题吧。给一个正经的不用找规律的做法。 考虑设 \(F_n\) 表示前 \(n\) 个格子的答案，\(f_n\) 表示最后降落在 \(n\) 的方案数，显…
2022/9/15 23:20:13 人评论 次浏览 -
CF1450E Capitalism 题解
首先发现这个 \(|a_i-a_j|=1\) 的形式比较接近差分约束，稍微转化一下就是：\(-1\le a_i-a_j\le 1\) 且 \(a_i\neq a_j\)。于是你会发现 \(a_i\neq a_j\) 不是差分约束的条件。 换个角度。容易发现一条边相连的两个点一定奇偶性不同。考虑原图中若存在奇环，那么显然这是自…
2022/9/14 23:20:47 人评论 次浏览 -
[Luogu]SP2128题解
[Luogu]SP2128 KROW 题意 共有 \(t\) 个 \(n \times m\) 的由 .、x、o 组成的字符矩阵。设矩阵中连续 \(k\) 格为 x 小 A 加一分，连续 \(k\) 格为 o 小 B 加一分。 正文 最坏时间复杂度：\(\mathcal{O}(tnmk)\) 算法：暴力 此题我第一眼看就知道很水（尽管我调试了半天）…
2022/9/14 23:19:04 人评论 次浏览 -
「题解」洛谷 P8512 [Ynoi Easy Round 2021] TEST_152
有三个维度，序列维，操作维，询问维。 尝试扫描线，枚举一下扫哪个维能做。 或者考虑序列维上有颜色段均摊的性质。 这样不难想到在操作维上从小到大扫描线，或者说对询问维的 \(r\) 作扫描线，用 set 维护序列维上的连续段。 现在将询问 \((l,r)\) 挂在了 \(r\) 上，扫描…
2022/9/14 6:19:05 人评论 次浏览 -
「题解」洛谷 P8511 [Ynoi Easy Round 2021] TEST_68
简要题意：给定带点权树，对每个点求出其子树补中选出两个数异或得到的最大值。 考虑整个树中的最优解是 \(a_x\oplus a_y\)，那么除了 \(x\) 和 \(y\) 到根的链上这些点以外，其他的所有点答案都是 \(a_x\oplus a_y\)． 这样只需要考虑如何求出一条到根的链的答案。 考虑…
2022/9/14 6:19:05 人评论 次浏览 -
一百五十天一千题（DAY 1）
一百五十天一千题 （DAY 1） 目前总题数： 0 目前CF分数： 1325 T1： （ABC 268）C - Chinese Restaurant // 题解 const int N = 1e6 + 10; /*模拟即可但是纯暴力是N^2的 会TLE考虑到要把 A[I] 移动到 p=I-1需要操作 a[i] - p % N 或者 (a[i]-p+1)%N或者 (a[i]-p-1)%N;用…
2022/9/14 6:16:31 人评论 次浏览 -
P8506 标题计数 题解
题目传送门 这道题是十分简单的送分题 要是在CSP-S考到该多好，当然是肯定不可能的 看题目描述我们可以知道 当是以一个#和一个空格开头且后面跟有其他字符时即为一级标题 而且在#前无论有多少个空格都无所谓 比如 # abcd # abcd# abcd# a#b3#c#d # # abcd都是一级标题…
2022/9/12 23:24:34 人评论 次浏览
