Sophonの博客

题意简述 不含前导零且相邻两个数字之差至少为 \(2\) 的正整数被称为 windy 数。windy 想知道，在 \(a\) 和 \(b\) 之间，包括 \(a\) 和 \(b\) ，总共有多少个 windy 数？ 题目分析 数位DP模板题 定义状态 \(dp_{i, j}\) 为长度为 \(i\) 的windy数中，最高位为 \(j\) 的数的数目。 状态转移方程也很容易得到，可以直接从前一位转移过来： \[dp_{i, j} = \sum dp_{i - 1, k} (|j - k| \geq 2)\] 主要的难点是在计算 \(1\) 到 \(n\) 之间的 windy 数，这可以分为几个步骤处理。 第一步，求出所有长度小于等于 \(len - 1\) （\(len\) 为 \(n\) 的长度）的，以 \(1\) ~ \(9\) 为最高位的 windy 数的总数。 第二步，求出所有长度为 \(len\)，最高位小于 \(n\) 的最高位的 windy 数的总数。 第三步，求出所有长度为 \(len\)，最高位等于 \(n\) 的最高位的 windy 数的总数。这一步是最难想的，需要 ...

题意简述 给定 \(n\) 个单词，将这 \(n\) 个单词从前往后拼接在一起，若相邻两个单词的后缀和前缀相同则将其重合在一起。 如输入 sample please ease in out，sample 与 please 拼接得 samplease，samplease 与 ease 拼接仍得 samplease，最终得 sampleaseinout 题目分析 题目的关键在于求出两个字符串之间的最长公共部分，即相等的前缀与后缀。这很容易让人联想到 KMP 的 \(next\) 数组，它的定义是一个字符串的前缀的最长的相同的前缀与后缀的长度，\(next[len - 1]\) 的定义就是这个字符串的最长的相同的前缀与后缀的长度。 因此，对于字符串 \(s1\) 和 \(s2\)，我们只需要将 \(s2\) 拼接在 \(s1\) 前面，例如将 sample 与 please 拼接为 pleasesample，再求出这个字符串的 \(next[len - 1]\) 等于 \(2\)，就可以简单地得到公共部分为 ple，再从 \(2\) 开始截取 please 的后半部分 ease 拼接到 ...

题意简述 给定一颗\(N\)个节点的树，求树上长度为\(K\)的路径的数量 输入 第一行两个数字\(N\)，\(K\)，如题意 接下来的\(N−1\)行中，每行两个整数\(u,v\)表示一条树边\((u,v)\) 输出 一个整数\(ans\)，如题意 数据范围 \(1 \leq N \leq 50000\) \(1 \leq K \leq 500\) 题目分析 虽然此题可以看出是个点分治模板，但由于\(K\)的范围较小（小于等于\(500\)），所以树形DP也可以解决这道题 定义状态\(f_{u,i}\)为从\(u\)开始的路径中长度为\(i\)的路径的数量，可以很容易得出状态转移方程 \[f_{u, i} = \sum_{v \in son_u} f_{v, i - 1}\] 回到题目本身，题目中要求我们找出所有长度为\(K\)的路径 以\(u\)为根节点考虑，可以将所有的路径分为两种：经过点\(u\)的和不经过点\(u\)的 对于后者，可以直接递归处理；对于前者，我们可以以点\(u\)将其分为两条路径，两条路径的长度和为\(K\)。所以，根据乘法原理，我们只需累加f[v][i] * ...

题意简述 给出\(n\)个单词，统计每个单词在全体单词（包括自身）中的出现次数 题目分析 对多个模式串进行匹配，求每个模式串的出现次数，显然是AC自动机模版题 本题与模版的区别在于，本题中单词可能会有重复，因此要用一个\(cnt\)数组记录\(Trie\)树上每个节点被覆盖了几次，再用一个\(vis\)数组记录当前节点是否已经被累加过了 如果当前节点\(i\)还没有被累加过（\(vis_i = false\)），就将它往上能跳到的节点都加上\(cnt_i\)，扫完后再将\(vis_i\)变为\(true\) 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include<bits/stdc++.h>using namespace std;const int MAXN = 1000000 + 5;const int MAXM = 20 ...

再不更新这里都长草了 前置知识 KMP Trie树 前言 AC自动机是一个字符串匹配算法，与KMP的区别在于，AC自动机可以用\(O(\sum |s_i| + |S|)\)的复杂度在文本串中同时查找多个模式串，例如这道题 对于初学者 就是我 而言，可以简单地将AC自动机理解为KMP + Trie树，整个算法分为三步： 将所有的模式串建成一颗Trie树 求出Trie树上每一个节点的失配指针（fail）（类似KMP的next） 将文本串在Trie树上进行匹配 算法过程 建立Trie 这一步和普通的字典树一样，不解释 12345678910void insert(string& s) { int p = 0; for(int i = 0; i < s.length(); i++) { if(t[p][s[i] - 'a'] == 0) { t[p][s[i] - 'a'] = ++tot; } p = t[p][s[i] - 'a']; } num[p ...

郑重声明：本作品为奇幻小说，不涉及也不参与任何现实中的意识形态纠纷。对于作品中的任何魔怔设定，本人一概不负任何责任。 起源 这个系列来源于@Schwarzkopf_Henkal 的脑洞： 然后我和SH就在犇犇里有一句没一句地语C 简介 借助高度发达的魔法技术，人类征服了地球上最后一块丰饶的大陆——南极。然而，大量的资源从冰盖中被开采出来后，只是让原本就十分尖锐的社会矛盾雪上加霜。就在这时，一具被封冻在南极冰盖中70年的躯体引起了全世界的注意…… 为了解决问题，从左翼到右翼的所有人都在用魔法实践自己的观点。随意识形态的激烈交锋而来的，是全世界范围的激烈战争，战火从南极，南美洲，北美洲，东亚，西伯利亚一直烧到欧洲。进步同盟与联合国的疆界每天都在反复进退，没人知道这一切何时才会结束…… 人物设定 Schwarzkopf Henkal 姓名：Schwarzkopf Henkal 昵称：Henkal 工作单位：南极国际科学考察团 -> 南苏维埃共和国主席团 现居地点：阿蒙森-斯科特永久中立自治区 -> 南极苏维埃共和国 政治立场：马克思列宁主义 爱好：甜点，意大利面，哲学，共产主义 ...

图片加载可能要等一会…… 图片很大有3.5M，大家耐心点 自1453年东罗马帝国灭亡后，君士坦丁堡，这座城中之城再度易手。 在走上未曾设想的道路后，充满宗教热忱的罗斯人高呼着“恢复东罗马帝国荣光！”的口号，如潮水般涌向了西亚，企图收复拜占庭时代的五大牧首区——罗马，君士坦丁堡，安条克，耶路撒冷，亚历山大港 战姬骑士团首先将矛头对准了土耳其。那些带有“上帝赐予的力量”，或者说是“玛丽亚在人间的代言者”的姑娘们，挥舞着十字剑和战锤冲过多瑙河，踏上了巴尔干半岛的东色雷斯地区。经过三个星期的“圣战”，被凯末尔改为博物馆的圣索菲亚大教堂重新成为一座东正教的教堂。假如不是宗教狂热让她们不敢破坏这座神圣的城市，君士坦丁堡战役的持续时间可能还会更短。 攻占君士坦丁堡后，罗斯人们作出了更让其他国际震惊与困惑的举动：进攻叙利亚。 她们没有理会仍然盘踞在安纳托利亚半岛东北部的土耳其残余势力，挥师南下，直取古城安条克（今称安塔基亚），随后又对叙利亚发起猛攻。 “也就是说……”穿着礼服的黑发少女眨了眨眼睛。 “那些疯子的行动根本就没有什么原因”，秘书耸了耸肩，“他们根本就不是出于什么政治或经济上的目的，纯 ...

1971年7月，伏尔加格勒 夜深了。 伏尔加格勒的月光从未如此清冷，仿佛坟墓中散发出的荧光，喃喃着不知是谁的坟墓主人的姓名。星星死气沉沉地排列在月亮周围，如同穿着黑衣一言不发的随从。假若一个虔诚的基督教徒同时看到天上与地上的情景，一定会想起《圣经》中关于审判日的描写，月亮与星星是于天中排列的天使，将要审判世间的一切罪恶。 街道上传来人们的尖叫与呐喊，时不时还闪烁着几点火光。有人在奔跑，有人在哭号，有人在喊叫试图维持秩序，也有人带着颤抖的声音怒吼着，但随即嘎然而止。 但最后，都被轰鸣的机械碰撞声所取代。 ——这就是年仅六岁的欧若拉对那天晚上的全部记忆。 外面嘈杂的声音持续了很长时间，欧若拉好奇地忍不住爬到窗台上去看，但立马就被父亲拽了下来，严厉地小声了呵斥一句，但父亲的神色立即又被一种被压抑着的悲哀所取代。在困惑与茫然中，欧若拉懵懵懂懂地被父亲哄到卧室里。 “你就呆在这里，赶快睡觉，不管听到什么都不要喊叫。外面有人撞车了，很快就会没事的。” 父亲用严肃的语气向她解释。年幼的欧若拉并没有意识到，父亲额头上渗出的汗珠已经出卖了他此刻的心情，对她而言，父亲是撑起天空的支柱一样的存在，是绝对正确 ...

最近几天翻找自己的学习笔记时，忽然发现自己的Hexo博客已经长了几个月的草，于是一时兴起又更新了一下Hexo博客，但在构建博客时出现了问题： Hexo与Node.js的兼容性 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126mike@MacBook-Pro ~/hexo $ hexo g [15:13:57]INFO Validating configINFO Start processingINFO Files ...

　　每一个中国人都知道，自己祖国的全名是“中华人民共和国”，其中的“人民”昭示着这是一个社会主义的国家。但或许有人不知道的是，社会主义的火种，是如何在这片几代人之前还是半封建半殖民地的国家扎下根的？ 　　在今天，离我们那个时代或许已经十分遥远，但这并不能作为我们忘却斗争精神的理由。须知，我们今日的昌盛，不是资本家们施舍的，而是无数人民英雄们抛头颅、洒热血换得的！我们难道能因为出生在一个所谓“岁月静好”的年代，就忘记了革命年代的理想与信念吗？不！我们永不忘记！ 　　《红星照耀中国》最早出版于1937年。 　　那个时代坏吗？坏，因为那个时代军阀混战，国土沦亡，最顶层的吸血鬼肆意掠夺人民的财产，用来充实自己家族的钱包。而底层的平民命如草芥，仅仅是活下去都要付出无法承受的代价。帝国主义肆虐，公然查收中国的政治，经济，在租界耀武扬威。买办阶级为一己私利打压民族工业，公然为帝国主义充当马前卒。牛鬼蛇神横行人间。可以说，那个时代是“坏”的。 　　那个时代好吗？好，因为那个时代共产运动风起云涌，共产党人踏过漫长的征途，在西北建立了革命的根据地。“地火在地下运行，奔突；熔岩一旦喷出，将烧尽一切野草，以及 ...