yaoxi-std / yaoxi-std.github.io Goto Github PK
View Code? Open in Web Editor NEWyaoxi-std的个人博客
Home Page: https://yaoxi-std.github.io/
yaoxi-std的个人博客
Home Page: https://yaoxi-std.github.io/
https://yaoxi-std.github.io/2021/12/17/sol-p4248/
[AHOI2013] 差异 题解
https://yaoxi-std.github.io/2022/01/09/sol-cf553e/#more
CF553E Kyoya and Train
https://yaoxi-std.github.io/2021/11/27/sol-p3233/
P3233 世界树 题解题面题目链接 解法以下所有的“关键点”都表示题目中的议事处 看完这题题解后去学习了虚树(然后day2上午模拟赛考了道类似虚树但不用建$lca$的题目) 于是看到$\sum m \le 3 \times 10^5$ 直接建立虚树(然而如果没学过虚树就看不出来了)。 用pair<int, int>储存树上节点到达最近关键点的距离和关键点编号以便于比较。先对虚树上的节
https://yaoxi-std.github.io/2022/01/23/sol-p3690/
P3690 【模版】动态树(Link Cut Tree)
https://yaoxi-std.github.io/2021/12/30/sol-p4015/
P4015 运输问题题面题目链接 解法怎么会有这么sb的题目啊。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
https://yaoxi-std.github.io/2021/12/05/sol-p4245/
P4245 【模版】任意模数多项式乘法题面题目链接 解法对于任意模数的多项式乘法显然无法直接套用$NTT$。而由于数量级过大,采用std::complex的$FFT$也会产生比较多的精度丢失。 方法1:
https://yaoxi-std.github.io/2021/12/17/top-poly/
【专题】多项式主要为$FFT$,$NTT$,多项式求逆等变换,可以和生成函数结合起来考计数题。这篇题解中有对多项式乘法的较详细证明过程。 对于使用生成函数判断方案是否合法(而不是统计方案的数量),使用单模数容易被卡,建议在$998244353$,$1004535809$和$469762049$中选取两个,其原根都为$3$。 若题目中要求对奇怪的数取模,一定记得计算模数的原根,有可能不是$3$! 题
https://yaoxi-std.github.io/2021/12/06/sol-at2064/
AT2064 Many Easy Problems 题解题面题目链接 解法对于每个节点$u$,考虑其对$f(i)$的贡献。 正面的贡献不好计算,考虑用总方案数减去不经过$u$的数量,则 \begin{aligned} f(i) &= \sum\limits_{u=1}^{n}{\left(\binom{n}{i} - \binom{n-siz_u}{i} - \sum\limits_{v \in
https://yaoxi-std.github.io/2021/11/25/sol-p7154/
P7154 Sleeping Cows P 题解题面题目链接 解法先分析性质。首先排序不影响答案所以将其排序。若$t_i$所能匹配到的最大$s$的下标为$x$,则如果放弃$t_i$就意味着$s_1$到$s_x$都要被匹配。所以在此思路上$dp$则需要维护两个指针分别指向最小的还没考虑的$s$和$t$,每次选择较小的一边进行更新。不妨将两个数组合并顺序去做。 考虑$dp$,设$dp_{i,j,0/1
https://yaoxi-std.github.io/2021/12/31/sol-p4009/
P4009 汽车加油行驶问题题目题目链接 解法分层图跑dijkstra。 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
https://yaoxi-std.github.io/2021/11/29/sol-p4606/
P4606 战略游戏 题解题面题目链接 解法 圆方树上圆方果 圆方树下你和我 圆方树前建虚树 欢乐多又多 /kk 看到$\sum|S|$于是开始套路地想到虚树。 但是给定的是一个无向图不是一棵树啊…… 所以要想办法把图转化成一棵树,这样的数据结构叫做圆方树。 这里假设你已经学会圆方树了 考虑圆方树的性质。显然对于一对节点$(u, v)$,它们在圆方树上的路径中的圆点(不包括自身)就是删掉后能使得
https://yaoxi-std.github.io/2021/11/22/sol-cf702f/
CF702F T-Shirts 题解题面题目链接 解法首先不难想到朴素的做法,对每个人枚举所有T恤。但是这样显然无法进一步优化。 但是发现可以按顺序枚举所有T恤$i$,对每个人$j$若$v_j \ge c_i$则将$v_j$减去$c_i$,同时将$cnt_j$加一。 下面考虑如何用数据结构优化。我们需要一个可以查找第一个$\ge c_i$并且能支持区间减去$c_i$的数据结构,这个可以用平衡树做到
https://yaoxi-std.github.io/2021/12/17/top-virtualtree/
【专题】虚树这种东西想到要用很容易,关键是建完虚树后怎么做。 虚树题的特征为多次询问且出现$\sum M \le 10^5$一类的数据范围。 如果题目给出的是一张图而不是一棵树,可以思考是否能够结合圆方树等算法转化为虚树。 对于每次询问,将询问的节点和其在原树上的$LCA$单独建出来$dp$即可。
https://yaoxi-std.github.io/2021/12/24/sol-p2766/
P2766 最长不下降子序列问题题面题目链接 解法第一问直接$O(n^2)$求。 第二问根据第一问$dp$的合法转移建立$DAG$图,拆点并求出最大流。即对于$\forall a_j \le a_i, dp_i = dp_j + 1$,连接$j_1 \to i_0$,流量为$1$,且连接每个$i_0 \to i_1$。如果$dp_i=1$则连接$S \to i_0$,$dp_i=ans_1$则连接
https://yaoxi-std.github.io/2022/01/17/sol-p4002/
P4002 生成树计数黑,真$^{\text{TM}}$的黑啊(指题目的颜色)
https://yaoxi-std.github.io/2021/11/22/sol-cf710f/
CF710F String Set Queries 题解又卷出来一道黑题哈哈哈题面题目链接 解法首先看到多模匹配想到AC自动机。 这个强制在线看起来很麻烦的样子,因为AC自动机必须要离线下来才能build。所以就引入一种新的算法叫做“二进制分组”。 二进制分组这个算法一看名字就很$\log$ 维护一个stack,里面的值都是2的次幂。每次操作在栈顶插入一个1,如果栈顶的两个数相同就将其合并,并改
https://yaoxi-std.github.io/2021/11/27/sol-p2495/
P2495 消耗战 题解题面题目链接 解法虚树模版题,不多说。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868
https://yaoxi-std.github.io/2021/11/23/sol-p6144/
P6144 Help Yourself 题解应该是第一次在学校午自习时卷OI(然后sxy走进来看了我一眼啥也没说) 题面题目链接 解法对于这种若干区间求值的题目,肯定先按照左端点或者右端点排个序。 不妨先来考虑对于$k=1$的情况dp状态怎么设。套路地设$dp_i$表示以$i$为当前覆盖的最右端点的联通块数目之和,下面要加入一条线段$[l,r]$,思考插入这条线段对$dp$值的影响。对于$i\lt
https://yaoxi-std.github.io/2022/01/23/sol-p1501/
P1501 [国家集训队] Tree II
https://yaoxi-std.github.io/2021/11/28/sol-p3803/
P3803 【模版】多项式乘法(FFT)题面题目链接 解法模版题了属于是(但我只会写递归的FFT) 为了防止自己忘记就写一下证明吧。 前置知识多项式表示方法系数表示法即 f(x) = \sum_{i=0}^{n-1}{a_ix^i}点值表示法不妨将多项式看成一个$n-1$次函数,从上面取$n$个点来唯一地表示这个函数。 设想一下高斯消元法,就能知道为什么$n$个不同的点就能唯一确定这个函数了。 f
https://yaoxi-std.github.io/2021/11/26/sol-p7155/
P7155 Spaceship P 题解题面题目链接 解法AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
https://yaoxi-std.github.io/2021/12/17/top-suffixarray/
【专题】后缀数组 SA虽然有不少此类题目可以用字符串hash瞎搞 记住代码中每个数组的含义: 数组 含义
https://yaoxi-std.github.io/2021/12/25/sol-p3254/
P3254 圆桌问题题面题目链接 解法较为显然的二分图网络流。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868
https://yaoxi-std.github.io/2021/12/21/sol-p4011/
P4011 孤岛营救问题题面题目链接 解法显然的状压分层$BFS$。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
https://yaoxi-std.github.io/2021/11/24/sol-cf575a/
CF575A Fibonotci 题解题面题目链接 解法$K \le 10^{18}$ 显然矩阵快速幂优化。矩阵转移方程如下: \begin{bmatrix} f_i & f_{i-1} \end{bmatrix} = \begin{bmatrix} f_{i-1} & f_{i-2} \end{bmatrix} \
https://yaoxi-std.github.io/2021/12/27/sol-p3357/
P3357 最长k可重线段集问题题面题目链接 解法在P3358的基础上,多出来了线段与$x$轴垂直的问题,如果和刚刚一样连边就会导致$i \to i$自环的问题。所以进行拆点,如果$l=r$则连接$in(l)$和$out(r)$,否则连接$out(l)$和$in(r)$。 AC代码12345678910111213141516171819202122232425262728293031323334
https://yaoxi-std.github.io/2022/01/15/extra-blog-live2d/#more
Live2D 搭建一日闲来无事,忽觉Live2D。网上找教程,却嫌不够详细。奈何?奈何?只得自己摸索。
https://yaoxi-std.github.io/2022/01/27/trip-wc2022/
WC2022游寄冻零冬眠营几日游,学习了LCT等算法
https://yaoxi-std.github.io/2021/11/26/sol-bzoj2720/
BZOJ2720 列队春游 题解题面题目链接 解法对于这种全排列的题目发现不太好用$dp$。仔细观察发现对于每个人的期望视野都是独立的,可以直接相加,所以直接算$E(c)$表示有$c$个人的高度小于该同学时该同学的期望视野。答案显然$\sum\limits_{i=1}^{n}{E(c_i)}$。 考虑如何求$E(c)$。根据期望公式易得$E(c) = \sum\limits_{i=1}^{c}{i
https://yaoxi-std.github.io/2021/12/17/top-networkflow/
【专题】网络流网络流的话,先口糊好怎么建图,然后复制默写一下板子就好了。 难点其实有两个,一个是如何建图,另一个是输出路径。 如果一道题有许多奇怪的限制,并且$n$和$m$很小,导致$O(n^2m)$可以通过,就可以往网络流方面去想。 其实网络流24题的全称叫网络流和线性规划24题? 费用流需要注意的地方 费用流建反边的$cost$是原来的$cost$的相反数,即需要add(u, v, c, f)
https://yaoxi-std.github.io/2022/01/18/sol-p4726/
P4726 【模版】多项式指数函数(多项式exp)
https://yaoxi-std.github.io/2022/01/07/sol-cf773f/
CF773F Test Data Generation
https://yaoxi-std.github.io/2021/12/30/sol-p4014/
P4014 分配问题题面题目链接 解法不就是个二分图最小/最大权匹配吗,就这也能紫题? AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808
https://yaoxi-std.github.io/2021/12/30/sol-p4012/
P4012 深海机器人问题题面题目链接 解法图蛮好建的,跑MCMF。 AC代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
https://yaoxi-std.github.io/2022/01/25/sol-p4491/
P4491 [HAOI] 染色
https://yaoxi-std.github.io/2022/01/18/sol-p4725/
P4725 【模版】多项式对数函数(多项式ln)
https://yaoxi-std.github.io/2021/12/22/sol-p1251/
P1251 餐巾计划问题题面题目链接 解法题目中已经暗示了要用费用流。 使用流模型,流表示餐巾的数量。但是不易处理餐巾干净与否,所以拆点,将一天拆成两个点,分别表示这天拥有的干净餐巾数量和脏的餐巾数量。为方便表述,分别设为$used_{i,0}$和$used_{i,1}$。 由于每天需要使用$r_i$块餐巾,所以让$used_{i,0}$连向汇点$T$,费用为$0$,流量为$r_i$,表示这天至少
https://yaoxi-std.github.io/2021/12/30/sol-p4013/
P4013 数字梯形问题题面题目链接 解法三次询问分别拆点构建网络流即可。 费用流不能在残余网络上加边重新跑,否则无法保证最大/最小费用。 数组应当开$20 \times 40$而不是$20 \times 20$。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484
https://yaoxi-std.github.io/2021/12/27/sol-p3356/
P3356 火星探险问题题面题目链接 解法问题很容易转化成最大费用最大流,拆点分别考虑即可。 如何输出路径呢?只需要跑一次$dfs$或$bfs$,从$S$到$T$走反边流量非零的边即可,记得每次走完将反边的流量$-1$。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
https://yaoxi-std.github.io/2021/11/22/sol-p4632/
P4632 New Home 题解题面题目链接 解法把询问离线下来,考虑3种操作:新开一家商店,关掉一家商店,查询一个点的不方便指数。 先考虑查询。显然具有二分性,考虑判断一个区间
https://yaoxi-std.github.io/2021/12/05/sol-p4238/
P4238 【模版】多项式求逆 题解
https://yaoxi-std.github.io/2021/12/27/sol-p3358/
P3358 最长k可重区间集问题题面题目链接 解法先离散化,然后在坐标上连接$l_i \to r_i$,花费为$r_i-l_i$,其他边$i \to i+1$流量为$k$,显然这样得到的最大费用最大流就是答案。 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495
https://yaoxi-std.github.io/2021/12/04/sol-cf526g/
CF526G Spiders Evil Plan 题解题面题目链接 解法有意思,很有意思。 首先我们暂时忽略路径必须经过$x$的限制进行思考。容易想到最长的一条路径是树的直径,且其他路径都是一个叶子到另一个叶子的类型,接着发现如果路径必须经过$x$也需要保证最长路径经过直径的其中一个端点(显然最优)。于是想到以直径两个端点为根分别建一棵树,分别求根经过$x$到一个叶子结点的最长路径后$\max$,
https://yaoxi-std.github.io/2021/12/20/sol-p2761/
P276 软件补丁问题题面题目链接 解法这题不是网络流! 状压+最短路即可。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
https://yaoxi-std.github.io/2021/11/25/sol-p3715/
P3715 魔法咒语 题解题面题目链接 解法睡觉去了有空再补 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
https://yaoxi-std.github.io/2021/12/16/sol-p3809/
P3809 【模版】后缀排序 题解题面题目链接 解法模版题不多说 123456789101112131415161718192021222324252627282930313233343536373839404142434445struct suffix_array { int n, sa[MAXN], rk[MAXN], tp[MAXN], ht[MAXN]; void r
https://yaoxi-std.github.io/2021/12/10/sol-p6329/
P6329 【模版】点分树|震波题面题目链接 解法题目里都说了是点分树 发现自己学过的点分树现在已经不会写了,改天来补个点分树的题解吧。 AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
https://yaoxi-std.github.io/2021/12/24/sol-p2770/
P2770 航空路线问题题面题目链接 解法$O(n^3)$的$dp$显然(bushi 考虑网络流的做法。首先每个点经过一次就想到拆点,然后按照原图连边,从$1$到$n$的最大流$\ge 2$就有解。 需要注意测试点$2$是$1$到$n$有连边且只有$1 \to n \to 1$这种走法的,但其实可以不用特判解决,输出路径时如果剩余流量$=+\infty-2$时多跑一次即可(具体见代码)。 AC代码
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.