iOS
AT_abc180_d
贪心思想，STR 值增长得越慢，可能得到的 EXP 值就越多。 根据此，我们在 (x) 较小时，可以乘 (a) 也可以加 (b)，选择运算后较小的一种情况。在某一时刻，当 (x times a > x + b) 时，可知一直到最后都应选择加 (b)（前者是几何级增长，后者是算术级增长）。然后计算能加的次数即可。 具体实现如下： 还是菜。
AT_abc294_d
题意 有 (n) 个人在银行里排队等待工作人员叫号。接下来有 (q) 个事件，事件的类型分为 (3) 种。 1 工作人员叫一个当前未被叫号的人过来。 2 x 代表编号为 (x) 的人来了（保证 (x) 至少被叫号一次）。 3 重复呼叫没有来的人当中编号最小的，并要求输出其编号。 思路 依据题意模拟。使用一个数组，记录每个人是否来过，以及没来过的人的最小编号。对于每个操作 (2)，
AT_abc295_d
很显然，满足条件的子段的异或和均为 (0)（因为每个数都出现了偶数次，而两个相同的数的异或值为 (0)）。问题转化为求异或和为 (0) 的子段的个数。 不难想到，可以从前往后扫一遍，并且计算异或和，可以得出起点为 (1) 且满足条件的子段。那么如何计算中间的子段数量？有如下可行的方案：计算异或和并不是直接异或本身 (a_i)，而是异或 (2^{a_i})（把每个数的状态用二进制表示，不同数字的位置
AT_abc294_c
题意 给定长度为 (n) 的序列 (a) 和长度为 (m) 的序列 (b)，序列 (c) 为这两个序列连在一起组成的。求 (a) 和 (b) 中的每个元素在 (c) 中分别是第几小。 思路 STL 的练手题。输入时将 (a) 和 (b) 中的元素存入 (c) 中，然后使用 sort 从小到大排序，最后再使用 lower_bound 函数查找即可。 代码实现十分简洁： 还是菜。
AT_abc295_c
题意 (n) 个袜子，每个袜子有一个颜色，如果有两个袜子的颜色相同，则可以把它们配成一对袜子。求一共能配成多少对袜子。 思路 看到颜色值域 (1 le a_i le 10^9)，用普通的数组存不下。可以考虑对序列 (a) 排序，求出相同颜色袜子的数量 (k)，则可以产生 (leftlfloordfrac{k}{2}rightrfloor) 对袜子。将答案累加即可。 Code 代码实现十分简洁：
AT_abc302_c
题意 有 (n) 个字符串，它们的长度都为 (m)。问能否通过改变它们的顺序，使得后一个字符串能由前一个字符串只改变一个字母而得到？ 思路 本题数据范围 $ 2 le N le 8 $，非常小，因此可以考虑全排列枚举所有的情况，最后检验是否存在符合要求的顺序即可。 代码如下： 还是菜。
AT_abc302_d
题意 一个人要送礼物给另外两个人，现有 (n) 件礼物要选一件送给第一个人，价值分别为 (a_1,a_2,cdots,a_n)，有 (m) 件礼物要选一件送给第二个人，价值分别为 (b_1,b_2,cdots,b_m)。求在两件礼物之差不超过 (d) 的情况下，价值总和的最大值。 思路 首先不难想到，要将 (a) 和 (b) 分别排序。然后对于每个 (a_i)（(b_i) 做法同理）,在 (b)
AT_abc302_e
题意 给定一个有 (n) 个点的无向图。初始没有任何边。 接下来有 (q) 次操作，分为 (2) 种类型： 1 u v：连接 (u) 和 (v),保证没有重边、自环。 2 v：删除连接 (v) 的所有边。 每次操作后，输出没有连接其它任何点的点的数量（即度数为 (0) 的点的数量）。 思路 看到操作次数 (1 le q le 3 times 10^5)，可以推测输出的答案需要动态维护。
AT_abc303_d
看到本题，很容易想到贪心，对每一段相同的子串计算最小代价。但这种思路的评测结果显示有 (3) 个测试点 WA 了，因此解法错误。既然贪心行不通，我们不妨使用 dp，对每一位进行分类讨论并求最小耗时。 设 (dp_{i,j}) 表示 Capslock 状态为 (j) 时（(j) 为 (0) 或(1)，(0) 表示熄灯，(1) 表示亮灯），前 (i) 位的最小耗时，接下来具体分析状态转移方程： 记 (
AT_abc187_e
考虑将 (1) 号点定为树根，然后通过搜索确定结点之间的父子关系。对于每次操作，先判断该边两端的点的父子关系，然后再分类讨论进行操作。 如何维护每个点的点权呢？注意到，修改有很多次，但查询只在最后有一次，因此可以考虑树上差分。具体地，设 (a_i) 表示 (i) 的点权，(f_i) 表示 (i) 的父亲，(sum_i) 表示 (a_i) 与 (a_{f_i}) 的差，对每次操作进行分类讨论。 假设
P4747 [CERC2017] Intrinsic Interval 题解
题目链接：Intrinsic Interval 讲讲析合树如何解决这种问题，其实这题很接近析合树的板题的应用。 增量法进行析合树建树时，需要用 ST 表预处理出 (max) 和 (min) 以便 (O(1)) 查询极差，然后线段树去维护 ([l,r]) 上的极差减区间端点做差即 (diff-(r-l))，当这玩意等于 (0) 时容易知道，([l,r]) 就是一个连续段，而我们观察到这个东西是 (g
算法模板 v1.3.1.20240120
算法模板 v1.1.1.20240115：之前的历史版本已经不可寻，创建了第一份算法模板。 v1.2.1.20240116：删除“编译”-“手动开栈”与“编译”-“手动开O优化”；将“编译”-“CF模板”中的第20行代码cin>>T;注释；删除“读写”及其目录下的内容；删除“图论”-“欧拉图”-“混合图”；删除“图论”-“可达性统计”；删除“数据类型”-“高精类”。 v1.3.1.20
Petrozavodsk Summer 2019. Day 9. MEX Foundation Contest【杂题】
比赛链接 A. The One Polynomial Man 给定模数 (p) 和 (0 sim p - 1) 的两个集合 (U,V)，求有多少个有序对 ((a,b)) 满足： (f(a,b) = prodlimits_{z in V} left( frac{(2a+3b)^2 + 5a^2}{(3a+b)^2} + frac{(2a+5b)^2 + 3b^2}{(3a+2b)^2} - zr
GYM102596L Yosupo's Algorithm【分治，支配对】
给定平面上 (2n) 个点，每个点有坐标 ((x_i,y_i))，权值 (w_i) 及颜色 (c_i)。 所有点满足：若 (c_i=0)，则 (x_i <0)；若 (c_i=1)，则 (x_i > 0)。 (q) 次查询，每次给定 (L_i,R_i)，你需要选择两个点 (i,j) 满足如下条件： (c_i= 0,c_j=1)。 (x_i < L,x_j > R) 或 (x
Solution Set【2024.1.20】
A. 整除 首先特殊考虑 (x = 1) 的情况，不难发现其合法当且仅当 (sumlimits c_i = m)。 对于 (x > 1)，我们有 [sumlimits_{i = 0}^{m - 1}x^i = frac{x^m - 1}{x - 1} ]因此我们不妨考虑 (f(x) = sumlimits_{i}c_ix^{a_i} times left(x - 1right)) 在模 (x
0-1背包问题 初理解
第一次做这题确实没什么思路，看了卡哥的视频也是似懂非懂，现在整理一下。 首先明确变量有哪些，物品种类，单个物品重量，单个物品价值，背包的最大容量容量；这些变量该如何融入递推公式中呢？ 先明确题目所求的是什么，在背包容纳范围下的价值最大。 为了求容量空间为N的价值最大，可以推想容量空间为1，为2该怎么求？ 单个物品重量，单个物品价值其实是包含在物品种类这个变量中的。 综合所有变量，我们可以确定dp
题解 P8085 [COCI2011-2012#4] KRIPTOGRAM
【洛谷博客】 思路并不是很直接的一道哈希题，并不算特别难，但也不简单。 分析 看到题意后有字符串匹配，很容易想到哈希。 因为每一个明文对应着一个密文，可以记当前单词距离到上一个相同单词的距离（如果没有即为 (0)），可以观察到明文和密文的单词距离序列如果能相同，就说明可以对应上。 为了快速判断这样一个单词距离序列相同，可以用哈希。 滑动查询区间的时候，需要移除新区间中被移除单词第一个位置的哈希值，