RedGrey的博客

在刷AtCoder Beginner Contest 351时遇到这题：G - Hash on Tree，没能做出来，看题目描述感觉好像也不是太复杂的样子，但是看了题解之后，瞬间感觉这道题一点都不Beginner，题解中提到了一个Static Top Tree的数据结构，搜了一下基本没搜到什么直接的资料，看了题解感觉理解起来也非常困难，便想着用自己的语言记录下来，方便后续复习。 Static Top Tree Static Top Tree是一颗深度为O(logN)O(logN)O(logN)的二叉树，它可以用来描述子树之间的合并。 为了描述怎样构建一个Static Top Tree，我们先描述合并的反过程，分解一棵树： 首先对这棵树进行HLD(Heavy Light Decomposition)分解，关于HLD，可以参考：https://usaco.guide/plat/hld?lang=cpp 假设HLD之后树的结构如下所示： 然后重复执行下面的4个步骤： 选择连接root的Heavy Path，移除Path上的所有Heavy Edges 上一步之后，可能会出现多棵 ...

原题链接：https://www.codechef.com/problems/JUMP Jump mission 题目描述 有 NNN 座山排成一排，每座山都有一个 1∼N1 ∼ N1∼N 的唯一编号。第 iii 座山的索引为 PiP_iPi​，高度为 HiH_iHi​。大厨从第一座山出发，目标是到达第 NNN 座山。而他唯一能做的，只有从一座山跳到右侧的一座山上（不允许向左跳）。从第 iii 座山跳到第 jjj 座山上需要花费 (Hi−Hj)2(H_i − H_j)^2(Hi​−Hj​)2 的能量。大厨处于第 iii 座山时，他必须为山上的居民们准备一道特别的菜，以答谢居民们让他使用他们的材料。做这道菜需要花费 AiA_iAi​ 的能量（有些菜大厨特别喜欢做，做完之后神清气爽，所以 AiA_iAi​ 可能为负）。为了增加难度，我们规定只有当满足 i<ji < ji<j 且 Pi<PjP_i < P_jPi​<Pj​ 时，大厨才能从第 iii 座山跳到第 jjj 座山。 请帮大厨选择一种“跳山”的方式，并使得他的能量花费最小。注意能量花费可以为负。 ...

原题链接：https://open.kattis.com/problems/avoidingairports Avoiding Airports 题目描述 有nnn个国家，国家间有mmm条航班，第iii个航班可以从国家aia_iai​飞到bib_ibi​，起飞时间为sis_isi​，到达时间为eie_iei​，David当前在国家111，当前时间为000，David想要去国家nnn，他不在乎旅行一共要花多少时间，但是他特别讨厌在机场等待，如果他在起飞前等待了ttt时间，则它会获得t2t^2t2单位失望值，帮他找到一条失望值最小的路线。 输入 行 输入值 含义 范围 1 n mn\ mn m 国家数量 航班数量 1≤n,m≤200,0001\le n,m \le 200,0001≤n,m≤200,000 2...m+12...m+12...m+1 ai bi si eia_i\ b_i\ s_i\ e_iai​ bi​ si​ ei​ 起点 终点 起飞时间 到达时间 1≤ai,bi≤n,0≤si,ei≤1061\le a_i,b_i \le n,0 \le s_i,e ...

前言 前段时间OpenAI推出了Sora，展示了一系列生成的demo视频，效果非常惊艳，许多小伙伴肯定也都是心痒难耐，想要迫不及待的尝试一下，文生视频是否真的能够达到它所展示的效果。但可惜的是，到目前为止OpenAI的Sora仍然还没有公测。前段时间无意中看到了Open-Sora，在Github上开源了第一版模型权重，可以直接下载下来体验效果，于是便尝试了一番，看看它的效果如何。 Open-Sora初次体验 项目官方地址 https://github.com/hpcaitech/Open-Sora 硬件需求 根据README中描述，生成分辨率为512x512，2s长度的视频，需要的显存大小是24GB；我理解只要显卡的显存达到这个要求就能够跑起来，只是不同型号的显卡生成视频的速度可能有所区别。由于我个人并没有满足硬件需求的机器，因此我在 https://featurize.cn/ 上租了一台GPU实例来尝试，目前这个平台上的资源非常紧张，GPU实例基本上都是被占满的，很难租到满足需求的实例，大家也可以自行寻找一些其他的平台。 环境安装 正常按照官方GitHub仓库中的README一步步 ...

原题链接：https://codeforces.com/contest/932/problem/F F. Escape Through Leaf 题目描述 有一颗n(2≤n≤105)n(2\le n \le 10^5)n(2≤n≤105)个节点的树，根节点为111，每个节点上都有两个值与它关联，记第iii个节点上的两个值分别为ai,bi(−105≤ai,bi≤105)a_i,b_i(-10^5\le a_i,b_i\le10^5)ai​,bi​(−105≤ai​,bi​≤105)，你可以从某个节点跳到以它为根的子树的任意节点上，从xxx节点跳到yyy节点的代价为ax∗bya_x*b_yax​∗by​，对于每个节点，计算跳转到任何一个叶子节点最小的代价；注意：1.根节点不可能是叶子节点；2.叶子几点本身的代价为000 输入格式 第1行：nnn 第2行，空格分隔：a1 a2 ... ana_1\ a_2\ ...\ a_na1​ a2​ ... an​ 第3行，空格分隔：b1 b2 ... bnb_1\ b_2\ ...\ b_nb1​ b2​ ... bn​ 接下来共n−1n-1n−1 ...

原题链接：https://codeforces.com/contest/311/problem/B B. Cats Transport 题目描述 沿路有n(2≤n≤105)n(2\le n\le 10^5)n(2≤n≤105)座土堆，第i−1i-1i−1和第iii座土堆之间的距离为di(1≤di<104)d_i(1\le d_i \lt 10^4)di​(1≤di​<104)米，有m(1≤m≤105)m(1\le m\le 10^5)m(1≤m≤105)只猫，第jjj只猫在tj(0≤tj≤109)t_j(0\le t_j\le 10^9)tj​(0≤tj​≤109)时刻走到土堆hj(1≤hj≤n)h_j(1\le h_j\le n)hj​(1≤hj​≤n)上，然后在该土堆上等待，饲养员从第一个土堆出发，速度为111米/单位时间，按顺序从111到nnn走过所有土堆，如果ttt时刻到了第jjj座土堆，猫已经在这座土堆上了，则将这只猫带走，猫的等待时间为t−tjt-t_jt−tj​，共有p(1≤p≤100)p(1\le p \le 100)p(1≤p≤100)个饲养员，求将所有 ...

原题链接：https://codeforces.com/contest/1388/problem/E E. Uncle Bogdan and Projections After returning to shore, uncle Bogdan usually visits the computer club “The Rock”, to solve tasks in a pleasant company. One day, uncle Bogdan met his good old friend who told him one unusual task… There are nnn non-intersecting horizontal segments with ends in integers points on the plane with the standard cartesian coordinate system. All segments are strictly above the OXOXOX axis. You can choose an arbitrary ...

求解最大公约数 问题：求两个数a,ba,ba,b的最大公约数。 我们把a,ba,ba,b的最大公约数记为gcd(a,b)gcd(a,b)gcd(a,b)。 朴素算法 朴素的算法是，求出a,ba,ba,b的素因子分解，取两个数共同的素因子，即为最大公约数： a=p1a1p2a2...pnana=p_1^{a_1}p_2^{a_2}...p_n^{a_n} a=p1a1​​p2a2​​...pnan​​ b=p1b1p2b2...pnbnb=p_1^{b_1}p_2^{b_2}...p_n^{b_n} b=p1b1​​p2b2​​...pnbn​​ gcd(a,b)=p1min(a1,b1)p2min(a2,b2)...pnmin(an,bn)gcd(a,b)=p_1^{min(a_1,b_1)}p_2^{min(a_2,b_2)}...p_n^{min(a_n,b_n)} gcd(a,b)=p1min(a1​,b1​)​p2min(a2​,b2​)​...pnmin(an​,bn​)​ a1,a2,...,an,b1,b2,...,bn≥0a_1,a_2,...,a_n,b_1,b_2 ...

问题描述 如果a∗b≡1(modn)a*b \equiv 1 \pmod na∗b≡1(modn)，≡\equiv≡符号表示a∗b%n=1a*b \% n=1a∗b%n=1，%\%%表示模运算，模运算就是取余，x%y=x−⌊xy⌋∗yx\%y=x-\lfloor\frac{x}{y}\rfloor*yx%y=x−⌊yx​⌋∗y，例如5%3=25\%3=25%3=2 则a,ba,ba,b在模nnn情况下互为模逆元，模逆元可以记为a−1a^{-1}a−1，即a−1≡b(modn),b−1≡a(modn)a^{-1} \equiv b \pmod n,b^{-1} \equiv a \pmod na−1≡b(modn),b−1≡a(modn) aaa在模nnn的情况下，存在模逆元的充要条件是gcd(a,n)=1gcd(a,n)=1gcd(a,n)=1，gcd(a,n)gcd(a,n)gcd(a,n)表示aaa和nnn的最大公约数，即aaa与nnn互素。 简单描述一下，非正式的证明： 必要条件证明：如果aaa与nnn不互素，设gcd(a,n)=d>1gcd(a,n)=d \gt 1 ...

IOI 2007 TRAINING 原题链接：https://oj.uz/problem/view/IOI07_training 官方题解：https://ioinformatics.org/files/ioi2007solutions.pdf 题目描述 有NNN个节点，MMM条边，其中N−1N-1N−1条边是“树边”，NNN个节点和这N−1N-1N−1条边能够组成一颗所有节点都连通的树，其它的边都是“非树边”，每一条“非树边eee”都有一个相应的费用w(e)w(e)w(e)，这些“非树边”是可以删除的，删除边需要付出对应的费用；现在的任务目标是：删除某些“非树边”，使得剩下的图中，不存在边的数量为偶数的环，并且删除“非树边”所付出的费用和最小，求这个最小费用。 解决方案 参考：https://ioinformatics.org/files/ioi2007solutions.pdf 题目要我们求删除一些“非树边”使得不存在边数为偶数的环时删除的边的最小费用，我们把边数为偶数的环称为“偶环”。我们可以逆向思维思考：从一棵树开始，我们需要寻找一个总费用最大的“非树边”集合，将这些“非树边 ...