iOS
CF292D Connexted Components
原题传送门 分析 首先一眼看到这个题，第一个想到的肯定是 dfs 暴力每次询问时从左往右把边一条一条加进来，再从右往左加一遍，然后维护连通块个数。但是这样的复杂度显然是 (O(mk)) 的。所以我们需要一些优化。 注意到在加边的时候有些边并不会改变连通块的个数。这些边我先称之为无用边。于是我们可以进行两次预处理，一次从左往右，一次从右往左。每次预处理的时候把所有无用边删去，只存非无用边的编号，放在
洛谷 P1438 无聊的数列
这题题解的做法千奇百怪，有写了两棵线段树的，有线段树套差分的，还有线段树套二阶差分的。我承认是我看不懂所以我决定写一篇只用一棵线段树的题解。 分析 众所周知，普通线段树的懒标记存的是一个待更新的量。那对于这个题来说，直接存和（也就是 add 操作在这个线段上的影响）肯定是不切实际的，因为知道了这个线段上待更新的和之后并不能很方便的计算出两个子线段上待更新的和。那既然不能直接存，那就间接存。我们可以
ABC306F Merge Sets
原题链接 分析 观察要求的式子：(sum_{1 leq i lt j leq N}f(S_i, S_j))，发现可以拆成每一个集合 (S_i) 的贡献的和。那么我们考虑每一个集合 (S_i) 的贡献。 显然，对于每一个 (S_i) ，其贡献就是 (sum_{i lt j leq N}f(S_i, S_j))，也就是它与其后每一个集合 (S_j) 的 (f) 函数值相加。那么现在我们来深入剖析一下
ABC314G Amulets
原题传送门 提供一个常数巨大的暴力数据结构做法。 分析 看到这种极值类问题，可以先想一想二分。由于这题中可以击败的怪物一定是一段连续的前缀，所以考虑二分这段前缀的长度。 由于本题中一道护身符免掉的是一种类型的怪物所造成的总伤害，所以考虑单个怪物的伤害是没有意义的。接下来我们只考虑某一区间中同一类型的怪物所造成的总伤害。 那么二分之后考虑如何判断可行性。显然根据贪心的原则，我们一定会优先考虑免掉 造
CF111D Petya and Coloring
原题传送门 分析 考虑将竖直线从左往右扫，发现左半部分的颜色种类数不减，而右半部分颜色种类数不增。于是如果要保证任意时刻两半颜色数量一样，则这个相等的颜色数量一定不变。考虑竖直线在 (1)、(2) 列之间和在 (m - 1)、(m) 列之间时，发现这两个时刻左半部分颜色数量相等，也就是 (2) 到 (m - 1) 列中的所有颜色都在第 (1) 列中出现过。同理 (2) 到 (m - 1) 列中的颜
CF1263F Economic Difficulties
原题传送门 分析 考虑 dp。设 (w[0/1][l][r]) 为区间 ([l, r]) 内的设备不与上 / 下树连通且不影响其他设备与上 / 下树连通性时可以删除的最多边数。可以枚举 (l)，递推 (r)。假设我们现在要从区间 ([l, r)) 得到区间 ([l, r]) 的答案，考虑可以多删哪些边。发现多删去的边一定是 (x[r]) 及其若干祖先组成的一条链。于是可以观察这条链最多可以延伸到哪
洛谷 P4580 [BJOI2014] 路径
传送门 分析 可以考虑 dp。先朴素地定义 (dp[i][j]) 表示当前在结点 (i)，已经走过了 (j) 个结点（含当前）的方案数。发现没法处理括号匹配，于是加一维 (k) 表示当前还剩 (k) 个前括号没有匹配。又发现没法处理前导 (0)。于是考虑再加一维表示当前的最后一位是什么状态。 发现如果要排除掉前导 (0) 的话，只需要知道 将要转移到我的这个状态 所在结点上的 (0) 是不是作为一
CF384E Pilgrims
原题传送门 分析 约定：钦定 (1) 为根。下称修道院所在点为黑点，城镇所在点为白点。记 (F(x)) 为 (x) 的父亲。 对于每个黑点 (x)，我们可以求出将哪些白点删去会使得其要求无法达成。显然，删去以 (x) 为根时 到 (x) 所有距离最远的点的 LCA 与 (x) 的路径上的点一定会使 (x) 的要求无法达成。于是，我们可以求出以 (x) 为起点的最长链，以及以 (x) 为根时所有到
ABC334G Christmas Color Grid 2
第一次 AK abc，写篇题解记录一下。 原题传送门 分析 发现实际上是要求删去每个绿点之后会多出几个连通块。发现这跟割点的定义很像，于是考虑建图，在相邻的绿点之间连边。然后就只要知道每个点到底被包含在几个点双里。我们使用圆方树，此时就只需要统计每个点的度数就可以了。 代码
ABC334F Christmas Present
非常好 dp，使我线段树旋转。 原题传送门 分析 首先由于两点之间直线线段最短，我们肯定是希望从头一直送到尾，最后回家。但是有了 (k) 的限制，就麻烦了。 考虑一个 dp。我们设 (dp[i]) 表示刚送完第 (i) 个孩子时所要跑的最短距离。转移的时候我们枚举上一次回家是在送完哪一个孩子之后。设 (d[i]) 表示第 (i) 个孩子的位置到第 (i - 1) 个孩子的位置的距离，(d_0[i]
CF1916E Happy Life in University
关于我赛时线段树忘了开四倍空间导致白吃了一发罚时这档逝 原题传送门 约定 (x) 子树内的叶子称为 (x) 的叶子。 与 (x) 颜色相同的点称为 (x) 的同色点或 (x) 色点。 所有在 (x) 子树内的、到 (x) 的路径上（两端不含）没有 (x) 的同色点的 (x) 的同色点称为 (x) 的极浅同色点。 分析 首先考虑两个点要是没有祖先关系，那必然是选择两个叶子最优。想到枚举 LCA 算贡
Solution Set - 训练计划 链表
咕掉了两道不可做题（指黑色）。 梦幻布丁 放在链表的题单里，和链表有什么关系呢？？？ 因为都是在对颜色整体进行操作，我们可以根据颜色拉出来对应的链表。 那么每次合并就相当于把一个链表接到另一个链表上去，暴力修改，那么是 (O(n)) 的，但是要怎么维护答案呢？ 首先可以处理出不做任何操作时的答案 (ans = 1 + sum_{i = 2} ^ n [a_i not= a_{i - 1}])。那么
CEIT算法训练-双指针部分题解(T1-3)
Anagram Search 题意简述 两个字符串 (s) 和 (t) 相似的定义为：(s) 可以打乱之后重新排列成为 (t)。题目给出(a) 和 (b)，问 (a) 中有多少子串(连续的一段)与 (b) 相似。 同时，(a) 中还含有 (?) 字符，他可以等价于任何字符（可以变成任何字符） 解题思路 实际上，根据题目对于相似的定义，我们可以知道，对于任意字符串(s)和(t)，只要满足长度相等，且
1.31 蓝桥杯练习5题
1.31 蓝桥杯练习5题 退役哩，但是下学期还要打蓝桥。好久没写题脑袋空空，准备每天写几个练手。 1.[P8599 蓝桥杯 2013 省 B] 带分数 题意：(100) 可以表示为带分数的形式：(100 = 3 + frac{69258}{714})。 还可以表示为：(100 = 82 + frac{3546}{197})。 注意特征：带分数中，数字 (1) ~ (9) 分别出现且只出现一次（不
搜索训练（dfs+bfs）持续更新
DFS [NOIP2000 提高组] 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 a
AtCoder Beginner Contest 337 D
AtCoder Beginner Contest 337 D D - Cheating Gomoku Narabe 题意：(W) 列的矩阵，矩阵由 o、x、. 三种字符组成。你可以进行若干次操作（可以不做），每次操作可以把矩阵中的一个 . 改成 o。请问最少经过多少次操作后，能在矩阵中找到位于同一行或同一列的连续 (K) 个 o。 思路：这题思路挺有意思的，有点滑动窗口的味道。要同一行或
DIV4(小菜鸡Codechef)
Advitiya 思路： 判断 16 17 18 的时候输出 ADVITIYA 不是就输出 WAITING FOR ADVITIYA Code: #include <bits/stdc++.h> using namespace std; signed main() { int n; cin >> n; if (n >=
UIWindow的概念与使用
UIWindow的作用 UIWindow是UIView的子类用于显示程序内容。每一个UIView想要将内容显示到屏幕上都需要依赖于一个UIWindow。 iOS应用程序要想正常运行至少要有一个UIWindow存在，通常这个UIWindow也就是应用程序的主窗口keyWindow。 APP中可以同时出现多个UIWindow，并且多个UIWindow之间是相互独立的。它们可以同时出现，但只能有一个作为
github加速访问
来源：https://github.com/521xueweihan/GitHub520/blob/main/README.md 2.1 手动方式 2.1.1 复制下面的内容 该内容会自动定时更新 2.1.2 修改 hosts 文件 hosts 文件在每个系统的位置不一，详情如下： Windows 系统：C:WindowsSystem32driversetchosts Lin
6.【2024初三年前集训测试1】
��� (Huge打了一场模拟赛，又垫底了。qwq) 2024初三年前集训测试1 T1学说话 (100pts) 水题，秒了。 单词被下划线分隔开，对于每个单词来说，只要记录最长的单词长度，用 (tot) 临时记录，遇到下划线就清零， (ans) 记录最大值，最后输出即可。 代码 T2膜拜大佬 (0pts→100pts) 哈希水题，把每位大佬的哈希值存起来，时间复杂度 (large O(su
【iOS ARKit】环境反射
环境反射 在使用 iOS AR中 渲染虚拟物体时，RealityKit 默认使用了一个简单的天空盒（Skybox，即IBL环境资源贴图），所有带反射材质的物体默认会对天空盒产生反射。 但在AR 中，使用IBL 技术实现的天空盒反射有一个很大的问题，那就是不真实，因为天空盒由开发者在开发时设置，不能实时地反映用户使用时的真实环境。为
【京东云新品发布月刊】2024年1月产品动态来啦
1）【莫奈可视化平台】新品上线 京东莫奈可视化平台通过自由拖拽、图形化编辑、所见即所得的方式，快速实现极致酷炫、直观清晰的视觉场景，将海量繁杂数据背后所蕴含的价值更直观、深层、全面的展现出来，辅助决策者合理决策。 2）【移动端应用监控 SGM-mobile】新品上线 移动端监控SGM-Mobile专注于监控收集移动端App的真实用户感知体验数据，目前支持Android、iOS两