My Favorite Things_

🎹🎈💻

算竞笔记 - 题集/板子整理（C++）

Preface 参考主要来自《算法竞赛入门经典：训练指南》、OIWiki、CP Algorithms等资源和多方博客、课程，在自己的码风下所著注：部分实现可能用到较新语言特性，烦请修改后在较老OJ上使用；原则上提供的代码兼容符合Cpp20及以上标准的编译器 Header #include "bits/stdc++.h" using namespace std; #define PRED(T,X) [&](T const& lhs, T const& rhs) {return X;} typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef pair<ll, ll> II; typedef vector<ll> vec; template<size_t size> using arr = array<ll, size>; const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } const static ll lowbit(const ll x) { return x & -x; } const ll DIM = 1e5; const ll MOD = 1e9 + 7; const ll INF = 1e18; const lf EPS = 1e-8; int main() { fast_io(); /* El Psy Kongroo */ return 0; } Misc 开启GCC debug容器: add_compile_definitions(-D_GLIBCXX_DEBUG) 数学快速幂 // 注：爆int64考虑__int128或相关intrinsic // MSVC: https://codeforces....

Project SEKAI 逆向 - 笔记归档

Preface Cutoff: 24/01/05 Revision: 24/09/26 其实分析工作主要是在此后才真正起步…不过实在找不到时间写帖子orz 对最新知识有兴趣或也想参与研究的话，还请参阅以下Repo及其Wiki： https://github.com/mos9527/sssekai https://github.com/mos9527/sssekai_blender_io Project SEKAI 逆向（1）：文件解密及API初步静态分析分析variant：ColorfulStage 2.4.1 （Google Play 美服） 1. 解密 metadata 注：不适用于新版本；请参见后文“动态提取” 利用 Il2CppDumper 对apk中提取出来的global-metadata.data和il2cpp.so直接分析，可见至少metadata有混淆 IDA静态分析libunity.so, 定位到export的il2cpp_init；没有发现有关混淆的处理考虑直接分析il2cpp.so，定位到global-metadata.dat有关流程从这里的xref可以很轻松的摸到Il2Cpp的metadata加载流程 (注：部分变量已更名) _BYTE *__fastcall MetadataLoader::LoadMetadataFile(char *a1) { unsigned __int64 v2; // x8 char *v3; // x9 __int64 v4; // x0 _BYTE *v5; // x8 unsigned __int64 v6; // x9 const char *v7; // x0 int v8; // w21 int v9; // w20 _BYTE *mapped_metadata; // x19 __int64 v11; // x8 __int64 v13; // [xsp+0h] [xbp-E0h] BYREF unsigned __int64 v14; // [xsp+8h] [xbp-D8h] char *v15; // [xsp+10h] [xbp-D0h] size_t len[2]; // [xsp+30h] [xbp-B0h] __int64 v17[2]; // [xsp+80h] [xbp-60h] BYREF char *v18; // [xsp+90h] [xbp-50h] char *v19; // [xsp+98h] [xbp-48h] BYREF __int64 v20; // [xsp+A0h] [xbp-40h] unsigned __int8 v21; // [xsp+A8h] [xbp-38h] _BYTE v22[15]; // [xsp+A9h] [xbp-37h] BYREF _BYTE *v23; // [xsp+B8h] [xbp-28h] sub_17A953C(); v19 = "Metadata"; v20 = 8LL; v2 = (unsigned __int64)(unsigned __int8)v13 >> 1; if ( (v13 & 1) !...

PSJK Blender卡通渲染管线重现【1】- 预备工作

Preface 同上次封笔算是承上启下了，刚好能从琢磨卡通渲染的部分（重新）入手…毕竟旧工作这方面留下的问题远远比解决的多（）集训前时间也算充裕，看看能写多少吧版本: 日服 5.0.0 （烤森更新）设备：Mac Mini M4 (2024) 1. 预备工作之前有在 Android 实机（注：Pixel 2 XL）上用 RenderDoc 跑过捕捉…除了设备性能相对羸弱和捕捉死慢以外可用性其实不错不过如今有了 Mac 这方面也许可以不用强加这种限制先前捣鼓 GPTK 的时候读过它的 README，注意到这段相当有趣： …and inserting the following environment variables to enable Metal debugging and processing of debug information: MTL_CAPTURE_ENABLED=1 D3DM_DXIL_PROCESS_DEBUG_INFORMATION=1 改个环境变量就能调试…比在 Win 上捕捉第三方 Game 得方便太多；应付后者用 RenderDoc/PIX 还学会了各种奇怪的注入方式（？）——不过，回到正题，这个变量放到wine + D3DMetal转译层以外好用吗？游戏准备 Apple Silicon 的 Mac 无一例外都可以原生跑 iPhone/iPad OS 上的 App —— CPU，GPU零 overhead 不过注意“可以”，AppStore上并搜不到多少能直接装的应用… 但是万幸还有PlayCover可以直接装解密过的 IPA；后者 armconverter 上一搜即得...

PSJK Blender卡通渲染管线重现【2】- 角色及舞台 Shader

Preface Shader部分其实已经有不少现成工作，比如 https://github.com/KH40-khoast40/Shadekai https://github.com/festivities/SekaiToon 至于为什么要自己重新造轮子…有时间。还要什么理由？除此之外（敲黑板）最后实现是要进 Blender 的嘛… PV：愛して愛して愛して在Xcode调试Metal甚至有Render Graph方式呈现的资源依赖…库克太谢谢你了🥲 上一篇并没有往SRP后处理前的工作去看；这里直击SRPBatcherPass 很巧的是恰好这个Pass处理的正包含角色部分，下面逐步分析注：后文向量都将以图示方向表示 1. Eye-Highlight 简明概要的效果 - 即给角色眼睛表现添加卡通风格高光这部分由额外Mesh表达（注意缩写ehl），在Pass中作为第一个Mesh出现回到 Metal 调试，观察反编译可知几个效果上的细节高光‘闪烁’效果 u_xlat0.x = FGlobals._SekaiGlobalEyeTime * UnityPerMaterial._DistortionFPS; u_xlat0.x = floor(u_xlat0.x); u_xlat0.x = u_xlat0.x / UnityPerMaterial._DistortionFPS; u_xlat1.x = u_xlat0.x * UnityPerMaterial._DistortionScrollX; u_xlat1.y = u_xlat0.x * UnityPerMaterial._DistortionScrollY; u_xlat0.xy = fma((-u_xlat1.xy), float2(UnityPerMaterial._DistortionScrollSpeed), input.TEXCOORD5.xy); u_xlat16_0.xy = _DistortionTex.sample(sampler_DistortionTex, u_xlat0.xy).xy; u_xlat16_2.xy = fma(u_xlat16_0.xy, half2(2.0, 2.0), half2(-1.0, -1.0)); u_xlat0.xy = float2(u_xlat16_2.xy) + float2(UnityPerMaterial._DistortionOffsetX, UnityPerMaterial._DistortionOffsetY); u_xlat1.x = UnityPerMaterial....

PSJK Blender卡通渲染管线重现【3】- SDF 面部渲染实现

Preface 在v2面部模型更新后游戏终于引入了SDF面部阴影；实现上和市面上已有的大部分方案大同小异本文分享自己在Blender中正确实现该效果的一种思路注意：由于个人水平有限错误难免，强烈推荐阅读以下文本作为预备知识：二次元角色卡通渲染—面部篇 by MIZI 卡通渲染——360度脸部SDF光照方案 by Yu-ki016 Signed Distance Field by 欧克欧克 1. SDF 概述 SDF面部阴影在解决朴素法线/N dot L阈值阴影在极端光照角度表现上的不足以外提供了表现上相当大的自由具体实现上也相当简洁，以下是HIFI Rush中的应用例图源：Tango Gameworksのチャレンジが詰まったカートゥーン調リズムアクションゲーム『Hi-Fi RUSH（ハイファイラッシュ）』（1）キャラクター・モー*ション・エフェクト編美术在（凭不同光照角度于原几何上的）渲染输出为蓝本，手绘出基于角度的阈值图后经某种合成算法后生成一张以亮度映射到光照角度的SDF图像着色上，SDF可以将点/Fragment渲染的问题转换为物体/Object整体渲染的问题最后的着色与且仅与光照角度有关（敲黑板），某种程度上来说等效于对法线一致的平面作阴影合成上，有 Valve 在 SIGGRAPH 2007 上做的技术分享和相当多教程会介绍的8-points Signed Sequential Euclidean Distance Transform/8SSEDT 在之后的文章中将会对这两者进行更深入的实现和剖析当然，本篇还是以复现游戏效果为主 2. 游戏内实现抽出游戏所用的SDF贴图如下在 Photoshop 中查看阈值，很显然是上文所介绍过的类似模型回忆我们所需的阈值对应光照角度；接下来马上就会用到（再次敲黑板） 3. Blender 实现光照角度从角度出发，考虑单个光向量 $l$ —— 如图（来自 RTR4 …当然这里和BRDF并没有直接联系由于对称性很显然只凭 $\hat{n} \cdot \hat{l}$ 我们只能获得 $θ \in [0, 90 \degree]$ 的光照角（ $< 0$ 部分背光故省去）...

算竞笔记 - GCD及相关专题

691C. Row GCD You are given two positive integer sequences $a_{1}, \dots, a_{n}$ and $b_{1}, \dots, b_{m}$ . For each $j = 1, \dots, m$ find the greatest common divisor of $a_{1} + b_{j}, \dots, a_{n} + b_{j}$ . 引理： $g c d (x, y) = g c d (x, y - x)$ 引理：可以拓展到 **数组 $g c d$ 数值上等于数组差分 $g c d$ **；证明显然，略注意该命题在数组及其差分上取子数组时上并不成立，如 991F. Typora怎么快速加页面内链接… 记 $g_{p f x} = g c d (a_{2} - a_{1}, a_{3} - a_{2}, \dots a_{n} - a_{n - 1})$ 于本题利用 $g c d (a_{1} + b_{1}, a_{2} + b_{1}, \dots a_{n} + b_{1}) = g c d (a_{1} + b 1, a_{2} - a_{1}, a_{3} - a_{2}, \dots a_{n} - a_{n - 1}) = g c d (a_{1} + b_{1}, g_{p f x})$ 即可 int main() { fast_io(); /* El Psy Kongroo */ ll n,m; cin >> n >> m; vector<ll> a(n); for (ll& x: a) cin >> x; // gcd(a_1+b_1,a_2+b_1,....

算竞笔记 - 哈希类型专题

1. Candy Rush TL;DR - 串哈希加速比对 + big hash trick 2023-2024 ACM-ICPC Latin American Regional Programming Contest 官方题解：https://codeforces.com/gym/104736/attachments/download/22730/editorial.pdf 取 $C_{i}$ 出现频率为向量做前缀和后可发现有效区间频率差为 $k \cdot 1_{n}$ ；直接比对平摊复杂度为 $O (n k \log n)$ , $O (k)$ 来自于比对本身而比对可以转换为 $O (1)$ 形式，trick如下：若 $a, b$ 对应区间有效，一定有： $f r e q_{b} = k \cdot 1_{n} + f r e q_{a}$ 而在做前缀和是，可以及时消掉 $k \cdot 1_{n}$ 项：即为全非 $0$ 时全 $- 1$ 此时的比对即变成 $h a s h (f r e q_{b}) = h a s h (f r e q_{a})$ 造一个能 $O (1)$ 更新的 $h a s h$ 即可让最终复杂度可以变为优秀的 $O (n l o g n)$ 题解 $h a s h$ 为 $(b a s e^{i} \cdot c_{i})$ - 避免碰撞可以采用更大int类型或模数，或同code开array于不同base计算后比较 #pragma GCC optimize("O3","unroll-loops","inline") #include "bits/stdc++.h" using namespace std; #define PRED(T,X) [](T const& lhs, T const& rhs) {return X;} typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef __int128 i128; typedef unsigned __int128 ui128; typedef pair<ll, ll> II; typedef vector<ll> vec; template<size_t size> using arr = array<ll, size>; const static void fast_io() { ios_base::sync_with_stdio(false); cin....

算竞笔记 - 平衡树相关专题

Treap ATTENTION: 出门左转 https://caterpillow.github.io/byot 谢谢喵又名笛卡尔树，随机BST；支持 $l o g n$ 插入，删除，查找及闭包操作(push_up) https://cp-algorithms.com/data_structures/treap.html https://oi.baoshuo.ren/fhq-treap A. std::set 类容器 template<typename T> struct treap { struct node { T key; ll priority; ll l, r; // push_up maintains ll size; }; vector<node> tree; vec free_list; private: void push_up(ll o) { tree[o].size = tree[tree[o].l].size + tree[tree[o].r].size + 1; } II split_by_value(ll o, T const& key) { // 偏序 [<, >=] if (!o) return {0,0}; if (tree[o].key < key) { // 左大右小 auto [ll,rr] = split_by_value(tree[o]....

算竞笔记 - 线段树专题

注: segment_tree 均采用 1-Index 访问； segment_tree::reset(vector&) 中vector为0-Index 242E. XOR on Segment 区间二进制改+lazy传递+二进制trick You’ve got an array $a$ , consisting of $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ . You are allowed to perform two operations on this array: Calculate the sum of current array elements on the segment $[l, r]$ , that is, count value $a_{l} + a_{l + 1} + \dots + a_{r}$ Apply the xor operation with a given number x to each array element on the segment $[l, r]$ , that is, execute $a_{l} = a_{l} \oplus x, a_{l + 1} = a_{l + 1} \oplus x, \dots, a_{r} = a_{r} \oplus x$ This operation changes exactly $r - l + 1$ array elements....

算竞笔记 - 题集/板子整理（Python）

Preface 以下Code为Cpp 版本的直接移植；请考虑前者为上游及第一参考源 Python 实现，一般地优先考虑动态开内存和哈希化查找(e.g. defaultdict代替线性存储) Code部分未加分类，还请善用Cpp 版本 + Ctrl-F Header from collections import defaultdict 图论领接表 class graph(defaultdict): def __init__(self): super().__init__(list) def add_edge(self, u, v): self[u].append(v) DSU class dsu(dict): def __getitem__(self, key): if not key in self: super().__setitem__(key, key) return super().__getitem__(key) def find(self, u): if self[u] != u: return self.find(self[u]) return self[u] def join(self, u, v): self[self.find(u)] = self.find(v) def same(self, u, v): return self.find(u) == self.find(v) HLD class HLD: def __init__(self, g: graph = None): self....