165

五、用go语言，证明：在一棵红黑树中，从某结点 x 到其后代叶结点的所有简单路径中，最长的一条至多是最短一条的 2 倍。 文心一言： 首先，我们要理解红黑树的性质。红黑树是一种自平衡的二叉查找树，它满足以下性质： 每个节点或是红色，或是黑色。 根节点是黑色。 每个叶节点（NIL或空节点）是黑色。 如 ......

题面 给一棵 \(n\) 个节点的树和一个整数 \(K\)。每次操作，等概率随机选一个所在连通块大小大于 \(K\) 的点，并删掉这个点和与之相连的所有边。重复操作直到图上所有连通块大小不超过 \(K\)，求期望操作次数，答案对 \(998244353\) 取模。 \(K< n\le 100\) 。 ......

题目链接 点击打开链接 题目解法 略有些套路的概率题，不过中间的把操作序列看成排列的操作还是很妙的 首先套路的考虑期望的线性性，有两个方式：把贡献放在点上或点集上，这里采用后面的方式做 对于每一个树上的集合 \(S\)，假设大小为 \(n\)，相邻的点为 \(m\) 考虑这个集合独立的限制为：相邻的 ......

ARC 165 - F - Make Adjacent Statement 给定一个长度为 \(2n\) 的数列 \(a\) ，其中对于每个数 \(i \in [1,n]\)，恰好在 \(a\) 中出现两次。每次可以将两个相邻的数交换。最后要求 \(\forall i \in [1,n] : a_{ ......

https://blog.csdn.net/zcz_822/article/details/128694447?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%B8%A6%E8%BE%93%E5%85%A5%E5%AD%98%E5%82%A ......

这类分组问题无非就是两种搜索顺序： 1.对于每个元素，枚举它可能分配到哪一个组 2.对于每个组，枚举它可能容纳哪些元素 这道题先把猫的体重从大到小排序，可以减小状态空间： #include <iostream> #include <algorithm> #include <stdlib.h> usi ......

B. Sliding Window Sort 2 被题目名里的滑动窗口误导了，于是卡 B 40min /fn Description 给定长度为 \(n\) 的排列 \(P\) 和一个整数 \(K\)。一次操作定义为选择一个长度为 \(K\) 的区间，对原排列的这段区间升序排序，其余位置不变。 你要 ......

本文介绍一款工具 go-callvis，它能够将 Go 代码的调用关系可视化出来，并提供了可交互式的 web 服务。 ## go-callvis 使用 ##### 依赖 - Go 1.17+ - Graphviz (可选，当工具指定了 `-graphviz` 时需要) ##### 工具安装 ``` ......

Preface 这场前三题是上周四写的，今天课有点多本来想着把最近两场CF的博客先写下的 但后面发现还有CCLCC的杂谈没写，写完发现由于晚上要上课没时间了，只能先把这场先写一下 A - Sum equals LCM 设\(n=\prod_{i=1}^k p_i^{c_i}\)，不难发现令\(A_1 ......

区间排序问题，主席树优化建图，最小字典序拓扑排序（priority_queue） problem 给定一个长度为 \(n*2\) 的序列，其中每种元素恰好出现了 2 次。 允许每次选择任意两个相邻的元素交换。 那么必定存在一个最小 \(k\)：使得 \(k\) 次交换以后所有相同的元素都是相邻的。 ......

Problem StatementFor an integer sequence $X=(X_1,X_2,\dots,X_n)$, let $X[L,R]$ denote the integer sequence $(X_L,X_{L+1},\dots,X_{R})$. You are given ......

arc165F 题目描述： 给定 \(n\) 和一个长度为 \(2n\) 的序列 \(a\)，满足 \([1,n]\) 每个数恰好出现两次。 每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列 \(a\) 满足 \(\forall i\in[1,n]\ a_{2\times i}=a_{ ......

D - Substring Comparison simple 的好题捏！ 只考虑每两个串的第一个位置，假设这两个位置不同，那么可以定出一个大小关系。将所有大小关系建成一张图，如果这张图是个 DAG，那么就可以成立了，如果有环，说明环上的点都是一样的，因此可以将这些数缩成一个点，然后把对应的串往后移 ......

赛时：看不懂题，啊这！ 赛后：就这？ 题目描述 有一个简单相连的无向图，其顶点数为 \(n\)，编号为 \(1\) 至 \(n\)。图中有 \(m\) 条加权边，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)，权重为 \(w_i\)。此外，连接两个顶点的简单路径的权重是简单路径中包 ......

题目描述： 给定 \(n\) 和一个长度为 \(2n\) 的序列 \(a\)，满足 \([1,n]\) 每个数恰好出现两次。 每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列 \(a\) 满足 \(\forall i\in[1,n] \quad a_{2i} = a_{2i-1}\)。 ......

ARC165 A 猜的结论,质因数\(\ge2\) 感觉证明不难 #include<bits/stdc++.h> using namespace std; int t; int n; int main() { // freopen("date.in","r",stdin); // freopen(" ......

AT_arc165_d [ARC165D] Substring Comparison 题解 Links 洛谷 AtCoder Description 给定正整数 \(n,m\) 和 \(m\) 个形如 \((A_{i},B_{i},C_{i},D_{i})\) 的限制条件。 判断是否存在一个长度为 ......

AT_arc165_b [ARC165B] Sliding Window Sort 2 题解 Links 洛谷 AtCoder Description 给定正整数 \(n,k\) 和一个长度为 \(n\) 的整数 \(P\)，你需要选择一个长度为 \(k\) 的区间 \([l,l + k - 1]\ ......

赛时 45min 切 A~C，降智不会 D，罚坐 1h，喜提 rk70+ -> rk170+。 A - Sum equals LCM 可证明结论：若 \(N\) 只含有一种质因子则无解，否则有解。 B - Sliding Window Sort 2 这么多 corner case 的题竟然 10mi ......

洛谷传送门 AtCoder 传送门 悲，赛时代码赛后被 hack 了。 发现对子段排序不会使排列的字典序变大。因此若存在长度 \(\ge k\) 的递增子段直接输出原排列。 否则答案与原排列的 \(\text{LCP}\) 至少为 \(n - k\)（可以通过对 \([n - k + 1, n]\) ......

前天的晚上打这道题，和同学一起想出了思路，开心。 题意描述 给你一个数 \(N\)，问你存不存在一个数列 \(A_1,A_2,\ldots,A_n(2 \le n)\) ，使得 \(\sum_{i=1}^n A_i=N\) 并且 \(\operatorname{lcm}(A_1,A_2,\ldots ......

啥都不会。自闭了。 A 显然填充 \(1\) 不会影响 \(\text{lcm}\)。 枚举 \(n\) 的互质且 \(\text{lcm} = n\) 的因数，看和是否 \(\le n\) 即可。 B 注意到答案的字典序肯定大于等于原排列。 如果存在 \(\ge k\) 的上升子段就直接输出原排列 ......

D1a5y。 记录 \(x(1\le x\le n)\) 出现位置分别为 \(l_x,r_x(l_x< r_x)\)，讨论一下发现当两个数 \(x,y\) 满足 \(l_x<l_y,r_x<r_y\) 时操作后 \(x\) 一定出现在 \(y\) 前面，不然可以交换位置以达到更优步数。否则发现无论怎 ......

有点结论场的感觉了。 A 题面 简单题。证明一个结论，只要 \(n\not=p^q(p \text{是} n \text{的一个质因子})\)，都是有解的，反之无解。 先证明 \(n=p^q\) 无解，假定 \(n\) 分解为 \(p^a\times p^b(a\le b,a+b=q)\)，此时两数 ......

《Programming Abstractions In C》学习第57天，开始第4章“Introduction to Recursion”的学习，p161-p165，总结如下。 一、技术总结 1.recursion vs stepwise refinement 答：p164， The strate ......

**描述** 用户行为日志表tb_user_log | id | uid | artical_id | in_time | out_time | sign_cin | | | | | | | | | 1 | 109 | 9001 | 2021-08-31 10:00:00 | 2021-08-31 ......

# 模拟4总结 [toc] ### 总体上 个人感觉这一次做题非常舒服，第一题和第四题都想出来了，只可惜第三题做对了一点（最大值） ### 个体上： #### 第一题： 很可惜，tarjan写错了，实际得分是65分......说明算法流程不是很掌握 确实tarjan容易打错，特别是要注意合并的位置， ......

# AtCoder Beginner Contest 165 https://atcoder.jp/contests/abc165 ## C - Many Requirements dfs ```CC #include using namespace std; const int N = 15, M ......

37款传感器与模块的提法，在网络上广泛流传，其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块，依照实践出真知（一定要动手做）的理念，以学习和交流为目的，这里准备逐一动手试试多做实验，不管成功与否，都会记录下来——小小的进步或是搞不掂的问题，希望能够抛 ......

难度中等 370 给你两个版本号 version1 和 version2 ，请你比较它们。 版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一 ......