iOS
2024.7.26 集训笔记
1. 单调栈 给定一个长度为 (n) 的数列 (a)，对每个数字求出其右/左边第一个值大于等于它的数字的位置。 考虑从左到右扫整个序列，维护一个栈，里面存放可能成为答案的数字，当遍历到一个新的数 (a_i) 的时候，可以发现栈中 (leq a_i) 的数就再也不可能成为答案了，那就把它们弹掉，此时栈顶就是答案，之后加入 (a_i)。 由于栈中的元素是单调不升的，故得名单调栈。 这么做的复杂度：
Nordic Collegiate Programming Contest (NCPC 2021)（SMU 2024 ICPC网络赛选拔赛）
Nordic Collegiate Programming Contest (NCPC 2021)（SMU 2024 ICPC网络赛选拔赛） A Antenna Analysis 思路 原式可拆成： [(x_i-x_j)-c(i-j)=(x_i-ccdot i)+(-x_j+ccdot j) ]分别维护下两个的最大值即可。 代码 C Customs Controls 思路 隔得久有点忘了，大致思
SMU Autumn 2024 Personal Round 1
SMU Autumn 2024 Personal Round 1 前言 拉了，后面有空再补补。 A. Lex String 思路 排序后取最小，记录连续取了几个，不要超过 (k) 个即可。 代码 B - Creep 思路 前面用01或者10串填满，后面放剩下的。 代码 C. Mystic Permutation 思路 数据小，直接暴搜即可。 代码
【前缀和+开区间二分】codeforces 1187 B. Letters Shop
题意 第一行，输入一个正整数 (n(1 leq n leq 2*10^5))，代表字符串 (s) 的长度。 第二行，输入一个字符串 (s)。 第三行，输入一个正整数 (m(1 leq m leq 5*10^4))，代表接下来要输入的询问次数，对于每次询问：输入一个字符串 (t(1 leq |t| leq 2*10^5))，并保证 (sum_{i=1}^m{|t_i|} leq 2*10^5)。 保
The 2020 ICPC Asia Shenyang Regional Programming Contest Northeastern University（SMU 2024 ICPC 网络赛选拔赛2）
The 2020 ICPC Asia Shenyang Regional Programming Contest Northeastern University（SMU 2024 ICPC 网络赛选拔赛2） D. Journey to Un'Goro 思路 队友写得，没看。 代码 F. Kobolds and Catacombs 思路 将 (a) 排序后的数组设为 (b)，然后判断 (a) 和
macOS Sequoia 15.0.1 (24A348) 正式版 ISO、IPSW、PKG 下载
macOS Sequoia 15.0.1 (24A348) 正式版 ISO、IPSW、PKG 下载 iPhone 镜像、Safari 浏览器重大更新和 Apple Intelligence 等众多全新功能令 Mac 使用体验再升级 请访问原文链接：https://sysin.org/blog/macOS-Sequoia/ 查看最新版。原创作品，转载请保留出处。 作者主页：sysin.org ma
中国大学生程序设计竞赛（秦皇岛）正式赛东北大学秦皇岛分校（SMU Autumn 2024 Team Round 1）
中国大学生程序设计竞赛（秦皇岛）正式赛东北大学秦皇岛分校（SMU Autumn 2024 Team Round 1） Problem A. 贵校是构造王国吗 I 思路 官方题解很清晰明了。 代码 Problem D. 茶和咖啡 思路 和题解类似。不过我们是用线段树维护前缀最小的物品。 代码 Problem G. 最大路径 思路 懒得写了，题解写得很清楚，赞 代码 Problem J.
Motherboard Chipsets
目录2007年的intel电脑的主板CPUCPU的内存请求内存映射IO造成的内存空洞CPU的运行模式决定有多少物理内存可以被访问参考 2007年的intel电脑的主板 Intel Core2 QX6600的CPU CPU 对外通道：针脚（pins）= 引脚（lead）= 管脚 = 接脚 如何发起交互：内存地址空间、I/O地址空间、中断。 针脚：33个针脚用于传输物理内存地址、64个针脚用于接收/
20241002 模拟赛
这场爆零了。（惨 先把题目发上来吧。 A. 躲避技能 难度：绿 机房大佬又给出解法：对于每个账号的位置，我们+1；而关键点，我们-1。（这里其实可以不必考虑正负，最后取abs就行了） 然后遍历一遍整棵树，将每个节点（除了根节点）作为根的子树点权和算出来，乘上该节点与其父亲连的边的边权，每个节点的加起来就行了。 仔细想发现这样做是很自然的。不必走的边自然会被省掉，手玩一下就能领会
AT_abc374_f Shipping
原题链接 不难发现一次发出一定是 (a_i+kx,kin mathbb{Z}) 的时刻，因为你一次发出不然就是可以发出抓紧发出，否则肯定是要等到下一次有新包裹要发出再发出，不然你中间等待没意义。也就是说相当于从一个时刻开始连续发送若干次。 设 (f_{i,j}) 为在第 (i) 个包裹到达时，总共有 (j) 个包裹还没发出时，已发出包裹的发出时间和的最小值。 转移时枚举 (i,j)，再不断发出包裹
LCT 优化 Dinic
我觉得这东西有必要记一下，因为光是看 PPT 很难自己写出代码……具体步骤相关啥都没写。 另外学这个东西也不是很必要…… Solution 我们需要一个维护最小值、最小值编号，支持区间加的 LCT。需要支持以下操作： (find_root(u)) (link(u,v)) (cut(u,v)) (find_min(v)) (add(u,value)) （注意到只需要实现 access） 首先 B
LOJ 6041 事情的相似度 题解
Statement 先把串 reverse，多次给 (l,r)，求 [ max_{lle i<jle r}{text{LCP}(i,j)} ]Solution (text{sqrtlog}simtext{sqrt})：莫队 + 线段树 / 树状数组 / set，用 SA 做 (nm/omega)：bitset 乱搞 (log^2)：SAM + LCT + BIT 在 parent 树上，
P4093 序列 题解
Statement 给出 (n) 个数的序列 ({a_i})，接下来 (m) 秒中每一秒会有一个数发生变化，然后恢复。 问最长的子序列长度，使得任意时刻这个子序列不下降。(nle 10^5) Solution 设 (b_i) 为 (i) 最小能变成的数，(c_i) 为 (i) 最大能变成的数 [ f(i)=max_{j<iland c_jle a_iland a_jle b_i}{
P3527 MET-Meteors 题解
Solution 单次二分：二分时间，做这个时间前的所有操作，然后线性统计。 注意到可以整体二分，直接整体二分是 (O(nlog^2 n))。 考虑扫描序列，用线段树维护每个时间段内该位置的增加值，差分一下可以实现。 将这棵线段树持久化一下，一个国家所有位置同时二分即可 (O(nlog n))，可惜空间太大。 回到整体二分，考虑 Solve 相当于一堆区间加后单点查，差分后可线性求出每个国家的权值
P3250 网络 题解
Solution 单次二分：问“重要度 (ge x) 的所有操作，且 (t) 时间点还存在的所有操作中，是否有不经过这个点的” 整体二分：保持操作、询问按时间有序，即预先按时间排序，下传时保持有序； 对于一次 Solve，对于所有重要度 (ge mid+1) 的操作（加入、删除），考虑与询问按时间混合排序，然后依次回答。 这里有比树剖更好的处理方法：树上差分，一次加入路径 ((u,v)) 就给 (
P3215 括号修复 题解
Statement 维护一个括号序列，有以下操作： 区间覆盖 区间翻转 区间反转（左括号变右括号，右括号变左括号） 区间问最少改多少位能使括号序列合法，保证有解 Solution 单纯没想到答案怎么算。。。 首先一段括号序，如果消除中间的所有匹配，最终一定形如 ))))(((，这个信息是可合并的 设这时左括号数为 (a)，右括号数为 (b)，答案等于 (lceilfrac a2rceil+lc
平面最近点对 & 最小周长三角形 & 曼哈顿距离最近
Statement 求平面最近点对的距离，距离定义为欧几里德距离。 Solution 考虑按 (x) 排序，分治计算 先往左右递归，设得到的答案为 (d)，当前算跨过中点的答案，那么答案 (ge d) 的点对可以不用枚举 设中点为 (m) 对 (iin[l..m])，(x_ile x_m-d) 的不用枚举；对 (jin[m+1..r])，(x_jge x_m+d) 的不用枚举 对于所有 (iin
P5416 = UOJ 198 时空旅行 题解
Statement 一棵树，每个节点上有一个集合，每个儿子集合由父亲集合增加一个点 ((x_i,c_i)) 或删除一个点得到。根节点集合为 ({(0,0,0,c_0)}) 多次询问，每次问 (u) 点的集合内，(min{(x_i-x)^2+c_i}) Solution 首先你认真读完题发现原题中 (y,z) 都是没用的 然后离线 DFS 一遍，问题变成加点，删点，问 (min_{i}(x_i-x)
Gym 100543G Virus synthesis 题解
Solution 首先只考虑回文串的答案；我们重点考虑的是偶回文串 结论：对于偶回文串 (u)，从其最长的长度小于等于他的一半的回文后缀，或其父亲转移过来，一定是最优的 证明： 设 (u) 的一个回文子串为 (v)（不是父亲），你要让 (vto u) 的转移最优 首先 (v) 不能跨过 (u) 的中点，因为此时“从父亲转移过来”一定不会更劣 其次 (v) 不能位于 (u) 的中间（非前后缀），因
题解：AT_abc374_c [ABC374C] Separated Lunch
无耻的广告更好的阅读体验~ 最近在搞个人博客博客园的差点忘了更了。 已经沦落到在写这种水题题解了。 题目翻译 有 (n) 队人，每个队人数不同，把他们分成 2 组（同一队的不能拆开），使两组人数差距尽量小。 形式化题意：有 (n) 个数，把它们分成两组，使两组和的差尽量小。 说句闲话：感觉这题目很经典，但我没有原题作为证据（大雾 解法 本来觉得我这菜鸡实力是不可能做出来的，已经准备摆烂了，此时我
E. Expected Power
E. Expected Power You are given an array of $n$ integers $a_1,a_2,ldots,a_n$. You are also given an array $p_1, p_2, ldots, p_n$. Let $S$ denote the random multiset (i. e., it may contain equal elemen
P4690 镜中的昆虫 (动态区间颜色数) 题解
Statement 区间涂颜色 区间颜色数 Solution (O(text{polysqrt})) 略。 (O(text{polylog})) 颜色段均摊有两层含义： 随机数据下：任意时刻的颜色段个数期望 (O(log n)) 非随机数据下：每次推平时访问的颜色段个数均摊 (O(n)) 首先维护每个点 (i) 的 (pre_i)，一次询问相当于二维偏序。 考虑单点修咋做，他对 (pr
完美转发（模板）--T&&
在C++模板编程中，完美转发（Perfect Forwarding）是一种技术，旨在保留函数参数的值类别，即在将参数传递到另一个函数时，无论参数是左值还是右值，都能够保持它的原始性质，而不会因为转发丢失性能或引入不必要的拷贝。 完美转发的关键在于通过模板的转发引用（Forwarding Reference），结合 std::forward，将参数以最合适的形式传递给目标函数。 为什么需要完美转发？