模板免费网站建设,大数据开发过程,wordpress实现代码块,工作管理app本文将同步发表于洛谷#xff08;暂无法访问#xff09;、CSDN 与 Github 个人博客#xff08;暂未发布#xff09;
本蒟自2025.2.8开始半停课。 任务计划#xff08;站外题与专题#xff09;
数了一下#xff0c;通过人数比较高的题#xff0c;也就是我准备补的题暂无法访问、CSDN 与 Github 个人博客暂未发布
本蒟自2025.2.8开始半停课。 任务计划站外题与专题
数了一下通过人数比较高的题也就是我准备补的题刚好差不多100道题。于是……
摆烂百题计划开始糖丸了
2025.2.8 Network Network of Schools DP优化——矩阵 数论——容斥、二项式反演 DP优化——斜率优化 数据结构——左偏树 数据结构——吉司机线段树 数据结构——李超线段树 2025.1.4 新的一年
今日歌曲New Year’s Day
去年停课的时候是有记日祭的但是有一些是手写的一直都还没有整理好。今天看到一个简单的trick想记下来。于是就又开始写日祭了。 P2831 [NOIP2016 提高组] 愤怒的小鸟 一道远古状压题了。一是指题目本身远古二是指这道题是好久之前就该做的题。看到第一篇题解的trick想起去年暑假集训的时候也有这样一个trick但是忘了是哪道题。这个trick挺简单的但也挺好用状压时如果目标状态是全0或全1并且转移顺序不影响结果那么可以直接从最低位的1或0转移因为最低位最终一定会被转移而顺序又不影响结果所以这样做可以优化掉 O ( n ) O(n) O(n) 的复杂度。其他的按正常状压即可。 [ARC100E] Or Plus Max 今天学了sosdp挺神奇的一种dp。这个题算是板子题吧。只用维护子集的最大值与次大值即可。
今天下午给初二机房的办了一场比赛整体比较顺利。所以没做什么题。比赛链接CWOI-N ER NYR 1。
今天感觉要掉橙了但是Rated的比赛还要等一周。想着把之前那篇被打回的题解改了交了但是晚上写给初二机房的的题解了没空。看明天改吧。
2025.1.10 新的开始
今日歌曲Castles Crumbling
今天考完期末回来一看天塌了掉橙了。明天打一场比赛。
现在终于确定15班后续的各种事项了。又是一个新的开始。
另外我就莫名奇妙地进省选了尽管是体验名额。还有一个有趣的事实 我没有提高组一等奖然而我进了NOIP体验名额我没有NOIP一等奖但我进了省选体验名额。 期待人生中的第一场SCOI希望不要爆零。
2025.1.12 言而无信
今日歌曲Back To December 好吧其实是存货
我果然是一个言而无信的人。踩一脚前天的日祭昨天还是没打比赛。
今天%你赛除了暴力的B和C其它全挂了分。至于A调试的时候把模数写掉了。被暴扣70分呜呜呜。
最终荣获 30 10 30 0 70 30 10 30 0 70 301030070 的高分。 A - 括号序列 题目给一个由左右括号构成的字符串 s s s对于每一个位置 i i i输出有多少个子串满足这个子串是一个合法的括号序列并且 i i i 这个位置在子串中。 题解简单维护前缀与后缀的括号数量即可。忘写该死的模数暴扣70pts。 C - 矩阵删除 题目给一个 n × m n \times m n×m 的 01 矩阵我们想在每一行删除一个元素得到一个 n × ( m − 1 ) n \times (m - 1) n×(m−1) 的矩阵。其中删除的元素的位置 ( i , a i ) ( 1 ≤ i ≤ n ) (i, a_i)(1 \le i \le n) (i,ai)(1≤i≤n)满足 ∣ a i − a i 1 ∣ ≤ k ( 1 ≤ i n ) \vert a_{i} - a_{i 1} \vert \le k(1 \le i \lt n) ∣ai−ai1∣≤k(1≤in)。请问最后能得到多少种不同的矩阵。两个矩阵如果删除的元素位置不同但最后得到的结果相同我们认为是相同的。由于答案很大输出答案对 1 0 9 7 10^97 1097 取模的值。 题解比较板的DP但是赛时思路没那么清晰也没去推式子。分别维护对于每一个位置的方案数以及与旁边位置重合的方案数推出式子后发现全都是求和于是用前缀和维护即可。
2025.1.13 乐极生悲
今日歌曲Wonderland
今天期末考试考完了整体还行语文更是考到了惊人的 127.5 127.5 127.5要知道我之前最高的一次也就 122 122 122 左右而且还经常上不了 120 120 120这次简直是超常发挥。听到成绩的时候直接喜极而泣了。
下午体育课刚好初一体锻放歌放得全是霉霉的歌我还去点了几首。开心。
然而下课要集合的时候我小跑了一下而这下就恰好被足球爆头眼镜镜架直接断掉箍牙的铁丝直接断掉嘴皮直接被铁钉磨得烂掉鼻子被眼镜压了一个印子还在流鼻血。
真是乐极生悲。
2025.1.17 傻子游戏
今日歌曲Foolish One
今天开始上课六天。
昨天听说 jmr 拿了清华一等约。祝贺他。
这周二1.14已经回到15班了。
昨天晚上玩梗发癫还玩了离谱的傻子游戏。达成成就在5.5h里睡够8h。
上午%你赛T1忘了判零挂了10ptsT3是之前做过的一道原题于是赛时死磕最后没调出来。赛时的思路基本上是对的但是没想到容斥又因为我钦定的一个条件有问题导致正确性略有问题最后没调出来。
喜提 90 90 90 分。 A - 串 题目在虱子王国一句话由 n n n 个词组成其中恰好有 k k k 个词是怪的其它的词都不是怪的。众所周知负负得正我们定义一句话的一个区间是怪的当且仅当其中含有奇数个怪词。请构造一句符合条件的话使得其中怪的区间数量最多。 题解发现答案为奇数块乘上偶数块。构造即可。 B - 艺术家 题目给定一个长度为 n 的颜色序列 c c c。再给出 m m m 个区间第 i i i 个区间为 [ l i , r i ] [li, ri] [li,ri]保证任何两个区间都是不相交或包含的关系。在接下来的 q q q 个单位时间内第 i i i 个时间会给定 x , y x, y x,y表示将 c x c_x cx 变为 y y y。请对于每一个区间求出最早的其中所有颜色都互不相同的时间。 题解 保证任何两个区间都是不相交或包含的关系。 所以可以把区间建成一棵树。当一个子区间合法其父区间才有可能合法。在原数轴上维护 l s t i lst_i lsti 表示 i i i 之前第一个颜色与 i i i 相同的点则一个区间内部颜色互不相同等价于 max { l s t i , l ≤ i ≤ r } \max\{lst_i, l \le i \le r\} max{lsti,l≤i≤r}。使用线段树维护。对于 l s t lst lst 的更新用 set 维护。即可。难写死了还没写完。 C - 黑白树 [ARC108F] Paint Tree 题解画一个直径上吊着节点的图讨论一个节点在什么时候可以带来贡献。容斥计算即可。
晚上打了入门赛可以加咕值了。
晚自习最后10分钟记一些话。 我的信竞在进步么看起来好像是的。要是拿现在的我和一年前的我对比那已足以 k k k 倍杀。但……补过的题还是不会做码量大一点的又不愿意写一到晚自习就写不动了于是写一会儿又开始划水。我倒有一个优点就是一般不会去刷水题除了入门赛。但是难一些的题……绿题效率低蓝题想不全于是又看题解紫题几乎无法独立完成。 最终做了的题似乎是白做。 …… 终究还是人的问题。 2025.1.18 正难则反
今日歌曲Wildest Dream
这两天换了头像。
今天上午VP CF Round 997 (Div. 2)。 [CF2056A] Shape Perimeter 计算重叠部分即可。 [CF2056B] Find the Permutation 我们总是建从小节点到大节点的有向边对这个DAG进行拓扑排序。因为我们有时并不想让一个小节点往大节点连边所以用堆维护入度为零的点即可。可恶赛时多测不清空卡了我一发。 [CF2056C] Palindromic Subsequences 挺玄学的构造题。我们希望大概长这样的结构 $$ \underbrace{1,\ 1,\ 1,\ \dots,\ 1,}{a个1}\ 2,\ 3,\ 4,\ \dots, a 3,\ \underbrace{1,\ 1,\ 1,\ \dots,\ 1}{a-1个1} $$ 这样构造出的答案有 a ( a 2 ) 1 a 2 a(a 2) 1 a^2 a(a2)1a2 个可以通过。稍微分讨一下即可。 赛后看了一下题解发现自己好唐 1 , 2 , 3 , … , n − 2 , 1 , 2 1,\ 2,\ 3,\ \dots,\ n-2, \ 1,\ 2 1, 2, 3, …, n−2, 1, 2 [CF2056D] Unique Median 又是一道正难则反计算坏的序列的个数。这道题的trick挺巧妙的但没接触过确实想不出来。发现长度为奇数的序列一定不是坏的所以只考虑偶数长度序列。对于一个序列的中位数 x x x将序列中 ≤ x \le x ≤x 的数化为 − 1 -1 −1其它的化为 1 1 1。若最终区间和为 0 0 0那么这个序列就是坏的。另外要注意去重。维护前缀和即可。 [CF2056E] Nested Segments 组合数学。这个包含或不交的关系恰好和昨天的B差不多。我们想要尽可能多的节点数量那么需要构造成二叉树。这里具体不想证明。对于某一个节点设其儿子数量为 c n t u cnt_u cntu则计算 ∏ C c n t u − 1 \prod C_{cnt_u - 1} ∏Ccntu−1卡特兰数即可。
下午先把E题改了学习了一下吉司机线段树。这东西挺好理解的写起来也很爽但就是又臭又长又难调。 P10639 [BZOJ4695] 最佳女选手 这道题本来是第二道模板题的但因为第一题相当于第二题的子问题所以直接冲着这道题来了。写板子即可。啊啊啊终于还是讨厌上吉司机线段树了啊。
今天整理了一些去年的日祭。还没把手写的整理上去。
2024.1.19 简直糖丸
今日歌曲All You Have To Do Was Stay
今天上午%你赛T1爆零了简直糖丸。一共得了 60 60 60 分的高分。
下午给初二讲题讲得……简直糖丸。
烦球今天最后几乎啥都没干。
啊不是为什么T1爆炸啊。
2024.1.20 简直乐丸
今日歌曲Daylight
昨晚又是在5.5h内睡满8h的一晚。
今天上午VP CF Round 998 (Div. 3)。才做四道糖丸了。 [CF2060E] Graph Composition 赛时就很唐。并查集查联通并算连通块即可。 [CF2060F] Multiplicative Arrays 一道很好的DP组合数学题。赛时推式子感觉推出来了结果赛后再一看伪了。很容易发现 ∑ i 1 l e n [ a i ≠ 1 ] ≤ 16 \sum_{i1}^{len}[a_i \neq 1] \le 16 ∑i1len[ai1]≤16所以DP计算非 1 1 1 元素的情况再用组合数学即可。 [CF2060G] Bugged Sort 这个题就很 “tricky”。bushi自己随便造的词。这篇题解感觉讲得比官方题解还要清晰。可以观察到当 n ≥ 3 n \ge 3 n≥3我们可以任意正常交换两组的位置。因此我们可以将两组数进行翻转。换而言之进行翻转的次数必须是偶数次。这里记翻转次数为 c n t cnt cnt。我们把较小的数放在 a a a较大的放在 b b b。若按 a a a 排序后 b b b 有序那么该组数据有解当且仅当满足这三个条件之一 2 ∣ c n t 2 \mid cnt 2∣cnt ∃ b i − 1 a i , 2 ∣ n , 2 ∣ i \exists b_{i - 1} \lt a_i,\ 2 \mid n,\ 2 \mid i ∃bi−1ai, 2∣n, 2∣i此时可以选择交换奇数组数翻转以改变 c n t cnt cnt 的奇偶性处于“无敌”状态。 2 ∤ n 2 \nmid n 2∤n此时可以翻转全部以改变 c n t cnt cnt 的奇偶性。 否则无解。判断即可。
今天下午看了一个2025年度第一个乐子原帖内部帖简直乐丸。
又一个新梗诞生了 chen_zhe 管理制度错了就要改不能让无辜的人以泪洗面如果管理制度还是这样的话洛谷将会越来越腐败我大不了就棕名我要让洛谷知道瞎诬陷的严重性 2025.1.21 反则难证
今日歌曲deja vu第一首非霉歌曲
今天上午VP CF Round 999 (Div. 1 Div. 2)状态还好。 [CF2061C] Kevin and Puzzle 有点思维的DP题目挺好的。 [CF2061D] Kevin and Numbers 又是一道正难则反。我们很难将 a a a 合并那就把 b b b 中不合法的进行拆分。用 map 维护即可。其实这道题也好证 只是想凑一个小标题罢了。 [CF2061E] Kevin and And 这题有点……难评。为什么字典树过不了啊…… 因为 m m m 很小所以对 b b b 进行状压再将 a a a 的变化量压进堆里选最大的 k k k 个即可。好吧其实不是特别理解。
F 听不懂。
附一张梗图。 这里声明一下不是 jmr 讲得不好而是实在听不懂。
2025.1.22 比特塞特
今日歌曲Maroon
年前最后一天了。
上午%你赛 100 10 60 0 170 , r a n k 4 10010600170,\ rank\ 4 10010600170, rank 4。T3没用 bitset 优化暴扣了 40 40 40 分。可恶。 A - bins [BalticOI 2010 Day2] Matching Bins 差分即可。 C - candies[BalticOI 2010 Day2] Candies 题解。
2025.2.8 水讨论区
今日歌曲Bigger Than The Whole Sky
今天洛谷讨论区关闭了。以后不能水讨论区了。
这个寒假什么也没干。一看进度已经和初二的差不多。但是他们第一遍拉得挺快估计效果不大。
我如果现在回去在那边又吃不饱。于是就只有多肝一肝把之前的进度补上来。
晚上打ABC392。 [ABC392E] Cables and Servers 略考细节的题。先找连通块之后再找每个连通块中的返祖边即无用的边再把连通块连通即可。 可是这题我赛时AC后来突然想到一个hack。还没改烦死了。 [ABC392F] Insert 先写一个 O ( n 2 ) O(n ^ 2) O(n2) 的做法发现可以分块。所以分块即可。赛时想到分块但没写烦死了。
2025.2.9 终于战胜
今日歌曲Holyground
今天做了一些综合题。 [Gym 101982D] Count The Bits 很普通的一道DP题可是赛时都在想组合数学。 d p i , j dp_{i, j} dpi,j 表示到第 i i i 位模 k k k 的值为 j j j 的数中 1 1 1 的数量 c n t i , j cnt_{i, j} cnti,j 表示到第 i i i 位模 k k k 的值为 j j j 的数的数量直接转移即可。 [Gym 103466I] Space Station 神奇搜索题暴搜剪枝略微组合数学即可。 神奇卡常题目拼尽全力2700ms终于冲进3s。 [Gym 102428F] Fabricating Sculptures 神奇DP题。最开始看题解都没看懂一是自己确实不理解是怎么算的二是题解写得比较简略看了好久才看懂。 设 d p i , j dp_{i, j} dpi,j 表示从上往下一层层放当前一共放了 i i i 个最下面一层放了 j j j 个的方案数。有方程 d p i , j ∑ k 1 j d p i − j , k ∗ ( j 1 − k ) dp_{i, j} \sum_{k 1}^j dp_{i - j, k} * (j 1 - k) dpi,j∑k1jdpi−j,k∗(j1−k)希望没写错。将这个式子拆开再维护前缀和即可。开了long long见祖宗。 [Gym 104172F] Sum of Numbers 很有趣的一道题。很容易发现两个相邻字符串长度之差的绝对值为 0 0 0 或 1 1 1。暴搜即可。 赛时的想法是将原字符串平均分再给 0 0 0 或 1 1 1 的偏移。可是偏移少了一些虽然没 TLE 但一直 WA拼尽全力无法战胜。 赛后再改一改拼尽全力终于战胜。
今天本来说再补补昨天的 F改改昨天的 E结果今天的第三题看半天看不懂昨天的 E 和 F 都没做。
最终今天做了四道题。
感觉心态有点崩。尤其是看第三题的时候。
……
