Mx
  • 2024-11-20NOIP2016 提高组 蚯蚓
    NOIP2016提高组蚯蚓算法一容易想到用优先队列维护最大值,但是有“其余蚯蚓长度增加\(q\)”这个条件,考虑怎么快速地处理。我们把增加的总长度记为偏移量\(delta\)。每个数在加入前,把不产生贡献的时间的偏移量减去,再存进去就可以了。时间复杂度\(O(mlogn)\),用priority_queu
  • 2024-11-16【学习笔记】Segment Tree Beats/吉司机线段树
    链接区间最值操作HDU-5306支持对区间取\(\min\),维护区间\(\max\),查询区间和。很容易想到一个暴力,我们每一次找出这个区间的最大值\(mx\),如果\(mx>x\),那么暴力修改这个位置的值,否则已经修改完毕,退出,时间复杂度为\(O(n^2\logn)\)。打一打补丁,对线段树上的每一个区间维
  • 2024-11-16Codeforces Round 987 (Div. 2)
    CodeforcesRound987(Div.2)总结A常见的套路,将一个序列变为不下降序列所需要改变的值的最小数量,考虑最大能保留多少个,显然是求最长上升子序列,而这题给出的\(a\)序列保证不上升,所以只需要考虑相同长度的一段。#include<iostream>#include<cstdio>#include<cstring>#
  • 2024-11-16CF2031D 题解
    原题链接最后悔的一集,感觉D\(<\)everything。考虑由确定的点推出其他点的答案,发现最高点的答案是确定的,设其位置为\(x\)。然后根据题目定义,发现可以分成\([1,x-1],[x,n]\)两个区间,\([x,n]\)答案均为\(h_x\)。对于\([1,x-1]\)区间,我们找到第一个\(>[x,n]\)区间最小
  • 2024-11-15[CEOI2023] The Ties That Guide Us 题解
    Description你用销售机器人的利润雇佣了一名助手,现在你准备好去拿走装有CEOI奖章的保险箱了。保险箱位于一所由\(n\)个房间所组成的大学建筑内,这些房间由\(n-1\)扇门连接。每个房间都可以从其他任何房间到达,且每个房间最多与\(3\)扇门相连。你和你的助手都有描述建筑物
  • 2024-11-14MX 2025--炼石计划 NOIP 模拟赛 #20
    打得抽象。T3,T4放俩难的板子。由于是MX的题,就不放题意了。邻间的骰子之舞发现复制操作不会超过\(64\)次,而粘贴操作肯定是越均匀越好,直接二分暴力跑就行了。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#
  • 2024-11-13SS241113C. 数据结构 (struct)
    SS241113C.数据结构(struct)题意有\(n\)个数,\(m\)个操作,\(n,m,a_i\le10^6\),每次操作给区间\([l,r]\)的所有数字加\(1\),然后输出全局颜色数量,操作独立。思路感觉不好想,对我来讲有点难,需要更聪明的脑袋和丰富的想象力。首先\(O(n\sqrt{n})\)的莫队做法是显然的,假设
  • 2024-11-13P8314 [COCI2021-2022#4] Parkovi
    最大值最小是二分答案的特征。二分完后每个公园可以覆盖距离不超过\(k\)的领域,要覆盖整棵树。二分完后需要check。最可能的路线是贪心和dp。好像本质上都存储了可能成为答案的组合的部分信息,但贪心确定了这个组合当前的唯一性,dp并没有,只能保证最优解一定属于被划分出来的某
  • 2024-11-12mx s26
    A\(n\)是偶数,\(a,b,c\)都是素数,平方不改变奇偶性,则\(a,b,c\)中有一个偶数或三个偶数,但偶素数只有一个,所以不妨令\(a=2\),枚举\(b\leq\sqrtn\)就可以算出\(c\)。需要判断\(b,c\)是否是素数,可以用线性筛或是埃氏筛做到这点。为了避免常数过大,最好只枚举\(b\)为素数的
  • 2024-11-12MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构,先把下标转成从\(0\)开始,以方便用同余描述位置。倍增。用二元组来表示位置:\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,
  • 2024-11-11SA SAM
    发现很久不写字符串所有模板都忘了,还是要复习一遍。SA后缀排序令\(sa_{i}\)表示排名为\(i\)的后缀编号,\(rk_i\)表示后缀\(s[i:n]\)的排名。有两种求法:朴素倍增,时间复杂度\(\mathcalO(n\log^2n)\)。每次更新两个关键字,暴力sort,重新编号\(sa\)。基数排序,时间复
  • 2024-11-11[P4344 [SHOI2015] 脑洞治疗仪]
    P4344[SHOI2015]脑洞治疗仪说句闲话:模拟赛因为没注意push_up痛失70ptsSolution:感觉比较好写的线段树,维护几个变量:\(lmx,rmx,mx,cnt\),lmx表示该区间从左端点开始的最长连续脑洞的长度,rmx,mx类似.cnt表示该区间内有多少个点是0然后注意一下push_up:voidpush_up(Tree
  • 2024-11-10[NOIP2018] 赛道修建
    好题好题,太棒了这题!直接想是十分困难的,你连\(dp\)状态都想不出合理的,因此考虑二分答案,转化成一个判定问题。下文\(d\)表示二分出的答案。设\(sum_i\)表示\(i\)子树内的合法路径数,那他就一共分为两部分:来自于\(sum_{son}\),直接累加即可。经过\(i\)的路径。我们
  • 2024-11-10C. 小红打怪 (python解)-牛客
    C.小红打怪(python解)-牛客原题链接:C.小红打怪问题分析:小红的全体打击技能对所有怪物造成1点伤害。队友1的单体打击技能可以对任意单个怪物造成1点伤害。队友2的范围攻击技能可以对相邻的两只怪物分别造成1点伤害(可对已死亡的怪物使用)。思路:设定一个函数check(mx)
  • 2024-11-10MX S28
    A对于一个子矩阵\((x_1,y_1),(x_2,y_2)\),其元素和为\(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}S_i\cdotS_j=(\sum_{i=x_1}^{x_2}S_i)(\sum_{j=y_1}^{y_2}S_j)\),\(O(n^2)\)枚举一下\(S\)的所有子区间的和放进一个桶里再检验一下即可。即对于一个子区间和为\(S_1\),需要累加和
  • 2024-11-08[TAD] Triangles of Absolute Differences-反帕斯卡三角形
    [IMO2018]TrianglesofAbsoluteDifferences-反帕斯卡三角形前言叠甲笔者不是学数竞的,在此感谢我的数竞生为我讲解题目。笔者学艺不精,且知识面浅薄。所以本文章仅用作搞抽象(争取练就惊人注意力。正文一、引入看完这道题目的要求,相信大家都能想起一个很熟悉的东西:
  • 2024-11-07【线段树合并】雨天的尾巴
    题意给一棵\(n\)个节点的无根树,共\(m\)次操作,每次操作是一个三元组\((x,y,z)\),表示路径\((x\toy)\)全部发一袋类型为\(z\)的救济粮。问最后每座房子存放最多的是哪种救济粮。思路看到树上路径的操作,首先考虑差分,但本题的特殊之处在于每个节点有\(10^5\)种不同的
  • 2024-11-06IOI 2011 Race
    [IOI2011]Race题目描述给一棵树,每条边有权。求一条简单路径,权值和等于\(k\),且边的数量最小。输入格式第一行包含两个整数\(n,k\),表示树的大小与要求找到的路径的边权和。接下来\(n-1\)行,每行三个整数\(u_i,v_i,w_i\),代表有一条连接\(u_i\)与\(v_i\),边权为\(w_i\)
  • 2024-11-06[ARC087F] Squirrel Migration
    模拟赛题,不知道为什么放在最后一题,感觉评分过高了。首先是经典问题,最大值是\(\sum\min(siz,n-siz)\),证明考虑每条边上界。考虑证明的构造,对于重心的每个儿子拉出子树,求出子树大小即可转为序列上问题:每个点不跟内部匹配即可满足最大,容易证明充要。朴素dp发现怎么也避不开两
  • 2024-11-05Tree
    P4178Tree题目描述:给定一棵n个节点的树,每条边有边权,求出树上两点距离小于等于k的点对数量。数据范围:\(1≤n≤4×10^4\)\(1≤k≤2×10^4\)说句闲话感谢著名CB大师red_fire倾情推荐%%%在机房三个人唇枪舌剑了一小会,我们的CB大师直接开搞线段树,而仔细研读了数据范围的本
  • 2024-11-01Leetcode—624. 数组列表中的最大距离【中等】
    2024每日刷题(198)Leetcode—624.数组列表中的最大距离实现代码classSolution{public:intmaxDistance(vector<vector<int>>&arrays){intm=arrays.size();intn=arrays[0].size();intmn=arrays[0][0];intmx=ar
  • 2024-10-30CF980-Div2-D
    CF980-Div2-D题意从\(1\)开始决策,若选当前数,则累计贡献\(a[i]\)并跳到\(j\)位置,\(j\)是\(\lti\)且没有决策过(包括选了和没选)的最大位置(操作\(1\))。若不选当前数,则跳转到\(j\)位置,\(j\)是\(\leb[i]\)且没有决策过(包括选了和没选)的最大位置(操作\(2\))。求最大得
  • 2024-10-29「KTSC 2024 R2」跳跃游戏 题解
    睡了一觉,打呼噜被老胡叫醒了/lh睡醒场切,vectorfind是\(O(size)\)的调了40min/fn思路考虑最终得到了\(\mathcalO(Q)\)个连续的\((len,val)\)代表线段长度和线段的\(A_i\),可以用map简单得到。结论:必然存在一种方案,使得在\((i-K,i]\)中必然存在跳跃的起点
  • 2024-10-27P11234 [CSP-S 2024] 擂台游戏 题解
    P11234[CSP-S2024]擂台游戏题解前言作者在考场上用了约1h把前三道题做完了,然后用了约半小时想了带\(\log\)的做法,但是我决定放手一搏去想线性的做法,于是又想了有1h之后觉得想到了正解,然后我就一直写到了考试结束,但是最终没有调出来遗憾离场,因此写个题解来纪念一下。