某

某岛

... : "...アッカリ～ン . .. . " .. .

http://www.shuizilong.com/house
http://www.shuizilong.com/house/feed/ (RSS订阅地址)

星舰狩猎者评测

我玩过的 STG 接 上文。 STG 类型在街机上曾经有过一段辉煌的历史！我刚记事那会儿最早玩到的街机游戏就是 鼓楼商厦 顶楼的 彩京 和 吞食天地（最早顶楼好像还不叫波卡猫，而且古典街机更多，而且二楼还有那个时候传说中的 台式烤肠，6 块钱一个记忆犹新啊）。可能是我童年最喜欢的两个地方之一，还有一个就是城隍庙的一处神秘 FC 卡带店，满橱柜的黄色 FC 卡带啊。。。。。。噢天。 不过彩京显然对当时的我来说还是太困难了，于是可能玩吞食天地更多，我还记得有一次看到有人快打到曹操死了，然后我果断续了个币，结果没打一分钟就结局了的故事囧。不过鼓楼的街机对我来说还是太贵了，后来还是去打家门口附近的各种 1￥ 四个币的黑街机房，开始了我的街机厅生涯，哈哈除了屏幕垃圾点，玩起来一样嘛。。。 后来上了小学之后可能玩的最多的 FC 上的 沙罗曼蛇 和 兵蜂，还有一直都没怎么玩懂的 B 计划。FC 上还借过别人 烈火 的卡带，那个速度感也是惊为天人，就是对眼睛不太友好。后来 PS 上玩的最多的可能是 大流士。PC 上玩的最多的肯定是 雷电，反倒是东方 Project，黄昏的天使可能我玩得反而没那么多。 这么看总之就是各种类型的 STG 好像我都玩过一点。 所以好像一玩就 get 到了 tony 想表达的点，一个 boss rush 的纵版 stg，而且 boss 还有类似彩京里头的模块设定，玩家可以选择直击核心，也可以选择各个击破，削弱 boss 的火力。然后还加入了典中典之三选一肉鸽卡牌成长囧（但是其实没有构筑，你最终都会加满的，这样看可能把僚机作为构筑的一部分做进去更好，不过比起小蜜蜂或者沙罗曼蛇的僚机，如果能做成彩京的那种僚机可能更好！），武器分主武器和副武器，好像可以鼠标两个键一起按，增加火力。大招子弹时间其实我觉得操作让节奏变得很怪，个人感觉不如 1942 的大招或者 […]

2026/6/4
阅读更多

MuShanghai x AI Game Jam

Back Ground 从 Developer Relation 到 Corporate Training 随着 Kimi K2 系列的大卖，最近的工作内容重心又多了一块，就是跑各个大厂去给大家做企业员工培训囧。这里面包括互联网大厂、游戏公司、传统 500 强等等等等，广义上感觉其实是 Sales 的范畴，但是因为我们没有部门墙，所以我也有机会能够参与其中。培训的形式呢其实和做 Developer Releation 时安排工作坊（Workshop) 时的内容大同小异，但具体的内容我通常根据具体目标公司的受众不同做相对应的调整，顺便会提前做一些问卷调查，看看对方最关心的问题是什么，大概最近两个月里已经跑了 Bilibili、喜马拉雅、小红书、携程、网易互娱和网易雷火，好像还有一个名字忘了的车企囧（你可能已经看过了我的名字出现在了你们公司的各种海报上囧）。 所谓教然后知困，自然收集素材、准备材料和回答各类问题的过程，也促使我进行了一大堆思考，自然也留下了一堆待解答的问题。所以我希望尽可能可以正自己的一个好人的视角、让各种观点都能找到佐证为目标，来去收集更多有价值的甚至是非共识的信息（因为根据信息论，非共识的信息墒最大囧），不断地更新自己的知识库来更好的服务客户，特别是在这样一个共识还没有那么明确的时刻。 其中最让我受启发的分别是去小红书和网易雷火分享的过程。小红书因为自己也在训练它们的 AI 搜索模型，有具体而丰富的场景，雷火则是很早的就认识到 AI 在游戏生产各个环节的重要性，交流的过程让我备受启发。正好这周看到有三个 AI Vibe Coding 主题的 Game Jam，于是就想从里面挑了一个参加一下！事实证明，果然不虚此行 … 什么是 MuShanghai https://mushanghai.xyz/ https://t.me/+dngZ49zj9hE1YzM1 https://x.com/themu_xyz 其实这个活动上个月有联系到我。。甚至我还去做了 presentation！！！，，， （虽然当时我还在巴黎。。。于是就只能远程给她们做了 week1 开幕的 presentation 囧。。。） 当时主办方和我说的是她们想在上海办一个科技火人节。。。。甚至时间更长持续四周。。。这谈何容易。。。 遥想当年。。我和 Tina Zhen 搞一个为期一天的 defi.wtf 都让我累得半死（虽然筹备周期只有一天！。。。 看 tg […]

2026/6/2
阅读更多

《赛博行动酒保行动》相关

为了去隔壁给 talk，不得不又重温了本作 = =。 游戏说 99：我只负责调酒，不负责拯救世界 我觉得要是游戏也和隔壁 NeurIPS 一样，发时间检验奖（Test-of-Time Award）的话，一个评判标准我觉得大概得是这个游戏是否引领了很多 xxx-like，那按照这个标准 rogue 是必然能上榜的，《银河战士》和《恶魔城月下夜想曲》大概也能的！ 在调研了一番之后，很神奇的是我觉得《赛博行动酒保行动》后续也有很多酒保行动-like 的！ 首先我觉得本作的设计在一个 game jam 体量的作品里还是非常特别的！你说它是模拟经营吧，不能说没有但是怎么看也不如今年爆红的《沙威玛传奇》，这个游戏绝对是 AI 游戏的代表作了，哈哈玩法我觉得是那种经典古早 flash 游戏，最后一看人家作者还真写 flash（什么，《沙威玛传奇》都能玩出竞速模式吗？）。 你说它是 galgame 吧，hmmm，它居然连对话选项都没有，但分支剧情又都是通过调酒玩法和经营的分数去触发的，这点又类似《仙剑客栈》那样的传统模拟经营了。 我觉得整体氛围最接近显然是 Coffee Talk 系列，虽然背景设定类似《奥秘：蒸汽与魔法》那样有点偏奇幻。 然后同样赛博朋克世界观下的有《红弦俱乐部》以及之前在游机会玩到的《爱&机器人维修技术》。 居然还有这么多联动。。。 – 如何评价少女前线与VA-11 Hall-A赛博朋克酒保行动的联动活动？ – 赛博朋克酒保行动和赛博朋克红究竟联动了啥？（特别节目）【夜之城求生指南】

2025/12/3
阅读更多

《疯狂动物城2》观后感

由于最近在填坑，所以刚好记录一下剧情。 （剧透警告!） 剧情 首先感觉两部的核心除了尼克和朱迪这一对 cp 的性格和阵营上的冲突，还有一个是如何维护 Zootopia 的 DEI（尽管这好像是一个被用坏掉了的词），第一部是肉食动物与草食动物之间，第二部则是哺乳动物和爬行动物之间。 故事开场利用了一场马里奥赛车一样的追逐戏快速的让我进入了状态，并且通过留下的蛇皮也制造了十足的悬念。使得我开始期待一个梅兰妮或是神偷卡门那样的展开，可结果光速发生第一次剧情上的反转，此时朱迪和尼克的阵营上的冲突也开始显现，尼克作为混乱中立显然不想掺和进去，而朱迪作为守序善良自然要贯彻自己 make the world a better place 的信念自然不惜深入险境。 不过我这里感觉是这个翻转比隔壁阿兹卡班的囚徒还要快，凭借蛇蛇的一面之词朱迪的立场就光速翻转，还险些害死了 Chief Bogo！接下来就进入死亡圣器的逃亡环节，朱迪像 cyberpunk 2077 里流浪者阵营一样开始了大逃亡，经过一个神似长弓溪谷坠机之地的水上集市（但是人很多）的地方之后，来到了一个有点像元组星球大战那样的地下酒吧，然后莫名其妙任务道具就丢了。中间一段踩河马脑袋的演出真的就像这类3D平台跳跃游戏的解谜一样，前面甚至还有铺垫的，你肯定在奥德赛 or 古惑狼里遇到过类似的关卡。 钻管子的演出也让人感觉有点梦回超级马里奥大电影。然后尼克就被抓了，说实话我要是朱迪这个时候我肯定已经后悔自责的要死了，第一要务肯定是去救尼克，而不是信任这个蛇蛇。不过尼克遇到了神仙队友居然这么轻易的就越狱成功了。 话说这只竹叶青居然叫 garry，ib 里的 garry 也恰好代表色是蓝色。 然后第二波翻转我方小队里迅速的出现了一个内鬼，说实话我一开始还以为蛇蛇和这个猞猁是 cp 关系，然后上演一场出类似隔壁叙拉古人那样对家族的反抗的剧情，结果居然跳反了？不过这期反派实在战斗力不太行，被有惊无险的光速击败了。 女性主义 回来的路上 m200 说到，尼克在本作不就是一般意义上的女主位置么。确实，不过这种创作手法也不是第一次见到了，最经典的例子可能就是《空之轨迹FC》里的艾丝蒂尔和约修亚了吧。然后尼克本作完全就是宠妻狂魔，朱迪感觉完全就像是少根筋的直男似的，拜托我都没你这么焦虑！也就是你是迪士尼童话故事的主角不然感觉中间我们都死好几次了都。 逗比的预言家，这款19年前的游戏为何能一战成名？带你笑着看完神作《空之轨迹》 游戏说 27：电子游戏与性别歧视 上面这个视频居然没提到寄生前夜的女主 Aya，她可是我小时候玩过的觉得印象最深刻的女主角了，可能原因之一是她除了要和 boss 作战，还要面对来自身体内部线粒体内部的对抗与挣扎。 总之我觉得本作无论是对女性主义，对 DEI，对刻板印象的反击（神话、寓言故事里蛇通常是邪恶的）都处理的非常自然，感觉比《冰雪奇缘》还要棒！（除了没有女同）

2025/12/2
阅读更多

AtCoder Beginner Contest 409

先把所有数都减一，n 表示进行了 n 个回合。 设 E[i] 为最后 i 出现的期望次数。那么显然 E[n] 最容易求，就是每次都 p，E[0] 也容易求，每个回合的 delta 只与当前有多少个 0 有关，看起来可以递推。 E[n-1] 则需要讨论一下，E[n-2] 就更要讨论了。 仔细观察，我们发现不得不枚举第一次出现 i 的时刻，设 A[i][j] 等于 i 第一次出现在 j 时刻的概率，我们有： E[i] = A[i][j] B[n-j] | j = 0..n 这里 B[i] 表示当前最高位后续再进行 i 个回合期望出现多少次，和求 E[0] 类似，这个值只与后续进行的回合数有关！ 进一步，考察 A[i][j]，最后第 j 时刻必然是 p 事件，前面二项分布即可： A[i][j] = C(j-1, i-1) p^i […]

2025/6/12
阅读更多

Luogu P5325. 【模板】Min_25 筛

测模板，标准 min_25 筛用法：先筛出素数 k 次方和（设为 g_k，然后用因式分解去暴力 dp 需要求的函数。 本题只看素数位置，f(p) = p(p-1) = p2 – p，满足 f(p) 是一个 p 的多项式，只需要筛 g1, g2。 https://www.luogu.com.cn/record/209169800

2025/3/20
阅读更多

UOJ #188. 【UR #13】Sanrd

题意：次小素因子前缀和。 类似 PE 521 求最小素因子前缀和，虽然不是积性函数，但不妨碍我们筛。 令 S(n, k) 表示次小质因子 >= P[k] 时的前缀和（P[0] = 0)。 转移，分两种情况： 1. 剩余部分是一个更大的素数，贡献是，p * (g[id(n)] – g[p])。 2. 枚举最小因子分解，递归。 #include <lastweapon/io> using namespace std; const int N = int(1e6) + 9; LL n; int nn; int P[N], Pn; LL di[N], g[N]; int dn; inline int id(LL x) {return x <= nn […]

2025/3/20
阅读更多

《浅谈函数最值的动态维护》学习笔记

感觉需要按照 这个顺序 重新复习一下线段树，掌握一下先进姿势！ 李白天，《浅谈函数最值的动态维护》，国家集训队2020论文集 吉如一，《区间最值操作与历史最值问题》，国家集训队2016论文集 https://cp-algorithms.com/data_structures/segment_tree.html 数据结构闲谈：范围分治的「双半群」模型 Segment Tree Beats! 初步和其他 https://oi-wiki.org/ds/seg-beats/ USACO Guide, Segment Tree Beats 【补档】关于线段树上的一些进阶操作 Kinetic tournament tree 初步 《浅谈函数最值的动态维护》阅读随笔 首先我觉得最重要的就是仔细学习 atc 模板： https://atcoder.github.io/ac-library/production/document_en/segtree.html https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html 虽然线段树模板茫茫多，但是这个无疑依然是目前最有生命力的一个，它不仅适用范围广，速度快（里面居然是个 zkw 树），而后面的 lazysegtree 模板的原理现在大家所说的「双半群」模型。 领悟之后我们发现大部分线段树问题竟然都变成了无脑填空题囧！！ Luogu P4314. CPU 监控 UOJ #164. 【清华集训2015】V 而另一个技术就是势能线段树！简单来说就是有些修改操作破坏半群性质修改的情况，我们找到区间后先暴力清空，或者放宽找区间的代码，递归下去。 这样看似暴力，但是因为有些时候修改操作可以势能分析，发现复杂度没变！ 最经典的模型就是区间取模取根，区间染色，以及区间 CheckMin QueryMax！ Codeforces Round 250 (Div. 1) Problem D. The Child […]

2025/3/15
阅读更多

UOJ #164. 【清华集训2015】V

https://uoj.ac/problem/164 Kimi 居然会做这个题的暴力 https://kimi.moonshot.cn/share/cvaqfgsjc3febjghkqh0， 除了一些细节问题（欧姆定律和电阻公式实际不需要，要开 long long），实际能拿 40 分！ 然后注意到本题的这个区间减操作，是不能减成负值的（AI 居然也能注意到？），所以我们还需要支持区间最值操作，而区间赋值操作是可以用区间最值模拟的，具体说来我们需要维护一个双半群，标记合并是： struct F{LL a0, b0, a1, b1;}; F comp(F r, F l) { return F{ max(l.a0+r.a0,-INFF), max(l.b0+r.a0, r.b0), max(l.a1,l.a0+r.a1), max(l.b1,l.b0+r.a1,r.b1) }; } 注意这里历史标记需要当前标记的信息来维护，所以不能开两个线段树分别维护。 https://uoj.ac/submission/745579

2025/3/15
阅读更多

Luogu P4314. CPU 监控

https://www.luogu.com.cn/problem/P4314 先不考虑赋值操作，先拿个 20 分。 再考虑赋值操作对标记的影响，显然我们不能对每个状态开一个 vector 记录所有历史操作，但我们发现赋值操作可以清空前面的所有历史操作，且之后的加减操作可以和这个赋值操作合并。 因此我们只需要 (a, b) 两个数表示先加再赋值即可描述标记。 再讨论操作，对于加减操作，如果之前存在赋值，我们转化成赋值操作即可。 手写下放标记思路是比较清晰的。 https://www.luogu.com.cn/record/207893466 难点主要是分情况讨论，赋值存在和不存在的情况，如果开 LL 的话还可以用哨兵少开一个数组！ 当然我们发现强行套 atc 模板双半群填空大法也是可以的！ https://www.luogu.com.cn/record/208212684 后来经过这个题的启发，我们发现直接用 checkMax 去模拟赋值可能是更好的选择? https://www.luogu.com.cn/record/208211497 这个写法果然和模板相性更好，不仅不用分情况讨论，合并操作更简洁减少犯错的机会， 而且 checkMax 能模拟 set，反过来却不能，应用范围也更广更强大！ 还有一个细节是 op 和 mapp 里是不需要 checkMax(b, a) 的，因为维护标记的过程就隐含了这层逻辑。

2025/3/14
阅读更多

Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)

Problem E. 又是树上又是反常游戏（misere-game）的，不过和之前的 Goodbye 2024 的这个题一样，都不会进行太深的轮次，所以都不需要用 sg 理论等高级知识 = =。 必胜态：存在一条到必败态的决策。 必败态：所有决策都引向必胜。 我们按照 w 从大到小排序，显然选择最大的 w 决策必败，其次所有更大的 w 都在决策点子树里的状态也必败，反之必胜（后手剩下的决策都引向必胜）。 因此第一问只需要用 dfs 序，看子树里有没有处理过的点即可，最简单的是直接用树状数组每次标记下求个和，也可以求所有更大节点的 lca 看在不在子树里，因为可以基数排序所以后者实际可以 O(n)，标程用了前后缀和看子树外有没有省去了 lca 和树状数组。 第二问难度陡增。。 除了上面的情况，后手要赢，要么没得走，要么必然存在先手还能走的决策，只要从这些决策里选最大的先手走完必然自己不能再走，就可以确保获胜， 所以剩下的必胜态也必须都像第一问里的状态那样，能够一步将死对面。 因此我们可以枚举先手和后手的决策，然后看不存在第三步即可。 但是这样复杂度太高，我们考虑只枚举后手决策，因为按上面的分析第三步可以打包处理，现在只需要检查是否存在合法的先手决策即可。

2025/1/30
阅读更多

区间子串询问

Codeforces, The history of some recurring problem Luogu P6292 区间本质不同子串个数 https://uoj.ac/problem/608 https://www.fzoi.top/problem/4449 初见杀，实际套路，应该放一起做！ 首先能离线当然考虑离线（Ukkonen 可以魔改支持左删，但是好像还是不能很好的支持左加和右删，否则我们甚至能莫队？）， 那么我们只要维护一个线段树记录询问左端点在不同位置的答案，考察增加操作对线段树的影响，发现只影响 fail 树向上的节点，最后一步动态树优化即可，复杂度 O(nlog2n + mlogn)。 和 BZOJ_2555 相比，这里由于我们不需要强制在线，动态树不需要在后缀自动机插入字符时候跟随 SAM 变化形态，只需要在全部插入完后根据 fail 树构建即可，因而也可以树链剖分啊启发式合并啊替代动态树的环节。 具体来看，先考察 Luogu P6292 区间本质不同子串个数，每次添加新字符时，先把所有位置都加 1，然后类似 dquery 一题的搞法，我们记录上次添加的时刻以去掉重复计数的部分，而这只需要沿着 fail 树向上，并记录每个状态上次计数的时刻即可。这里的线段树只需要支持区间加减，区间求和，因而也可以用树状树组替代。 观察这里的动态树这里其实唯一的用处就只有压缩 fail 树 = =，我们只需要维护上次访问的标记即可，其它信息都可以从 SAM 中拿到，因为 Splay 之后父节点和自己刚好形成压缩后的 endpos 区间。 fzoi 那枚只需要把线段树从区间加常数变成加等差数列。再看 uoj 608，这里我们线段树需要支持的是区间等差数列 checkMax，由于这个标记是单调的，所以可以简单标记持久化，动态树同样只起到压缩 fail 树的功能，完全不用改！

2025/1/2
阅读更多

UOJ #131. 【NOI2015】品酒大会

https://uoj.ac/problem/131 显然我们只需要在后缀树上 dp 即可，比较容易的写法是逆序构造 sam。https://www.luogu.com.cn/record/196889119 另外因为后缀树组的 height 数组上建笛卡尔树叶可以构造出 fail 树等价结构，而 height 数组恰好对应了 n-1 个内点，height 对应后缀共享的最长公共前缀 len，n 个空儿子恰好对应了 |endpos| = 1 的叶子结点。(https://github.com/981377660LMT/algorithm-study/blob/585e0b2b800fa08ae1fc4e89fd53fa64a2683510/17_%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D/%E5%90%8E%E7%BC%80%E6%A0%91/SuffixTree.go https://www.luogu.com.cn/record/196821208 另外此处也可以不显示构造出后缀树。 使用并查集 https://uoj.ac/submission/482165 或者单调栈也可以。

2025/1/2
阅读更多

各种筛

任之洲, 《积性函数求和的几种方法》, 国家集训队2016论文集 朱震霆, 《一些特殊的数论函数求和问题》, 国家集训队2018论文集 周康阳, 《关于积性函数求和问题的一些进展》, 国家集训队2024论文集 https://oi-wiki.org/math/number-theory/du/ 新版min25筛（O(n^(2/3))）详解 Peter的莫比乌斯反演与各种筛法题单 https://www.cnblogs.com/A-Quark/p/15779093.html https://codeberg.org/trizen/sidef/src/branch/master/NUMBER_THEORY_TUTORIAL.md https://github.com/yosupo06/library-checker-problems/issues/1118 https://github.com/danaj/Math-Prime-Util/blob/a4e83603fa8966950016fd18cf4114787167e973/lmo.c#L8 COMPUTING π(x): THE MEISSEL, LEHMER, LAGARIAS, MILLER, ODLYZKO METHOD 习题 积性函数求和 https://projecteuler.net/problem=639 https://projecteuler.net/problem=708 SPOJ divcntk 素数计数相关 LOJ #6235. 区间素数个数 素数计数 LOJ #6202. 叶氏筛法 素数和 https://loj.ac/p/6053 https://projecteuler.net/problem=521 最小素因子求和 https://www.luogu.com.cn/problem/SP19975 最小素因子求和 https://uoj.ac/problem/188 次小素因子求和 https://www.cnblogs.com/zjp-shadow/p/10202492.html 次小素因子

2024/9/26
阅读更多

The 2024 ICPC World Finals Astana

恭喜 PKU 连冠！太强了 Orz。。 https://codeforces.com/blog/entry/134044 https://github.com/SnapDragon64/ACMFinalsSolutions/tree/master/finals2024 Problem B. Bingo for the Win! 签到题。只需要枚举最后一张牌，然后看编号最大的有这张牌的选手即可。 （据说 o1 也会这个题 Orz。） Problem C. Citizenship 签到题。要处理时间戳，代码肯定比上一题长。 Problem F. Friendly Rivalry 二分答案，然后 dfs 求出所有连通块，然后类似拔河那个题，看这些连通块能否凑成容量为 n 的背包。 最后单独构造一下方案即可。 Problem D. Doubles Horseback Wrestling 给定 n 组区间，问可以最多凑出多少对区间，使得可以从这对区间中各取一个数和为给定的 s。 挺有趣的题，首先一般的匹配算法肯定不行了，考虑扫描线贪心。最后每组区间中一定有一个数取 <= s/2，不妨我们从中间分成左右两侧。 假设所有左侧的区间都是单点，那么贪心策略显然，就对所有右区间进行扫描线，从大到小扫描，然后每次拿潜力最小，也就是左端点最大的区间即可。 考虑一般情况，那么需要在左右两侧同时向中间扫描，贪心策略不变。注意到现在有些区间可能会在两侧的事件中同时存在，因此需要开一个全局 used[] 数组记录一下，然后每次贪心要 while 循环，找到第一个没用过的区间进行匹配。 最后再把剩下来的元素两两匹配即可。 Problem J. The Silk Road […]

2024/9/21
阅读更多

AtCoder Beginner Contest 371

Problem E. I Hate Sigma Problems 询问区间不同元素数目有各种经典离线和函数式线段树做法，但是这个题要统计整体，直接上数据结构复杂度反而不太对。 我们可以单独统计每种元素对答案的贡献，而这个只要计算其补集即可，复杂度 O(n)。 https://atcoder.jp/contests/abc371/submissions/57884316 Problem G. Lexicographically Smallest Permutation 原题等价于求字典序最小的 AP^x，由于 P 是个排列，显然可以只考察它的循环分解。我们从左到右贪心的确定 AP^x 的每一位以及打包得到其所在的循环所有位置的结果，按顺序考察每一组这样的循环。我们总能得到一组形如 x = r (mod c) 的限制，这里的 c 是循环的长度，我们要在贪心结果尽可能小的同时，不破坏之前得到的所有限制条件。 我们可以合并这些条件，计算所有这些 c 形成的 lcm，但是这样这个 lcm 可能会特别大。注意到我们并不需要计算具体的 x，并且对于所有互素的 c，显然这些限制是不互相影响的，这提醒我们只需要考察和更新所有 c 的因子所形成的限制条件，进一步我们只需要维护所有素数幂的限制即可。 https://atcoder.jp/contests/abc371/submissions/57872303

2024/9/17
阅读更多

AtCoder Beginner Contest 369

Problem E. Sightseeing Tour 什么 K 只有 5？那么 floyd 预处理，暴力搜索即可。 https://atcoder.jp/contests/abc369/submissions/57867165 Problem F. Gather Coins 等价于 O(nlogn) LIS，注意记录决策，用递归构造方案。 https://atcoder.jp/contests/abc369/submissions/57490934 Problem G. As far as possible 经典题，上次见到还是 2021 年 Meta Hacker Cup 的 Final Round！存在一个非常简单且好写的贪心，就是树 dp 的时候返回子树最长链，其它链全部加到全局的数组里最后丢出去排序即可。 但如果不知道这个贪心这个题会巨复杂囧。 https://atcoder.jp/contests/abc369/submissions/57491760

2024/9/17
阅读更多

RPGMaker 2k3 百科

(Seriously, use any RPG Maker made after XP or some other engine entirely instead of trying to be clever and hack around with 2k3.) —— https://github.com/elizagamedev/oneshot-legacy/ 之前写过不少推荐 RPGMaker 2k3 的文章，前段时间看 EasyRPG Repo 还发现了一个有趣的 issue，不过可见很多旧的代码连编译都不行了，但是我依然相信这种随心所欲，控制一切的感觉！ 当务之急自然是给旧代码做整理，最好能赶在 2k3 的文化遗产消失之前 … 为什么选 除了 这些原因 依然有 丰富的作品集和活跃社区 各类神奇的补丁 最好的开源解释器 EasyRPG 各种魔改 EasyRPG 实战 galgame 猜拳 四合一小游戏 随机地图 roguelike card […]

2024/9/1
阅读更多

OneShot 的考古

最近看 ynoproject 上右下角居然多了一个 oneshot，我心想这个也不算是传统的梦日记派生吧，于是就去研究了一下。 和 ib、madofaza 等作品一样，这款作品也出过重置版，并且时间更早，神奇的是，和前面的作品不同，oneshot 的重置居然是基于 rmxp？那样不是相当于只领先了一个版本。 自己学习下发现居然是 基于 mkxp 的魔改。 反而是 2k3 的原版，因为 https://rpgmaker.net/ 挂掉后，没那么容易找到资源了，还好 discord 也有遇到同样问题的朋友。 – https://www.mediafire.com/download/6ocmn9l8iq8b9xd/Oneshot_v1.03_en.zip

2024/9/1
阅读更多

2024“开创拓芯”游戏创享节的相关记录

前言 上周末比较有价值的活动是北京的 智谱 AI Demo Day，台北的 Coscup 以及后续的 ABS。。。但是智谱的活动依然是在它们的 office 里，名额太少，台北的活动又比较远，需要做更仔细的规划。。还好这个时候看到 Tony 老师和卡姐都转发了开拓芯的活动，地点就在 Google Shanghai 旁边的正大广场顶楼。。。（什么原来这个建筑里面还有这么大一个空间）。 看了一下嘉宾。。什么。。不仅有 P 社，还有开发了《脑叶公司》的月计！！。。这一定要去了。。。虽然已经早就过了报名阶段。。。但 Tony 老师还是很给力的帮我搞到了邀请函！！。。。 正篇 书接上文。。。之前提到 CJ 回来之后，我出现了较为严重的戒断反应。。。因为这次有鹰角的孵化器赞助。。。 所以就出了图图姐。。。 根据前回 CJ 的经验。。造成游场体力下降最大的两个因素主要是假毛和鞋子。。要不是有个展位提前跑路留下了很多椅子估计人就直接 G 了。。。显而易见的是作为一名黑长直。。出图图姐的好处是首先我可以不用带假毛。。。鞋子也打算用平常的鞋子替代。。（其实那个鞋子是琴春的遗产。。） 果然这个组合体力就可以维持体力槽一直在线。。。

2024/8/6
阅读更多

CJ 回来后的戒断反应

https://zhuanlan.zhihu.com/p/711839108

2024/7/31
阅读更多

Luogu P10221. [省选联考 2024] 重塑时光

首先会做这个题。 https://www.luogu.com.cn/problem/P6846 const int N = 18; struct Edge { int a, b; void in() { RD(a, b); --a; --b; a = _1(a); b = _1(b); } bool in(int s) { return (s&a)&&(s&b); } } E[N*N/2]; Int f[1<<N]; bool bad[1<<N]; int n, m; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif […]

2024/7/8
阅读更多

Luogu P5308 [COCI2018-2019#4] Akvizna

wqs 二分显然，最多每轮得分是 1，lambda 上限可置为 1。 直接 dp 复杂度 O(n2) 可以拿 34 分。 const int N = int(1e5) + 9; pair<DB, int> f[N]; int q[N], cz, op; int n, k; bool ok(DB lambda) { cz = 0, op = 0; q[cz] = 0; REP_1(i, n) { auto g = [&](int j){ return MP(f[j].fi + (DB)(i-j)/i - […]

2024/6/18
阅读更多

wqs 二分

https://oj.uz/problem/view/NOI19_feast 经典题，首先这个题有一个众所周知的神奇做法，既贪心 k 次，每次求出最优子序列，然后取反。 这个做法首先当然再 k 很大的时候有点力不从心，只能拿 59 分，而且如果要求每次必选，好像正确性也变得堪忧了。 https://oj.uz/submission/997020 当然此题的 wqs 二分非常好写，可以作为例题。 https://oj.uz/submission/997059 https://codeforces.com/contest/1279/problem/F 和例题几乎一样。 https://www.luogu.com.cn/problem/P3606 也可以从导数的角度考虑，类似 [NOI2012] 骑行川藏，最优状态时每段的导数必然相等，因此直接二分这个导数即可。这题貌似也是。 https://loj.ac/p/3132 Luogu P5896. [IOI2016] aliens https://www.luogu.com.cn/problem/P5896 Luogu P6246. [IOI2000] 邮局 加强版 加强版 https://www.luogu.com.cn/problem/P4767 https://www.luogu.com.cn/problem/P6246 树相关 P2619 [国家集训队] Tree I 题解 P5633 最小度限制生成树 Balkan OI 2019 Tennis FHC 2021 Final Problem D: Vacation P4383 [八省联考 2018] […]

2024/6/11
阅读更多

歌唱王国

https://www.luogu.com.cn/problem/P4548 https://www.luogu.com.cn/problem/P6835 https://vjudge.net/problem/HDU-3992 https://vjudge.net/problem/Gym-104551B https://vjudge.net/problem/HDU-3689 https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-ii/description/ #include <lastweapon/string> #include <lastweapon/number> using namespace lastweapon; int Z; int f() { <pre><code>int n; RD(n); VI P; DO(n) P.PB(RD()); auto pi = kmp(P); Int z = 0; while (n) { z += pow(Int(Z), n); n = pi[n-1] + 1; } return z; </code></pre> } int main() { #ifndef ONLINE_JUDGE […]

2024/5/19
阅读更多

Lean 相关

由于各自不同的原因，发现大家这个学期都开始学习起 Lean 了起来，我也不能免俗囧。L∃∀N 一看 logo 就很帅，有点 DUNE 的设计感有没有？ 感觉首要工作是先复习一下 Haskell，这样也不必中途翻阅语法手册。显然 Lean4 从 Haskell 里借鉴了相当多的语法和设计思想，说来惭愧，虽然我之前试图用 Haskell 刷刷题，但是总是感觉不得要领，被复杂度卡的死死的囧不得不中途切回 cpp 艹。fingertree 什么的也看的云里雾里，感觉还是我的姿势水平不够，还需特别努力！ 然后初学 Lean 我是建议先看 Mathematics in Lean，本书直接使用 mathlib，让你不必过早的被细节劝退，又可以顺便复习一下熟悉的数学知识（初等数论她不香吗，天天学代数人都学傻了）。而且还提供对应的 Github 仓库，可以 step-by-step 边看别改。Lean 不能没有 mathlib，就像是 cpp 不能没有 std，西方不能没有耶路撒冷？ （目前感觉这语言除了优化不行哪哪都还可以？） 再然后感觉可以试试写点题目，比如可以试试先证明静态直径算法？ 学习 Lean (proof assistant), Wikipedia https://leanprover-community.github.io/learn.html Lean Focused Research Organization Theorem Proving in Lean Mathematics in Lean Type […]

2024/5/11
阅读更多

动态直径相关

众所周知，求直径有两种经典方法，两次 dfs() 和树形 dp。其中前者要求边权非负。这是因为在边权非负的情况下，我们插入一个新节点，直径要么不变，要么其中一个点和原先的直径重合，因而经典的合并子树维护直径的算法也依赖这个性质。 盘点一下动态直径的做法基本也可以分为两大类： 链分治 这种做法是对 dp 做法的衍生，因为轻重边树链剖分（Heavy Light Decomposition）也可以看成是链分治（Centroid Path Decomposition），所以我们把各种树链剖分也算在内。 动态树和 Top Tree 也都可以从链分治的视角来审视， 所以至少有下面三类做法： 链分治 动态树 https://codeforces.com/contest/1192/submission/259130679 Top Tree 子树合并 还有一类做法是基于边权非负时直径的可合并性，这衍生出另外几种做法， 线段树维护点分树 https://codeforces.com/contest/1192/submission/58806431 splay 维护括号序列 ？ 线段树维护 eular/dfs 序 https://codeforces.com/contest/1192/submission/189685098 通常说来如果题目告诉你非负那么通常这类做法更好写。 （当然上面链分治的时候也可以利用这个性质来进行状态转移，来写出常数也许更低的版本。） 题目 SPOJ QTREE4 SPOJ QTREE5 LOJ #6038. 「雅礼集训 2017 Day5」远行

2024/5/4
阅读更多

BZOJ 3153. Sone1

https://darkbzoj.cc/problem/3153 https://www.luogu.com.cn/problem/P5649 Top Tree 入门题，久闻大名！今天来挑战（自虐）一下。虽说是 Top Tree 入门题，但是网上大部分代码都是用 AAAT（参见某集训队论文，这个称呼甚至真的只是占位符而不是发明人名字缩写），也就是 Splay 维护虚子树信息的三叉动态树，其实我们之前也是遇到过三叉动态树的，比如： QTREE4 | QTREE5 | QTREE7 SRM 624 Div1 1000. TreeColoring CF1192B Dynamic Diameter 不过这几个题都不涉及子树修改，所以只需要 access() 的时候顺手维护虚子树的状态即可逃课，而这个题里我们终于不得不直面灾厄了 … 和一般的三叉动态树里我们遇到的状况一样，最难的就是把 access() 过程里的虚实切换讨论清楚。 首先看图。我们增加辅助节点，来维护虚子树组成的 leafy tree， leafy tree https://oi-wiki.org/ds/wblt/ https://oi-wiki.org/ds/leafy-tree/ 添加辅助节点的想法，则类似于边分治里面我们强行弄成完全二叉树，不过这里和线段树那种 leafy tree 不同，我们可以直接用 Splay 来维护，因此插入一个新节点非常容易写，然后 … 搜了一圈，感觉 jerry3128 的这篇文章 写的最好，甚至给了四种方法的对比，基本上除了常数部分的复杂度分析都讲得特别清楚了 Orz。

2024/5/1
阅读更多

Top Tree 学习笔记

最近一场的 ABC 的最后一题，官方题解介绍了一种基于 static top tree 的做法，虽然这个题明明可以直接用树链剖分。 然后我发现这个题解我读的并不是很懂，仔细复习了一下发现我之前对 top tree 的理解有误区。读了 negiizhao 的文章后认识到应该从历史文献中找线索，所以： Top Tree: A top tree is a binary tree that embodies a contraction of a tree into a single edge via a sequence of rake and compress operations. 所以根据 Tarjan 的定义，Top Tree 一定是一个反应从独立的边开始反向通过 rake/compress 操作合并成单一簇的结构，也许类似思路的还有记录点分治过程形成的点分树，Kruskal 重构树还有划分树、Gomory–Hu Tree 这类结构。 当然关于 Link-Cut Tree、Top Tree […]

2024/5/1
阅读更多

The 2023 ICPC World Finals Luxor

首先恭喜 jly!!! Orz，然后怎么还没人写题解？我来对着标程口胡一下 = =。 https://codeforces.com/blog/entry/128559 https://github.com/SnapDragon64/ACMFinalsSolutions/tree/master/finals2023 Problem Y. Compression 相邻的相同元素都先压缩掉，然后因为只有..010101… 所以连续删除末尾偶数个字符，直到长度 <= 3 即可。 Problem P. Turning Red 第一反应解模线性方程，但是有一个灯至多只关联两个按钮这个额外条件，因而知道一个按钮的状态，就能立刻推出另一个，于是就变成签到题了。 我们将灯和按钮视作二分图，对于每个连通块，我们只需要枚举其中任意一个按钮的状态，其它按钮的状态就都能确定，在 dfs 的过程中看有没有矛盾即可，代码也很像二分图判定。 Problem W. Riddle of the Sphinx 脑经急转弯，先问 a,b,c,a+b+c，如果不自洽那么要么是前面 a,b,c 错，那么 a+b+c 错。此时我们再问 a+2b+3c，如果和 a,b,c 仍然不自洽那么说明其中有一个是假的，但此时我们可以通过后两问的线性组合，得到不依赖其中一个元素且百分百正确的询问，从而寻找出哪一个询问为假。 Problem Q. Doing the Container Shuffle 非常有趣的概率题，第一反应当然是利用期望的线性性质，每个轮次独立讨论，感觉像是某种逆序对的板子。 但是有个麻烦的点是这个移动的过程会有一些后效性，破坏之后的状态。。。 但是发现分类讨论之后，这个过程居然产生的影响也是局部的！直接取 min(cur, last) 进行每个轮次的询问即可 Orz。 Problem V. Three Kinds […]

2024/4/23
阅读更多

新巴别塔

旧约 说来惭愧，我最早是从某本软件工程的书里了解到的巴别塔这个典故的（因为我毕竟真的是软件工程系嘛。。。我系的经典作品还是要读一下的！虽然我更喜欢理论但是毕竟 math 太鶸 = =。。）那本书自然就是 —— 《人月神话》了。当然，那本书的角度，是认为交流导致信任的缺失、而信任的缺失进而导致工程的失败，和原本的命题 —— 人类是无法相互理解的，关联并不大。 直到今天我依然十分喜欢那本书的各种隐喻的，无论是焦油坑还是巴别塔，但是那本书的结论，放在今天依然成立吗？ 这似乎是要打个问号的，面向对象自然不是，开源软件也有一些问题，区块链嘛当然也不够成熟、但今天我们还有 llama3 呢！ 新约 所以前段时间偶然读到《二次元手游与萌文化的歧路》那篇文章的时候，起初我并没有十分理解，囫囵吞枣的就翻过去了 —— 这也容易解释，我是杂食动物，主机、PC、二游、同人、黄油、链游… 就没有我不涉猎的。但我毕竟没有深入的玩过原神（太肝了的就不是我的菜），也不玩社区，所以那篇文章里很多东西读的云里雾里。 但是随着最近麻辣仙人的这波攻势，使得很多原本文章里的观点，变得不言自明了。= = （不愧是先知啊！） 【没补档】史黄色精英论坛是如何通过循环论证批量生产谣言的 【吐槽向】麻辣人是如何扰乱社区的 作为一个杂食动物，其实我很多时候还是无法理解麻辣仙人的逻辑 —— 为什么我们不去玩《兰斯》系列，或者《ドーナドーナ》？珀尔诺她的身体难道不更香吗… 一些分析尝试解答上面的问题，它们认为： 1. 麻辣仙人与其说玩游戏，不如说玩的是社区。 2. 麻辣仙人享受自己受害人的身份。 3. 麻辣仙人的诉求不在于二次元纸片人ml，而是要让所有厂商和其他玩家对自己ml。 这也是区分麻辣仙人和 ml 玩家的核心 criteria。 「你们为什么胆怯？」 当然，按照歧路先知的观点，我们不应该再继续挖掘下去了 —— 因为再继续看下去就要有害身心健康了 —— 但是越是这样反而越令人好奇，毕竟人类就是这样，好奇心害死猫。另一方面这一群体居然现在是如此的庞大，使得我们不得不去解构背后的原理和成因了。我们不禁要问，造成这一切的原点是什么？简单的用巴别塔的隐喻来说明似乎是远远不够的。。。 那么我的观点是，原点就是这个！随着时间的演变，用今天流行的话来说，就是 —— 引天雷。 单纯从战术层面上说，这个肯定是一个高级技巧，很多作品里的角色都有引天雷的技能，最符合字面的例子可能是《火影忍者》里的雷遁麒麟，佐助在和鼬决战的时候用这招打掉鼬一条命。其次想到的是《三国杀》里的张角、还有司马懿也都可以通过改判定的方式 literally 引天雷。btw 张角在《三国志11》里直接就有妖术和落雷，但那是主动技所以不算～一定要利用环境才算～比如最近的一些《魔兽争霸3》单侍僧挑战电脑（令人发狂的）的视频里利用野怪坑死电脑英雄的战术就比较符合这种设定。 【魔兽争霸3】 挑战发狂电脑下限的新世界纪录 当然我们这里的情况 —— […]

2024/4/20
阅读更多

Sora 的想象与思考

Not everything that isn’t true is a lie. —— Black Mirror You can’t fight progress. The best you can do is ignore it, until it finally takes your livelihood and self-respect away. —— Kurt Vonnegut，Jr. 后 ChatGPT 时代，人工智能的发展似乎没有我们想象的那样慢，也没有我们想象的那样快，它以一种温和的、如同温水煮青蛙般的节奏正在缓慢的侵蚀着我们曾经熟悉的周遭世界。 尽管依然有 很多、很多 fundamental 的 问题 没有解决，在刚刚结束的农历新年里，依然有许多非常重要的 Breakthrough 正在发生着。 Google 发布了 Gemeni 1.5，Navida 发布了 Chat with RTX，当然这其中最让人震惊的一定还是 OpenAI […]

2024/2/19
阅读更多

test

test The function is_square(n) typically checks if a given number [ n ] is a perfect square.

2023/11/15
阅读更多

Facebook Hacker Cup 2023 Round 1

TBD

2023/10/7
阅读更多

AtCoder Beginner Contest 322

TBD

2023/10/7
阅读更多

LLaMA 2 相关

哪里玩原版 / LLaMA 2 Demo HuggingChat/Llama-2-70b-chat-hf Hugging Face Space 7B | 13B | 70B Perplexity 7B/13B Replicate 7B | 13B | 70B sdk.vercel.ai nat.dev 怎么玩 / How to Prompt <s>[INST] <<SYS>> {{ system_prompt }} <</SYS>> {{ user_message }} [/INST] <s>[INST] <<SYS>> {{ system_prompt }} <</SYS>> {{ user_msg_1 }} [/INST] {{ model_answer_1 }} </s>\ <s>[INST] {{ […]

2023/7/21
阅读更多

HuggingFace AI Game Jam

https://twitter.com/huggingface/status/1682400068626677760 https://twitter.com/dylan_ebert_/status/1682413292646481922

2023/7/21
阅读更多

ACL 2023

Tutorials T1: Goal Awareness for Conversational AI: Proactivity, Non-collaborativity, and Beyond T2: Complex Reasoning in Natural Language T3: Everything you need to know about Multilingual LLMs: Towards fair, performant and reliable models for languages of the world T4: Generating Text from Language Models T5: Indirectly Supervised Natural Language Processing T6: Retrieval-based Language Models and Applications […]

2023/7/11
阅读更多

Trans 相关…

https://www.youtube.com/@ContraPoints The Gender Dysphoria Bible https://knowyourmeme.com/memes/egg-transgender

2023/7/8
阅读更多

Note on 人工智能转岗经验谈

最近转岗了人工智能方向，（等等，你不是 Crypto 选手吗？但是考虑到你看人家巴比特都 All in AI，顺带还把 Crypto 一顿踩，我这个也没什么丢人的吧哈哈哈。）考虑到应该有很多人需要吧，我记录一下自己的经验。 《算法导论》 可能很多人不知道，最新版的《算法导论》更新了一个 Selected Topic 章节，专门讲了机器学习！内容是最最基础的 聚类（Clustering） 和 梯度下降（Gradient descent） 哈哈。内容和 吴恩达的那个 差不太多。但我会认为《算法导论》编排的更好，因为后者有些过于 self-contained 了，前者会给我们更多的 cross link 和复杂度、误差的分析。。。 啊。。要是我早看了这个，之前 几次 百度之星决赛 的时候是不是就可以都 auto-win 了（某平行世界线） 14 年支持向量机 15 年乱搞 16 年 RL 所以其实 ML 的基础知识真的越来越重要的，面试无关岗位的时候说不定还会冷不防问你一下= =。。。而且，其实更早的时候，IPSC 里就考过一次 ML 的算法（16 年 L 题），还是最简单的 MNIST 那个东西。。。你看，你只要掌握了基本的 ML 知识，你就能领先我们一大堆选手了！ 《21 个项目玩转 TensorFlow》 […]

2023/6/26
阅读更多

CodeTON Round 5

Problem E. Tenzing and Triangle 只要能写出暴力 dp 就成功了 90% 啦！ 不妨先把所有点都加起来，考虑最优能通过覆盖节省多少。我们发现一个有用的性质是，三角形覆盖的区域，是不需要重叠的，因此似乎可以简单的 1D/1D 动态规划。 这里我们用树状数组，可以维护出三角形覆盖区域的代价。 #include <lastweapon/io> #include <lastweapon/fenwicktree> using namespace lastweapon; const int N = int(2e5) + 9; int n, k, A; vector<PII> P[N]; LL f[N]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n,k,A); LL z = 0; REP(i ,n) […]

2023/6/25
阅读更多

DMOPC ’22 Contest 5 P5 – Twos and Threes

https://dmoj.ca/problem/dmopc22c5p5/editorial 题意：给定一个含有障碍的棋盘，问是否可以用 1×2、1×3、和长度 3 的 L 形多米诺骨牌完美覆盖。 分析：先弱化问题，考虑如果只有多米诺骨牌，那么判断是否能铺满只需要二分图匹配即可，进一步如果我们考虑 L 形，可以用网络流建模，参考 这个题。因此基本思想可能是某种网络流？ 看起来也确实如此，每个点至少连 1 个，至多连 2 个，所以上下界网络流即可。

2023/6/24
阅读更多

AI 伴侣相关

a16z, It’s Not a Computer, It’s a Companion! Li Jin, Building Psychological Attachment — Not Just Ownership — Into Web3

2023/6/23
阅读更多

Luogu P2179. [NOI2012] 骑行川藏

https://www.luogu.com.cn/problem/P2179 最优解情况下每个分量的导数相同，二分这个导数即可。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e4) + 9; int n; double e, s[N], k[N], u[N]; double calcV(double x, int i) { double l = 0, r = INF, mid; int cnt = 233; while(cnt--) { mid = (l+r)/2; if(2*k[i]*s[i]*mid*mid*(mid-u[i])*x > -s[i]) l = mid ;else r = mid; } […]

2023/6/22
阅读更多

Note

VC perspective Sequoia, The New Language Model Stack A16Z, Emerging Architectures for LLM Applications 红杉美国最新AI预判｜新的语言模型技术栈全解 a16z最新预判｜AI虚拟陪伴生态全解析 朱啸虎：ChatGpt对创业公司很不友好，未来两三年内请大家放弃融资幻想 | 大模型创业价值消失了？朱啸虎与傅盛隔空激辩 AI or die: ushering in a new era of user research The bigger-is-better approach to AI is running out of road 大模型的改进 Compression rate zxytim, 压缩下一个 token 通向超过人类的智能 Token size https://www.anthropic.com/index/100k-context-windows https://mp.weixin.qq.com/s/p4JfnUE5cbRZtiIJPRr2LQ Extending Context Window of […]

2023/6/21
阅读更多

《重返未来：1999》节奏相关

钝评1999运营，问题很多，但从数据来看节奏可能没那么大 《重返未来：1999》跌入塔西佗陷阱，国产二游工业化飞蛾 《重返未来：1999》开服快有一个月了，tl;dr:，对这个游戏我的感想就是。。。 —— 不讨论游戏性我们还能做朋友。 就是我给人推荐的时候也希望大家只看她的剧情的而不要去下载游戏坐牢的。《重返未来：1999》是一款优点和缺点都非常明显的游戏，她的优点是，剧情本身和电影化的演出是非常打动我的，以至于让我感觉它甚至不像是一款手游。特别是维尔汀这个角色，让我的代入感非常强，让我回忆起很多学校里的回忆，第三章的剧情直接骗了我好多的眼泪，但是考虑到我现在什么都不做发发呆也有可能流眼泪，所以未必是个很有说服力的 Case。它的剧情主旨，神秘学家的设定，不管你理解成《哈利波特》那样的魔法师，还是 Think Different 里的 Those who think different，还是历史上的少数族群，我觉得都是非常棒的解读。 但她的缺点太过于明显了，作为一款商业游戏，她被设计的十分不好玩，这一点在糟糕的运营和策划的共同努力之下，被无限放大了，如果说开服的争议还能通过运营的手段抢救回来的话，现在就连我都觉得她已经是一款将死的作品了。。。这不能不让人反思和警醒。 （WIP

2023/6/18
阅读更多

Luogu P2050. [NOI2012] 美食节

https://www.luogu.com.cn/problem/P2050 用 上一题 的做法可以拿 60 分，考虑优化。我们发现对于每个厨师，它所被利用的边一定是一组前缀，因此可以贪心每进行一次增广后再动态加入新的边。 #include <lastweapon/io> #include <lastweapon/mincostflow> using namespace lastweapon; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int n, m, p; RD(n, m); p = 800; int s = n+m*p, t = s+1, nn = 0; mcf_graph<int, int> G(t+1); REP(i, n) G.add_edge(s, i, RD(), 0); REP(i, p) […]

2023/6/13
阅读更多

Luogu P2053. [SCOI2007] 修车

https://www.luogu.com.cn/problem/P2053 看起来可以 dp，不过每个人修每个车地代价并不相同。 于是可以二分图建模。 #include <lastweapon/io> #include <lastweapon/mincostflow> using namespace lastweapon; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int m, n; RD(m, n); int s = n*(m+1), t = s+1; mcf_graph<int, int> G(t+1); REP(i, n) { G.add_edge(s, i, 1, 0); REP(j, m) { G.add_edge(n*(j+1)+i, t, 1, 0); int c; RD(c); […]

2023/6/13
阅读更多

Luogu P1973. [NOI2011] NOI 嘉年华

https://www.luogu.com.cn/problem/P1973 O(n4) 暴力写的好是能过得。。。。 #include <lastweapon/io> using namespace lastweapon; const int N = 200 + 1, PN = N*2 + 1; VI P; int L[N], R[N], s[PN][PN]; int pre[PN][N], suf[PN][N]; // 一边为 j，另一边至多 int f[PN][PN]; int n, pn; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n); REP(i, n) { RD(L[i], R[i]); […]

2023/6/10
阅读更多

Luogu P1971. [NOI2011] 兔兔与蛋蛋游戏

https://www.luogu.com.cn/problem/P1971 https://vjudge.net/problem/HDU-3446

2023/6/10
阅读更多

Luogu P1995. [NOI2011] 智能车比赛

https://www.luogu.com.cn/problem/P1995 先复习一下 这个题。。。 #include <lastweapon/geometry> using namespace lastweapon; using namespace CG; const int N = 21; DB dp[N][4], x[N], y[N][4]; int n; bool ok(int i0, int j0, int i1, int j1) { Line s(Po(x[i0], y[i0][j0]), Po(x[i1], y[i1][j1])); FOR(i, i0+1, i1) { if(Seg(Po(x[i], y[i][0]), Po(x[i], y[i][1])).sgn(s) < 0 && Seg(Po(x[i], y[i][2]), Po(x[i], y[i][3])).sgn(s) < 0) return […]

2023/6/9
阅读更多

Luogu P2086. [NOI2012] 魔幻棋盘

https://www.luogu.com.cn/problem/P2086 差分维护 gcd 是一个很常见的技巧了。。 先写个线段树拿点部分分吧。。。（然后发现讨论 n,m 大小。。暴力开 o2 能过。） #include <lastweapon/io> // #include <lastweapon/segtree> using namespace lastweapon; const int N = int(5e5)+9; /* LL gcd(LL a,LL b) { return b?gcd(b,a%b):abs(a); }*/ inline LL gcd(LL a,LL b) { if(a<0) a=-a; if(b<0) b=-b; if(!a) return b; if(!b) return a; LL t=__builtin_ctzll(a|b),tmp; a>>=__builtin_ctzll(a); do { b>>=__builtin_ctzll(b); if(a>b) { […]

2023/6/9
阅读更多

Luogu P1933. [NOI2010] 旅行路线

https://www.luogu.com.cn/problem/P1933 经典插头 dp，但是和传统的一条路径问题相比，我们还需要压缩进轮廓线上位置的标号，还要维护插头的方向（递增还是递降），然后关键是插头的方向信息在 m=3 的情况下，是可以客串连通性信息的，这样可以把插头控制在 int 范围里（恰好 32 位，注意用 uint。） /* Last Weapon is my own algorithms library for competitive programming, it is a fork from ACL with some alternative algorithms and additional features. Use it at your own risk. Repo: https://github.com/lychees/last-weapon Blog: https://www.shuizilong.com/house */ #pragma comment(linker, "/STACK:36777216") #define LOCAL #include <functional> #include <algorithm> #include […]

2023/6/8
阅读更多

Luogu P1954. [NOI2010] 航空管制

https://www.luogu.com.cn/problem/P1954 第一问显然可以 dag dp，求出每个点的真实最晚发车时间， 然后用这个东西贪心构造。 第二问还是用同一个 dp 数组，不过这次贪心构造的时候，我们忽略所有询问点传递闭包里的节点。 #include <lastweapon/io> using namespace lastweapon; const int N = int(2e3)+9; VI adj[N], rdj[N]; int f[N], k[N], o[N]; bool vis[N]; int n, m; void dfs(int u = 0) { vis[u] = 1; f[u] = k[u]; for (auto v: adj[u]) { if (!vis[v]) dfs(v); checkMin(f[u], (f[v] ? f[v] : […]

2023/6/8
阅读更多

Luogu P2048. [NOI2010] 超级钢琴

https://darkbzoj.cc/problem/2006 https://www.luogu.com.cn/problem/P2048 可以先写一个暴力 RMQ 解决 K=1 的 10 分代码，确保自己没读错题理解成字符串问题了囧。 那么 top K 可以用类似 [USACO3.1]丑数 Humble Numbers 那个题里的方法，开个堆，每次找到一个数就分裂一下塞回去。 这个题数据量足够大，询问数组的下标从 0 开始，还要询问 rmq 的位置，非常适合用我们新学习的 O(n)-O(1) RMQ 大显身手！。。。 #include <lastweapon/bitwise> using namespace lastweapon; const int N = int(5e5) + 9; int s[N]; int n, K, L, R; template<typename T> struct rmq { vector<T> v; int n; static const […]

2023/6/7
阅读更多

Luogu P2046. [NOI2010] 海拔

https://www.luogu.com.cn/problem/P2046 简单的平面图最小割，难点是证这个是最小割。 代码主打的是一手对称。= = #include <lastweapon/io> #include <lastweapon/dijkstra> using namespace lastweapon; int n, s, t; int id(int x, int y) { if (x == -1 || y == n) return s; if (x == n || y == -1) return t; return x*n + y; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", […]

2023/6/7
阅读更多

Luogu P3227. [HNOI2013] 切糕

https://www.luogu.com.cn/problem/P3227 简单最小割~ #include <lastweapon/io> #include <lastweapon/maxflow> using namespace lastweapon; int P, Q, R, D, s, t; int id(int p, int q, int r) { return r*P*Q + p*Q + q; } bool inGrid(int p, int q) { return 0 <= p && p < P && 0 <= q && q < Q; } int […]

2023/6/6
阅读更多

Luogu P8500. [NOI2022] 冒泡排序

https://uoj.ac/problem/768 https://www.luogu.com.cn/problem/P8500 区间相交当然是很麻烦的。。前几天 CF #875 C 的时候还能用 hash 大法蒙混过关。。这次肯定不行了。。 我们先把这种情况放在最后处理，先写一个 28 分的代码。 Lemma 1. 我们只需要利用条件中出现的值。 这个性质可以指导我们进行离散化，从而方便使用各种数据结构。 Lemma 2. 对于性质 B 的情况，未确定的数单调递增。 可以简单调整得到，Vijos 1893 也考察了交换带来的具体影响。 所以在这种情况下我们可以不统计 未确定数和未确定数之间 的逆序对，因为必然是 0，但是这个性质不是通用的，我们不如先把所有数填出来，最后统一跑一遍求逆序对的代码，这样可以减少讨论。 Lemma 3. 从左到右扫描时，对于能填的数，尽量在最优情况下填更小的值。 这个是上面的性质的推广，显然对我们更有用。 所以综上所述，我们只需要开一棵线段树，记录当前填每个数时的代价，然后每次区间修改，区间求最小值即可。 最后只要考虑区间交就可以了。 我们最终的目标是处理出两个数组，A[] 表示所有已经被填的数，B[] 表示未填数的下界。 然后用线段树扫一遍，得到完整的 A[] 即可。 再看看性质 A，1 的情况那么全部只能填 1，直接填进 A[] 里，对于 0 的情况，我们希望继续利用 Lemma 3，从右向左扫描区间，尽可能晚的去填数。 最后去掉性质 A 只要按权值从大到小然后用并查集挖去每个阶段处理过的位置即可。 https://uoj.ac/submission/626775

2023/6/6
阅读更多

Luogu P3629. [APIO2010] 巡逻

https://www.luogu.com.cn/problem/P3629 求两次直径的高级做法好像已经烂大街了。。 这里贴一下更常规的换根 dp。。 做法就是 Two Paths 多考虑一种情况即可~~ #include <lastweapon/io> using namespace lastweapon; const int N = int(3e5) + 9; int dn[N], up[N]; // 子树内直径，子树外直径 int d[N][4], e[N]; // 子数内 top4 最长距离，子树外最长距离 VI adj[N]; int n, K, z; void upd(int d[], int v) { if (v > d[0]) d[3] = d[2], d[2] = d[1], d[1] […]

2023/6/5
阅读更多

USACO 2018 February Contest, Gold Problem 2. Directory Traversal

基本就是 Tree Distances II， 转移函数稍微调整下。 #include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; int n, m, h[N], c[N], l[N]; LL f[N], g[N]; VVI v; void dfs1(int r, int p = -1) { for(int& a : v[r]) if (a != p) { dfs1(a, r); h[r] += h[a]; f[r] += f[a] + h[a]*l[a]; […]

2023/6/5
阅读更多

Luogu P3647. [APIO2014] 连珠线

https://www.luogu.com.cn/problem/P3647 https://oj.uz/problem/view/APIO14_beads 无根树不太好设计状态，想办法转成有根树，然后用子树替换大法。 再跑换根 dp。 我永远爱宏。 #include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; int d[N][2], e[N][2], z; VII adj[N]; int n; #define dv (max(d[v][0], d[v][1] + w)) #define tv ((d[v][0] + w) - dv) #define dp (max(e[u][0], e[u][1] + pw)) #define tp ((e[u][0] + pw) - dp) void dfs1(int u […]

2023/6/4
阅读更多

IZhO 2017. Problem F. Hard route

https://oj.uz/problem/view/IZhO17_road 如果不考虑方案数的话是非常好写的，类似上一题，我们只需要维护向下的 top3 和向上的 top1 即可。 然后用均值不等式可以得到最优解一定是 a*(b+c) | a >= b >= c。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e5) + 9; int dn[N][3], up[N]; VI adj[N]; int n; void upd(int d[], int v) { if (v > d[0]) d[2] = d[1], d[1] = d[0], d[0] = v; else if (v […]

2023/6/3
阅读更多

SPOJ TWOPATHS. Two Paths

https://www.spoj.com/problems/TWOPATHS/ https://codeforces.com/problemset/problem/14/D 题意：求两条不相交路径的积的最大值。 分析：dfs 序维护直径 有一个非常棒的性质。。。就是可以求子树内的直径和子树外的直径。。所以我们只要再 dfs 一次，然后每次 query 出来两个直径乘一下。。可惜 O(nlogn) 也许过不了大数据。。。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e5) + 9; int L[N], R[N], dep[N], id[N], nn; VI adj[N]; int n; struct rec{ int d, dd, ld, rd, D; void init(LL _d, LL _dd) { d = _d; dd = 2*_dd; D […]

2023/6/2
阅读更多

换根 dp

http://www.usaco.org/index.php?page=viewproblem2&cpid=766 #include <lastweapon/number> using namespace lastweapon; const int N = int(1e5) + 9; VI adj[N]; Int f[N][3]; int c[N]; int n, k; Int s(int u) { return f[u][0] + f[u][1] + f[u][2]; } void dfs(int u = 0, int p = -1) { REP(i, 3) if (!c[u] || (c[u]-1) == i) f[u][i] = 1; for […]

2023/6/1
阅读更多

洪恩电脑 —— 开天辟地

开天辟地 2 开天辟地 7 奇怪的旧 CD 收藏网站 我只是想找 这个题 的原型。。但是也许 flashpoint 里就有？

2023/5/30
阅读更多

Facebook Hacker Cup 2022 Round 2

https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2 Problem A. Perfectly Balanced 题意：给定一个字符串，每次询问一个子串，问是否是几乎平衡的。 几乎平衡的定义是，从子串中删除一个字符后，长度为偶数，且前半段中每个字符的出现次数与后半段相等。 A1 中字符集来自小写字符。A2 中字符集来自任意 int。 分析：再考虑弱化，如果字符集只有 {0, 1}，那么我们只要先判断下长度是否为奇数，然后枚举一下删哪个位置，然后树状数组比较一下两段 1 的个数是否一样即可。 再考虑如何不枚举删哪个位置，哪么就讨论从哪边删，然后看两边的 diff 是否是一即可。设 S(l, r) 表示 [l, r) 这个区间里 1 出现的次数，那么就是比较一下 S(ml, r) – S(l, ml) = 1 或者 S(l, mr) – S(mr, r) = 1。 因此对于 A1，我们只要开 25 棵树状数组就能通过。对于字符集任意的情况，我们把所有数字映射成一个随机 uint，然后看 diff 是否恰好是某个字符的映射即可。代码反而比 A1 更简单。 #include <lastweapon/bitwise> #include <lastweapon/fenwicktree> […]

2023/5/29
阅读更多

Codeforces Round #875

久违地冲了一局。。。无悬念的差点爆 0 了。 Problem A. Copil Copac Draws Trees 题意：给定一个树，和边，初始根节点是点亮的，每回合你可以按照边地顺序扫一遍所有边，如果其中一个点是点亮的，那么点亮另一个点。问多少回合后所有点被点亮。 分析：显然不考虑边顺序的话，就是求树的深度，这个过程也可以看作树 dp。。 dp[i] 存两个值，分别表示最少被点亮所需的回合数，和被点亮时所用边的编号。转移的时候讨论一下编号即可。 Problem C. Hyperregular Bracket Strings 题意：问有多少长度 n 的合法括号序列，满足给定的所有区间也时合法的括号序列。 分析：个人感觉非常棒的题目。首先不考虑区间的话就是卡塔兰数 {C_i}。 然后考察 [1,4] [2,3] 和 [1,3] [2,4] 两种情况，前者比较容易分析，[2,3] 现在一定是一个独立的合法括号序列，[1]-[4] 然后两个位置虽然不连续，但是也构成一个独立的合法括号序列。而后者 [2,3] 则要求 [1] [2,3] [4] 分别是三组独立的卡塔兰序列，因为中间重合的部分对前缀和的 delta 一定是 0（反证法）。 这样看的话最后结果一定是若干 {C_i} 相乘，难点就是分解出这些独立的区间的测度，看起来结构简单，写起来却并不容易，我们无法像表达式解析那样简单的递归或者用一个栈，考虑到还有区间共享端点的情况就更麻烦了。 然后有一个非常巧妙地思路。。。给每个区间随机分配一个 uint 数，然后把前缀和改成 xor 前缀和，然后用 hash[] 记录每种区间集合影响下的测度数，就能轻易处理不连续的状态，并区分上面说到的嵌套和重叠两种情况了。 这种 hash 的思想非常实用，比如去年 […]

2023/5/28
阅读更多

Luogu P5828 边双连通图计数

https://www.luogu.com.cn/problem/P5828 和 上一题 几乎一样，双倍经验！ #include <lastweapon/poly> using namespace lastweapon; Poly H, HH; int n; LL C2(LL n) { return n*(n-1)/2; } int b(int n) { Poly A(n); REP(i, n) A[i] = H[i] * -n; Poly B = HH.mod(n) * A.exp(); return (B[n-1] * fac[n-1] / n).x; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif […]

2023/5/28
阅读更多

EC Final

2018 Gym Bilibili J.Philosophical … Balance 题意：给定一个长为 n 的字符串，记 s_i 为从 i 开始的后缀，求：     n ≤ 2×10^5 做法：lcp + 纳什均衡 2019 Gym 2021 Gym

2023/5/27
阅读更多

拉格朗日反演定理

资料 浅谈多项式复合和拉格朗日反演, alpha1022 多项式复合和拉格朗日反演 学习笔记, siriehn_nx Newton’s Method of Polynomial, picks Lagrange inversion theorem, adamant 这个东西好像具体数学里也提到过。。。但是角度不太一样？？ 习题 Luogu P5373. 【模板】多项式复合函数 Luogu P5809. 【模板】多项式复合逆

2023/5/27
阅读更多

Luogu P5827. 点双连通图计数

https://www.luogu.com.cn/problem/P5827 有一个东西叫做 labeled counting lemma。其实就是交代了 EGF 卷积的组合意义。 说的是给两个 EGF，F(x), G(x)，那么 F(x)*G(x) 就是这两个对象重新标号之后所生成的对象的有序对，比如如果 C(x) 是连通图。那么 C^k(x)/k! 就是有 k 个连通分量的图，进一步就能推出 EGF 里 exp 的组合意义。 这个题多项式很容易构建，因为任意图都可以构建出 block-cut tree~ 方法是我们思考有根版本的 C(x)，那么这个根节点一定在一个 block 里，我们枚举这个 block 的 size i，那么这个 block 剩下的部分都能连一个 C(x)。。这部分就是 C(x)^(i-1)，然后再乘以 b_i 就好。。。这个部分可以用 exp 表达。 剩下的是这个题的难点，就是拉格朗日定理。。其实有标号树就应该要学会这个。。只是那个问题里我们有太多方法可以逃课。。 在有根树问题里，移除了根节点之后，剩下的就是有根树本身的生成集族，所以有递归公式： (1)   剩下的全都是拉格朗日反演的代数技巧，我们类比这种做法来解决点双和边双的计数问题，核心都是建立各自的 EGF 与 有根连通图 EGF 之间的关系，我们不妨也设它们分别为 b = B(x)、y = […]

2023/5/26
阅读更多

无标号连通图

https://oeis.org/A001349 Weisstein, Eric W. “Euler Transform.” From MathWorld–A Wolfram Web Resource. 题解 P5900 【无标号无根树计数】 没找到相关的题目0.0. #include <lastweapon/poly> #include <lastweapon/number> using namespace lastweapon; const int N = int(1e2) + 9; VVI Partition; VI cur; int n, m; void gen(int n, int s = 1){ if (!n){ Partition.PB(cur); } else if (n >= s){ cur.PB(s); gen(n-s, s); […]

2023/5/24
阅读更多

AtCoder Beginner Contest 284

Ex. Count Unlabeled Graphs k = 1 的情况下，显然就是无标号图计数。 所以做法也必然不会弱于 原题。 回忆原题中，我们对点集的对称群，按照 cycle index 进行分类，再去生成对应的边置换群，再得到边置换群的 cycle index。不过看起来这里我们既要考虑边染色，还要考虑点染色，好在它们的结构都是用初始的点群的 cycle index 所决定的，可以一起参与计算。 最后再 简单冗斥 一下即可。 #include <lastweapon/number> using namespace lastweapon; const int N = int(5e1) + 9; Int Fact[N]; VVI Partition; VI cur; int n; void gen(int n = ::n, int s = 1){ if (!n){ Partition.PB(cur); } […]

2023/5/23
阅读更多

Luogu P4708. 画画

题意 无标号欧拉图计数 分析 做法基本和 SGU 282. Isomorphism 一样。 #include <lastweapon/number> using namespace lastweapon; const int N = int(5e1) + 9; Int Fact[N]; VVI Partition; VI cur; int n; void gen(int n = ::n, int s = 1){ if (!n){ Partition.PB(cur); } else if (n >= s){ cur.PB(s); gen(n-s, s); cur.pop_back(); gen(n, s+1); } } Int […]

2023/5/23
阅读更多

Luogu P6295. 有标号 DAG 计数

对于有标号图，假设我们得到了不连通情况下的 EGF，那么求对应的连通图有常见套路（可参见 城市规划那个题 和 荒漠那个题）。 因而问题转换为不连通的情况，也就是 上一题。 我们需要先想办法构造卷积。 (1)   这里需要用一些 trick，最后得到。 (2)   #include <lastweapon/poly> #include <lastweapon/number> using namespace lastweapon; LL C2(LL n) { return n*(n-1)/2; } int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); #endif int n; RD(n)++; Poly F(n); Mint i2 = invFac[2]; FOR(i, 1, n) { F[i] = invFac[i] * pow(i2, […]

2023/5/19
阅读更多

BZOJ #2863. 愤怒的元首

设 表示恰好有 j 个点入度为 0 的方案，有： (1)   复杂度 O(n3)，我们可以利用前缀和 + 冗斥优化掉里层的枚举，有： (2)   这里利用了牛顿二项式展开，(1+x)^n，把 x = -1 代入。

2023/5/19
阅读更多

HDU 3303. Harmony Forever

题意 对于集合S，有两种操作：1、B X；2、A Y。B X代表将X加入集合S，并赋予X一个序号，代表它是第几个数；A Y代表从集合S中找出mod Y最小的数，输出的是该数的序号。 做法 非常厉害的一个题。 对 y 进行讨论，小的 y 每次加数的时候暴力更新，而大的 y 转换成 rmq 问题。 （这个我觉得是这题的难点，对于取模操作我很难去往看起来复杂度更高的 rmq 上面想。） 注意到这个 rmq 我们是可以离线的，而对于静态的问题是可以单调栈的（参考之前的 O(n)-O(1) RMQ），而只有加数操作，可以变成集合分裂，反过来就变成并查集。 const int N = int(4e4) + 9, M = int(5e5) + 9, SM = 1009; char T[N]; int n, A[N], AA[N], P[M+1], id[M], nn; VI res; int Find(int x){ […]

2023/5/12
阅读更多

聊聊《明日方舟 Side Story 孤星》与《崩坏：星穹铁道》

CP29 期间刚好这两个东西同时上线，所以也许比较一下是有意义的，当然我不喜欢捧一踩一，这两款当然都是在各自领域非常棒的手游了。（但你不是全程都在捧一踩一吗…） 技术力 从技术力的角度，显然《崩坏：星穹铁道》依靠《原神》的引擎，《明日方舟》肯定完全没有可比性的啦，唯一遗憾的是可能是相比《原神》过于肝的设计，这次《崩坏：星穹铁道》做了很多的简化，把跳跃都简化掉了（但是增加了踩在楼梯上的细节），所以看起来《崩坏：星穹铁道》更像是某种本格回合制 RPG… 因而又获得了轨迹代餐的称呼。 世界观 从世界观构建的角度我也觉得这次《崩坏：星穹铁道》设计的更胜一筹，特别是罗浮仙舟的设计，让我想起了《轩辕剑 IV》，但是《轩辕剑 IV》里也只是做到了机关人和飞行器而已，而罗浮仙舟的青铜朋克的设计更浓，想象也更加大胆了~ 都已经有行星要塞了。 至于《明日方舟》里的移动城市是什么样，至少我感觉我好像没什么印象，全靠脑补… 也许像《此时此刻的我》里的海利鸣？ 剧本 但是这次从剧本的角度分析，《Side Story 孤星》是完全打爆了同期的所有作品，甚至说已经有了相当的文学性也不为过。。。 【明日方舟】专业角度看《孤星》究竟是不是一个好故事？ 非常惭愧的说此前的剧情我确实都是 Skip 的… 直到去年的叙拉古人。。。但是叙拉古人最好的当然只是德狗这个人物的塑造和补完，剧情上倒是相对比较普通，至少是很容易挑刺的。但是这次孤星最后的几段演出都是可遇不可求级别的，特别是对克里斯滕的描绘，甚至对费尔迪南这个人物的描绘 —— 不！准确的说，孤星这次每一个相关人物的描绘（除了凯尔希），人物弧都是非常饱满的！特别是体验到这种挖了好几年的坑给你圆回来的感觉，让人感觉非常棒。 克里斯滕 V.S. 可可利亚 克里斯滕这个 Boss 塑造的最成功的的地方，我觉得就是剧本对这个角色的克制。。 做加法简单，而做减法难。。 事实上，整个孤星剧情中，克里斯滕似乎都没有多少台词。 她台词最多的地方，可能是最后的最后，它和石棺的一段连续的 QA。。。 相比之下，可可利亚这个反派，好像全程智商下线，完全成了星核的工具人，相比之下，克里斯滕和石棺，甚至更多的是一种平等的关系。。 游戏性 这点其实比较个人向.. 我自己认为从游戏性的角度上方舟是比星穹要好玩的… 这点也许从各自的肉鸽就能看出来… 方舟的肉鸽感觉算是博览众家之长，甚至做出了点《杀戮尖塔》的感觉，数值上也设计得恰到好处。甚至都能有各种社区比赛。 【直播回放】第三届仙术杯积分赛day1 2023年5月10日17点场 【联锁对抗S12】幻神无人问津，看冷门干员各显神通 不亚于仙术杯的精彩程度！来看看外国明日方舟玩家组织的竞技比赛吧！ 而星穹的肉鸽。。。虽然看上去是真的很努力在抄《黑帝斯》了，但是人家《黑帝斯》毕竟是个动作游戏啊。。。所以导致星穹的肉鸽结果本质还是要堆练度。。。数值完全失败。。。 立意 孤星的立意也是非常棒的，关于科学伦理的辩论，很容易让人想到最近 OpenAI 和 Google 对于通用人工智能的辩论。 Sam Altman: OpenAI CEO […]

2023/5/12
阅读更多

SGU 208. Toral Tickets

https://codeforces.com/problemsets/acmsguru/submission/99999/205409750 https://vjudge.net/problem/SGU-208 题意 给定一个 n∗m 的单面方格纸，然后把方格纸的长边卷起来，卷成一个圆柱体，再把收尾也接起来，形成一个 torus。求对格点进行黑白染色的方案数。 分析 Polya 计数，数据范围很小，暴力做循环分解即可。 难点是对于 n == m 的情况，要考虑 rt90()。 #include <lastweapon/bignum> using namespace lastweapon; const int N = 20; int a[N][N], b[N][N]; bool v[N][N]; int n, m; bignum z; int f(){ int z = 0; RST(v); REP(i, n) REP(j, m) if (!v[i][j]) { int x = i, y […]

2023/5/11
阅读更多

BZOJ 3625. [Codeforces Round #250]小朋友和二叉树

https://darkbzoj.cc/problem/3625 #include <lastweapon/io> #include <lastweapon/poly> using namespace lastweapon; const int N = int(5e3) + 9; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int cn, n; RD(cn, n); ++n; Poly A(n); DO(cn) { int c; if (RD(c) < n) A[c] += 1; } Poly C = (Poly{1} + (Poly{1}-4*A).sqrt(n)).inv(n) * 2; FOR(i, 1, n) […]

2023/5/11
阅读更多

Luogu P4841. [集训队作业2013]城市规划

Luogu | BZOJ https://www.cnblogs.com/Narh/p/10046287.html 题意 有标号连通图计数。 – https://oeis.org/A001187 分析 非常经典的题目，众所周知有三个做法！ 分治 FFT … 多项式求逆 https://darkbzoj.cc/submission/236083 多项式对数 https://darkbzoj.cc/submission/236071

2023/5/8
阅读更多

HDU 5279. YJC plays Minecraft

题意 给定一张由 n 组有标号完全图形成的图，第 i 个完全图的结点数为 ai。这些完全图之间形成一个环，每个完全图中编号最大的点向下一个完全图编号最小的点连一条边。 问该图中生成森林的方案数。 分析 首先自然考虑完全图内部的情况，定义 表示 n 点的完全图的生成森林方案数， 类似处理连通图时的方法，我们枚举 i 表示 0 号点所在的连通块中还有其它多少个点，可得转移方程： (1)   这里 是经典的完全图生成树公式。上式进一步展开后可以发现卷积形式，可用分治 NTT 求解。 再考虑完全图之间的情况，考虑容斥。显然不合法的情况，只有环上边全部存在，且所有完全图中首尾均连通。 设这种情况是 ，只要把首位连起来考虑即可，转移和上面几乎一样： (2)   不用分治直接 NTT 就行了

2023/5/6
阅读更多

LiberOJ #3723. 「SDOI / SXOI2022」子串统计

https://loj.ac/p/3723 https://www.cnblogs.com/zkyJuruo/p/16403110.html 题意 很神奇的题。。。考虑暴力 dp。。不难有。。 FOR(i, 1, n) { REP(l, n-i) { int r = l + i; dp[l][r] = (dp[l+1][r] + dp[l][r-1]) * occ[l][r]; } } 只要用后缀数组预处理出 occ 即可，复杂度 O(n2)。 #include <lastweapon/bitwise> #include <lastweapon/number> using namespace lastweapon; const int N = int(5e3) + 9; int C[N], key[N], t1[N], t2[N]; int n; namespace SA { […]

2023/5/4
阅读更多

On O(n) – O(1) RMQ

RMQ 转 LCA 再转 +-1 RMQ 的经典算法虽然小时候就听说过（指 lrj 的黑书），但是大概命运也跟什么 斐波那契堆 呀、Strassen Algorithm 呀什么的一样，属于理论更优但是因为常数太大而从来没写过的东西， 但是最近看到的一个十分 practical 的基于分块大法、单调栈和位运算的版本，不需要考虑 LCA，代码超短，而且常数很低！ 一个RMQ问题的快速算法，以及区间众数 On O(n) – O(1) RMQ [Tutorial] Range minimum query in O(1) with linear time construction RMQ 标准算法和线性树上并查集 RMQ 一般做法回顾 先回顾一下 RMQ 问题的一般做法， 线段树 可以说是实践中最 practical 的做法，支持修改这个性质太好了，维护其它相关信息也很方便，而且现在还有各种无责任 zkw 树，跑的也飞起，就连 atcoder library 的模板里写的都是 zkw 树，还可以用树链剖分，动态树推广到各种树上 RMQ 的情况，如果你只学一个算法那肯定选这个。 Sparse Table […]

2023/5/2
阅读更多

圆方树

https://oi-wiki.org/graph/block-forest/#%E4%BE%8B%E9%A2%98 https://codeforces.com/gym/102512/problem/A https://www.shuizilong.com/house/archives/spoj-9577-dynamic-tree-connectivity/ https://www.shuizilong.com/house/archives/spoj-375-query-on-a-tree/ 仙人掌 https://codeforces.com/problemset/problem/231/E LibreOJ #2587. 「APIO2018」铁人两项 巧妙的标号，设方点的权值为周围圆点的个数，圆点的权值为 -1，那么任意一个合法的 (s,f)，中间合法的 c 恰好等于它们在圆方树上路径的权值和。于是直接树 dp 即可。 Codeforces Round 278 (Div. 1) E. Tourists 圆方树后转化为 QTREE。 如果我们方点的权值记为所有周围圆点的最小值，那么修改圆点操作可能会影响 O(n) 个节点， 但是其实我们可以只考虑有根树，方点只记录孩子中圆点的最小值，那么操作就只会影响 O(1) 个节点了， 这样统计答案的时候，如果 lca 是方点，只要再向上取一个最小值即可。 这个技巧在 之前 也出现过。 Luogu P8456. 「SWTR-8」地地铁铁 https://www.luogu.com.cn/problem/P8456 难点在于什么情况下两点之间同时存在白路径和黑路径，但不存在黑白路径。 这个题还需要找到每个双连通分量内的所有边，所以还需要开个边栈。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e6) + 9, […]

2023/5/1
阅读更多

AtCoder Regular Contest 158

https://zhuanlan.zhihu.com/p/614019740 Problem C. All Pair Digit Sums 和 #159 的最后那个题 一样，我们也需要考虑容斥，计算进位所带来的代价。 注意枚举每一位的时候，进位可能会产生复杂的后效性（进位再进位…）我们不能仅仅考察那一位。。。 而是需要整个后缀都纳入考虑，比如对于一个末尾是 17 的数那么符合条件的就是末尾 >= 83 的数。。。 可以排序后二分查找或者线性做，复杂度 O(nlognlog(Ai))。 #include <lastweapon/io> #include <lastweapon/number> using namespace lastweapon; const int N = int(2e5) + 9; LL a[N], b[N]; int n; int f(LL x) { int z = 0; while (x) { z += x % 10; […]

2023/4/28
阅读更多

AtCoder Regular Contest 159

https://atcoder.jp/contests/arc159/tasks https://www.bilibili.com/video/BV1M24y1L7gt https://www.cnblogs.com/cjjsb/p/17302607.html Problem B. GCD Subtraction 和前一天 Beginner Contest 297 的 D 题很像！但是需要更多的智力。 不失一般性，考虑 a <= b，首先我们构造一个数据让暴力挂掉，比如 a=n, b=n+1，因为每次 d = gcd(a,b) 都是 1。 对于 d 不是 1 的情况，后面的 d 也都是 d 的倍数，因此可以直接 a/=d, b/=d 然后归成 d=1 的情况处理。 现在就是考虑 d = 1 的情况具体会持续多久，也就是我们要找到一个最小的 t，使得新的 d > 1， 如果我们能 O(1) 的算出这个值，那么每次至少 /= 2，我们就能得到一个 O(logn) 的做法。 […]

2023/4/25
阅读更多

AtCoder Beginner Contest 299

https://www.cnblogs.com/Lanly/p/17344724.html Problem D. Find by Query 简单二分。 Problem E. Nearest Black Vertex 首先圈内的点必须全部染白，否则不满足条件。 然后最优状态一定是剩下点全是黑，如果这也不满足条件那么一定无解了。 所以只要两个 bfs() 分别染色和检查即可。。 Problem F. Square Subsequence 一般的 idea 是子串问题和字符串算法有关，子序列问题和动态规划有关。 然后首先得会做一个串版本的，既给定一个字符串，判断有多少不重复的子序列。 这是一个经典问题。https://leetcode.cn/problems/distinct-subsequences-ii/ 难点在于计数的时候如何不重不漏，方法就是对于同一个等价类中的所有元素，我们找到一个代表元，在这里我们当然找出现时刻最早的，然后 dp 的时候对于每个字符只要从最晚时刻转移过来即可（晚出现对于早出现的计数存在包含关系）。 这样这个 dp 过程就是一个简单的在 dag 上的转移。 再来考虑这个问题。 一个简单的想法是 dp[i][j] 表示第一个串的末尾是 i，第二个串的末尾是 j 的方案数。 但我们没法向上面的 dp 方法一样简单完成去重（考察 aaa）。 但是遇事不决我们可以暴力枚举。。。枚举的位置当然是第二个串的初始位置。。。 这样在 dp 之后，我们只需要检查第一个串的结尾的下一个最接近的第二个串的开始字符的位置恰好是我们枚举的位置即可。。 这样就以复杂度加一维的代价轻松的解决了这个问题。（然后把倒推改成顺推。。） Problem G. Minimum Permutation 构造字典序最小，让人想起 […]

2023/4/25
阅读更多

AtCoder Beginner Contest 298

Problem F. Rook Score 我们记录每一行和每一列的和 R[], C[]，那么答案是某个 R[] + C[] – X[][] 注意这里 X[][] 可能在输入里，也可能不在，前者只有 O(n) 种， 后者对每一个 R，我们只要找其中最大的 C，所以其实也只有 O(n) 种。 排序后二重循环加个剪枝即可。 #include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; set<PII> P; map<int, LL> R, C; vector<pair<LL, int>> RR, CC; int r[N], c[N], x[N]; int n; int main() { #ifndef […]

2023/4/25
阅读更多

AtCoder Beginner Contest 297

Problem D. Count Subtractions 想到前几天 uoj 出的那个 gcd 数论题。。。 Problem E. Kth Takoyaki Set Humble Number? 结果居然暴力就过了。。。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e2) + 9; int n, k, a[N]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n, k); REP(i, n) RD(a[i]); set<LL> s; s.insert(0); DO(k) { […]

2023/4/24
阅读更多

gradio_client 介绍

随着最近 HuggingGPT 和 AutoGPT 的火爆，让 LLM 作为 Control 调用各种各样的 Domain Expert Models 也成为了一个常见的需求了。 连 Gradio 也在上周推出了 gradio_client 功能。 顺带一提。。前几天 OpenAI 三巨头之一的 GDB 在 Ted 给了一个 talk，也再次向公众秀了一把 ChatGPT Plugin… 可惜 量子位的这篇报道 明显是混淆了 AutoGPT 和 ChatGPT Plugin… 调模型可以算做使用工具的一环，但 AutoGPT 核心的 feature 是 Auto 啊。 总之，先让我们看看 gradio_client 具体都能做些什么吧~！ 背景 在具体讨论 gradio_client 之前，我们不妨稍微回顾一下当前开发者的现状，随着 ChatGPT 的火爆和其极其廉价的，近乎于倾销的定价模式，使得 OpenAI API 已经几乎成为所有开发者的标配，甚至许多开发者都将开源 LLM […]

2023/4/22
阅读更多

从 Self-Healing Code 到 Generative Agents

The Anatomy of Autonomy: Why Agents are the next AI Killer App after ChatGPT LangChain Blog, Autonomous Agents & Agent Simulations The Complete Beginners Guide To Autonomous Agents 在 上篇文章 写完之后，这个话题有了更高的热度，先后有 Self-hearling Code、BabyGPT、AutoGPT、OpenGPT 到 Generative Agents 等一大堆相关论文和应用。 不得不再做一篇总结了。。。 Self-Healing Code 就像自然界许多令人羡慕的具有自愈能力的生物一样。。。早在大强人工智能时代来临之前，能够写出在运行阶段具有自愈能力的代码，就一直是软件开发者的追求。 一种最简单的设计可能是 优雅降级（Graceful Degradation），比如考虑到 OpenAI 的服务经常不稳定，那么在系统检测到 OpenAI API 挂掉的时候，调用一个 local 的 LLM 作为补充，就是一种构建优雅降级的方法，类似 Windows 里的安全模式？ […]

2023/4/13
阅读更多

提示工程与微调魔法

本文用来记录我对这两个东西的一些笔记。。。 对于大型语言模型（LLM）的研究，一般可分为预训练（pre-training）、模型微调（tuning）与提示工程（promting）三个阶段，门槛和难度也依次降低，其中预训练阶段显然不是我这种级别的玩家可以染指的，但是需要有必要的知识以便于选择合适的模型进行微调（鸡尾酒里的基酒），对于具体模型的选择可参考 其它资料，本文着重介绍后两个东西。 模型微调 和 提示工程 的区别在于后者不改变模型的权重。。。所以后者当然还是比微调简单多啦。。只有在提示工程解决不了的时候我才会去考虑模型微调（能不做 pre-trainning 不做呢 不做 pre-trainning）。。虽然两个东西现在其实都挺玄学（empirical science）的。。。但是我个人觉得模型微调还是比提示工程更魔法一些的。。 许多人轻视提示工程的重要性。。（比如 奥特曼 自己）。。。但是我觉得它在这个阶段确实依然会是很重要的东西。。比如。。当年的元素法典就曾帮助到我很多。。。而 LLM 的提示工程就更重要了。。。简直就是新时代的 提问的智慧 啊。。而且。。。我靠。。提示工程就是自然语言编程的雏形啊。。。多少年来梦寐以求的东西。。。 虽然这个东西是对 LLM 的研究方法，不过我们迁移到诸如 Stable Diffusion、多模态或者其它的什么复杂的模型上应该也问题不大（因为 Transformer 模型被迁移到了很多领域上，视觉领域甚至也有自己的大模型，所以现在很多概念都是统一的）。通常说来能用提示工程解决的肯定也能用模型微调解决（但最好别）。。反之则不能。。 比如说 纸喵上次画的那张钢笔画。。但是更复杂点如果要画模型中目前没有的某个特定画风或者某个特定的人物、动作时。。就可能需要去模型微调了。 再比如我要做 AI Cosplay。。。比较简单的比如模仿猫娘、可能提示词搞搞就可以了。。。 但我要模仿特定的历史名人。甚至我自己时。（除了性格它需要有特定领域的知识）。最好选择模型微调。。 像是 LangChain、GPTIndex 等辅助工具、看起来能实现不少模型微调才办得到的事。。但也只是属于比较高级的提示工程玩法 (Augmentation)。。而像 LoRA 看起来只是外挂了一个文件有点像是提示工程。。但实际上她进行了模型微调。。。。。 不过似乎我也能把提示工程认为是一种最简单的模型微调。。把模型微调认为是比较复杂的提示工程。。。 然后嗯，你猜的没错。。。事实上还真有二者的微妙结合。。。一种叫做 提示微调 的东西。。。 而且。。以后会不会出现 online incremental tuning （类似人类的长期记忆）。。。现在我们也不好说对吧。。 SD 提示工程 Stable Diffusion Book, 绘画指南 元素法典制作委员会 控制网络 […]

2023/3/31
阅读更多

后日谈，SHLUG 月度分享（下）

（从杭州回来路上在火车站里面居然撞见 Yu 老师了。。。而且去的地方都是西湖。。这是多小的概率啊。。。） 继续讨论 上文 最后剩下的。。。降临派、拜 AI 教与人机联合体。。。 Know your enemy —— GPT-4 的缺陷 Sparks of Artificial General Intelligence: Early experiments with GPT-4 ｜（中文版） | （中文精简版） 还是回到微软的这篇报告。。。。GPT-4 是强人工智能吗？。。。首先这个问题你还没完全说服我呢。。。。 阿西莫夫和一大票哲学家对强人工智能有个基本假设，就是强人工智能必然具备一些类似灵魂的特性。比如说，无法复制，有某种不可逆的终止过程，小到需要定期睡眠，必然有情绪问题，等等。。。关于这个观点，就想上问我认为类地行星不是生命存在的必要条件一样。。类人的感情和生命形态也不是智能的必要条件。。。 那么我们需要拿出更有说服力的论据。。幸运的是在 拆解追溯 GPT-3.5 各项能力的起源 一文中，也已经帮助我们总结了： 六、****GPT-3.5 目前不能做什么**** 虽然GPT-3.5是自然语言处理研究中的重要一步，但它并没有完全包含许多研究人员（包括 AI2）设想的所有理想属性。以下是GPT-3.5不具备的某些重要属性： 实时改写模型的信念：当模型表达对某事的信念时，如果该信念是错误的，我们可能很难纠正它： 我最近遇到的一个例子是：ChatGPT 坚持认为 3599 是一个质数，尽管它承认 3599 = 59 * 61。另外，请参阅Reddit上关于游得最快的海洋哺乳动物的例子。 然而，模型信念的强度似乎存在不同的层次。一个例子是即使我告诉它达斯·维达（星球大战电影中的人物）赢得了2020年大选，模型依旧会认为美国现任总统是拜登。但是如果我将选举年份改为 2024 年，它就会认为总统是达斯·维达是 2026 年的总统。 形式推理：GPT-3.5系列不能在数学或一阶逻辑等形式严格的系统中进行推理： 在自然语言处理的文献中， […]

2023/3/30
阅读更多

后日谈，SHLUG 月度分享（上）

上周非常开心的参加了 SHLUG Monthly 的月度分享。。 P1 | P2 我已经忘记上次出门是什么时候了。。再一次见到这么多朋友于我来说也是非常激动的。。 （当然这好像这个活动也是刚刚恢复的，之前因为封控。。连 Hacking Thrusday 都转移到线上去了。。。） 首先本来的 slide 应该是具体的推销我现在在填的那个游戏。。。也就是。。《木桶饭妹抖行动》。。 顺便讲解一下整个技术栈（开源）。。以及我是怎么出图的。。 但是前段时间一个是写剧本把自己写出了内伤。。（毕竟是 mtf 主题的。。结果现在 被小川同学降维打击了。。。）。。 其二是 AI 在这个月确实有点让人应接不暇的意思。。 所以最后的 slide 更多的好像变成关于 AI 的讨论了。。 当然现在你在任何地方都能看到 AI 的讨论。。我觉得这就是技术奇点该有的样子。。。 作为新时代的纺织女工。。为了不被淘汰。。了解相关的知识是十分必要的。。。 而且可能这个阶段 NLP 研究人员也未必就能比你懂很多。。（很多重要的问题依然是玄学和 open problem）。。 首先。。去年 novelai leak 出去的时候。。于我来说是非常兴奋的。。。 再加上国内发生的种种事情。。让我对未来又重新燃起了希望。。。（于是把头像又从黑白变成彩色了。） （当然最后能解封的那么快。。哈哈。。。仿佛一切都未曾发生。。大家就像是一个只有 256 token 的 AI。。。。。还是极大的出乎我的预料的。。） novelai 的 leak 在我看来就是盗火的普罗米修斯。。。 果不其然。。。AI 绘图（特别是开源的，民用的。。）再接下来的数个月内突飞猛进。日新月异。。 已经可以进入生产阶段了。。。以摧枯拉朽之势… 开始影响各种画师、美工的工作了。。。 […]

2023/3/28
阅读更多

钢琴练习

自然大调 For River #C 2323.. – 简谱 [双手简谱]For River-To the moon – 指法 【搬运】For River (Johnny’s Version)钢琴教学 _ To the Moon – Smart Game Piano – 五线谱 【钢琴】【曲谱分享】To the Moon – Piano(Ending Version) 团子大家族 #G 651..4316..2512216.. – 【搬运】团子大家族钢琴教学 _ Clannad – Smart Game Piano 鸟之诗 偲芳歌 十二国记-偲芳歌-钢琴谱-完美编配版 你离开了南京，从此没有人和我说话 【钢琴翻弹】你离开了南京，从此没有人和我说话 悬崖村 F -> G -> bB […]

2023/3/10
阅读更多

EasyRPG x ChatGPT

前言 使用 ChatGPT 设计 Gameplay 的例子已经越来越多。 https://twitter.com/tarukosu/status/1632009079840444419 现在应该已经有许多将 ChatGPT 融入到 GamePlay 中的尝试了吧… 我肯定是动作很慢的了。。。 通信 首先依靠 yno 肯定是可以实现的，不了解 yno 的同学，可以先阅读 这篇 yno 考古， 仔细一想这个东西不会比之前写的《少女终末旅行》里的枪战功能更复杂。。。 不过我们还是要对两边的通信相关的代码再进行一次 Review。。。 这里先给出结论： 表面看来，这两个版本最大的区别是 yumeboo 版本的 chatbox 是实现在游戏内部的，但是这个其实不是必须的，事实上 yumeboo 的服务度里有一段隐藏的代码，是原版的 js chatbox。 实际最核心的区别是 ynoproject 版本的收发包都是在 cpp 侧进行的，而 yumeboo 版本则是都是在 node 端进行的。从效率和封装上可能前者更好，但是后者代码更简洁也更容易魔改，所以要增加和 ChatGPT 通信相关 feature 的话，后者可能是更合适的！（而且前者还多一个 go server 我不会用。。而且那个 go server 居然是 one […]

2023/3/6
阅读更多

ControlNet 相关

秋葉aaaki，【AI绘画】controlnet安装/使用教程 动作控制 景深 线稿上色 Gligen 【画像生成AI】★3/8更新版★webui世界が変わったこれは入れておけ拡張機能の紹介 AI绘画 Stable Diffusion 像素角色动画模型初探 直出SpriteSheet

2023/2/26
阅读更多

The 1st Universal Cup, Stage 4, Ukraine

https://qoj.ac/contest/1106 Problem A. #include <lastweapon/io> using namespace lastweapon; const int N = int(2e5) + 9; LL a[N]; int n; LL z; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif Rush { RD(n); REP(i, n) RD(a[i]); sort(a, a+n); LL z = a[n-1]*a[n-2] + a[1]*a[0]; DWN(i, n-2, 0) z += a[i] * a[i+2]; cout << z […]

2023/2/19
阅读更多

EasyRPG —— Sliding Puzzle

代码：https://github.com/w3itch-crafter/RM2k3-Sliding-Puzzle 之前想参考的《もしもスマブラだった》中的镜头实现来做一个手动拉伸和缩放视角的效果（类似某魔兽 rpg 地图 —— BOOM 海战！），结果研究一下最后还是失败了。。。 这一次来试试用同样的方法试试能不能做 Sliding Puzzle 小游戏。。。 当然这个 common event 肯定是能搓出来的。。不过肯定没法维护就是了。。 首先还是在开箱子的时候，执行一条自定义指令 “.sliding_puzzle”。。 然后再自定义指令里单独进行画图。。。 那么首先还是看显示图片是哪一条命令。。。 发现是 CommandShowPicture。。。 然后里面调用的是。。 Main_Data::game_pictures->Show(pic_id, params); 但是这个 params 里并没有包含切图的功能。。 但是我记得 sprite 里是有 src_rect 属性的。。 嗯虽然是有的但是耦合程度非常高。。唯一比较灵活的修改的地方是一处。。 SetSrcRect(Rect{ sx, sy, sw, sh }); 反正不是切行走图就是切地图块。。里面的参数都是写死的。。。 所以看起来比较简单的写法。。应该是在绘图前，进行截胡。。。弄一个全局变量。。 但是很快发现绘制地图和生成地图的过程。。显然是分开的囧。。所以没办法。。 只能给 sprite 和 params 增加一组新属性 myRect 用来在画图前截胡。。

2023/2/16
阅读更多

The 1st Universal Cup, Stage 3, Poland

https://qoj.ac/contest/1103?v=1 https://twitter.com/noimi_kyopro/status/1624549003038965760 Problem B. Bars n 个人排成一排开酒吧，每个人可以选择开或不开，且每个人会去自己以外的左右最近 2 个开业酒吧各 1 次（没有则不去），第 i 个人的酒吧每招待一个顾客得 p_i 元，最大化总利润。 先写个暴力压压惊。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e6) + 9; LL f[N]; int p[N]; int n; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif Rush { RD(n); REP(i, n) RD(p[i]); fill(f, f+n, 0); FOR(i, 1, n) […]

2023/2/15
阅读更多

DP 优化练习

https://www.cnblogs.com/flashhu/p/9480669.html Luogu P2513. [HAOI2009]逆序对数列 https://www.luogu.com.cn/problem/P2513 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e3) + 9; int f[N]; int n, m; int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); #endif RD(n, m); f[0] = 1; FOR(i, 1, n) { DWN_1(j, m, 1) { int t = max(0, j-i); DWN(k, j, t) f[j] += f[k]; f[j] […]

2023/2/14
阅读更多

NOI 2009

诗人小 G 啊。。我觉得这个还是挺难的。。。 #include <lastweapon/io> using namespace lastweapon; const int N = int(1e5) + 9; long double f[N]; int pre[N]; char str[N][31]; int s[N]; PII Q[N]; int cz, op; int n,l,p; long double poww(long double x, int b) { long double z = 1; while (b) { if (b&1) z *= x; x *= x; […]

2023/2/14
阅读更多

TypeDB Forces 2023

https://codeforces.com/contest/1787 TypeDB Forces 2023 (Div. 1 + Div. 2) C (dp) D(dfs), 严格鸽 TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!), Immortality Problem G. Colorful Tree Again 题意：给定一个边权图，初始固定每个边有颜色和边权。每个节点也有颜色，初始都是黑色。 每次操作可以改变一个节点的颜色，并询问当前最大的好的路径的权值和是多少。 一个路径是好的，当且仅当路径上的所有点颜色相同，并包含了所有该颜色的边，且路径上经过的所有节点的颜色为白。 解法：这个题首先第一反应是 QTREE 4 和 QTREE 6 的某种结合。。。 但是仔细读题发现判定的条件是 path 而不是 component ！！！ 因而题目难度大幅简化。。。但是想写得简洁依然会很困难。。。 首先第一步当然是剔除不合法的颜色。。。（最好用度数做简单的判定，不要在 dfs() 的时候判定。。） 然后再 dfs() 的时候，剩下的路径都有且仅有一个最高点。。我们对所有最高点位 u 的路径都放在一个堆里维护，记做 Q[u]… 那么在用所有的 […]

2023/2/10
阅读更多

Nas 买来做什么…

1、存电影做自己的流媒体服务器。 2、照片、手机、备份系统。 3、DS file 做私人云盘。 4、装 MariaDB 做自己的私有数据库，PHP/Web Station做个人Web服务。 5、装 docker，然后在 docker上装各种东西比如Home Assistant/Node-RED，做你的智能家居中枢。 6、虚拟机装OpenWRT，假设私有梯子。 作为一名海盗党兼重度松鼠症患者，没有 Nas 的生活是不可想象的… Nas 的最基础用法肯定是离线下载了。。。看一下 Nas 都可以装些什么吧.. 1. Pirate Library Mirror http://pilimi.org/ 听起来十分诱人。。存储人类自诞生以来的全部知识。。虽然自己读不完，但是作为 GPT 的语料看起来也是非常有用的。 可惜这玩意儿实在是有点太大了。。。而且拖拽速度太慢。。而且目前检索服务也很多，完全不需要本地备份一份。。 2. BlueMaxima’s Flashpoint https://bluemaxima.org/flashpoint/ Flash 游戏简直是巨大的游戏设计宝藏。。。今年的 ggj 里有一个词条就是你的游戏是否致敬了某个古老的 flash 游戏的 idea 并将其发扬光大（Old Meets New）。 当然出于保护互联网文化遗产这个目标来看这个也是非常重要的。 3. 天马 G 复古游戏前端 https://www.bilibili.com/video/BV1eM4y197aY/ 有点像是 Mac 上的 OpenEmu，不过它们社区的网盘里什么 rom […]

2023/2/9
阅读更多

Global Game Jam 2023 参赛纪录

57. [20] When a program changes one or more of its own instructions in memory, it is said to have self-modifying code. MMIX insists that a SYNCID command be issued before such modified commands are executed. Explain why self-modifying code is usually undesirable in a modern computer. —— THE ART OF COMPUTER PROGRAMMING VOLUME 1, […]

2023/2/7
阅读更多

The 1st Universal Cup, Stage 2, Hongkong

Problem A. TreeScript 简单树 dp。 const int N = int(1e6) + 9; VI adj[N]; int dp[N]; int n, z; void dfs(int u) { dp[u] = 0; for (auto v: adj[u]) { dfs(v); checkMax(dp[u], dp[v] + 1); } int c = 0; for (auto v: adj[u]) { if (dp[u] == dp[v] + 1) ++c; } if […]

2023/2/7
阅读更多

The 1st Universal Cup, Stage 0, Nanjing

Problem G. Inscryption 其实就是括号序列。。首先考虑是否有解，那么肯定待定位置都填 '('。 那么接下来就是保证合法的情况下，尽可能多的将待定位置填成 ')'。。那么这个肯定尽可能选一段后缀去填更优。 上面的观察已经足够写一个基于二分答案的解了，不过我们可以做的更好。。。 对于每个待定序列，我们都贪心的首先将其设置成 ‘)’，再之后遇到不合法的情况时，再进行调整， 而这只需要记录我们前面有多少待定的位置被填成 ')' 即可。 const int N = int(1e6) + 9; int a[N]; int n; bool ok() { int p = 1, q = 1, o = 0; REP(i, n) { if (a[i] == 1) { ++p; ++q; } else if (a[i] == -1) { if […]

2023/2/7
阅读更多

Codeforces Round #850

Problem A. Monsters (easy version) 易知，最后一定是消成 [1,2,…,b] 这样的情况，然后一次连锁操作全部删除（好像炉石里有张类似的卡）。 对于只需要处理一次询问的情况，我们可以直接对 a 数组进行排序，然后贪心得到最后的 b 即可。 const int N = int(2e5) + 9; int a[N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif Rush { RD(n); REP(i, n) RD(a[i]); LL s = 0, b = 0; sort(a, a+n); REP(i, n) if (a[i] > b) s += […]

2023/2/7
阅读更多

舟游同人游戏

不对劲的明日方舟 Another 银河城 不知道是啥但菜单 UI/UX 很帅

2023/2/3
阅读更多

RM2k3 机能增强 —— EasyRPG Player 魔改版

https://www.youtube.com/watch?v=v4kx7yXRlig To do list 单词不被断行 禁止行首标点 如何编译 cmake . -D PLAYER_BUILD_LIBLCF=ON -D VCPKG_TARGET_TRIPLET=x64-windows-static -D CMAKE_TOOLCHAIN_FILE=D:\Dev\Github\vcpkg\scripts\buildsystems\vcpkg.cmake -D CMAKE_BUILD_TYPE=Debug cmake --build . 剧本快进 剧情是游戏的最重要组成部分，现代 Galgame 引擎通常都是有完善的控制功能的，例如快进，自动播放，退回等等。 我们第一步是希望给 RM2k3 增加快进功能。 在最简单的实现中我们只要一行即可，配合 EasyRPG 的 F、G 的快进功能，即可实现快进。 不过一般的 Galgame 似乎都使用 LCTRL 作为快进功能，但是这个键并没有在常量列表里。 如何修改留作思考题。 https://github.com/w3itch-crafter/RM2k3-Sliding-Puzzle/commit/a416ef7030d9e9d0d8de4c1672c4d51fb6097cd2 自动换行 https://github.com/w3itch-crafter/RM2k3-Sliding-Puzzle/commit/0589ac549e56cccdfb50321b67f0242f25421be1 https://sf-zhou.github.io/programming/chinese_encoding.html void Window_Message::StartMessageProcessing(PendingMessage pm) ... int PendingMessage::PushLine(std::string msg) 真彩色图片 我们知道 RM2k3 默认的图片素材全部都是 256 色的 […]

2023/1/27
阅读更多

AtCoder Regular Contest 154

https://atcoder.jp/contests/arc154/tasks A B 给定两个字符串 s、t，每次你可以删除 s[0]，并将其插入到 s 的任意位置。 问至少多少次操作，可以让 s = t。 C 给定 A、B 两个数组，每次可以选择 A 数组中的一个数 A[i]，令 A[i] = A[(i+1)%n]。 问是否可以让 A = B。 Problem D. A + B > C ? 交互问题，有一个排列 P ，你可以询问至多 25000 次内还原出原排列。每次询问 (i,j,k) 返回是否 Pi + Pj > Pk。 n <= 2000 先找最小的，然后转化成排序问题。 使用归并排序确保比较次数最少。 E F i = […]

2023/1/22
阅读更多

《海之歌》设定与剧本

人物设定 主角组 パスカル（Pascale） 种族：海精灵 阵营：守序善良 擅长：歌唱、初级剑术、高级水系魔法 本作女主，拥有一头金色长发的海之精灵，安琪拉王国年幼的长公主。 佩戴一把哥哥曾经送给自己的佩剑（较短）和象征安琪拉文化的海豚形状的项链。 绝招是互换海洋的力量召唤巨浪与旋涡带走对手，可静可动，有一个妹妹和一个从小一起长大的女仆。 Prompt: {{{long golden hair}}}, loli, sword, half elf, ranger, Wreath, Indigenous 一些设定稿。。 pic.twitter.com/9PgpCs3Q12 — 小島みなこ 🏳️‍⚧️ (@MinakoOikawa) January 19, 2023 エイダ（Ada） 种族：人类 阵营：混乱中立 擅长：高级智力、高级学术 本作女二，白色短发文静的妹子，奥瓦联邦的四公主。 喜欢阅读，天性聪颖，学习任何知识都很快。但因为是女性，加上自身性格软弱，因而才能不被大人们重视而被忽视。 与邻国的王子订有婚约。 安琪拉组 露易丝 黛尔芙特（Louise Delfault） 帕斯卡露的女仆，比帕露年长，被帕露称为姐姐。 高阶精灵组 リヴェンデル（Rivendell） 种族：高等精灵 阵营：中立善良 メリッサ（Melissa） 种族：独角兽 阵营：混乱善良 グリーン（Grimm） 种族：高地矮人 阵营：守序善良 ロイ（Roy） 种族：树人 阵营：守序善良 Class […]

2023/1/19
阅读更多

dfs 序求 lca

前情提要 前几天做了一下 Educational Codeforces Round 141 的 F 题。。。看起来是个动态直径，之前网赛我出过一次，翻出标程应该能秒。但是写起来发现要改的地方实在很多，大概是我的标程实在不怎么高明。 于是看了一下代码最短的家伙们都写了啥，于是我被 这份代码 震惊了。 第一反应是，虽然转移我看不懂，但是应该就是一颗 zkw 树，等价于 这篇文章里所提到的算法三 嘛。。。 …but wait, 你的 lca 在哪里。。。 之前 Dynamic Diameter 里我们是在 euler 序上建线段树。。。实际上是隐含了一个求 lca 的过程的。。。 但是这里明显是 dfs 序吧。。。。。。 まさか？… LCA dfs 序也可以求 lca？ 搜了一下，原来还真有！ 核心思想：虽然 lca 自己不会出现在区间里。。但是你的孩子会啊。。。找到这个点再求父亲，或者，直接在建 st 表的时候就直接放父结点就行了！ 好吧。。反正我是想不到。。囧。。 这个板子显然各方面都是完胜 euler 序 lca 的。。。特别是有的题里同时出现 dfs 序和 lca 的时候 —— […]

2023/1/17
阅读更多

Codeforces Round #844

又是久违的 tourist round。。。 Problem D. https://zhuanlan.zhihu.com/p/599333683 Problem F – Bracket Insertion 题意 构造一个初始为空的括号序列，执行 n 次插入操作，每次操作任选序列中的一个位置，插入 "()" 或 ")("。 问最终构成的括号序列为合法括号序列的操作方案的概率。 题解 组合计数。 先转换成计数问题，不难发现，对于第 i 次操作，我们有 i*2-1 种插入的位置可供选择，因而求出合法的操作方案总数，处以 1*3*5*...*2n-1 即可。 麻烦的是，我们甚至不能把每次插入的一对括号看成是一个独立的元素，后续插入操作甚至可以从中间破坏它。 回忆 Catalan 序列的做法，虽然和这个题看起来有很大的不同，前者是计数合法的括号序列总数，本题是计数合法的操作方案。 但是依然可以给我们提供许多有益的思路。回忆 Catalan 序列的卷积形递推公式。 我们实际上是考察第一组匹配的括号，然后分别枚举括号内或括号外的括号层数，以进行递归。 这个题是否可以使用同样的策略呢？ 我们同样固定第一组括号，那么之后的括号，只会是下述三种情况之一：L(M)R。 因为被初始括号所分割，这里 L M R 的状态都独立的。 这里 L 和 R 的 size 可以合并在一起，这样我们只要枚举 M 的 size 即可。 这样我们就有了类 […]

2023/1/16
阅读更多

Test

A B C 做法二 #include <lastweapon/number> using namespace lastweapon; const int N = int(1e2) + 9; Int f[2][N][N][N]; int n, m; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n, m, MOD); int p = 0, q = 1; f[p][0][1][1] = 1; #define u f[q][kk][ii][jj] REP_1(a, n-1) { swap(p, q); RST(f[p]); […]

2022/12/24
阅读更多

P3768 简单的数学题

核心： phi * 1 = n (ID^k phi) * (ID^k) = S_k 其中 S_k 是 等幂求和 函数， 上面的 phi 卷 1 的结果也可看做是 S_0。

2022/12/16
阅读更多

AtCoder Beginner Contest 281

https://atcoder.jp/contests/abc281/tasks C 经典两个堆。 D 背包。 E. 经典 Tire 树 DP。 G. 组合 dp。比赛写的是： dp[i][j][k]：前 i 层，一共用了 j 个顶点，且第 i 层使用了 k 个。 转移 O(n) 一共 O(n4) 结果发现没办法简单的用前缀和降低复杂度。 正确的方法是简化状态！不考虑分了几层，直接用已经考察过的顶点数划分阶段： dp[i][j]：一共用了 i 个顶点，且最外层使用了 j 个。 Ex. 构造生成函数，贴多项式模板。 https://zhuanlan.zhihu.com/p/590914324

2022/12/12
阅读更多

ChatGPT 相关

NovelAI 还没玩明白… 这几天又来了个 character.ai 和 ChatGPT。。。 官宣 OpenAI Annoucements, ChatGPT: Optimizing Language Models for Dialogue 用例 Building A Virtual Machine inside ChatGPT OpenAI -ChatGPT 相关介绍一览 跑团 https://twitter.com/fladdict/status/1599631601415049216 在 ChatGPT 中实现了一门新的编程语言：GPTLang，并用这个语言写了一个排序算法 Vitalik, Updating my blog: a quick GPT chatbot coding experiment https://twitter.com/omarsar0/status/1600149116369051649 时尚设计 简繁转换 工具 ChatGPT for Google ChatGPT for zhihu https://twitter.com/jordnb/status/1599880721077633024 https://github.com/pionxzh/chatgpt-exporter https://github.com/rikumi/tietie-bot 其他模型 投研报告 […]

2022/12/5
阅读更多

AtCoder Grand Contest 059

https://atcoder.jp/contests/agc059/tasks Problem A. My Last ABC Problem 只想出了暴力 dp。。。关键是在于考察区间中不同的相邻位置的数量。。 设为 x，答案就是这个值的 ceil(x/2)，证明可以用鸽巢原理。 Problem B. Arrange Your Balls 反而我觉得比 A 简单，从大到小排序，dfs() 构造即可。

2022/12/5
阅读更多

AtCoder Beginner Contest 280

https://zhuanlan.zhihu.com/p/588960895 https://t.me/algorithm_daily_of_minako/7755 Problem Ex. Substring Sort https://www.spoj.com/problems/SUBLEX/ https://www.luogu.com.cn/problem/P2178 https://www.codechef.com/problems/TSUBSTR https://www.codechef.com/problems/QSTRING

2022/12/4
阅读更多

Codeforces Global Round 24

https://codeforces.com/contest/1764 https://t.me/algorithm_daily_of_minako/7665 Problem D. Doremy’s Pegging Game 总之很像是 上一场的 D 题。。也是需要枚举一些东西的组合计数。。。 先枚举最后剩下的角度，再枚举这个角度中间还剩几个即可，最后记得讨论一下奇偶。 Problem E. Doremy’s Number Line 首先如果 x 能被染色，那么 x-1 也一定能被染色，因此我们只要求出能够构造出的最大值，并和 k 做比较即可。 那么显然我们有平凡下界 a[0] 和平凡上界 a[0] + b[0]，这是因为我们最后一步必须染 0。 现在我们不考虑 0，看剩下的数最大染色能否到达 a[0]，于是我们归约到了一个子问题，但是这里我们还是有一颗关于排列的搜索树需要处理。 问题的核心就是考察这棵搜索树，寻求剪枝。 我们发现只要根据 a 进行排序，就可以把搜索树的规模优化成 O(n)。 具体看 题解。。。 还有一种做法是按 a+b 进行排序，也可以把搜索树的规模优化成 O(n)。 具体看 这里。。。 利用排序重新组织搜索顺序倒是搜索题的常见剪枝技巧。。。不过这次是直接变成简单贪心。。。 总之看起来很简单。。但是对我来说还是挺难的。。。 Problem F. Doremy’s Experimental Tree 让人想起 […]

2022/12/1
阅读更多

事实核查，以乌鲁木齐火灾为例

https://twitter.com/dikaioslin/status/1597099497233952769

2022/11/29
阅读更多

SPOJ MUSKET. Musketeers

const nn=100; type int=longint; var G:array[1..nn,1..nn] of boolean; D:array[1..nn,1..nn] of boolean; A:array[1..nn] of int; an:int; t:int; n,i,j:int; function c(k:int):int; begin exit((k-1) mod n +1); end; procedure init; var i,j:int; t:char; begin fillchar(g,sizeof(g),false); fillchar(d,sizeof(d),false); an:=0; readln(n); for i:=1 to n do begin for j:=1 to n do begin read(t); if t='1' then g[i,j]:=true; end; readln; end; […]

2022/11/22
阅读更多

Pinely Round 1

https://codeforces.com/contest/1750 https://t.me/algorithm_daily_of_minako/7364 Problem B. Elimination of a Ring 比赛的时候第一反应是 SPOJ. MUSKET，做法是破环为链 + O(n3) 区间 dp。（连数据范围也颇具迷惑性 Orz。。。） 不过感觉不太对劲… 因为求的是最大。。。那么如果有一个孤立元素，那么一定可以倚靠着这个元素作为墙，答案为 n。 进一步，我们可以证明，只要有大于等于 3 种以上元素，都可以最后归约到这种情况，答案同样为 n。 因此只剩下两种元素的情况，但是两种元素时 pattern 是固定的。。。是 1 2 1 2 … 答案为 n/2 + 1。 Problem D. Carry Bit 这个题 O(nk) 类 Pascal dp 很好想也好写，但是对我们解这道题并没有用，因为我们不知道怎么优化， 即使是更简单的情况，比如如何从组合数的递推公式直接得到通项解对我来说也是非常困难的。 （Induction 当然不算。） 所以看到这个范围应该直接考虑组合方法。 首先我们可以得到一个 raw 的公式。。。。Binom(n, k) * p3[n-k]。。 […]

2022/11/22
阅读更多

Note about FTX

想不到这么快就第二季了。。。 https://twitter.com/adamscochran/status/1593020859156865026 https://kordan.medium.com/ftx-%E5%A6%82%E4%BD%95%E5%9C%A8%E4%B8%8D%E5%88%B0%E4%B8%80%E5%80%8B%E7%A6%AE%E6%8B%9C%E7%9A%84%E6%99%82%E9%96%93%E5%BE%9E%E4%B8%96%E7%95%8C%E7%AC%AC%E4%BA%8C%E5%A4%A7%E4%BA%A4%E6%98%93%E6%89%80%E5%88%B0%E7%A0%B4%E7%94%A2%E6%B8%85%E7%AE%97-%E4%BA%8B%E4%BB%B6%E5%9B%9E%E9%A1%A7%E8%88%87%E6%AA%A2%E8%A8%8E-ad1e241278d9 https://web.archive.org/web/20211025144026/https://haihongblog.com/ https://twitter.com/DegenBing/status/1591259884829704192 https://twitter.com/XMRer/status/1592736163194105856

2022/11/16
阅读更多

Permutation

由于上一场 G 题没做出来。。打算重新复习一下各种排列相关的知识。。。 Combinatorial Problems and Exercises, 2nd Edition, László Lovász, #3 Permutations The Art of Computer Programming, Vol. 3 Sorting and Searching, 2nd Edition, Donald E. Knuth, 5.1. Combinatorial Properties of Permutations 第一部分 错位排列（） 自反排列 https://mathworld.wolfram.com/PermutationInvolution.html https://en.wikipedia.org/wiki/Involution_(mathematics) 交错排列 http://oeis.org/A000111 https://en.wikipedia.org/wiki/Euler_numbers 类 Catalan 递推公式 类 Pascal 递推公式 生成函数 http://oeis.org/A008282 第二部分 循环分解 https://www.shuizilong.com/house/archives/my_problems/ 不动点 逆序对 #include […]

2022/11/14
阅读更多

ICPC World Final 2021

传送门 提交地址 前情提要 官方题解 代码 感觉今年题目貌似比 去年 简单，是我的错觉吗？（反正几何题大家都不会去开的）。 还是按照我认为的难度排序。。。 Problem H. Prehistoric Programs https://acm.timus.ru/problem.aspx?space=1&num=1745 https://codeforces.com/gym/101341/problem/A 贪心乱搞。 Problem A. Crystal Crosswind 我们需要找出必须是 ‘#’ 的点和必须是 ‘.’ 的点，剩下的可以随便填。 考察每组 wind 能够给出的信息： (1): 首先对于其中的每组 (x, y) boundary，(x, y) 必然填 ‘#’，且 (x – wx, y – wy) 必然填 ‘.’。 (2): 除此之外，对于每个不在 boundary 的点 (x, y)，也是能给出一定信息的（风大概还有个 z 轴从上向下吹的。。），要么 (x, y) 是 […]

2022/11/12
阅读更多

CodeTON Round 3

https://codeforces.com/contest/1750 Problem D. Count GCD 似乎是 隔壁原题… Problem E. Bracket Cost https://zhuanlan.zhihu.com/p/581182890 没做出来似乎是因为 读错了题… 给定一个括号序列，问所有子序列的平衡代价 f() 的和。 f() 定义为，用最少的 shift 和 insert 操作，使该序列平衡。 注意 shift 操作可以任选一个子串进行… Problem F. Majority 问有多少长度位 n (n<=5000) 的 0-1 序列，满足该序列可以执行任意次连接操作变为全 1. 连接操作定义为，选择一个区间 i,j, 满足 si = sj = 1，将 [i,j] 全部变为 1，要求操作前区间中 1 的数目 >= 0 的数目。 dp[i][j] 表示最终状态长度为 i，且左边有连续 […]

2022/11/7
阅读更多

Codeforces Round #831

http://codeforces.com/blog/entry/108451 https://zhuanlan.zhihu.com/p/579487089 题意 给你一个含有 $n$ 个元素的可重集合 $A$，集合 $A$ 的每个元素是一个单元素集合 ${a_i}$。 定义一次操作由以下两步构成： 选择 $A$ 中两个交集为空的集合 $S$, $T$。 删除这两个集合，将它们的并添加进 $A$。 之后, 我们构造一个可重集合 $M$，表示当前剩下的所有集合的大小。 你可以执行任意多次操作，问所有不同的 $M$ 的总数。 做法 如果初始的元素互不相同，显然原问题等价于分拆数，虽然原问题是以合并的方式给出的。 那么原问题等价于带有某种限制的分拆数，限制为某些元素之间必须分拆。 分拆数我们知道有很多高级做法。。。比如欧拉五边形数、生成函数云云。。。。但是这个题 $n$ 只有 2000，大概率都用不到。 考虑分拆数最朴素的 DP。。。我们把分拆的结果按照从大到小排序。。那么每一种情况唯一对应一个单调递减且和为 n 的序列。 dp[i][s][j]: 当前考察前 i 个位置，和为 s 且末尾为 j 的方案数。 有： const int N = int(1e3) + 9; int dp[2][N][N]; int n; […]

2022/11/4
阅读更多

Educational Codeforces Round 138

https://codeforces.com/contest/1728 https://zhuanlan.zhihu.com/p/575699975 https://zhuanlan.zhihu.com/p/575702697 Problem D. Letter Picking 区间博弈 dp，状态 f[][]，但是比一般的博弈 dp 要简单，转移 trivial。 首先我们可以两轮操作绑定在一起转移，只要考虑长度为偶数的状态，并且也不用记录上一轮选了什么字符。 进一步不难归纳出结果只有可能是先手胜或平局，进一步简化状态和转移。 #include <lastweapon/io> using namespace lastweapon; const int N = int(2e3) + 9; char s[N]; bool f[N][N]; int n; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif Rush { n = strlen(RS(s)); REP(i, n+1) f[i][i] = 0; […]

2022/10/31
阅读更多

NovelAI 法术指南

潘多拉之盒 NovelAI Leak 1 NovelAI Leak 2 Leak 资料分析 [NovelAI][非教程] 让本地 NovelAI 更进一步：泄露包都有啥东西？ NovelAI 本地泄露版达到网络版效果的教程-哔哩哔哩 【AI绘画】再次进化！novelai真官网版本解压即用 无需下载！这次1分钟内不用学也能会用 交互界面 主要有开源的 AUTOMATIC1111 维护的 Stable Diffusion WebUI（更新非常勤快！） 和 4chan 大佬根据官方 leak 资料整合出来的 NAIFU（NovelAI AI Image Frontend Ultimate）。 WebUI 关于 AUTOMATIC1111 /stable-diffusion-webui (https://github.com/AUTOMATIC1111/stable-diffusion-webui) 的 FAQ https://stable-diffusion-book.vercel.app/ NAIFU 【AI绘画】再次进化！novelai真官网版本解压即用 无需下载！这次1分钟内不用学也能会用 法术书 Tags 表 NovelAI法术书 展品 https://t.me/rhodesIslandcp/138828 MISC https://github.com/koishijs/novelai-bot 3D https://twitter.com/mishig25/status/1605239800264540161 […]

2022/10/9
阅读更多

Test

https://zhuanlan.zhihu.com/p/570591659

2022/10/7
阅读更多

卡农

卡农 理论知识 什么是卡农进行？ 上面的视频里有 卡农进行 的历史。 反正你可以理解成 cpp std library。。。 6种方法让你的卡农进行听起来不一样 这个视频教了一些变换的方法。。。（大概类似如何扩展线段树来支持区间求和 和 区间最值。。。 整整100首含有卡农进行的华语流行歌片段，一次听个够 这个视频有一些题库。。。（大概） 幼稚园 【电钢琴】小姐姐弹奏最简版卡农 。。20 分 brute-force 版本，有手就行。。。和弦只需要弹根音。。。就 15634145 简单循环。。 为了向下个阶段过度左手尽量只用小拇指！！！。。。 小学生 《卡农》钢琴C调改编版，保留经典原味，适合新手学习 学钢琴必弹《卡农》完整版翻译简谱 下面琴谱稍微有一些不太一样，我觉得上面的版本更好听。。。不过不妨碍练习。。。 初中生。。 接下来要换根了。。不对。。变成原版 D 大调。。。 这个我就不会了。 U.N.OWEN就是她吗？ https://www.bilibili.com/video/BV1Fx411N77Q/ 你离开了南京，从此没有人和我说话 E 大调 532,321(5,6) 16,5(4,5) 553,6523(3,6) 216,2(4,5) 65,3(4,3) 2316,5(4,5) 553,6523(1,4) 216,1(4,4|3) 532,321(5131,6317) 16,5(411,5257) 553,6523(3,6) 2162(4,5) 653(4145654,357537) 23165(4141,5252) 553,6523(1535,4141) 2161(4141,4146) […]

2022/9/24
阅读更多

Educational Codeforces Round 135

https://codeforces.com/contest/1728 https://zhuanlan.zhihu.com/p/562734265 Problem D. Letter Picking 区间博弈 dp，状态 f[][]，但是比一般的博弈 dp 要简单，转移 trivial。 首先我们可以两轮操作绑定在一起转移，只要考虑长度为偶数的状态，并且也不用记录上一轮选了什么字符。 进一步不难归纳出结果只有可能是先手胜或平局，进一步简化状态和转移。 #include <lastweapon/io> using namespace lastweapon; const int N = int(2e3) + 9; char s[N]; bool f[N][N]; int n; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif Rush { n = strlen(RS(s)); REP(i, n+1) f[i][i] = 0; for(int […]

2022/9/12
阅读更多

Codeforces Round #819

https://codeforces.com/contest/1726 https://zhuanlan.zhihu.com/p/562689105 C. Jatayu’s Balanced Bracket Sequence 调整法。 基础情况是 ((()))。。连通分量为 n。我们观察什么情况下连通分量会减少。 (()())。。比如这样。。条件是之前出现过层级一样的括号序列使得以当前位置结尾的合法序列不止一组。 于是只要开个 bool 数组记录一下哪些层级出现过就好了，当然弹栈的时候要恢复。 D. Edge Split 首先考虑树的情况，发现无论如何染色都不影响结果。 得知我们每条边染色的目的，是减少对应颜色的一个连通分量。 因此我们考虑将其中一种染色固定成一颗生成树，这样只要保证多出的边不构成一个环即可。 而这在只有 3 条额外边的情况下总是可以保证的。 E. Almost Perfect 统计长度为 n 的置换中，满足 $\lvert p_i – p^{-1}_i \rvert \le 1$ 的置换的数目。 对满足条件的置换进行循环分解，只有三种情况，(i) (i,j) (i,j,i+1,j+1)。 不考虑 4 的情况，可以枚举 2 的数目，两两配对，方案是： $$\Sigma \frac{i!}{j! * (i-2*j)! * 2^j}$$ 也可以用类似斯特林数的方法得到地推公式。 预处理这个在枚举 4 […]

2022/9/9
阅读更多

瓦喵之夏

瓦猫之夜，畅谈大理之行的感受 | 1783DAO 我去了中国最大的Web3聚会 发现人们想要的不是 Web3 未完成的乌托邦，洒下的青年火种—记瓦猫之夏大理 Web3 街会

2022/9/3
阅读更多

NOI 2022

https://www.zhihu.com/question/548696144 https://blog.csdn.net/liuzhangfeiabc/article/details/126594264 D1T1 https://www.luogu.com.cn/problem/P8496 会维护区间绝对众数的话，这个就是送分题了。。难点自然只剩下合并操作，可以选择的有平衡树启发式合并，函数式线段树 或 Treap，这里考虑用函数式线段树。 然后单个序列只有尾部插入和删除，所有就是栈的链表，然后每个链表再对应一个线段树。 （什么，vector 居然比 stack 要快？） #include <lastweapon/io> using namespace lastweapon; const int N = int(1e6) + 9, NN = 20*N; int n, q; struct Chairman_Tree { #define lx c[0][x] #define rx c[1][x] #define ly c[0][y] #define ry c[1][y] #define ml ((l+r)>>1) #define mr (ml+1) #define lc lx, l, […]

2022/9/2
阅读更多

Luogu P3765 总统选举

https://www.luogu.com.cn/problem/P3765 线段树维护潜在众数。 平衡树再进行核对。 我们可以用 atl 里的线段树，平板电视里的平衡树。 四舍五入等于啥都不用写。 #include <lastweapon/io> #include <lastweapon/segtree> #include <ext/pb_ds/assoc_container.hpp> using namespace lastweapon; using namespace __gnu_pbds; const int N = int(5e5) + 9; PII op(PII a, PII b) { if(a.fi == b.fi) return {a.fi, a.se+b.se}; if(a.se >= b.se) return {a.fi, a.se-b.se}; return {b.fi, b.se-a.se}; } PII e() { return {0, 0}; } […]

2022/9/2
阅读更多

Luogu P3369 【模板】普通平衡树

https://www.luogu.com.cn/problem/P3369 #include <lastweapon/io> using namespace lastweapon; namespace SBT { const static int N = int(1e5) + 9; int c[2][N], sz[N], ky[N], tot; #define l c[d] #define r c[!d] #define lx l[x] #define rx r[x] #define kx ky[x] #define sx sz[x] #define d 0 int new_node(int v = 0){ int x=tot++;lx=rx=0; sx=1;kx=v; return x; } void […]

2022/9/2
阅读更多

网络国家

在新一轮的封城和隔离期间，我阅读了 这本书， 考虑到当下中国的环境，它应该没有机会在中国大陆出版， 因而我翻译了其中的一部分，但基本上所谓翻译，其实只是使用了一些高级的机器学习翻译算法，加上我的一些调整。 首先，我特别享受阅读此书的过程， 此书使用一种类似伽利略的科学方法来重新审视历史这么学科， 相比福山，或是马克思的著作，此书认为历史并不是一个线性系统，而是一个会引导想多结局的混沌， 它更像是一个信息不完备的状态下的博弈。。书中还用了许多物理学现象做了很多类比，我特别喜欢这些段落。 这让我觉得本书的研究方法和结论都更加具有说服力。 以下是我关于此书的一些不同的意见， 大 Covid 期间想必大家 都读了不少书吧~~ 前 Coinbase 的 CTO，Balaji Srinivasan 上个月在网上发表了一本书，叫做《网络国家》。 说起来，区块链建国一直是大家热衷讨论的主题，早年就有在加州周围的公海上创业的尝试（Blueseed），去年伴随着萨尔瓦多、CityDAO、ConstitutionDAO 等实践，更是将这一热情推到了新高。。。 当然了，和《激进市场》一样，本书的很多说法都停留在思想实验的阶段，我们也应该抱着对 “历史虚无主义” 的批判来阅读这本书。。。 （此处应有旧版《国富论》中文译版的序言引用。。） 福山 与福山的线性历史观念不同，巴纳吉认为历史并不存在一种线性结构（linear progression），而是。 二十四史非史也。。 https://www.zhihu.com/question/28551520/answer/2388239123 但是我还是蛮喜欢这样的狂想的。。。比如《主权个人》，万一预言对了呢？ 相比《理想国》系列。。。这本书最大的好处。。就是作者的技术背景。。为它提供了更为新鲜的材料。。。用站在 2022 年夏天的视角。。重新审视了我们周遭的世界。。。 而不是只能 I know no way of judging the future but by the past … 。。技术革新绝对是推动社会变革最重要的动力。。。 或许最好的例子就是 核武器。。。。 也许下一项科技是人造子宫。。。（我相信这个科技树点出来之后。。。围绕着家庭建构。。性别独立的争论将会全部自然死亡。。。） 本书中。。。巴纳吉为我们描述了目前世界的状态，从冷战后的一超多强。。到一种新的三极结构。。并描绘了区块链建国的具体方式。。。 相反意见 […]

2022/8/31
阅读更多

旋转卡壳

https://oi-wiki.org/geometry/rotating-calipers/ https://www.luogu.com.cn/problem/P1452 | https://vjudge.net/problem/POJ-2187 直径 https://www.luogu.com.cn/problem/P3187 最小矩形覆盖 https://vjudge.net/problem/Gym-101175K 最小矩形覆盖、凸包宽度 https://codeforces.com/contest/1578/problem/F 最小矩形覆盖 + 微积分 https://vjudge.net/problem/POJ-3608 凸包间距 #include <lastweapon/geometry> using namespace lastweapon; using namespace CG; typedef vector<Po> VP; #define suc(x) (x+1==n?0:x+1) DB rc(const VP& P){ int n = SZ(P)-1, j = 1; DB d2 = 0; REP(i, n){ while (dett(P[i+1]-P[i], P[j+1]-P[j])>0) j=suc(j); checkMax(d2, max(dist2(P[i], P[j]), dist2(P[i+1], P[j]))); […]

2022/8/28
阅读更多

OFAC Sanctions && Tornado Cash

区块康波, Tornado事件持续发酵：监管之下的区块链，未来何去何从？ Fork It, #22 – PoW vs PoS https://web3101.fireside.fm/14 https://twitter.com/MinakoOikawa/status/1562976452571967488 https://blog.bitmex.com/ofac-sanctions-ethereum-pos-some-technical-nuances/

2022/8/27
阅读更多

BZOJ 1185. [HNOI2007]最小矩形覆盖

经典题。。 测模板。。 #include <lastweapon/geometry> using namespace lastweapon; using namespace CG; typedef vector<Po> VP; /*#define suc(x) (x+1==n?0:x+1) DB rc(const VP& P){ int n = SZ(P)-1, j = 1; DB d2 = 0; REP(i, n){ while (dett(P[i+1]-P[i], P[j+1]-P[j])>0) j=suc(j); checkMax(d2, max(dist2(P[i], P[j]), dist2(P[i+1], P[j+1]))); } return d2; }*/ #define suc(x) (x+1==n?0:x+1) DB rc(const VP& P){ VP R; […]

2022/8/27
阅读更多

AtCoder Regular Contest 146

传送门 https://atcoder.jp/contests/arc146 https://www.cnblogs.com/legendstane/p/16609911.html Problem A. Three Cards 取任意张也可做。排序两次，第一次用数字排序，第二次用字符串排序（但是要修改一下字典序的定义，不存在的字符取无穷大）。 Problem B. Plus and AND 题解里说二分，但是应该没有人会去写二分吧（复杂度一样）。。。 当然是去写按位贪心。。。每次确定第 i 位是否可以为 1，那么对于每个数需要求出与当前目标的距离。。 难点在于这个距离函数，需要各种讨论。 当然大牛们都是用位运算一行就把距离函数写出来的囧。。 Problem C. Even XOR Problem E. Simple Speed 计数，问有多少种满足以下条件的整数序列： 1. 每个数字出现的次数恰好为 Ai。 2. 相邻位置的差的绝对值恰好为 1。 个人觉得这个 dp 非常的优雅！ 首先不考虑条件 2，那么就是 多项式系数。 考虑条件 2，我们似乎可以暴力 dp… dp[i][j] 表示前 i 位，末尾为 j 的方案数， 但这个显然不可行。。因为我们没法记录每个数字当前还剩多少。。 所以核心是我们要避免去讨论当前状态里每个数字还剩多少。。。有办法吗？ 答案是有的！逐层推进 就行，也就是用数字的大小划分阶段。。。 那么一开始显然只有。。 […]

2022/8/25
阅读更多

Codeforces Round #814

传送门 https://codeforces.com/contest/1718 https://zhuanlan.zhihu.com/p/554786501 感觉掉了近 100 分。QAQ。。 题目还是非常不错的。。。特别是 D 题~~ 比赛时先开了 A2 但是写得非常有问题。。然后就只能先去写 A1 拿分。。。结果 A1 还写错了 1 次，并且 A2 就一直没 debug。。。 然后开 B 给的贪心也很失败。。需要特判很多情况。。。最后虽然发现了错误的 case。。。但是最后 debug 的时候居然写错了。。导致一直以为是 case 没找对。。。 Problem A. Burenka and Traditions 题意：有一个数组a，每次可以选择一个区间 [l,r] 和一个整数 x，将 al, al+1, …, ar 中与 x 异或，代价为 \ceil((r-l+1)/2) 问至少需要多少代价，数组所有元素均变为 0。 A1, n, ai <= 5000. A2, n […]

2022/8/17
阅读更多

AtCoder Beginner Contest 264

传送门 https://atcoder.jp/contests/abc264 Problem C. Matrix Reducing 数据范围很小，随便做。 #include <lastweapon/io> using namespace lastweapon; const int N = 10; int A[N][N], B[N][N]; int h1, w1, h2, w2; VI H; bool dfs(int k1 = 0, int k2 = 0, int h0 = 0, int w0 = 0) { if (k1 == h2) { if (k2 == w2) { […]

2022/8/15
阅读更多

AtCoder Beginner Contest 263

传送门 https://atcoder.jp/contests/abc263 Problem E. Sugoroku 3 被遗忘的游戏史：“纸牌马里奥”和“桌上塞尔达” 题解：先写转移方程，发现自环的情况可以消掉，然后就很 straight forward。 （官方题解 居然没有看懂。。。） #include <lastweapon/number> #include <lastweapon/fenwicktree> using namespace lastweapon; const int N = int(2e5) + 9; Int f[N]; int a[N]; int n; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n); REP(i, n-1) RD(a[i]); fenwick_tree<Int> T(n); DWN(i, n-1, 0) f[i] = (T.sum(i+1, […]

2022/8/11
阅读更多

[JSOI2008]Blue Mary开公司

https://www.luogu.com.cn/problem/P4254 https://darkbzoj.cc/problem/1568 这个 可真棒。。。 #define ll double struct Line { mutable ll k, b, p; Line (ll k = 0, ll b = 0):k(k),b(b){ p = 0; } ll y(ll x) const {return k*x + b;} bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < […]

2022/7/29
阅读更多

树分治

树分治思想简单，但细节变化繁多，很难模板化（至少我的代码里习惯会加一堆全局变量。。囧）。。 具体又可分为。。点分治，边分治，还有链分治。。。（也就是各种树链剖分，或许也可以归到树分治的范畴？）。。 更麻烦的还有动态树分治。。 https://oi-wiki.org/graph/dynamic-tree-divide/ 这个绝对是一个令人迷惑的称呼。。。到底你是 “动态树”分治，还是 “动态”树分治 啊。。。（实际当然是后者。。但是实际上有些用动态树分治解决的题目，确实可以用动态树解决。。= =。。。。。或许点分树这个名字更好？） 另外还有最近学到的用树分治来代替动态规划，用来求一类树上凸函数极值的问题。。。 https://vjudge.net/contest/122467#overview 点分治 https://www.shuizilong.com/house/archives/2014-acmicpc-asia-regional-xian-online/ 点分树 https://vjudge.net/problem/HDU-4918 http://hihocoder.com/problemset/problem/1065 SRM 624 Div1 1000 TreeColoring 树上凸函数求极值 https://codeforces.com/contest/566/problem/C https://qoj.ac/problem/2065

2022/7/26
阅读更多

atl 风 splay 模板

弄完了一个版本感觉还行 https://github.com/lychees/last-weapon/commit/58976a70bc0948c2073091c6cf2966a16e352127 目前例题用的是 GSS 系列。。。 不过 GSS3 这个题和 GSS1 一样都卡代码长度。。需要删点东西。。 GSS6 倒是很适合。。。 #include <lastweapon/segtree> using namespace lastweapon; struct rec{ int ss, ls, rs, ms; rec(int s = 0) { ss = ls = rs = ms = s; } }; rec e() { rec z = rec(-INF); z.ss = 0; return z; } rec op(const […]

2022/7/20
阅读更多

Codeforces Tinkoff Challenge – Elimination Round

G. Oleg and chess 先考虑网络流。。。是最朴素的二分图匹配。。。 还是设法要减少边的规模。。。我们类比扫描线来做矩形合并。。 从左到右扫描每一列，我们用函数式线段树，就能维护出代表这一列的线段树的根节点状态。。 那么只要从源点向根节点连过去一条容量为 1 的边即可。。注意需要保证这些线段树共享同一组闭合状态。。。 总感觉有更好的做法。。。 const int N = int(1e4) + 9; int T[N], H[N]; VI adj[N]; int n, m; namespace Chairman_Tree { #define lx c[0][x] #define rx c[1][x] #define ly c[0][y] #define ry c[1][y] #define lz c[0][z] #define rz c[1][z] #define ml ((l+r)>>1) #define mr (ml+1) #define lc […]

2022/7/15
阅读更多

BZOJ #3681. Arietta

https://darkbzoj.cc/problem/3681 网络流建模上比上题要简单。 函数式线段树方面需要线段树合并。 总之还是比上一题简单。 darkbzoj 不支持 cpp14，无法方便的使用 atl。。。（至少我不知道怎么改。。。） 值得注意的是对权值重复节点的处理，我们可以在叶子位置动态创建新的节点， 把旧叶子都包含在内，不影响复杂度。 另外对于之前的这类树上线段树合并问题，merge 的时候我们可以破坏掉之前的状态，覆盖式更新而不去 new_node() 以减少内存开支。 但是这个题里我们必须区别出这些状态（建图的时候会 query 到），所以还是老实的每次都 new_node() 为好。。。 const int N = int(1e4) + 9; struct Network_Flow{ const static int N = int(1e6) + 6, M = 2*N; int D[N], hd[N], suc[M], to[M], cap[M]; int n, m, s, t; inline void add_edge(int x, int […]

2022/7/15
阅读更多

UOJ #77. A+B Problem

首先还是类似 POJ 3469. Dual Core CPU 的最小割建模。 难点是对每个节点 i，我们需要构造辅助节点 i’，满足，如果存在满足条件的 j 在 T 割，那么 i’ 也一定在 T 割。 因为找 j 的过程是一个区间关系，暴力构造 i’ 的话边数太多。 类比确定染色方案后，查询结果这个问题，这个显然可以离散化 + 线段树（树状数组）， 我们发现可以使用线段树来刻画这些辅助节点以减少边的规模。（类似边分治里的加辅助结点？） （3b1b 演示的话。。大概就是把 i’ 这个辅助点，慢慢扩散成一个线段树，每扩散一层，叶子所连的边的规模就少一层。。）。 这种题目的出法后来在网赛里也出过。。。 另外这个题要考虑 j <= i 这个限制，最后还需要使用函数式线段树。 const int N = int(5e3) + 9; int T[N], X[N], Y[N]; vector<int> A; int n, z; namespace ST{ […]

2022/7/14
阅读更多

SRM 833

Div1 500 DP、状态分左右端点讨论即可。 – https://kmjp.hatenablog.jp/entry/2022/07/10/0930 Div1 900 WW 给定一个串，问排列成某个串复写两遍的形式 “WW”，最小代价是多少。 代价定义成每个字符的权重乘以它的位移。 https://kmjp.hatenablog.jp/entry/2022/07/10/1000 。。。费用流（二分图最优匹配）做法显然。。。（Tourist 使用 KM，kmjp 用的是费用流）。。。 。。。但是也可以直接贪心，参见 panda 教主的代码。

2022/7/14
阅读更多

Codechef JUNE15. Chefbook

https://www.codechef.com/submit/CHEFBOOK 我靠这个还要构造解。。。。 WA ing const int N = 1000, M = N*N; VI in[N], out[N]; struct Simplex { const static int N = int(1e4) + 9, M = int(1e4) + 9; DB a[N][M]; int b[N], c[M], X[M]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束 a[out][in] = […]

2022/7/7
阅读更多

Codechef FEB12. Flight Distance

https://www.codechef.com/submit/FLYDIST 非常暴力美学的线性规划。。。囧。。。不知为何，让我想起 SPOJ CAKE3。。。 值得注意的事。。。首先分数类是可以偷懒不写的…（暴力枚举分母）。。。 然后也没必要分 d[][] 和 w[][] 进行讨论，因为反正都相等了。。。 最后所有的约束关系恰好就是所有的三角不等式。。 （也就是 floyd 算法里的 kij、但这个题里因为反正都约束条件，所以你经典顺序写错的话也会不影响计算结果囧… ）。。。。 const int N = 10; int d[N][N], x0[N][N], x1[N][N]; int n; struct Simplex { const static int N = int(1e2) + 9, M = int(1e3) + 9; DB a[N][M]; int n, m; void pivot(int in, int out) { REP(i, […]

2022/7/6
阅读更多

BZOJ 3265. 志愿者招募加强版

https://darkbzoj.cc/problem/3265 https://blog.bill.moe/NOI2008-volunteer-advanced/ 经典错题。。。因为破坏了全幺模矩阵，线性规划无法保证求出整数解。。。 答案居然不会 LL = =。 const int N = int(1e4) + 9, M = int(1e3) + 9; struct Simplex { DB a[N][M]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束 a[out][in] = 1/a[out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束 DB t = a[i][in]; […]

2022/7/6
阅读更多

BZOJ 3118. Orz the MST

https://darkbzoj.cc/problem/3118 https://blog.bill.moe/bzoj3118-MST/ 小心重边。 const int N = 300 + 9, M = int(1e3) + 9; struct Tree { VI adj[N]; int fa[N], dep[N]; void dfs(int u = 1, int p = -1) { for (auto v: adj[u]) if (v != p) { fa[v] = u; dep[v] = dep[u] + 1; dfs(v, u); } } } […]

2022/7/5
阅读更多

Luogu P4412. [SHOI2004]最小生成树

https://www.luogu.com.cn/problem/P4412 https://darkbzoj.cc/problem/1937 这个题主要麻烦的点还是找环。。。 const int N = 50 + 9, M = int(1.5e3) + 9; struct Graph { int id[N][N]; struct edge { int x, y, w; void in() { RD(x, y, w); } } E[M]; int n, m; void in() { RD(n, m); REP_1(i, m) { E[i].in(); id[E[i].x][E[i].y] = id[E[i].y][E[i].x] = i; } } […]

2022/7/5
阅读更多

Luogu P3980. [NOI2008] 志愿者招募

https://www.luogu.com.cn/problem/P3980 https://blog.bill.moe/NOI2008-volunteer/ const int N = int(1e4) + 9, M = int(1e3) + 9; struct Simplex { DB a[N+1][M+1]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束 a[out][in] = 1/a[out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束 DB t = a[i][in]; a[i][in] = 0; REP(j, m+1) […]

2022/7/5
阅读更多

Luogu P4043. [AHOI2014/JSOI2014]支线剧情

https://www.luogu.com.cn/problem/P4043 https://darkbzoj.cc/problem/3876 https://blog.bill.moe/AHOI2014-plot/ const int N = int(5e3) + 9, M = int(3e2) + 9; VI in[M], out[M]; struct Simplex { DB a[N+1][M+1]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束 a[out][in] = 1/a[out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束 DB t = a[i][in]; a[i][in] […]

2022/7/5
阅读更多

Luogu P3337. [ZJOI2013] 防守战线

https://www.luogu.com.cn/problem/P3337 https://darkbzoj.cc/problem/3112 https://blog.bill.moe/ZJOI2013-defend/ const int N = int(1e3) + 9, M = int(1e4) + 9; struct Simplex { DB a[N+1][M+1]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束 a[out][in] = 1/a[out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束 DB t = a[i][in]; a[i][in] = 0; REP(j, […]

2022/7/5
阅读更多

BZOJ #3550. [ONTAK2010]Vacation

https://darkbzoj.cc/problem/3550 https://blog.bill.moe/bzoj3550-vacation/ const int N = int(1e4) + 9, M = int(1e3) + 9; struct Simplex { DB a[N+1][M+1]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束 a[out][in] = 1/a[out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束 DB t = a[i][in]; a[i][in] = 0; REP(j, m+1) […]

2022/7/5
阅读更多

线性规划

资料 https://oi-wiki.org/math/simplex/ https://blog.bill.moe/simplex-algorithm-notes/ https://notes.sshwy.name/Math/Linear-Algbra/LP-and-its-Dual/ https://www.zybuluo.com/winee/note/1186606 https://en.wikipedia.org/wiki/Simplex_algorithm https://en.wikipedia.org/wiki/Ellipsoid_method https://en.wikipedia.org/wiki/Interior-point_method https://www.codechef.com/viewsolution/7183029 https://github.com/kth-competitive-programming/kactl/blob/f6a97d9e5766c90ee71a97a90cd3faf6cff0ca72/content/numerical/Simplex.h ASC 2. Roads https://codeforces.com/gym/100197 https://www.luogu.com.cn/problem/P4412 https://darkbzoj.cc/problem/1937 https://darkbzoj.cc/problem/3118 「ONTAK2010」Vacation 「ZJOI2013」防守战线 [NOI2008] 志愿者招募 Luogu P3980. [NOI2008] 志愿者招募 BZOJ #3265. 志愿者招募加强版 const int N = int(1e4) + 9, M = int(1e3) + 9; struct Simplex { DB a[N][M]; int n, m; void init(int _n,int _m) { //a矩阵m行n列 n […]

2022/7/3
阅读更多

Codeforces Global Round 21

传送门 https://codeforces.com/contest/1696 https://zhuanlan.zhihu.com/p/533890061 Problem D. Permutation Graph 给定一个排列 A ，排列的每个位置对应图中的一个节点，如果一段区间的端点上的数恰好等于这个区间的两组最值，那么我们就给这两个端点位置之间连一条无向边。 问从位置 1 出发到位置 n 的最短路。 这个题有两种做法。。做法 1。。 只要考察路径上的必经之点。。不失一般性，我们考察最小数。。。 假设位置为 p，那么最后的路径一定经过这个位置，因为 p 左右两边互不联通，那么我们显然可以用 p 进行递归，变成 [0, p] 和 [p, n) 两个子问题，且两边对称，我们考虑 [0, p] 这个子问题。 和开始的状态稍微不同，因为我们知道最右侧必然是最大数，因此这一次我们要找 [0, p] 区间的最小数，设位置为 x，那么再次分割成 [0, x] 和 [x, p] 两个子问题。 其中 [x, p] 最大值和最小值都在两侧，直接返回 1，而 [0, x] 是一个结构一样的子问题，于是结束，整个算法只需要预处理前缀和后缀的最小、最大值和对应下标即可，复杂度 O(n)，非常简单。 const int […]

2022/6/27
阅读更多

Codeforces Round #800 (Div.1)

传送门 https://codeforces.com/contest/1693 https://www.bilibili.com/video/BV18Y411T71q https://www.acfun.cn/v/ac35355359_3 https://zhuanlan.zhihu.com/p/530668156 https://zhuanlan.zhihu.com/p/529953575 这场题目非常不错，有点 atc 的感觉了 … Problem B. Fake Plastic Trees 题意：给定一棵有根树，每一个节点有一个区间 l[i], r[i]。每次操作可以选择从根出发的路径，沿着路径上的每个点增加一个数，满足增加的数组成的序列非递减， 问至少多少次操作，能够满足每个节点的值都在其给定的区间里。 题解：树 DP 先弱化问题，假设 l[i] = r[i]。 设 dp[u] 表示以 u 为根节点的子树都满足条件时，至少需要多少次操作。 那么有 dp[u] = \sum dp[v] + (\sum r[v] < r[u])。 回到原问题，我们 dp 过程中贪心的让每个节点的标号尽可能大即可。 const int N = int(2e5) + 9; VI adj[N]; LL l[N], r[N]; […]

2022/6/21
阅读更多

GR14 投票 List

https://gitcoin.co/grants/5688/jediswap-first-amm-on-starknet-enabling-instantan https://gitcoin.co/grants/4665/via-protocol-web3-mastercard-best-ux-among-any-to https://gitcoin.co/grants/5007/lenster https://gitcoin.co/grants/6114/meta-space https://gitcoin.co/grants/5744/w3itch

2022/6/10
阅读更多

Minetest 如何实现游戏内转账

客户端修改 之前发现 Minetest 的引擎代码是和 easyrpg 一样是 cpp，那么也就意味着它也同样有机会可以使用 emscripten 编译到浏览器中运行。 网上搜了一圈，发现还真有人已经做了这件事。。。 https://blog.minetest.net/2022/03/27/March/ 那么现在转账命令就非常容易实现了，可以先写在 js 里，然后直接调用对应的 js 方法即可。 不考虑安全问题。。我们先做一个简易且泛用的实作。。用邪恶的 Dr.Eval 大法，执行任何脚本。。。 void escape_EM_ASM(const std::wstring &message) { std::wstring m = translate_string(message); std::string s(m.length(), 0); std::transform(m.begin(), m.end(), s.begin(), [] (wchar_t c) { return (char)c; }); MAIN_THREAD_ASYNC_EM_ASM(console.log("Msg: " + UTF8ToString($0)), s.c_str()); std::string c; c = ".EM_ASM "; if (s.find(c) != […]

2022/6/5
阅读更多

Minetest 相关

Background 之前在 SeeDAO 里和开发工会开会，聊游戏化产品，当时我举的例子是 EasyRPG，因为恰好有一个德语版的牧场物语同人游戏被考古发掘出来。 但是仔细想象即是是牧场物语、星露谷、动物之森这样的作品，沙盒的属性依然是十分薄弱的，那么自然想到的第一梯队自然是 Minecraft 和 Roblox 了（虽然我自己玩的更多的还是饥荒、Besiege、泰拉瑞亚这些）。 不过这样想来，沙盒游戏本身 大概也是一个 Roguelike 类似的概念，需要分成广义和狭义来讨论。 广义的话，有沙盒要素就算，那么大部分开放世界游戏（GTA、荒野大镖客）、和模拟经营类游戏（运输大亨、过山车大亨、铁路大亨、模拟人生、etcs）也都能算沙盒。 狭义的话，那么只有 Minecraft、Roblox 这样没主线的、GamePlay 全靠玩家自己想办法我才认为算。 那么都已经讨论到沙盒了，不妨搜一下有没有什么 Minecraft 的开源方案，首先我记得以前玩过一个叫做 CubeWorld 的东西， 它们还是一对夫妻店！但是很遗憾，这个作品 2019 年发布之后，作者好像就软跑路了。。。。。。 于是继续寻找 Minecraft Opensource Alternative。目前感觉社区分为最好，完成度最高的就是 Minetest！ 而且游戏的设计完美符合我心目中沙盒类游戏应该呈现的样子（Mods 是游戏里的一等公民，同时也想 Roblox 那样，支持 Games，完全可以当成是游戏引擎，和开发平台来使用。） 而且 Minetest 的底层和 EasyRPG 一样，也是 Cpp，那么完全也可以像 EasyRPG 那样使用 emscripten 技术编译成 wasm 在浏览器端运行，从而可以和 web3 生态完美协作。。。。 于是之后上周五又和 PM 们开了一次会，更新了一下需求。（啊，忘记录了？） Minetest […]

2022/5/23
阅读更多

近况

Life’s like a box of chocolates, you never know what you’re gonna get. 博士，您还有许多事情需要处理。现在还不能休息哦。 如此前所说，最近莫名其妙的空降到了某个跨国 GameFi 公司去做了 CTO？ 一下子要协调起各个部门 40+ 号人一起工作，且突然又使用起了亲切的 Google Calendar … 还让我蛮怀恋的 … 于是我又模仿起最初加入 Google 的时候的样子写了一封自我介绍。。 Hello everyone, you may probably have heard me on the Internet or TV show before … If not, I’d like to have a short introduction of […]

2022/5/14
阅读更多

mkxp-z

https://home.gamer.com.tw/creationDetail.php?sn=4835952 https://gitlab.com/mkxp-z/mkxp-z/-/issues/47

2022/5/3
阅读更多

加密货币和美元是合作伙伴，而不是竞争对手

案：前链闻的 Liu Feng 老师 在推特 呼吁中国有远见的政策制定者和真心期盼中国强大的爱国者，读一下 Niall Ferguson（算是目前最顶尖的金融历史学家了吧）的 最新文章，我读完觉得确实蛮有道理，于是稍微翻译了一下。。。 加密货币和美元是合作伙伴，而不是竞争对手 新冠疫情与俄侵乌战争所带来的破坏，显示了西方制度的优势和中国制度的弱点。 “我希望它能创造世界和平，或帮助创造世界和平。” 这是前 Twitter 公司首席执行官、现任数字支付公司 Block Inc. 负责人杰克-多尔西 (Jack Dorsey) 在 2021 年 7 月的一次网络研讨会上对比特币的评价。 更有可能的是，战争创造了全球对比特币的更大胃口。动荡的时代往往与货币转型有关。一个典型的例子是，在黑死病和百年战争时期，英国的货币体系被从根本上改变了 。 瘟疫过后，商品价格飙升–尤其是盐，其价格从 1347 年到 1352 年上涨了 7 倍。同时，黑死病的幸存者能够利用紧张的劳动力市场，用封建束缚换取现金工资。英国经济变得越来越货币化。 与此同时，欧洲商人开发了一种新形式的点对点信贷工具–汇票，促进了英国、低地国家和意大利北部之间的贸易。 更近的例子比比皆是。西班牙在新世界的征服改变了全球经济，增加了白银和黄金的供应，其中大部分用于支付哈布斯堡家族的欧洲战争。大英帝国的扩张输出了金本位制，创造了一个新的、更稳定的国际货币体系，其中英镑是主导货币。世界大战使英国被债务拖垮，并迎来了第一个美元主导的时代，美国货币与黄金挂钩，所有其他主要货币都不那么严格地与美元挂钩。 1971 年，又是冲突结束了布雷顿森林体系。随着越南战争的拖延，理查德-尼克松总统 打破了美元与黄金的挂钩，开创了一个新的法定货币浮动时代，起初的特点是高通货膨胀和汇率波动，然后是一系列国际协议（1985 年的《广场协议》，两年后的《卢浮宫协议》），后来是在通货膨胀下降和资本流动迅速增长的环境下，更多的临时安排和不太透明。 过去两年发生的事件–首先是 Covid-19 大流行病，现在是俄罗斯入侵乌克兰–具有足够的破坏性，使全球货币秩序似乎有可能再次发生转变。但它将采取什么形式呢？有两种假设已经浮出水面，但绝不是相互排斥。 首先是加密货币的时代已经到来。用科技公司 Steel Perlot Management LLC 的首席执行官 Michelle Ritter 的话 来说，”社交媒体的铰链时刻出现在 2011 年，当时来自利比亚、埃及、也门、叙利亚和巴林的视频、推文和其他帖子引发了阿拉伯之春 […]

2022/5/3
阅读更多

2k3 名作

2010 以前 Nepheshel http://til.sakura.ne.jp/soft_free/nepheshel/index.html イストワール Histoire http://www.sk.aitai.ne.jp/~kakesu/histoire_support/ 2010 以后 ふしぎの城のヘレン https://store.steampowered.com/app/418190/_/?l=japanese 汉化地址 流程攻略 https://w3itch.io/game/66 帽子世界 https://www.freem.ne.jp/win/game/20070 Komica Wiki シルフェイド幻想譚 https://silversecond.net/contents/game/silfade_gensou/ https://w3itch.io/zh-CN/game/270 アストロソス Download 寄生ジョーカー bilibili, 【某记者实况】 《寄生joker》 一周目完结 （日文动作恐怖） niconicopedia 来源 https://twitter.com/Lost_Paradigm/status/1510946194440130560

2022/4/14
阅读更多

使用 RM2k3 开发卡牌游戏

https://w.atwiki.jp/vip_rpg/pages/631.html 03非常好用，我之所以会选择用03去做游戏是因为这么几个优点↓ 首先它自带后面几个版本没有的画面放大方式，也就是说它可以自己选上x2、x3、x4的画面显示倍数，全屏也不用担心辛辛苦苦画的东西糊成一坨翔！ 其次它自带着像素的字体，之后无论是XP、VA、MV，想要显示这样的像素字体都是不容易完成的。 一个比较细节的点是在播放BGM的时候，03以及00都可以做到无缝的改变音乐的倍速以及声道，但是如果使用VA，改变音乐倍速是会让音乐重新播放的 再然后，就我这个画画的家伙而言，320×240的分辨率真的很好偷懒啊哈哈哈哈哈XD 它的地图图块绘制起来也非常简单，自动元件的切分方式多少比VA好画一些 不过作为一个比较老款的引擎，它也的确是有着它的缺点的， 譬如说事件相较于后面几作，显得有些繁琐，该有的例如独立开关这样比较常有的功能这里也还没有， 绘图方面因为索引图片256色的限制，制作图片时多少会有些麻烦，也不能在里面导入太清晰的图片素材了， 另外至今也有一些不知道如何产生的不明确的BUG，虽然出现的几率相当相当小，不过也还是会给填坑造成困扰，所以得养成时常备份保存的习惯呢 —— Steam RM2k3 评测 上面这段 Steam 上关于 RM2k3 的 评测 基本上说的已经很不错了。。。 早期的 2k3 设计简单，代码没有加密，使得坊间有非常多成熟作品和素材网站可供参考，这对于美术苦手的我来说无疑是一大福音。 同时 2k3 的编辑器使得制作做 story telling 相对之前用 小黑屋 的代码来手撸 着实容易许多，除了我可能需要更加先进的类似 galgame 那样的，可快进，可回放的剧情演出系统。 当然以上所有这些我此前都觉得瑜不掩瑕。。。因为 2k3 相较其它几个版本的 RM 有一个致命的缺陷。。。。 那就是缺乏脚本语言，使得想实现什么功能的时候会非常头痛，（虽然 common event 理论上也是图灵完备的） 且不说复杂的游戏机制了，举个不那么恰当的比喻，就比如类似 dota1 里面的装备合成，能完成肯定能完成的，如果有可能就要写一大堆的 if-else，非常复杂触发不利于维护。 而实现难度的上升，就会导致游戏的玩法趋于同类化。。。反正我对于在 2k3 这种受限制的情况下做出新的玩法的开发者无比敬佩。。。但那一定不会是我的己之道。。。 EasyRPG 这点在我发现了 ynoproject […]

2022/4/4
阅读更多

地图演出细节相关

地图名字 https://www.bilibili.com/video/BV1QJ411X7iJ?t=317.4

2022/3/27
阅读更多

海之歌

Demo Github 背景设定

2022/3/19
阅读更多

RM 2k3 扩展指令系统

List .call x 执行除自己之外，其它玩家编号为 x 的公共事件 .exec x 执行所有玩家，编号为 x 的公共事件，包括自己 .turnon_FOV 开启视野模式 .turnoff_FOV 关闭视野模式 .gen c0 c1 生成一个标准 rogue 迷宫，以 c0 编码作为墙壁，c1 编码作为可通行区域。（当编码在 4000-4500 时，计算因 autotile 所产生的 offset）

2022/3/17
阅读更多

《もしもスマブラだった》中的镜头实现

镜头语言在设计游戏时非常重要，除了可以加强叙事，在一些玩法中也是 Gameplay 的重要组成成分。 （e.g. 在《狂父》的最后，aya 在倒地之后，父亲举起电锯的画面有 一个缩放镜头的特写， （Dungeon of the endless 中，需要缩放镜头来进行人员部署。。。 但是众所周知，RM2k3 里居然没有镜头对象，也没有像隔壁 Wolf RPG Maker 以及 GameCreator 里那样的缩放操作，使得需要缩放镜头的地方变得非常难以处理。。。 之前发现在场景切换的时候实际上是有 zoom-in，zoom-out 事件的，但是想进去魔改之后却还是失败了。。。 云风老师鼓励我们，分析开源项目的时候，应该假设自己是代码的作者，想象自己是怎么写出来的，其实 easyrpg 和 pico8 一样，都是非常标准的主循环结构，都是 … while (true) { update(); draw(); } 之后就去爬了一下官方的 Blog。。。在读博客的时候发现了好多此前闻所未闻的 RM2k3 游戏。。。在 这篇文章 中，还出现了一个吊炸天的作品。。。。。。もしもスマブラだったら。。。 这个玩意有多厉害我就不多说了。。。 https://yno.yumenikki.info/?game=smash。。。。 众所周知。。。任天堂明星大乱斗里。。由于有四位玩家同时作战，对镜头的控制相对于、侍魂、月华剑士等作品来说，要显得更加复杂。。。 这种在正常游戏引擎里要实现尚十分困难。。。这是怎么在 RM2k3 里实现的呢。。。。 怀着好奇的心情。。。我打开了游戏的档案。。。结果。。。。 https://t.me/algorithm_daily_of_minako/4418。。。。 也就是说整个游戏中 tilesmap 模块只做障碍判定用，而显示的部分，全部都是几个图片。。。 然后再用几个变量去计算出缩放距离。。。最后每一帧之后都通过一个 500 行的 […]

2022/3/14
阅读更多

从法西斯主义手中保卫生活

匿名信来源： – https://twitter.com/jakobsonradical/status/1502927277713096704 公开的法西斯主义被消灭已有近 80 年。对现代人来说，法西斯这个词已然退化为一个用于一般化政治攻讦的贬义词，而失去任何具体的含义。 但与此同时，法西斯主义并没有真正死亡。与过去公开的阵营对抗不同，今天的法西斯主义以匿名的方式渗入到我们的日常生活中，以“习惯”的形式侵蚀我们的生活和我们的道德。 在这种隐秘的侵蚀下，我们变得冷漠而残忍，以他人的痛苦为乐，在其中汲取虚幻的优越感。我们沉醉于空洞的宏大叙事，用想象的集体胜利掩盖对自身命运的无力与绝望。我们为仇恨言论所吸引，自以为能在丛林竞争中获得优胜，而对“自由”、“民主”、“平等”、“正义”这些保卫自身的价值嗤之以鼻。 社会的撕裂、对未来的绝望、道德的沦丧、我相信这已经是我们这一代人的共同体验，无论你抱持何种意识形态。 但还没有到投降的时候。现代的反法西斯斗争，将是一切人反对一切人的战斗————不是对他人，而是对自己。为了从法西斯主义手中保卫我们的生活，我们必须要向自己宣战。 我们要战胜被结构性鼓励的懒惰。要超越容易获得的咨询、观点与知识，去主动地建立反思性的认知方式，以独立、自由的人的姿态面对社会。 我们要超越宣传、惯习与偏见，去认识具体的人，开放地面对每一个群体，从而体会到这个事实：人与人的共性远超过被夸大的异质性。 我们要保持心灵的开放，保持改变自身的能力，让求真意志超越无益的自尊，用真实的尊严保护自身的完整。 最重要的是，要允许自己保持无力。在强制性的权力面前、个体无力掌控自身命运。这的确是绝望的情境。一种选择是将自己的大脑改造成强权的形状，以营造狐假虎威式的权力感。而我宁愿保持自身的无力，暴露在绝望的处境中以保卫更重要的东西————我的道德、我的良知。 同学们，行动起来，保卫自己，保卫社会，保卫生活。 Anti-fascist

2022/3/14
阅读更多

vipRGなんとか 全集

代表作 もしもスマブラだったら テイルズオブRTP ジャンヌアクション セプテンバー 剑系列 1-4 5 6

2022/3/14
阅读更多

RM2k3 ChipSet

原理 https://rpgmaker.net/tutorials/975/ https://www.makerpendium.de/index.php/ChipSet https://www.makerpendium.de/index.php/AutoTile 素材库 http://www.mirai-online.de/?page=chipset

2022/3/12
阅读更多

Dungeon of the Last Tour

Source Code：https://github.com/lychees/Dungeon-of-the-Last-Tour 由于目前依然是通过消息来调用远端玩家的公共事件来实现多人交互，所以必须先输入昵称进入可发消息的状态才行。 之前说，7DRL 想做《少女终末旅行》的同人。。。顺便可以尝试自己魔改出一些 EasyRPG 的新特性。 网上搜了一圈，居然这部作品的同人游戏甚少（当然不是什么作品都有东方那样的人气啊！。。。） 能找到的就只有一个 烧书的，和一个 横版平台条约过关。。。 核心玩法 《少女终末旅行》的主线（如果算的话）是爬塔。。。 而爬塔就是 Rogue 的原始形态。。。虽然大部分都是往地下深处走。（Rogue、暗黑破坏神、以撒的结合）。。。 但是也有一些 Roguelike 是往上爬的。。最经典的例子莫过于是 Dungeon of the Endless。。。。 （但是说到爬塔，我最喜欢的是 《刀语》的最后一集。。但是其实这个爬塔的桥段。。早在 动画版的《新少年黄飞鸿》，和《太极宗师》里就出现过。。。。（后者就是日后大名鼎鼎的「战狼」的出道作 = =）。。 所以基本思想是想做成 Dungeon of the Endless 那样的开门模式。。。开一扇门会出现一堆怪主动冲出来。。（一波一波的类似塔防。。） 清理掉它们之后可以获得各种资源、装备。。。整备之后再开门。。。直到收集足够的汽油，最后大家一起驾驶着 SdKfz 2 前往上层。。。 https://www.pixiv.net/artworks/65909963 这个玩法最核心的机制是必须制作地图同步（单人就无所谓了。。如果要加入多人解谜的话。。必须花点时间做科研。。）。。。 地图拉升或是小地图也是必须的。。。（因为需要在开门之前制定战术、部署兵力。。） RM2k3 stg 似乎 rm stg 的 plugin 已经很成熟了。。。比如，我最早接触的同人游戏之一，很久很久以前《大众软件》上推荐的《沧海沉梦邓稼先传》就是 stg 玩法。。。 不过 RM2k3 有例子吗？还真有！。。。梦日记生化版恰好就是 stg […]

2022/3/10
阅读更多

德语学习

https://www.bilibili.com/video/BV14t411F7vo https://amara.org/en/videos/kYVHQUQrQhgr/de/212113/

2022/3/7
阅读更多

Codeforces Round #775

https://codeforces.com/contest/1648 https://zhuanlan.zhihu.com/p/476724675 https://zhuanlan.zhihu.com/p/476735877 B. Integral Array 判断一个序列中是否存在较大数除较小数下取整不属于该序列的情况。 有点上次 Tourist Round B 题 的既视感，注意这次别再写成 O(nsqrtn) 了 。。。 D. Serious Business 给定三行数字，要求左上到右下，只能向右 和 向下，方格取数，初始中间一行是关闭的，然后有 m 个操作，每次中间打开一个区间， 你可以从中选一些操作，要求使得最后方格取数的结果最大。 这个题我觉得出得非常不错，首先读完题目几乎把我要用分治告诉你了，那么第一感觉是去写线段树 dp。。。 但是具体怎么写。。。居然想不出来怎么做。。。 赛后看了一下果然就是线段树 dp …（也有人 cdq 分治。。） https://codeforces.com/contest/1648/submission/148591405 首先我们不妨弱化一下问题，给一个覆盖整个区间，且代价为 0 的操作，那么显然可以线段树，方法类似 GSS 系列，简单区间合并。。。 然后就是这个题厉害的地方，我们可以离线处理所有操作，对于每个操作，对这个操作所覆盖的区间进行询问，紧接着，将这次操作所产生的影响，加回到线段树里。。。 我觉得这个想法还是蛮奇妙的。。。 E. Air Reform 给定一个边权图，定义其补图的权值为原图上连接两点的路径中，边权最大值的最小值。问用同样的方式再从补图得到原图后，每一条边的权值。 我们只要求出补图的最小生成树，就可以简单的求路径上的最大值得到最终的边权。 于是我们只需要求出补图的最小生成树即可，而这个可以简单魔改一下 Kruskal。。。 是不是感觉有点像 #767 的 E 题？ F. Two […]

2022/3/7
阅读更多

我认识的俄国人如何看待乌克兰战争？

我当然无从知晓普通俄国人如何看待这场战争，但是或许可以自己认识的俄国人那里了解一二，为此我还尝试登录了一下 vk （现在因为手机号的限制已经登录不上了）。 我大学生活哈尔滨就是一座最初就是俄国人所建设起来的城市，我也特别喜欢《后裔弃兵》里所描绘的莫斯科 —— 满街都是国际象棋的选手、那满足了我对一个遥远国家的全部幻想，我的第一笔收入还是 CF 的出题费。 俄罗斯是一个伟大的民族，Google、Telegram、Ethereum 这些耳熟能详的项目接出自俄国人之手 —— 可是为什么都是移民到异国他乡之后呢？ hujle https://twitter.com/hujle_sugary 首先是我最近认识的一个朋友。。。hujle 是一个在俄国的梦日记社区的管理员，前段时间我们在一个开发群里一起聊如何魔改 EasyRPG 的多人版（也就是 Yno Project），它们自己也 Setup 了一个 Yno 的 Fork。 它的 Discord 社群里有许多有趣的人，有 meme 制作者，游戏开发者，我从与它们的讨论中学习了不少东西。 战争开始之后，许多人都处在了政治性抑郁之中，它的一个网友（美国人）给它发了一段温暖人心的信息，大意是：我非常喜欢你制作的梦日记 meme，并感谢你这么多年来为梦日记社区所做的一切，stay safe。 thank you for your kind words @AphexCarti i really appreciate the support 🙏ill do my best to stay strong and keep contributing […]

2022/3/5
阅读更多

英雄之时

https://store.steampowered.com/app/1656780/_/

2022/3/5
阅读更多

An 255

A beautiful takeoff video of @antonovairlines AN225 taken by @NiclasHCO. For the record, this was the last takeoff Mriya made, performing her very last mission on a position flight from BLL back to GML on 02/05/2022 😢🇺🇦❤#Ukraine #StopWarInUkraine #antonov225 pic.twitter.com/DWFiDFWjnR — IkerWater 🇵🇲🌊 (@Iker_Water) February 28, 2022 被炸毁的最后一架世界上最大的运输机An-225,原来飞机真的可以划破天空。 pic.twitter.com/77b6lDeWwa — loongtengfei (@loongtengfei) February 28, 2022 […]

2022/3/5
阅读更多

stand with ukraine

恐怕现在对世界影响最深远的事件就是 Covid 的和乌克兰战争了， 虽然进入新世纪之后，局部战争依然不断，但我们依然感觉战争离我们很遥远。 这次战争我们还作为旁观者说说笑笑，但下次还可以吗？ 或许这场战争我们需要从两个角度去认识它，正如 这位生活在乌克兰敖德萨的北京人 所说得那样，身前有坦克大炮，看得见，很恐怖。。。 （身后还有一个看不见，但真实存在的幽灵，更加恐怖。。。） 先亮身份。。。首先我认为一切侵略行径，无论以何种理由，都是不正义的 —— 乌克兰、叙利亚、阿富汗、伊拉克、etcs。 我觉得中国作为近代以来历次侵略战争的受害者，应当更能对所有受战争侵略的国家和民族产生共情。。。 像是俄罗斯军队保持了最大程度的克制，以减少对平民的伤亡。。。 （比如 在途经红绿灯的时候还会礼貌的停下来什么的。。） 这种愚蠢的叙事。。。感动感动自己就够了。。。 以下是收集到的关于乌克兰局势分析的三篇长推。。。 核武时代的地缘政治 https://web.archive.org/web/20220301014627/https://threadreaderapp.com/thread/1498192454352211968.html 民主的棘轮 https://threadreaderapp.com/thread/1498126818397896715.html 里面发明了一个词叫做 民主的棘轮，文章的结论大概和之前 安替在推上转发的另一篇文章 —— 为什么俄罗斯将输掉这场战争？ 是类似的。 现在这篇译文在微信上已被 block，这里推荐读原文，因为译文缺少了最后一段关于民族建构的论述。 https://twitter.com/kamilkazani/status/1497993363076915204。 文明社会的表征 https://threadreaderapp.com/thread/1499392869051904004.html Cultural institutions are grappling with whether to boycott Russian artists as the war in Ukraine continues. While attention has focused on those […]

2022/3/5
阅读更多

EasyRPG 地图缩放

Chat_Multiplayer::gotMessage call = ".zoom"; if (std::equal(call.begin(), call.end(), msg.begin())) { Transition::instance().running = true; Transition::instance().InitShow(Transition::TransitionZoomIn, Scene::instance.get(), 120); //Game_Map::Randomize(); return; }

2022/3/2
阅读更多

Yno.Yumenikki.Info 游戏列表

本家及同人 收录三款作品，另外两款同人均为本家的补丁。 关于角川版本，steam 的角川版本与 kikiyama 版本并无明显区别，使用了完整 rts 源，然后显示的版本号为 0.1a。 这是因为 kikiyama 官网的梦日记时机是分为 0.1 和当天发布的一个 bug 修复补丁，kikiyama 发布后不知为何一直没有把它们合并， 但是打上这个补丁的版本版本号显示为 0.1，或许是为了更加明确的区分，所以 steam 角川版本在标题画面明确标明了 0.1a。 虽然 3D 版本和 Project Yumenikki 毁誉参半，但是这个 0.1a 确实方便了许多玩家w，并且还提供了英文版本，目前 itch 上流传的俄语版本 也是基于 0.1a。 这些版本都没有进行加密！可以直接使用 rm2003 直接打开w… 作品名称 作者 相关链接 联机版 梦日记 kikiyama – jp | en | chs | cht | rus 梦日记随机版 vgperson […]

2022/2/27
阅读更多

Crypt of the Alexander

https://www.rpgmakerarchive.net/2017/05/crypt-of-alexander-rm2k-viprpg.html https://store.steampowered.com/app/247080/Crypt_of_the_NecroDancer/

2022/2/27
阅读更多

《地球冒险》同人作品的历史

https://rpgmakerhistoria.home.blog/2021/12/05/a-history-on-rpg-maker-earthbound-likes-and-fan-games-part-one/ https://rpgmakerhistoria.home.blog/2022/02/10/a-history-of-rpg-maker-earthbound-likes-part-two%ef%bf%bc/ 【游戏通鉴Vol.11(SP)】用爱编织出的世界：地球冒险三部曲（Mother三部曲）通览【4P】 案：考古 rm 游戏历史 的时候偶然看到的两篇文章，感觉非常有趣，稍微转译如下。 说来惭愧，我第一次了解这个作品果然还是从《任天堂明星大乱斗64》，里面的 Ness 作为隐藏角色出现，而且还是 4 个隐藏角色里最难解锁的一个。 而且其实我也没有认真的玩过这款作品，我的童年里最接近《地球冒险》的游戏可能是 —— 阿猫阿狗。 棒球、报纸、汽车、沥青。仅仅是将你的RPG游戏设定在当代，就会立即招致与HAL著名的《地球冒险》系列相比较。还需要有一种轻松的感觉，否则你可能就会变成像《寄生前夜》那样的恐怖游戏。当然，《地球冒险》游戏并不回避黑暗和迷幻的主题。像战争和犯罪这样的事情确实存在于我们当前的时代，但如果没有诡异的旋转，就很难真正将街区中的回合制冲突背景化。任天堂家庭友好型也是一个激励因素。僵尸启示录或外星人入侵，邪教，或某些事情需要发生（Earthbound有所有这些），我认为这就是为什么在制作现代的东西时，很容易转向 糸井重里 的方向。幻想和科幻本身就是荒谬的，而典型的美国理想的郊区则不是（取决于你问谁）。尽管仅仅是让你的游戏变得古怪就足以获得 “地球冒险” 的标签。 事情并没有改变。有一种独立游戏的论调围绕着对 “地球冒险-like” 的厌倦。我呃，不谈这个了。让我们只说当时围绕它的前景和态度与把每个平台游戏都比作《洞穴故事》差不多。很难凝练出究竟是什么引起了《Earthbound》的一切，即《Earthbound》。然而，随着RPG Maker社区的早期发展，真的没有那么多EB-like。当然有大量的粉丝游戏，但有趣的是，想想某些Squaresoft精灵的模块化程度对许多RPG Maker游戏的设定（以及代理故事）的影响比实际的艺术风格还要大。实际上，有一个专门的网站致力于提供为RM2K格式化的Earthbound翻版，以及事件教程。模板和资源比实际的方块游戏还要多（还有很多关于如何制作滚动数字的战斗系统帮助主题）。 EarthBound Max (RM95) (2000) 所以 Starmen.net 可能会被经常提起，因为它最早可以追溯到 2000 年，并且 承载了许多粉丝作品。粉丝游戏和应用程序页面有任何你能想象到的东西（有一个Earthbound Doom WAD，老天爷）。该网站的粉丝游戏论坛已经成为自己的RPG Maker社区，在为这篇文章进行研究时，一些用户名引起了我的注意。突出的早期游戏是EarthBound Max（RM95）（2000年）。这可能是最早的、最具体的类似于EB的RM化身。根据剩下的屏幕截图，它看起来是RPG Maker 95。它的Angelfire网站奇迹般地还在运行。遗憾的是，由于第三方主机的失效，下载无法恢复。剩下的就是写故事了。 EarthBound Force (RM2K) (2001) EarthBound Revolution (RM2K) (2002) Earthbound: Ness’s Legacy (RM2K) (2002) Demo […]

2022/2/26
阅读更多

7DRL 的准备

Github https://github.com/libtcod 文档在最下面。 教程 https://rogueliketutorials.com/ https://www.youtube.com/watch?v=r47iWInWJp4 http://www.roguebasin.com/index.php?title=Complete_Roguelike_Tutorial,_using_python%2Blibtcod http://www.roguebasin.com/index.php/Complete_roguelike_tutorial_using_C%2B%2B_and_libtcod_-_part_1:_setting_up 准备 pip install libtcod -i http://pypi.douban.com/simple --trusted-host pypi.douban.com

2022/2/22
阅读更多

旧数据

https://cowlevel.net/article/1843757 https://en.wikipedia.org/wiki/Fez_(video_game)#Reception https://bbs.a9vg.com/thread-8755591-1-1.html

2022/2/20
阅读更多

Dairy Dream Jam x 7DRL(7DRL)

https://www.roguelike.club/event2019.html https://www.roguelike.club/event2019.html https://itch.io/jam/dream-diary-jam-5 https://7drl.com/

2022/2/19
阅读更多

邪恶铭刻(wip

https://store.steampowered.com/app/286100/You_Have_to_Win_the_Game/ https://store.steampowered.com/app/405640/Pony_Island/

2022/2/19
阅读更多

Easyrpg 简中的字体 bug

很久之前读过 一篇文章，介绍过亚洲各地区所使用中文字体的不同，各种和制汉字自不必说，甚至同是使用繁体的台湾地区和香港地区，也是有许多细微差别的。 最近在翻译的 y2k 的过程中，汉化组发现，目前 easyrpg 所使用简体字库是有 bug 的，正好我这几天我正在调试中文版本的 ynoproject，需要编译 easyrpg，所以或许可以顺带把这个 bug 给修了。 下面是 y2k 版本更新后更新存档的画面， 可以看出，上面的“所”字和“将”字，明显是和制汉字，并且仔细观察的话，其实上面的文字中同时出现了中文字体和日文字体，分别是日文衬线体和简体中文的宋体， 因为字高不一样，混排在一起十分违和。 再以我 之前 y2k 的存档 举例，可见上面的黑字也是一个和制汉字，举个例子。。。 白井 黒子（しらい くろこ） 不妨再看一些例子，例如赤之世界和怪异症候群， 可见这个 bug 只会出现在 easyrpg 的简体中文中，而使用原版 rpgmaker rtp 打开或者使用 easyrpg 的繁体中文都是正常的。 我们看到这个 bug 只会出现在一些日文和中文中编码相同的汉字中，而对于一些差别更大，日本地区独有的和制汉字，则不会在这些游戏中出现， 观察了一下代码，我判断是 easyrpg 在找到有对应的日文版字体后，就默认用日文汉字显示了，因此只要把这个判断去掉应该就可以了。 目前修复后的分支在这里， https://github.com/lychees/ynoclient 当然我还顺手修了一下之前 ib 软键盘输入不了某个场景密码的 bug。。。 这些汉字的差别十分细微，别说海外社区了，我们自己也很容易忽视这些差别， 在眼下各地区汉字分裂的情况下，还是采用各地的标准为好。

2022/2/14
阅读更多

梦日记多人版 —— 你的梦中，我亦存在

Project Yno.Yumenikki.Info 参考资料 资源来源为一些 wiki 和玩家社区网站： https://community.easyrpg.org/t/compatibility-list/283 https://rpgmaker.net/misaos/ https://yumenikki.info/archives/hasei/ https://wikiwiki.jp/yumenikki-g3/ https://freegame-mugen.jp/tagcloud/RPG%E3%83%84%E3%82%AF%E3%83%BC%E3%83%AB2003_1.html https://www.freem.ne.jp/search/RPG%20%E3%83%84%E3%82%AF%E3%83%BC%E3%83%AB%202003 以及一些作者和译者的主页 https://vgperson.com/ https://sikv.web.fc2.com/ 命名格式 命名格式一律为：[游戏名_版本号_语言_特性] 例如最新的梦2记中文版的访问格式为：https://yno.yumenikki.info/?game=y2k_v0.104g_chs 如果游戏的版本号已经固定，会缺省版本号，只有翻译版本会加上语言，缺省语言的情况则为原版。 《地球冒险》同人 https://yno.yumenikki.info/?game=eb2 https://yno.yumenikki.info/?game=cogdis_v2.0 https://yno.yumenikki.info/?game=mother3andathird 参考资料 – 编译 web 版 – 升级 cpp —- 分割线 —- 剧情 除夕夜，派生群里组织了梦2记在线版的群聚活动。。。（这算是元宇宙的应用吗？） 集合的地点设定在了一处非常难以进入的薰衣草海洋。。。 我和雪梨一组，找了半天连第一幅地图也没有进去。。（对不起，2 记我连云玩家都算不上。。。）、 后来群里的金吼吼说可以当导游带我们一起前往… 于是有了 这次宛如梦幻般的体验。。。 三个人一起穿过图书馆的密道，走过方块世界的迷宫，在楼顶变成魔女飞过遥远的距离，打开电视剧在短波中进入另一段梦境， 最终穿过地下深处的沼泽，历经千辛万苦，终于来到了这处薰衣草池塘。。。其它群友早已等候于此，合影留恋。。。 我不得不说这次带给了我全新的，甚至是震撼的体验。。。（虽说，梦日记实际是描写孤独的游戏。。但这种另类的演绎实在过于迷人） 下线后立刻调查了一下这个梦2记在线版，果然开发并没有多久。。 https://github.com/ynoproject 目前看起来是基于 EasyRPG 提供的网页版，加了一个壳，可以显示其它角色控制的主角， 也就是说，它实际上也不限于梦日记系列。。。果不其然。。有国外的玩家做了 Ib 的版本。。。 https://ynonline.herokuapp.com/play.html?game=ib （虽然 […]

2022/2/6
阅读更多

Haskell 相关

本篇记录一下学习 Haskell 过程中查阅的资料和踩过的坑。 一般来说学习一个新的编程语言都从 Hello World 开始，但是 Haskell 里要展开介绍 IO() 就不得不涉及到 Monad， （不能理解 Monad 就是自函子范畴上的一个幺半群你还想用 Haskell 写出 Hello World ？） 这大概也是 Haskell 的学习曲线比较陡的原因，正因为此 Haskell 里的 Hello World 一般是用阶乘 或者 斐波那契数列， 学完之后就可以开始刷 PE 了，（因为 PE 几乎不用管 IO()、而且可以用暴力算法跑一天）。 学习的目标： – [ ] 理性愉悦。 – [ ] 达成 彩虹小马 成就：在 Codeforces 的一场 Div2 Round 中，使用不同的语言 AC 每一道题。 – […]

2022/1/15
阅读更多

NOI 2021

Day 1 轻重边 P7735 [NOI2021] 轻重边 对于每次操作打一个新的时间戳，用这个时间戳对路径染色，那么。。。 重边数 = 相同颜色的相邻点对数 = 路径长度 – 颜色段数，于是只需要求出颜色段数。 用 [SDOI2011]染色 的代码稍微改改即可。 路径交点 P7736 [NOI2021] 路径交点 LGV 引理 庆典 Luogu P7737 [NOI2021] 庆典 https://djy-juruo.blog.luogu.org/solution-p7737 图论题，算法都不难，但是要拼的东西很多，比较考验底力。。。暴力 Floyd 可以拿 20 分。。 正解先 scc()，然后题目的条件告诉我们可以用树来代替 scc() 后的 dag 去表示可达关系， k=0 的情况，直接在树上用前缀和减减即可，然后 这个题解 告诉我们可以使用虚树来避免讨论 k。。 我们用 atl 里提供的 scc()， 再从 这个题里找来 lca，（用倍增祖先我会 TLE。。） 再从 这个题里找来虚树， […]

2022/1/12
阅读更多

~ 岛娘今天吃什么 ~

[fvplayer id=”1″] \23:00 饥荒/ 邪恶铭刻 – 2022 02 15 15 55 53 – 2022 02 15 17 25 47 – 2022-02-15 21-42-17 – 2022 02 16 02 59 13 Github https://github.com/lychees/ https://competitiveprogramming.info/topcoder/handle/xiaodao Telegram Chanel 小島みなこの競プロ日常 https://t.me/algorithm_daily_of_minako Telegram Group 罗德岛制药 https://t.me/TwilightParliament 岛岛币 投喂地址 https://www.matataki.io/token/22

2022/1/11
阅读更多

NOI 2020

https://kewth.github.io/2020/08/05/NOI2020/ https://kewth.github.io/2020/09/03/NOI2020-%E9%A2%98%E8%A7%A3%E6%8A%A5%E5%91%8A/ Day 1 美食家 Luogu P6772 [NOI2020] 美食家 朴素 DP + 矩阵优化 40 分朴素分十分好拿，考虑到 T 十分大，也很容易想到接下来要矩阵优化。 具体实现，首先这里需要使用广义矩阵乘法维护 dp 状态，这个相信对于熟悉 动态维护树的最大独立集 的小读者来说一定不是什么难题。。。 然后对于美食节这些特殊事件，没有办法放进矩阵里处理，不过美食节数目不是很多，我们可以拉出来单独处理，美食节与美食节之间在用矩阵乘法。 命运 线段树合并必做习题。 时代的眼泪 P6774 [NOI2020] 时代的眼泪 给定一个 1 到 n 的排列，q 次询问，每次给定一个下标区间和一个值域区间求在给定区间内的元素的逆序对数。 很像上个月 abc233 的最后一题，不过区间逆序对没有什么太好的性质，貌似只能分块乱搞。 Day 2 制作菜品 https://www.luogu.com.cn/problem/P6775 01-背包 有 n 种材料，第 i 种材料有 ai 个。现要制作 m 种菜，每种菜恰好使用 k 个材料并且使用至多两种材料。求是否存在方案，如果存在则给出任意一个方案。 保证 […]

2022/1/10
阅读更多

Hello 2022

这场和 Youtube 主播 SecondThread 一个房间，（并且差点碾压了他！） LGM 不过如此 这场掉分的应该都是猜结论失败然后被 D 题拉扯了太多的时间的缘故。。。 传送门 https://codeforces.com/contest/1616 https://t.me/algorithm_daily_of_minako/3222 https://www.facebook.com/dreamoon4/posts/6748183141918539 Problem D. The Winter Hike 给一个 2n x 2n 的矩阵，开始左上角 nxn 的子矩阵有棋子，你需要把这些棋子移动到右下角 nxn 的格子里，支持的操作是 shift 一行 or 一列， 矩阵中有一些障碍，对于每个障碍，你可以花费一个代价删除它，操作没有代价可以任意进行，只要不遇到障碍，问最少花费多少代价满足要求。 结论题，取这 8 个数 + 右下角矩阵的值。 00aa 00aa aa00 aa00 Why？首先直接缩点 Dijkstra 是不够充分的的，反例是下面这种。 000— 00000- 000-0- —000 —000 —000 虽然我们成功的将左上角的材料运输到右下角，但是没有足够的空间去华容道。 有简单的方法判断是否有足够的空间调整，就是只对目标区域的四个角进行缩点。 而这于我们开始所说的结论是等价的。 Problem […]

2022/1/3
阅读更多

Good Bye 2021: 2022 is NEAR

传送门 https://codeforces.com/contest/1616 和 去年一样 。。。今年的 GoodBye Round 的 Pretest 也很强。。。 大家新年快乐啦。。。 Problem D. Keep the Average High 数列选数，要求如果原序列中多于1个连续的全被挑中，则满足平均值大于给定的 x，问最多可以选多少 dp，只要考虑长度为 2、3 的段满足条件即可，其它长度自动满足。 Problem E. Lexicographically Small Enough 给定两个字符串 s, t ，每次可以交换两个相邻字符，问至少几次交换可以使得 s 字典序小于 t。 考察 t[0]，方案一：找小于 t[0] 的字符交换到 s[0] 位置。方案二：找等于 t[0] 的字符交换到 s[0] 位置，之后迭代到下个位置。 每次都贪心的找最靠前的，可以开 26 个 deque 去记录这些位置，同时用树状数组维护删除事件。 Problem F. Tricolor Triangles 给定一个无向图 (n […]

2021/12/30
阅读更多

Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3)

传送门 https://codeforces.com/blog/entry/97795 https://zhuanlan.zhihu.com/p/444714636 这场因为出原题被喷惨了。。。 Problem C : https://po.kattis.com/problems/biblioteket Problem D : https://open.kattis.com/problems/bread | https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0448 Problem F : https://atcoder.jp/contests/arc115/tasks/arc115_e 特别是 F 题的影响最为严重。。。（但是我觉得这个 F 题真的是一个好题啊。。。 Problem D. Yet Another Sorting Problem 给定要给数组。可以对数组进行操作，每次选择三个不同的下标(i, j, k)。 交换这三个位置的数。a[i]移动到a[j]，a[j]移动到a[k]，a[k]移动到a[i]。 问能不能通过若干次操作，让数组有序（非减）。 寻找 invariant 。。。似乎这个三元交换操作不改变逆序对的奇偶性。。 猜想逆序对是偶数一定有解。。。 交了一发上去 WA 了。。。 最后发现没考虑相等的数。。 如果有相等的数，那么一定有解，因为可以拿这个数充当缓存区= =。。 Problem E. Frequency Queries 给定一棵n节点的树，树上每个节点有一个数字（范围1~n）。有q个查询，每个查询给出三个数 v, l, k。 问节点v到根的（最短）路径上的所有数字，出现次数大于等于l次的数字中，出现次数排第k的是什么？（可能有出现次数相同的，这时候输出任意都可） 离线树状数组 + […]

2021/12/16
阅读更多

The 2019 ICPC Asia Nanjing Regional Contest

https://codeforces.com/gym/103466 Problem A. A Hard Problem Problem B. Chessboard 开始以为是培养皿问题。。。 后来发现只能连续的整行 or 整列。。（话说我小时候抄书的时候就喜欢用这种扫描方式。。。） 简单组合数讨论一下即可。 Problem C. Digital Path Problem D. Holes 看起来是挺标准的期望 DP。。。居然是这套题里最难得题？ Problem E. Observation 不会。 https://blog.csdn.net/xym_CSDN/article/details/102906128 Problem F. Paper Grading https://blog.csdn.net/qq_43202683/article/details/104100136 Problem G. Poker Game Problem H. Prince and Princess Problem I. Space Station Problem J. Spy Problem K. Triangle

2021/12/10
阅读更多

Deltix Round, Autumn 2021

https://codeforces.com/contest/1609 https://www.cnblogs.com/qiulyqwq/p/15628985.html https://www.bilibili.com/video/BV1TF41187b3/ 于是成功的在筹办新一轮 CF Round 之前打回黄名了。。。（求轻喷。。。 这场题目中规中矩，想上分还是挺容易的。。。 Problem A. Divide and Multiply 把所有 2 因子收集起来，剩下的数里挑一个最大的乘以这些 2 因子，再加上余下的数即可。 Problem B/E. William the Vigilant/William The Oblivious 这两个放在一起说，给定一个 abc 字符串， 每次修改一个字符，问至少需要几次修改操作，可以使得该串中不存在 “abc” 模式的 子串/子序列。 子串的情况讨论讨论即可。 子序列的情况先解决静态的问题，然后用线段树维护即可。 Problem C. Complex Market Analysis 先筛法做素数判定，然后按照模数分段线性扫描，每次找到素数的时候看两边各有多少个 1。 假设左边和右边分别有 p 个 1 和 q 个 1，那么对答案的贡献就是 (p+1)*(q+1)-1。 Problem D. Social Network 读题鸭梨巨大。。 […]

2021/11/29
阅读更多

AtCoder Beginner Contest 224

在这里输入要转换的内容- https://atcoder.jp/contests/abc224/tasks E. Integers on Grid 类似经典的 POJ 1088. 滑雪。。 不过状态是稀疏的。。用高度划分阶段，维护一下每一行每一列前阶段的最优解，转移就可以优化到 O(1) 了。 F. Problem where +s Separate Digits 给定一个数字串，可以在中间添加若干 + 号， 问所有可能的表达式的和是多少。 比赛时我的做法是，先枚举最后一个加号的位置，写出暴力的 O(n2) dp。。。 然后仔细观察，把转移也优化成 O(1)。。。。 题解给出的方法是，类比期望的线性性。。。去枚举每个字符的贡献。。比上面的做法要好写。。。。 G. Roll or Increment 是非常有趣的题。。让我想起了 PE. 503.. 说有一枚骰子。。投掷完之后可以 d*A 的代价让数字 +d，或者 B 的代价重新投一次.. 问第一次投出 s 时，期望最少多少代价得到 t 显然大于 s 的话一定要重新投，否则要么重新投，要么加。。 和 PE 503 类似。。这个决策的分割点也是具有单调性的。。。 （准确的说。。这个题里是凸性。。所以可以三分决策分割点。。。这样就可以通过了） （然后和 […]

2021/10/26
阅读更多

Facebook Hacker Cup 2021 Round 1

A1. 给定一个 ’01-‘ 组成的字符串 s，设 f(s) 为忽略掉 s 中所有 ‘-‘ 字符后，相邻字符发生变换的次数。 求 f(s)。 扫一遍即可。 A2 统计所有 s 的子串的 f 值。 统计相邻的 ’01’ pair 的贡献即可。 const int N = int(1e6) + 9; char s[N]; int n; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif Rush { RD(n); RS(s); Int z = 0; char lc = '?'; […]

2021/10/21
阅读更多

Facebook Hacker Cup 2021 Round 2

Problem A. 贪心 Problem B. 做法有很多，比赛时用的是线段树合并。 Problem C. 小数据贪心模拟一下，大数据需要用数据结构维护这个贪心过程。 Problem D. String Concatenation 虽然题目叫 String Concatenation，但是是个背包问题，和字符串完全木有关系。 做法是暴力乱搞，乱搞的方法貌似有很多。假设 k 可以无穷大，那么根据鸽巢原理（pigeonhole principle），在 n >= 25 的时候就一定有解，考虑 k 很小，那么也可以根据生日悖论（birthday paradox）可以设计 n <= 1000 的解法。 然后一般情况下再搞一些剪枝，归约到 n <= 1000 以内即可。这种利用生日悖论的题好像以前 gcj 喜欢出。。

2021/10/21
阅读更多

AtCoder Regular Contest 128

https://atcoder.jp/contests/arc128/tasks https://www.bilibili.com/read/cv13612020 https://www.cnblogs.com/stinger/p/15416806.html arc 好难。。。（虽然题面都很简单） A Gold and Silver 著名的套利系列问题，但是这个题应该是里面最简单的一类，可以贪心， 扫一遍就行了。 B Balls of Three Colors 讨论一下最后保留哪个，然后就很容易了。 C Max Dot 先不考虑 𝑚 的限制。。。 考虑 n=2 的情况，如果 a1 < a2 的情况，显然资源全部都给 a2，否则只能对半分。 考虑 n 个数的情况，一定是 0 0 x x x x 这种 pattern，均分给一个后缀。 题解用的是调整法，也不难用归纳法证明，我们可以把后面的后缀合并起来看成是一个数，权值用平均值代替， 然后沿用 n=2 的方法即可。 我们枚举后缀，得到的 x 有可能不满足 m 的限制。 这个时候我们只要先把这些后缀填上 m，然后就可以递归到更短且 s 更小的问题。 […]

2021/10/20
阅读更多

Codeforces Round #749

又是 一轮构造 Round。。。 要想上分必须要瞬秒掉 E、F。。。 https://codeforces.com/contest/1586 https://zhuanlan.zhihu.com/p/422490422 Problem E. Moment of Bloom 构造。 任取一颗生成树，然后直接树上暴力拉路径即可，不需要写 lca = =。 Problem F. Defender of Childhood Dreams 构造。 假设有 c 种颜色，那么最大能支持 c^k 个点，答案就是 ceil(log(n,k))。 如何构造？每次将当前点集，按照顺序拆成 k 组，组外部之间全部连颜色 c，内部不再使用颜色 c，递归构造下去即可。 实现起来貌似只要一行，不需要憨憨的去写递归。。。 Problem G. Omkar and Time Travel 题目背景是命运石之门！ 感觉有点像 Codeforces Global Round 15 的 F 啊。。。 我们不妨用那个题的语言重新叙述这个题，看看有什么不同。 初始所里的传送门都是 active 的 传送之后会让传送位置在目标点之后的传送门更新为 […]

2021/10/19
阅读更多

动态dp

https://immortalco.blog.uoj.ac/blog/2625 https://darkleafin.github.io/2018/12/07/%E6%B5%85%E8%B0%88%E5%8A%A8%E6%80%81DP/

2021/10/18
阅读更多

Facebook Hacker Cup 2021 Round 3

果然记错时间了。。靠。。 没人提醒真不行。。。真的得提前丢 calendar 里。。。、 不过这场貌似是手速 round 、、、我肯定没戏。。。 代码 A. 有点类似上次 atcoder 那个维护区间的题， 不过相比 set，这个题用 dsu 维护更好。 B. 用线段树维护 dp。。 蛋疼的是这个题里的还有可能从外部绕回来。。。 虽然大概只要加一下二分查找，不过代码量增加了好多。。。。 一不小心就写疵了。。。 C. DP 。。不会。。 D. 貌似需要树链剖分。。。囧

2021/10/12
阅读更多

Codeforces Round #747

感觉智商被爆了。。F 是非常简单的构造题，代码量非常短，所以这场要上分，必须要能秒 F。。。 https://codeforces.com/contest/1594 https://zhuanlan.zhihu.com/p/419250842 首先如果 s 足够大，那么肯定可以做到不粘锅。。。 不妨考虑 k=1，大概可以鸽巢原理。。 2 2 2 2 2 只要 s >= 2n 就可以不粘。 再看一般情况，我们考察前缀和，只要构造出不存在两项差等于 k 的情况即可。 上面的 case 就是。。 [0][2k][4k]... 一般情况下最小的构造，大概长这样… [0,K-1][2K,3K-1][d2k,d2k+r]... d = n/k, r = n%k。 最后别忘了特判 s==k 的情况，这种情况下上面的构造可能只有一个区间， 然后虽然 s>=ss，但是因为前面有个固定的 0，还是会粘上。 bool ok() { LL s, n, k; RD(s,n,k); if (s == k) return 1; […]

2021/10/11
阅读更多

ICPC World Final 2020

传送门 提交地址 因为疫情原因，今年去年的 Final Adpot 了「宁理规则」，变成了 15 个题三人三机。。。 预感趣味性和策略性可能会降低好多，虽然 CF 上有红名大佬出来倡议反对这个规则，不过好像并不会改变什么。。。（BTW，结果这个题主本届 World Final 直接 win 了，可见他是真的关心这个比赛。。。） 事实也确实如此，感觉题目难度也比前几天的莫斯科邀请赛降低了好多。。变成手速 round 了。。。 (据说这场 8 个题才算签到。。可怕。。。) 以下按照我认为的难度排序。。。 Problem C. Domes 半平面交模板题。 Problem E. Landscape Generator 区间加减等差数列，单点询问。 显然可以线段树，不过这种只在最后询问一次的话用差分+部分和技巧就可以，签到题！ Problem G. Opportunity Cost 假设没有 max 0 这个操作，那么可以 O(n) 扫过去。 进一步观察，我们枚举 shadow 掉哪些维即可，最大值不变。 Problem O. Which Planet is This?! 分别处理每个纬度，差分之后转换成字符串问题，KMP 出所有匹配位置得到所有合法位移。 判断每个纬度的合法位移交集是否为空即可，这种看起来时几何的题最后发现可以用字符串算法通过的题目还是很有趣的，参见 […]

2021/10/6
阅读更多

。。。

$$\sum_{n=0}^{\infty}a_nx^n$$

2021/9/29
阅读更多

temp

民事起诉状 原告：唐飞虎，男，1991年11月12日出生，汉族，住安徽省合肥市瑶海区铜陵新村24栋205室，联系方式：15669978877。 被告：刘银山，男，1986年1月1日出生，汉族，住河南省洛阳市中州东路恒大绿洲14栋2单元104号。 诉讼请求： 1. 判令被告交还委托托管的所有计算设备。 2. 诉讼费由被告承担。 事实与理由： 被告2021年5月19日，与原告签订一份委托托管协议，并在上海市长宁区田园别墅111室签订合同一张，双方互相向对方抵押价值100万美金等价的资产，其中甲方向乙方托管100万美金等值矿机，乙方向甲方抵押价值100万美金的虚拟货币，抵押一周后，乙方即要求赎回其抵押的虚拟货币，但乙方收回虚拟货币后，未按合同要求归还甲方委托托管的等值计算设备，期间原告多次向被告索要机器未果，并拒绝归还在乙方公司所签署的相关合同。原告为维护自身合法权益，故诉至法院，请求法院支持原告诉请。 此致，洛阳市中级人民法院 附：本诉状副本 1份 申请人：唐飞虎 2021年9月27日

2021/9/27
阅读更多

Note on 多项式

Codeforces, hos.lyric 的多项式模板 Github, hos.lyric 的多项式模板 NaCly_Fish, 学习笔记：多项式全家桶 题单 菜鸡 Karry5307 的多项式题单 Lyric 的 Luogu 切题记录 P3706 [SDOI2017]硬币游戏 概率生成函数 字典 DFT：离散傅里叶变换 IDFT：离散傅里叶逆变换 FFT：A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). NTT：快速数论变换 MTT：快速毛爷爷变换，毛爷爷对 FFT 的改进以解决任意模数 FWT：快速沃尔什变换 FMT：快速莫比乌斯变换 背包问题 Luogu P4389 付公主的背包 https://www.luogu.com.cn/problem/P5339 […]

2021/9/22
阅读更多

树形背包

Luogu P2014 [CTSC1997]选课 Luogu U53204 【数据加强版】选课 ouuan的博客 树上背包的上下界优化 暴力枚举 O(n3) const int M = int(3e2) + 9; const int N = int(3e2) + 9; int dp[N][M], cost[N], value[N]; VI adj[N]; int n, m; void dfs(int u = 0) { FLC(dp[u], 0x80); DWN_1(i, m, cost[u]) dp[u][i] = value[u]; for (auto v: adj[u]) { dfs(v); DWN_1(i, m, […]

2021/9/19
阅读更多

后缀自动机构造后缀数组

https://uoj.ac/submission/507635 https://blog.csdn.net/BlackJack_/article/details/80657263

2021/9/15
阅读更多

树上斜率dp

BZOJ 1767. [Ceoi2009]harbingers | https://vjudge.net/problem/Z_trening-749 Luogu P2305. [NOI2014] 购票 http://acm.hdu.edu.cn/showproblem.php?pid=5956 https://codeforces.com/problemset/problem/1179/D Luogu P4360. [CEOI2004]锯木厂选址

2021/9/13
阅读更多

BZOJ 3165. [Heoi2013]Segment

记一下模板的写法。。。 做法一：李超树 https://github.com/lychees/ACM-Training/tree/master/Archive/BZOJ/3165.%20%5BHeoi2013%5DSegment 做法二：线段树套平衡树 因为李超树的大流行，树套树反而没人再去写了。。。 const int N = int(1e5) + 9; #define ll double struct Line { mutable ll k, b, p; int id; Line (ll k = 0, ll b = 0, int id = 0):k(k),b(b),id(id) { p = 0; } ll y(ll x) const {return k*x + b;} bool operator<(const Line& o) […]

2021/9/11
阅读更多

BZOJ 3533. [Sdoi2014]向量集

This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters /* This code has been written by MinakoKojima, feel free to ask me question. […]

2021/9/11
阅读更多

Educational Codeforces Round 113

B C 比赛时靠着直觉改对了样例直接交了。。。 感觉代码好像有 bug D 肯定比 [SDOI2009]虔诚的墓主人 简单，只要横纵坐标分别统计位于节点中间的点有多少个即可。 E meet-in-middle

2021/9/9
阅读更多

SPOJ COT6. Cut on a tree

https://www.spoj.com/problems/COT6/ https://github.com/lychees/ACM-Training/tree/master/Archive/Spoj/COT%20%E7%B3%BB%E5%88%97/COT6 前排膜拜主席。。。 做了好几天。。总算搞定了。。 算法一：李超线段树 + 线段树合并 DP 结构和 COT3 一样，方程和 Cash 一样，都是动态维护凸壳，询问与某个向量的点积的最小值。。。 后来我系统的学习了一下 线段树合并， 然后发现有一个题的做法是李超线段树 + 线段树合并，来搞树上 dp。。。 这个题的方程和那个题差不多。。。询问向量都是 (x, 1)，所以用 kx+b 来搞更方便。。。 可以预处理出所有的 sw，来做离散化，然后打标记只要整体平移 b，不会影响线段树的结构。。。 然后就没有然后了。。。复杂度 O(nlog2n)。。。 经过这个题我们发现。。线性分段函数极值 和 动态凸包 问题是等价的。。 根据情况可以互相转换。。看怎么写好写。。。 似乎还有一种 O(nlogn) 的做法。。。dfs 序 + cdq 分治。。。（尝试了一下失败了，原因是 cdq 分治两边的状态会互相依赖。。。） 晚上再试试。。。 我发现之前的模板里有一个 bug 的地方（我靠居然连 COT6 的样例都过不去。。） if (T[x].y(ml) > t.y(ml) || T[x].y(mr) […]

2021/9/8
阅读更多

SPOJ COT3

https://www.spoj.com/problems/COT3/ https://blog.csdn.net/huzecong/article/details/9142121 https://my.oschina.net/u/4321213/blog/3694105 非常 nice 的题目… 同时考察组合博弈和线段树合并。。。 不妨先考虑简单的问题，如何输出第一步的方案。 我们枚举第一步落在哪里，那么形成的黑链会把原树划分为若干子树，每组子树相互独立，于是变成游戏的和， 根据 SG 定理，我们只要能求出每个节点为根的 sg 值即可。 void gao(int u = 1, int p = -1, int SG = 0) { // 递归进来的 SG 表示子树外的游戏 for (auto v: adj[u]) if (v != p) SG ^= sg[v]; // 再 xor 上子树内的游戏 if (!col[u] && !SG) Z.PB(u); for (auto v: […]

2021/9/8
阅读更多

线段树合并

传送门 HJT，线段树合并，不为人知的实用技巧 题单，线段树合并：从入门到精通 Merge 操作是可持久化结构里的一个常见操作（在 Fhq-Treap 里、甚至是最基本的操作！）， 而线段树又以其灵活的懒标记系统，绝对是算法竞赛里最最灵活，最最实用的数据结构，个人认为，能否灵活的使用线段树是区分「菜鸡」和「大牛」的最好 Critiria 。。。 一旦掌握「线段树合并」这一进阶搞法，就又可以无脑的解决一系列树上统计问题、优化树形 DP 的转移等等，而且时间复杂度通常比替代算法更优！ 优势：泛用性强，在线算法，时间复杂度优秀 劣势：烧内存，偶尔需要使用一些技巧优化空间 模板题 [POI2011]ROT-Tree Rotations 主席原版文献里的母题，这个题里使用线段树合并的优势就非常明显了。。。 https://www.luogu.com.cn/record/57421680 CF600E Lomsat gelral https://codeforces.com/contest/600/submission/127804505 CodeForces #121 C. Fools and Roads 先来个热身，这个题记得 当年 只会动态树，于是比赛时在怒秀动态树，然后被卡到比赛结束。。。 赛后看了一下 shi 哥树上差分轻松 dfs 的做法，恍然大悟，所以印象深刻。。。 当然其实动态树秀成功了就没任何问题好吧！ 不过最好的做法绝对还是树上差分 + dfs()。 [Vani有约会]雨天的尾巴 /【模板】线段树合并 131 C 那个题等于这个题 z always = 1 弱化。。。 所以还是可以做树上差分。。。 只有需要用支持求最大值的数据结构维护。。 平衡树启发式合并、线段树合并什么的显然都行。 […]

2021/8/31
阅读更多

无规则游戏：阿富汗屡被中断的历史

“2001年，本·拉登离奇失踪，阿富汗的这场反恐战争似乎失去了一个胜利标志。当时，塔利班已经垮台，喀布尔也被攻占，唯有逮捕本·拉登，消灭“基地”组织，才算真正的战果。布什的对手不会主动说一声“我们投降了”，因为其对手并非一个国家、组织或固定实体，美军是要和一种环境战斗，与一种意识形态交锋。这种意识形态源自贫困、武力、仇恨、羞辱与侵略，并且已经深入伊斯兰世界的土壤之中。美军每发动一次镇压行动，阿富汗人被羞辱的感觉就会增加，仇恨的怒火也会更加旺盛。美国人的胜利越多，战争就越激烈；战争越激烈，怒火也会越旺盛。” ——

2021/8/29
阅读更多

Codeforces Round #741

传送门 https://codeforces.com/contest/1562 靠字符串题涨了点分 > <、 Problem B. Scenes From a Memory 给定一个不包含数字 0 的数，要求保留最少的数字，使得最后不是素数，有多解任意输出一组即可，保证一定有解。 先写个保留数字尽可能少的爆搜，然后果断猜一下最后保留的数字不会太多。。。 具体的话，就是如果存在 1 4 6 8 9 那么显然就是 1 位，剩下的只有。。 2 3 5 7 。。那么不能出现重复的数，否则可以整除 11，那么鸽巢一下方案已经非常少了。 最后结论貌似是保留 2 位即可。。。 当然用上面的爆搜的话，其实不用仔细去推，随便给个差不多的上界直接爆过去即可。。。 Problem C. Rings 脑经急转弯。 Problem E. Rescue Niwen! 挺傻的一眼题。。。套个 sa 模板就可以写 dp 了，中间类似求重复子串，要去掉 lcp。 LL z = 0; REP_1(i, n) { […]

2021/8/28
阅读更多

Codeforces Round #740

传送门 https://codeforces.com/contest/1558 久违的 Tourist round… 因为 B 题没做出来，直接又跌成蓝名。。。 Problem B. Up the Strip 给定下面的递推公式： $f(x) = \sum \limits_{y=1}^{x-1} f(x-y) + \sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$ f(1) = 1，求 f(n)。 const int N = int(4e6) + 9; Int f[N], s[N]; int n; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(n, MOD); […]

2021/8/28
阅读更多

GameCreator 存储相关

var saveData = [Game.getSaveData(), now, Game.currentScene.id, worldSaveData, playerVarialbeData, playerData, SinglePlayerGame.sceneDatas, audioInfo, triggerEventData, sceneObjectData, gameCommandData, sceneStatus, packageCustomData, needLoadUIs]; saveData = ObjectUtils.depthClone(saveData);

2021/8/20
阅读更多

各种谱子

https://zh.wikipedia.org/wiki/%E8%8C%89%E8%8E%89%E8%8A%B1_(%E6%B0%91%E6%AD%8C) 茉莉花 简单版 https://www.bilibili.com/video/BV1Xy4y1x7M5 复杂版 https://www.bilibili.com/video/BV1NB4y1M7ym https://www.bilibili.com/video/BV1s54y1p7YS https://www.bilibili.com/video/BV1YA411x7aq

2021/8/12
阅读更多

Codeforces Round #737 (Div. 2)

传送门 https://codeforces.com/contest/1557 说着要回 Div1，结果分越来越低了。。。 上紫名好难啊。。。。（暴风哭泣） Problem B. Moamen and k-subarrays 给定一个数组，拆成 k 个 子段，再重新排序，问这样是否能将这个数组排序，保证数字不相同。 然后开始默认需要拆 n 份，然后看相邻位置如果再排序后也相邻就让需要拆的份数 -1. Problem C. Moamen and XOR 给定 n,k 问有多少组长度为 n 的数组 a，满足 && 和大于等于 xor 和。(ai <= 2^k) 对 n 分奇偶讨论即可，比赛的时候对幂次取模结果 debug 了好久不能更蠢。。。 Problem D. Ezzat and Grid 给定一个 01 矩阵，问至少删掉多少行，使得相邻行 至少再某一列都有 1。 对于每一行，我们向下连边，这个东西显然是一个 dag，dp 求最长链即可。 因为是求最长链，可以对图可以有所简化，将边的规模缩小为 O(n)。 […]

2021/8/11
阅读更多

GameCreator 自动生成行走图

const fs = require('fs'); function gen(png, target, offset_x = 0, offset_y= 0, w = 32, h = 32) { let t; let json = JSON.parse(fs.readFileSync('avatar5.json', 'utf8')); json["picUrls"] = ["asset/image/_RM/VA/Characters/" + png + ".png"]; t = json["actionListArr"][0]["frameImageInfo"]; let ox = offset_x*(w*3); let oy = offset_y*(h*4); for (let i=0;i<4;++i) { t[i][0]["rect"][0] = -(w*1+ox); t[i][0]["rect"][1] = -(h*i+oy); t[i][0]["rect"][2] […]

2021/8/9
阅读更多

伊莎贝拉的奇幻历险

PC 端 测试服 地址 (可能领先数个版本) PC 端 Demo 地址 移动端 Demo 地址 Github 地址 网页版大航海时代 的 Demo 已经开发到一个段落，目前还只完成了生成大地图和进出港口的功能，先写个文章总结一下，顺便大力的吐槽一下 GameCreator … 其实上周 ChinaJoy 期间我已经吐槽过一遍了，本来还打算这周直接驻到神炎科技公司里去加一下速，不过很快疫情开始复苏，原版计划参加的展会和活动都陆续取消或转移到线上， 我也暂时滚回家里继续开启家里蹲模式了起来。 剧本相关 创作背景 学生时代在我的脑海中利用上课走神的间隙，大概 yy 出过三个剧本。 第一个是《红龙》，介绍一个被收养的龙族末裔少女，在觉醒力量之后所面临的抉择的故事。 第二个是《海之歌》，介绍一个具有魔法天赋的少女，在失去了自身的力量之后，在伙伴们的帮助下，重新走出阴影的故事。 第三个就是。。。。这个类似大航海时代 OL 同人的东西，虽然这个故事其实没有一个完整的故事脉络，大概只有两个少女在海上冒险的故事集。。。 很久很久以前 Vijos 的 岛儿生日模拟赛 大概是这个故事集里面的一些片段。 总之大概就是少女之间一边搞姬一边不断探索世界增长见闻的轻松的故事。。。 第一章的主线大概是帮助某 异国 少女还乡。。。 引言 伊比利亚地方， 葡萄牙王国的辛特拉山的山麓里，住着一个少女， 少女的名字是 伊莎贝拉。 伊莎贝拉致力于研究和翻译古代地中海文明的文献，日复一日的工作着。 那样平凡的的日常，因为这一天的事情而改变了 … 第一幕：启航 首先还是致敬大航海时代2，去里斯本找公爵。。。 因为 waifulabs […]

2021/8/7
阅读更多

Codeforces Global Round 15

传送门 https://codeforces.com/contest/1552 Problem C. 给定一个圆环，初始已经连了一些线段，要求连剩下的线段，问最优情况下，最后总交点最多是多少。 不考虑已经连的线段，对于剩下的我们按照最优情况 1234..1234.. 这样连就行。。 最后把已经连的拉进来一起统计即可。 btw，圆周上均匀分布的 n 个点互相连线可将圆分为多少块？ Problem D. 给定一个长度为 n 的序列 a，问是否可以构造一个长度同样为 n 的序列 b，使得 a 中的每个元素都是 b 中某两个元素的差。 n <= 10 Problem E. Colors and Intervals 给 n 种颜色，初始时给长度为 n*k 个位置染色，使得每种颜色恰好出现 k 次。 求构造 n 组区间的方案，满足对于每种颜色，都有一组区间的端点是这种颜色。 且，不存在某个位置，使得被区间覆盖超过 \ceil{n, k-1} 次。 (n, k <= 100) 贪心？显然我们总是选择那些尽可能小的区间，因此对于每种颜色，我们只需要考虑 k-1 种相邻的区间即可。 我们按照所有区间大小排序来依次选择？很遗憾这样是错的。但是稍微改改，按照每个区间的右端点来排序就对了。 […]

2021/7/26
阅读更多

AtCoder Regular Contest 124

传送门 https://atcoder.jp/contests/arc124/tasks Problem E. Pass to Next Problem F. Chance Meeting

2021/7/26
阅读更多

AtCoder Beginner Contest 211

传送门 https://atcoder.jp/contests/abc211/tasks Problem E. Red Polyomino 插头 dp 模板题，用 大字典里染色模型 的例子稍微改改就能过。 不过这个题 k 范围比较小，极限数据答案也才 64678，所以标程貌似期望你 dfs() 过去。 Problem F. Rectilinear Polygons 可以离线。树状数组即可。 注意讨论输入顺时针和逆时针两种情况。

2021/7/26
阅读更多

UOJ #608. 【UR #20】机器蚤分组

题意 https://uoj.ac/problem/608 给定一个字符串 T，每次询问一个子串 T[l,r]，返回其最长重复子串的长度。 做法 证明？参考 官方题解。 我们来讨论怎么用 SAM 搞子串的重复子串。 首先回忆怎么用 SAM 求最长重复子串。 直接返回 fail 树上非叶子节点的 len[u] 就好。 再考虑怎么求某个前缀 T[1,r] 的最长重复子串。 我们考虑离线，按照 r 端点从小到大排序， 按照顺序每次在 fail 树上找到前缀所对应的叶子节点， 往根节点染色即可。用染色路径上第一个碰到的节点的 len 的长度更新答案。 因为每个节点只会被染色一次，所以暴力染色即可。 最后考虑一般情况 T[l,r]，我们显然需要对染色进行区分， 我们希望每个状态越晚被染色越好，因为越晚，它可能对答案的贡献就越长。 我们不妨画一下示意图。。考虑下面的情况。。考虑到时刻 r 的时候经过节点 u。 u 历史上在时点 l1 和 l2 都被染色过，且 len[u] = 4，那么有： 设 l1 < l2 < r。 —l1, […]

2021/7/12
阅读更多

Atcoder 算法库

Atcoder 算法库（ACL） 出了快一年了，一直没仔细看，这两天写 《天才算法少女》 的主线剧情，正好复习一下这个。不过这玩意更新的着实挺慢的，还没我的 Template 算法多。。。不过至少可以和 rng_58 学习一下怎么写 test 。。。 首先讲一下怎么像 STL 一样加入 cpp 的默认头文件，方法当然是编辑编译器的 Search directories。这个库结构非常简单，对于不支持 ACL 的 OJ，估计也可以手动展开一下。 例题 为了推广这个库，rng_58 还准备了两场 ACL contest，用来测试模板。当然这个东西的适用范围还有待观察，毕竟模板的缺点是不能进去魔改，最典型的缺陷可能就是无法给 std::set<int> 里的二叉树节点加卫星数据 size 以实现求第 kth 大这种实用操作。。。？。。。（比如需要加卫星数据的并查集可能也没法搞了） A – Disjoint Set Union 并查集 – https://vjudge.net/problem/AtCoder-abc181_f B – Fenwick Tree 树状数组 C – Floor Sum 等差数列每一项除以 M 下取整的和。（这玩意居然也需要进模板？） $$\sum_{i = 0}^{N […]

2021/6/30
阅读更多

Google Code Jam 2015 Round2

http://dreamoon4.blogspot.com/2015/05/2015-google-code-jam-round-2.html https://codingcompetitions.withgoogle.com/codejam/round/0000000000433651 Problem A 简单扫一遍，对每个箭头，上下左右扫描，如果有孤立的结点那么显然无解。否则如果该箭头不指向其他箭头，那么答案 +=1。 const int N = int(1e2) + 9; char Map[N][N]; int n, m; bool impossible(int x, int y) { for (int i=0;i<n;++i) if="" (i="" !="x" &&="" map[i][y]="" )="" return="" 0;="" for="" (int="" i="0;i<m;++i)" map[x][i]="" 1;="" }="" bool="" to_edge(int="" x,="" int="" y)="" {="" (map[x][y]="=" '^')="" (map[i][y]="" 'v')="" '<')="" (map[x][i]="" '="">') { […]

2021/6/1
阅读更多

独立之光梦幻主机工作坊 Ep.1 —— Pico-8 第一次开发就上手

Pico-8 是由 Lexaloffle Games 创建的一个虚拟机和游戏引擎。它旨在模仿「幻想中的视频游戏机」，通过模拟1980年代前后视频游戏机的苛刻硬件限制，以刺激人们在制作游戏时的创造力和智慧，避免被现代工具和机器的许多可能性所淹没。这样的设计也使 Pico-8 游戏具有独特的外观和感觉。正是因为 这样的设计，Pico-8 游戏适合小型开发团队验证游戏原型，也适合用来参加 Game Jam，也是用来进行游戏开发教学的极好工具。 为该系统发布的著名游戏的原型包括《Celeste》、《Baba is you》等，它们都作为 Game Jam 的一部分创作的。 Pico-8 目前依然是社区最大的 Fantasy Console，Pico-8 的成功也使得坊间出现了一组 Fantasy Console 的家族，其中包含： – TIC-80 – Tiny Computer, 支持 HTML 5, Windows, Linux 32/64bit, Android & MacOSX 等多种平台。 – PicoLove – Pico-8 的 LÖVE 语言重制。 – LIKO-12 – 使用 LÖVE 语言重制的拥有 96kb RAM […]

2021/4/20
阅读更多

回国小记

伸手党 回国的航班上想找点书读一读打发一下无聊的飞行时间，第一个想到的就是跟进一下 TAOCP 写完了没有，然后赫然发现前段时间找到的那个棒棒的列有最新 TAOCP 小册子的网站居然 404 了。于是正好这几天在和 doc 交流 pokemon go，感觉一定会得到好的建议，于是他很快就丢过来两本。 有个简单的几何书，还有个博弈论的书 你选一个？ 这个简单的几何书我一看书名人就傻了，直接 pass。 后者还是能看进去的。。。 点进去初看怎么感觉行文风格有点接近 TAOCP 和稳操胜券。。。然后发现作者果然是 Conway。。。 后来意识到原来这本就是 ONAG。。On Numbers and Games (ONAG)。 是稳操胜券的姊妹篇。。。 大概 ONAG 和稳操胜券的关系。。有点像是。。 HTSI 和 数学与猜想。。（刚好后者也是两卷）。。 On Numbers and Games ONAG 这本书在讲述的其实就是 surreal numbers， 众所周知 Knuth 非常喜欢喜欢 surreal numbers，为此还专门写了本奇怪的小说。。 我高一的时候当做睡前读物看过一遍。。但是显然没读懂。。。 原来正确的姿势是先读 ONAG 啊。。。 当然在成书的时候，还没有 Surreal numbers 这个名字。 […]

2021/2/8
阅读更多

回國的注意事項

ごめん ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ ↵ […]

2021/2/6
阅读更多

2020 年终总结

TBD 写书 DeFi

2020/12/31
阅读更多

BZOJ 4025. 二分图

BZOJ 4025. 二分图 DarkBZOJ 传送门 https://www.cnblogs.com/ZeonfaiHo/p/7502056.html 题意 给定一个 n 个点, m 条边的无向图, 每条边在一定时间范围内存在. 要你判断每个时间点这张图是否为二分图。(n ≤ 1e5，m≤2e5) 题解 我们可以用 Link-Cut Tree 离线的维护图的连通性，方法是我们把图当成树来处理，维护出路径上最脆弱的边（也就是最早消失的边）即可，当新插入的边连接的两个点已经处在一个连通分量时，如果新的边更加健康，我们就去替换掉那条边，关于 Link-Cut Ttre 维护路径最值的操作，参考 HDU 4010。 （这好像其实也就是 Link-Cut Tree 最正经的用途之，优化网络流！） 回到这个题，我们只需要再维护一下路径的 size，判断一下是否有奇数个点（或者偶数条边）即可，由于现在考察的对象既有边又有点，还有换根操作，着实容易写错，干脆的把原图中的边也放进 Link-Cut Tree 里去维护。 代码。

2020/7/29
阅读更多

BOI 2020

BOI 2020 Day 1 传送门 HackMD 竞プロ日常 Problem A. Colors 题意 交互式问题，给定 n，每次你可以将头发染成 1-n 中间的一个数字，如果相邻两次的数字差的绝对值 >= C，那么男朋友会注意，返回 1，否则返回 0。每个颜色只能用一次，用尽可能少的询问找到 C。 题解 很优雅的倍增构造。 Problem B. Mixture 题意 动态维护若干瓶调味料，每瓶调味料中装有一定质量的 盐，胡椒与大蒜 的混合物，给定美食家最喜欢的调味料的组成，每次询问，可以增加一瓶新的调味料或者删除一瓶之前添加过的调味料，返回至少需要几瓶可以混合出美食家最喜欢的口味。 题解 不会。 Problem C. Joker 题意 给定一张有 n 个点 m 条边的无向图，每次询问给出一个区间 [L, R]，问是否存在奇环，使得环中不包含区间中的点。 题解 是否存在奇环，等价于二分图判定。静态可以 dfs，动态的话可以 dsu，最后外面套一层莫队算法即可。 当然也可以直接用 lct！ 对于删除 [l, r] 区间的边，我们可以用类似破环为链的方法，转化为每次询问保留 (r, l+m) 区间的边，显然边越少越容易合法，满足单调性。我们按照时间顺序依次插入所有边，用 […]

2020/7/28
阅读更多

BZOJ 2125: 最短路

BZOJ | Luogu https://cmxrynp.github.io/2018/10/29/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF/ https://blog.csdn.net/LPA20020220/article/details/88887231 题意 给你一个有 n 个点和 m 条边的仙人掌图，和 q 组询问， 每次询问两个点之间的最短路。 题解 圆方树 const int N = int(2e4) + 9, LV = 15; VII adj[N], adjj[N]; int dfn[N], low[N], tt, sta[N], top; int fa[LV][N], dep[N], D[N], DD[N], L[N]; int n, nn; inline int move_up(int x, int t){ for (int lv=0;t;++lv,t>>=1) if (t&1) […]

2020/7/23
阅读更多