iOS
CF1860C 题解
显然是一个博弈论题，考虑 dp。 定义状态 (dp_i) 表示先手走到 (i) 之后是否有必胜策略，不难发现以下几点： 若走到 (i) 之后无路可走，那么就必败。 若走到 (i) 之后对手只能走到一个必败点那么这就是必胜点。 除开以上两种情况都是必败点。 用 (1) 表示必胜，(0) 表示必败，所有操作就是对 dp 数组的单点修改和前缀最大值。 考虑用树状数组维护即可。
AT_abc318_g 题解
因为是图上路径是否经过某个点的问题，所以考虑建出圆方树，然后根据圆方树的性质，(a) 到 (c) 存在经过 (b) 的路径等价于 (a,c) 在圆方树上的路径经过 (b) 或者 (b) 所连接的方点，考虑暴力在圆方树上跳 LCA 即可，时间复杂度 (O(n + m))。 其实这题还可以多组询问，考虑把询问挂在 (b) 上然后树剖即可。时间复杂度是 (O(q log n + n log n + m
joig2022_e 题解
设计 (f_i) 表示以第 (i) 个数结尾的选择的最大值。 有 (f_i = f_j + a_i)（(type_i not = type_j)）。 发现可以选择的种类其实构成两段连续区间。 所以维护使得 (type_x = i) 的所有 (x) 的 (f_x) 最大值。 这个用线段树可以很简洁的维护。 于是就 (O(n log n)) 地做完了。
CF1093E 题解
来一发 (O(n sqrt n)) 时间，(O(n)) 空间的分块写法。 首先建模，把 数值 (x) 在两个数组中出现的位置作为坐标，问题就转化为一个二维动态数点。 考虑用序列分块维护第一维，第二维用 值域分块 维护，这样子平衡复杂度玩就得到一个 (O(n sqrt n)) 时间的做法，但是空间很大。 考虑到块与块之间并无联系，所以考虑 逐块处理 也就是说把每个块的修改与贡献离线下来分开计算，那么
浅谈维护叶子节点及其所构成的虚树的一类线段树
前言 我们都知道动态开点权值线段树的空间复杂度是 (O(n log V)) 的，但是很多题目中这样的空间是会被卡的，那我们能不能优化呢？ 实现 看看下面这一棵树： 在上图中，红色节点使我们平常会开的点。 但是我们发现，其实只要维护绿色的点和红色的叶子结点。 其实，绿色节点就是所有叶子结点的 虚树。 然后我们考虑如何维护虚树。 先明确一下虚树的性质：只有叶子节点和它们的 LCA。 LCA 最基础的
Top cluster 树分块
写点基础的东西。随便写的，勿喷。 top cluster 一个 cluster 是一个联通子图，且至多有两个点与其他部分连接 这两个点被称为 boundary node 其余点被称为 internal node，两个 boundary node 间的路径被称为 cluster path 而我们的树分块就是将原树分为 (sqrt n) 个 cluster 将 boundary node 看成点，cl
joigsc2022_e 题解
翻译 有长度为 (n) 的序列 (a) 和 (L)，你需要对于每个 (x in[1,n]) 求出若把第 (x) 个数到第 (n) 个数依次装入容量为 (L) 的箱子中（每个数的体积为它的值，若箱子装不下了，则会使用另一个空箱子）会使用多少个箱子以及最后一个箱子的质量。 题解 考虑一个显然的暴力，用二分找出每个盒子最装下那些数，总复杂度最坏是 (O(n^2 log n))。 然后其实可以考虑一个记忆
CF1862C 题解
考虑每个木板在水平放置后对每个位置上产生的贡献。 稍微手玩几组样例： 不难发现一个高度为 (h) 的木板在水平放置后会是位置 ([1,h]) 上高度增加 (1)。 但是高度最大是 (10^9) 这该怎么办？ 根据上面的结论，只有当最高的木板高度与 (n) 一致时才有可能相同，因此考虑直接差分维护即可，笔者代码实现为了方便清空直接写了 map 维护差分数组。
Codeforces Round #922 (Div. 2) ABCD
D. Blocking Elements 题意：在 (a) 中取 (m) 个元素，将原数组划分为 (m + 1) 个子段（可以为空），问 (m) 个元素和与子段和中的最大值最小为多少。 二分答案。 考虑 (f[i]) 表示取第 (i) 个元素，且在前 (i) 个中取出元素和的最小值。 [f[i] = a[i] + min(f[j]) (sum[i - 1] - sum[j] le mid)
CF264E Roadside Trees
https://www.luogu.com.cn/problem/CF264E 求最长上升子序列长度的经典方法是 dp，此题中设 (f_i) 为以 (i) 为结尾的答案不是很方便，所以此题中改写 (f_i) 为以 (i) 为开头的答案，转移就是 (f_i=max_{jge i+1,a_i<a_j} f_j+1)。 高度变 1 的限制让我们很不爽，对于第 (i) 时刻插入的树来说，相比最开始就
CF1000F One Occurrence题解
题目链接：CF 或者 洛谷 感觉很经典的题，而且给的 (5e5)，虽然莫队之类的很好想，但完全没必要去考虑这类算法，这种数据范围常数又大又开盲盒。很显然的具有单 (log) 的算法。 回忆下经典问题 “HH的项链”。其实对于区间颜色数的方法网上已经总结的很全了，常见的无非就莫队，维护 (last) 用 BIT、主席树之类的计数。这题和颜色数没啥太大关系，但分析方式是一致的。 考虑 ([l,r])
C/C++ 操作ini文件(SinpleIni 跨平台库)
最近在学习时，发现自己还不会操作ini文件，想着以前工作时接触到的项目或多或少都要用到ini文件去保存初始化程序的数据；所以赶紧去网上搜索以下C/C++操作ini文件都有些什么库可以玩玩；搜索到有： 1. inih：这是C语言小巧的库，更适合嵌入式开发； 2. iniparser：这是C语言的库，挺方便使用的，开源，两个.h文件和两个.c文件，但只能在Linux中使用； 3. si
Educational Codeforces Round 161 (Div. 2)
A - Tricky Template 难度: ⭐⭐ 题目大意 给定三个字符串a, b, c; 现在有一个模板串t, 如果字符串s和t匹配需要满足两个条件; 1- 如果 ti 是小写字母, 那么 si 和 ti 相同; 2- 如果 ti 是大写字母, 那么 si 不能 ti 的小写形式相同; 问是否存在一个模板串t使得a, b都和t匹配, 而c不匹配; 解题思路 本题要从a, b串下手,
CF1904C Array Game
题目传送门 codeforces 洛谷 题目大意 给你一个由 (n) 个正整数组成的数组 (a) 。在一次操作中，选取 ((i, j)) ，将 (|a_i - a_j|) 加到 (a) 的末尾。你的任务是在执行 (k) 操作后，最小化最后数组 (a) 的最小值。 思路 分三种情况： (k geq 3) 时，我们可以取两次相同的 (|a_i - a_j|) ，这样数组中就会出现两个相同的数，第三
P1699 [USACO19OPEN] Bucket Brigade B
题目大意 给一个 (10 × 10) 字符串矩阵，求从 (L) 开始（不经过 (R) ）到 (B) 的短路径。 思路 这道题因为是求最短，所以用 (DFS) 比较麻烦，于是我用的是 (BFS) 做。遇到障碍则跳过，到终点直接退出就行了。 code
react tips/webpack热更新原理/webpack优化性能/超级蔬菜配比
《react 使用小技巧》https://www.yuque.com/beilo/simpread/1706613177588 《webpack热更新原理》 https://github.com/febobo/web-interview/issues/126 Webpack Compile（webpack编译） Bundle Server（静态资源服务器，一般是 dist/build 文件夹 H
2018-2019, ICPC, Asia Yokohama Regional Contest 2018
Preface 又被输出格式创飞了，E题狂暴卡1h后面发现原来输出边的时候没有按照一小一大的顺序来输出 不过后面也没啥会的题了，几何、线代题做不来，对着一个四色定理题乱搞一波发现样例都过不去 值得一提的是这场前期完全是顺序开题，从A一直开到E A. Digits Are Not Just Characters 签到 B. Arithmetic Progressions 徐神开场写的，我题目都
KY146 魔咒词典C++
构建一个map，还是查找问题。 麻烦点就是要 分解输入的过程 #include<iostream> #include<string> #include<map> using namespace std; int main(){ string a,b; map<string,string> m; while(getline(
left 1 Codeforces Round 920 (Div. 3)
题目链接 D. 贪心思路初步是对的 最大配最小 但是，最小也可能配最小 比如 999 1000 1 2 这个例子，就是最小配最小 还是极端到极端的问题，两个极端都要考虑 E. A和B每走一步横坐标一定变化 所以若A的横坐标大等于B的，那么一定平局 A先手，我们可以知道A与B的横坐标之差如果是奇数，是A吃B。 A走 差/2+1，B走 差/2步 走完后A、B一定在同一行 那么再判在不在同一