- 博客(40)
- 收藏
- 关注
RSS订阅原创 [luogu9141] [THUPC 2023 初赛] 乱西星上的空战 -大模拟 - 计算几何
传送门：P9141 [THUPC 2023 初赛] 乱西星上的空战大家好我又来了，这次带给大家的依然是THUPC的传统艺能大模拟~个人点评：这题是我个人写完并通过的算法竞赛中的大模拟题中最长的一道，但可能并非最难写的。甚至在我看来，在你有一个相对完整的三维计算几何模板的情况下，码长只有这题三分之一的P7147 [THUPC2021 初赛] 麻将模拟器的实现难度都不低于这题。究其原因，这题的模块化特别强，各个模块之间基本上相对独立，特别适合进行抽象及使用各种oop技巧，尤其是在题目已经天然地给你划分好9个阶段
2023-03-10 14:29:45
678
原创 NOI2022代码
这里是liuzhangfeiabc的NOI2022代码。包含两天t1、t2的非官方std代码（已在洛谷上提交通过）。本来想在上一篇题解里放代码，但是这样文章就太长了，所以新开一篇文章放代码。
2022-08-30 01:32:53
538
原创 NOI2022 题解
这里是liuzhangfeiabc的NOI2022题解。目前更新了两天的t1和t2，两天的t3实在没心情去研究了……注：非官方题解，不保证绝对正确，做法不一定是官方做法。
2022-08-30 01:19:44
2586
原创 [loj3834] [IOI2022] 最罕见的昆虫 - 交互 - 二分
传送门：[https://loj.ac/p/3834](https://loj.ac/p/3834)题目大意： $n$ 个物品，每个物品属于一种类别。你需要维护一个物品集合，初始为空。支持操作：将某个不在集合中的物品放入集合；将某个集合中的物品移出集合；查询集合中出现次数**最多**的种类的出现次数。你需要回答：所有物品中出现次数**最少**的种类的出现次数。要求插入、删除、查询操作的次数分别不超过 $3n$ 次。...
2022-08-29 18:02:00
225
原创 [loj3831] [IOI2022] 囚徒挑战 - 构造 - 策略游戏 - 趣题
一篇仿M67风格的题解传送门：[https://loj.ac/p/3831](https://loj.ac/p/3831)看守打算和监狱里的足够多（但有限）名囚犯做一个游戏。看守在两张纸条上分别写了一个不超过 $n$ 且不相等的正整数，不妨记作 $x$ 和 $y$ ，把它们放在一个单独的房间里。房间里还有一块黑板，最初写有一个数字 $0$ 。接下来，看守将按照随机顺序依次叫一名囚犯进入房间，每名囚犯不知道他是第几个被叫的，也不知道先前有哪些人被叫到过，但保证每名囚犯恰好都会被叫到一次。每名囚犯进入房间后
2022-08-11 00:34:19
528
原创 [luogu8353] [SDOI2022 d2t2] 无处存储 - 卡空间 - 树分块 - 虚树 - 随机算法
传送门：P8353 [SDOI/SXOI2022] 无处存储免责声明：我不是本题的出题人。出题人是小N和小 Ω\OmegaΩ ，跟我小Z有什么关系？题目大意：给定一棵树，点有点权，支持链加、链求和。强制在线。（先别急着说“为什么省选放模板题”，接着往下看。）数据范围： n≤7×106，q≤5×104n \leq 7\times10^6，q\leq 5\times 10^4n≤7×106，q≤5×104。时空限制：5s, 64MB5s,\ 64MB5s, 64MB 。——是的
2022-05-17 01:09:29
508
原创 [luogu8352] [SDOI2022 d2t1] 小N的独立集 - 计数 - dp套dp
传送门：P8352 [SDOI/SXOI2022] 小 N 的独立集题目大意：给定一棵 nnn 个点的树，每个点的权值在 1∼k1\sim k1∼k 之间，问有多少种权值的方案使得整棵树的最大权独立集大小为 mmm ，对 m=1∼nkm=1\sim nkm=1∼nk 分别求解。因为是全场最简单（果然以我的水平只能出得出来这种送分题了吗），废话不多说直接上题解。我们都知道树上最大权独立集的求法：f[x][0/1]f[x][0/1]f[x][0/1] 表示以 xxx 为根的子树，根是否被选择的答案。而这
2022-05-16 22:25:48
316
1
原创 NOIP2021 题解
T1：两人轮流报数，规定所有含有 777 的数字及其倍数都不能报出，每次询问给出上一个报的数，求下一个报的数是多少（或判断上一个报的数不合法）。询问次数 T≤2×105T \leq 2 \times10^5T≤2×105 ，数字范围 n≤107n \leq 10^7n≤107 。题解：直接模拟题意即可。从小到大处理出所有含有 777 的数，这可以通过一个递推关系来实现：设 f(n)f(n)f(n) 表示数字 nnn 中是否含有 777 ，则有 f(n)=f(n/10) ∣ (n%1
2021-11-23 01:47:20
1474
原创 关于FFT中IDFT变换的推导：来自数学分析和线性代数的降维打击
注：考虑到对高中生友好的需要，本文尽量减少了对于高数和线代等前置知识的依赖。如果你是正在学习FFT的oi选手，可以放心食用。我当年在学习FFT的时候，大部分文章都会在讲完DFT的过程之后说“对于IDFT，我们只需要把单位根全部取个共轭，最后把结果除以 nnn 就行了”之类的话，当然它们会对此做出解释：DFT的过程本质上就是在做一个线性变换，我们对着线性变换的矩阵求个逆折腾一下就能变换回去了。设原始的多项式是 f(x)=a0+a1x+a2x2+...+an−1xn−1f(x) = a_0 + a_1x +
2021-10-09 20:36:11
1145
原创 [luogu7736] [NOI2021] 路径交点 - 线性代数 - 矩阵乘法 - 行列式
传送门：https://www.luogu.com.cn/problem/P7736题目大意：有一张kkk层的图，每相邻两层之间有一些有向边，保证第一层和最后一层节点数一样多（均为nnn个）。定义一组合法的路径形如：共nnn条路径，第iii条从第一层第iii个点出发，连向最后一层的某个点，且所有路径终点以及中间经过的所有点均互不相同。定义两条路径的“逆序数”是：如果两条路径经过的点依次是p1,...,pkp_1,...,p_kp1,...,pk和q1,...,qkq_1,...,q_kq1,..
2021-07-27 18:09:42
257
原创 [luogu7735] [NOI2021] 轻重边 - 数据结构 - LCT - 树链剖分
传送门：https://www.luogu.com.cn/problem/P7735题目大意：给你一棵树，最开始树上的边都是轻边，支持操作：1 x y1\ x\ y1 x y：把x∼yx \thicksim yx∼y路径上的边都变成重边，并把与这条路径相邻的边都变成轻边；2 x y2\ x\ y2 x y：查询x∼yx \thicksim yx∼y路径上有多少条重边。我寻思这不是经典题吗？NOI出原题？？？这个操作让我
2021-07-27 12:56:31
388
原创 [loj3528] [IOI2021] 位移寄存器 - 交互（提答？） - 高精度 - 并行计算 - 排序算法
orz dls AK IOI2021传送门：https://loj.ac/p/3528Warning: 此题非常有（du）趣（liu）题目大意：你有个长度为位的寄存器，一开始号寄存器里存了个位的数，你要通过寄存器的复制、赋值、按位与、按位或、按位异或、按位取非、左移、右移、加法操作实现对这些数进行求最小值或排序。这是今年（2021年）IOI的d2t3，我甚至不知道该怎么把它分类……这显然是个非传统题，也许可以勉强算个交互，但是这一点也不“交互”好吧，因为你除了最开始的...
2021-06-30 23:30:46
469
2
原创 [loj3464] [luogu7325] [WC2021] 斐波那契 - 斐波那契数列 - 递推 - 数论 - 循环节 - 扩展欧几里得(exGCD) - 扩展中国剩余定理(exCRT)
题目链接：https://www.luogu.com.cn/problem/P7325题目大意：定义如下“广义斐波那契数列”：。共有组询问，每组给出和，对于某个固定的模数，求最小的，使得。观察数据范围大概能猜出几点：1、是固定的，因此很可能要预处理一堆东西来实现单组快速查询；2、有一堆形如“是质数”“不含平方因子”之类的部分分，这在数论题中是很强的暗示——很有可能需要对每个质因子处理之后CRH合并，同时处理质数幂可能比处理质数复杂一些。斐波那契数列有一些很休闲的性质，比如我们通常会把
2021-02-07 18:16:09
349
原创 [loj3463] [luogu7324] [WC2021] 表达式求值 - 表达式树 - 计数
题目链接：https://www.luogu.com.cn/problem/P7324题目大意：给你个长度为的数组和数组之间的两种运算：对应位置元素取和取。再给你一个表达式，其中包含数组编号、括号和运算符（可能为两种运算之一或“”）。求：对于每一种把所有的“”替换成某种运算的方案得到的数组所有元素的和求和。题目的数据范围很诡异，和串长都只有，而更是只有。当然对此的“解释”是这样的数组编号就只有一个字符，处理表达式会比较容易。但是如果能开到更大的话处理起来也没难到哪去啊（就加一种情况的特判
2021-02-06 23:58:34
239
1
原创 [loj3462] [luogu7323] [WC2021] 括号路径 - 图论 - 等价关系 - 线段树合并 - 启发式合并
传送门：https://www.luogu.com.cn/problem/P7324好久没写题解了，最近放假闲得无聊，写了写这两天WC的题，顺手来一发题解。题目大意：给定图，每条边上正反方向分别标有某种括号的左括号和右括号，问有多少点对之间存在能组成合法括号序列的路径。这道题的关键是：这个“存在合法括号序列路径”到底有什么性质？如果我们在上建立关系：当且仅当点到点存在合法括号序列路径。方便起见这里姑且把的限制去掉。那么我们惊奇地发现，居然是个等价关系：（1）自反性：自己到自己是空串，
2021-02-06 23:13:49
349
原创 [luogu7147] [THUPC2021 初赛]麻将模拟器 - 大模拟 - dp
传送门：https://www.luogu.com.cn/problem/P7147
2020-12-29 15:58:27
5940
1
原创 [luogu5362] [SDOI2019R2 d2t3] 连续子序列 - 字符串 - 找规律 - 结论题 - 记忆化搜索
传送门：https://www.luogu.org/problemnew/show/P5362题目大意：有一个01串tm，满足tm(0)=0，tm(i)=tm(i>>1)^(i&1)。给定01串s和整数k，问有多少个本质不同的01串t满足：t是tm的子串，s是t的前缀，t的长度是|s|+k。全场无人ac的找规律神题。关于tm序列，有很多种解释方式，比如每个数的二进制...
2019-05-09 21:28:00
551
原创 [luogu5363] [SDOI2019R2 d2t2] 移动金币 - 博弈 - 阶梯nim - 组合计数 - 数位dp
传送门：https://www.luogu.org/problemnew/show/P5363题目大意：1×n的棋盘上有m个棋子，两个人轮流操作，每次可以将一枚棋子向左移动，不能跨过前面的棋子，也不能与其他棋子重叠，不能操作者输。给定n,m，求有多少种局面先手必胜。说实话看到这个题的我是懵逼的，喵喵喵？这不是原题吗？我团队里还有这个题的说。再仔细一看，喵喵喵？数据范围这么小？原题n<...
2019-05-09 21:26:02
466
原创 [luogu5361] [SDOI2019R2 d2t1] 热闹的聚会与尴尬的聚会 - 图论 - 构造 - 独立集
传送门：https://www.luogu.org/problemnew/show/P5361题目大意：给定无向简单图，你需要构造如下两个点集：1、使得其点导出子图中度数最小的点尽量大。设这个度数为p。2、求一个尽可能大的的独立集。设独立集大小为q。则需要满足：n/(p+1)<=q，n/(q+1)<=p。这里的除法是下取整。哈？最大独立集？！神仙sdoi居然出npc...
2019-05-09 21:23:34
360
原创 [luogu5360] [SDOI2019R2 d1t3] 世界地图 - 图论 - 最小生成树 - kruskal重构树 - 并查集
传送门：https://www.luogu.org/problemnew/show/P5360题目大意：给定网格图，左边界和右边界相连，每次询问挖掉一个横坐标区间之后其余部分的mst。先%一下现场切掉这题的ckw队长。每次询问可以看作把一个前缀和一个后缀拼起来做mst，因此我们可以先预处理出每个前缀和后缀的一些信息，再想办法把两棵mst拼成一棵。最简单的想法就是用lct维护动态ms...
2019-05-09 21:20:59
292
原创 [luogu5359] [SDOI2019R2 d1t2] 染色 - 组合计数 - dp - 线段树
传送门：https://www.luogu.org/problemnew/show/P5359题目大意：2×n的格子，用c种颜色进行染色，要求相邻的格子不能用相同的颜色，一些格子已经事先涂好了颜色，求方案数。先%一下现场切掉这题的rqy。我这里的做法与rqy的不同，我没看过官方题解不过我猜这个做法应该类似于官方题解的思路。先考虑一个最朴素的dp。设f(i,j,k)为前i列，最后一列...
2019-05-09 21:18:25
333
原创 [luogu5358] [SDOI2019R2 d1t1] 快速查询 - O(1)数据结构 - 线性求逆元
传送门：https://www.luogu.org/problemnew/show/P5358题目大意：给定初始全0的序列，支持：单点修改，全局加，全局乘，全局赋值，单点查询，全局查询。要求每次操作O(1)。现场平衡树过了的神仙深受我一拜。注意到操作只有单点和全局，而且虽然序列很长但是修改的点最多1e5个，我们就可以把所有的点拎出来重标号。我们发现，其实最麻烦的地方是怎么查询单点的...
2019-05-09 21:15:53
342
原创 SDIO2019R2游记＆入坑2周年感想
2017.5.8~2019.5.8入坑两年了，感想颇多。“黄金色的树林里分出两条路，可惜我们不能同时去涉足，但我们却选择了，人迹罕至的那一条，这从此决定了我们的一生……”选择了oi，就注定选择了一段与众不同的高中生活。不上课还是挺爽的。跟机房里各位julao从初中甚至小学就开始搞不同，我是完完全全地高中0基础开始。当时选择搞oi，一方面是因为自招完了没事干，正好...
2019-05-08 19:22:21
658
2
原创 趣题：怎么从一帮女装大佬中分辨出谁是真妹子？（大雾）
尝试一篇仿m67风格的博客。你受邀参加一场女装聚会，除了你和聚会组织者之外还有n个人参加，这些人你都不认识。组织者告诉你：这场聚会上所有人都会穿女装，但其中有一部分是真妹子，另外一些则是女装大佬。作为直男，你的目的显然是去欣赏妹子而不是女装大佬。然而到现场之后你慌了——单身多年的你竟然分辨不出哪些人是妹子。泡到一个女装大佬显然是一个让人想想就菊花一紧的事，你又不想白来一趟，于是赶紧向组...
2019-03-12 11:02:05
1184
2
原创 [bzoj3553] [luogu4332] [SHOI2014] 三叉神经树 - lct - 动态dp
传送门：https://www.luogu.org/problemnew/show/P4332题目大意：给定一棵树，每个点有3个输入信号的接口（连向外部或儿子）和1个输出信号的接口（连向父亲），1号点是根。信号是0或1。一个点输出的信号是输入信号中较多的那个。每次修改一个外部接口传入的信号，输出1号节点输出的信息。看到网上很多log^2甚至log^3的做法，这里放一个lct的一个log做法...
2018-11-20 21:18:50
368
原创 [zoj4058] [2018ACM青岛站·A] Sequence and Sequence - 高精度 - 数学
传送门：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5815&HPPROTID=f0b51c92个人第一场ACM，虽然6题Ag滚粗但还是非常值得回味的。虽然预料到会有高精度题，但是题目的疯狂程度还是超乎想象（当然没有队伍现场ac了）。题目大意：定义p序列为{1,1,2,2,2,3,3,3,3……}即连续2...
2018-11-19 17:26:48
739
1
原创 [ioi2018 d2t2] highway - 交互题 - 二分
题目大意：给定n个点m条边的无向简单连通图，图上有s,t两个点，你并不知道是哪两个，每条边的边权可以是a也可以是b(a<b)。每次你可以指定每条边的边权到底是a还是b，交互库会返回此时s到t的最短路长度，要求用不超过50次询问求出s和t。n<=90000,m<=130000。交互题历来是ioi的一大特色。今年的这道题给人的感觉跟去年的d1t1,d2t2两道交互的风格比较像，当...
2018-09-20 15:53:23
546
原创 [loj2864] [ioi2018 d1t2] seats - 线段树
传送门：https://loj.ac/problem/2864作死尝试这道全世界只有1人ac的神题。先%一波dsgsjk，这位吊打全世界的julao可能是全世界第二个做出这题的现役oi选手。题目大意：给定一个n*m的矩阵，矩阵中不重不漏地分布着0~n*m-1的元素。称一个大小为s的连续子矩阵是好的当且仅当其中不重不漏地出现了0~s-1的元素。每次交换矩阵中的两个元素，查询当前有多少个好...
2018-09-13 09:29:29
786
3
原创 [bzoj3153] sone1 - toptree
传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3153。AC这道超级工业题留念。花了我整整一个下午写代码+一个上午调代码……题目大意：维护一棵有点权的有根树，支持：linkcut，换根，对子树/链的赋值/加/询问sum/min/max。一看12个操作就知道是大毒瘤题。话说前几天我们某场校内模拟赛有位学长直接搬了这题原题上去...
2018-09-12 13:20:24
2712
原创 [ioi2018 d2t1] doll - 有趣的构造题
花了4个小时终于搞懂了这题……膜拜现场各种1h以内a掉的julao。这道题全场大概30几人ac，难度不算太高也不算太低，算是d2最简单，全场第二简单的题。你要构造一张图，其中起点编号为0，有m个给定的普通点，编号为1~m，你还可以添加若干个特殊点（数量自己决定，这里设为s个），编号-1~-s。所有点可以有任意多条入边，但起点普通点只能有1条出边，特殊点只能有2条出边。每个特殊点满足：当...
2018-09-06 21:56:29
801
原创 [ioi2018 d1t3] werewolf - kruskal重构树 - 二维数点 - 主席树
题目大意：给定n个点m条边的无向简单连通图，k次询问，每次给出两个点u,v和两个限制l,r，询问是否有一条从u到v的简单路径满足：路径上有一个分界点，前一半经过的点（包括u和分界点）的编号都>=l,后一半经过的点（包括v和分界点）的编号都<=r。全场大约十几人ac，我们全机房一块研究了一天终于搞出了一个像样的做法。（顺便%一下某ckw同学，看到题面16分钟直接秒掉！）这么工业的...
2018-09-06 20:43:44
551
原创 [loj2863] [ioi2018 d1t1] combo - 有趣的交互题
传送门：https://loj.ac/problem/2863斗胆来一发ioi题解。今年的d1t1是一道交互题。喜欢出交互题是ioi的一大特色之一，而国内的正式比赛中还是很少见到交互题的身影的（印象中只有wc2016和wc2018有交互题）。虽是ioi，但难度不算大的题还是会出现的，主要也是要考虑到世界各国选手的整体水平。本题算是今年6道题中最简单的一道，全场大约有一半的选手都成功ac...
2018-09-06 20:21:18
609
原创 luogu P4774 [NOI2018] 屠龙勇士 - 数论 - exgcd - 扩展crt
传送门：https://www.luogu.org/problemnew/show/P4774因为没a掉此题而cu滚粗的菜鸡来报个到。首先我们可以显然地发现对于每条龙，攻击它用到的剑是唯一确定的，用一个multiset预处理即可，记作di。需要强调两点：第一是不要用成set，第二是虽然里面存的元素是int但是你会用ll去查询所以还是要开ll，没错我的25分就是这么丢的……首先pi=...
2018-07-20 18:58:00
469
原创 luogu P4769 [NOI2018] 冒泡排序 - 计数
传送门：https://www.luogu.org/problemnew/show/P4769题目大意：考虑用冒泡排序的过程求一个排列的逆序对数，由于将pi从i位置移动到pi位置至少需要移动|i-pi|次，而每次交换最多实现2次正向移动，所以逆序对数的下界是1/2 sigma |i-pi|，当然这个下界并不总能达到（比如3 2 1有3个逆序对而计算得到的下界是2），求：给定n和排列p，满足字典...
2018-07-19 14:43:49
1157
1
原创 luogu P4768 [NOI2018] 归程 - 最短路 - 并查集 - kruskal重构树
传送门：https://www.luogu.org/problem/show?pid=4768题目大意：给定无向图，每条边有长度和高度，多次询问从某个点pi出发到1号点的最短路，并给出参数qi，规定所有能从pi出发仅通过高度>qi的边到达的点视为可以不耗费代价地到达。考场上写了一堆部分分，在距离比赛结束还有7分钟的时候想出了正解然而没时间写了……80分滚粗嘤嘤嘤。正解好像叫做“k...
2018-07-19 14:25:26
614
2
原创 Texas hold 'em - 模拟
传送门：https://jag2012autumn.contest.atcoder.jp/tasks/icpc2012autumn_b一副去掉大小王的扑克牌，你和对手分别摸2张作为手牌，桌面上还有3张已经亮开的牌和2张未亮开的牌。在亮开剩余2张牌后，你和对手分别从手牌+桌面上的牌这7张中选择5张，按规则进行比较，较大的一方获胜。比较规则为：同花顺>四条>葫芦>同花&g...
2018-06-29 13:07:39
2030
原创 codeforces 331D3 Escaping on Beaveractor - 线段树 - 扫描线 - 倍增
传送门：http://codeforces.com/contest/331/problem/D3第一篇blog送给这道折磨我一上午的码农题。题目大意很简单：b*b的平面上有n条互不相交且平行于坐标轴的有向线段，运动到线段上之后运动方向会改变成沿着线段的方向。有q组询问，每组给出起始坐标，出发方向和运动距离，求最后停在哪个位置。如果中途会离开平面范围内就输出从哪个位置离开的。一个自然...
2018-06-29 12:36:17
372
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人