- 博客(51)
- 收藏
- 关注
RSS订阅原创 C++17 下模仿 C++20 的 requires clause
这样写可以达到效果，但是也太费事了一点，关键是编译器在遇到 substitution failure 的时候并不告诉我具体是哪一个 substitution fail 了，而是悄无声息地转向另一个 overload candidate，于是我们也不能将所有 requirements 都写在一个 helper 里。遗憾的是我们课程是 based on C++17 的，这是出于多方面的考虑，在这里不多解释。最好放进一个 namespace 里，避免造成名字空间污染。出了一道让学生造个简单的。
2023-05-05 20:18:25
188
原创 Install deepin-wine QQ inside a docker image in Ubuntu 20.04
列出了一些在Ubuntu上安装QQ、微信的方法，均经过亲身实践。
2022-09-22 12:58:55
596
原创 在friend中让std::make_shared使用private构造函数
众所周知在创建std::shared_ptr对象的时候，我们总是应该优先选择std::make_shared而非手动地用new。《Effective Modern C++》中提到了若干种std::make_shared不奏效的情况，主要是如下几种：make系列函数不支持定制deleter大括号初始化物无法被完美转发由于weak_ptr的存在导致控制块和对象所占的内存被延迟释放在实际操作中，我们还遇到了一种特殊的情况：假设有一个类Widget的构造函数是private的，我们想在它的friend函
2022-05-13 15:30:34
1268
原创 C++ operator new 和 placement-new 笔记
当我们在C++中写出一条new表达式时，它的执行分为两步：分配所需的内存在分配的内存上构造对象这两步中，C++允许我们控制的是第一步，第二步是我们无法控制的。默认情况下，如果用new创建单个对象，第一步会调用一个默认版本的名为operator new的函数；如果是用new[]创建“动态数组”，那么第一步调用的是默认版本的名为operator new[]的函数。它们的声明如下：// operator new/new[] are not inlined// not in any namespace
2022-05-11 14:29:00
537
原创 CS101 2021Fall PA3,4 题解
CS101 2021Fall PA3,4 题解PA3PA3的题目描述真是四次PA中最令人一言难尽的一次，第一题和第二题一开始都有条件的缺失，尤其第二题的描述很不清楚，也没有样例解释，关于什么样的方案是本质不同的也没有准确严谨的定义，如果不是根据tag猜到了做法而是从题目本身入手去分析的话真的没法做。第三题的特殊输入方式也没有解释得很清楚。3001题意：给一张nnn个结点、mmm条边的无向图G=(V,E)G=(V,E)G=(V,E)，请选出VVV的一个子集UUU。如果某一条边两端的结点都在UUU中，那
2022-01-21 01:31:42
896
1
原创 CS101 2021Fall PA1,2 题解
CS101 2021Fall PA1,2 题解关于PA (Programming Assignment)鉴于PA的题目都没有在课上或讨论课上讲解过，piazza上也没有发过题解，GKxx打算简单整理一下这些题目的题解。对于其中的部分题目，我会尽可能多写几个能想到的算法，并提供一部分代码。水平有限，这份题解仅供参考，如有错误欢迎指出。如果对某些题目有同学有更好的做法，请直接发，不要联系我，我懒得再看了。建议以后的CS101可以在每次PA结束以后开放一个题解展示平台，并安排一两名助教审核提交的题解，可以
2022-01-18 17:28:22
1188
2
原创 XeLaTeX编译时不显示目录
今天遇到了XeLaTeX编译beamer文件的时候目录不显示的问题，即\tableofcontents失效，并且报错Rerun to get /PageLabels entry。其实解决方法就是按照它说的，rerun，也就是用XeLaTeX连续编译两遍。如果是VSCode，需要在settings.json里这样写{ "latex-workshop.latex.tools": [ { "name": "xelatex", "comm
2021-07-16 21:25:14
6487
4
原创 正则表达式的匹配算法与实现
注意，本文中的C++代码都是C++11的。0. 正则表达式0.0 语言设Σ\SigmaΣ为某个字符集合（或称“字母表”），由Σ\SigmaΣ中的符号构成的一个有序序列称为串（string），串sss的长度通常记作∣s∣|s|∣s∣。空串是一个长度为000的串，通常记为ϵ\epsilonϵ。由某个字母表Σ\SigmaΣ中的字符按某种方式构成的所有的串的集合称为语言（language）。我们可以定义串上的连接（concatenation）运算：串xxx和串yyy的连接结果xyxyxy是将yyy附加到x
2021-02-10 00:50:02
1851
原创 傅里叶变换：不只是多项式乘法
傅里叶变换：不只是多项式乘法动机我们的信息科学与技术导论课程期末需要做一个project，笔者选择的题目是跟信号处理有关的，而谈到信号处理就必然离不开傅里叶变换。笔者作为一个前OIer，曾经接触过用于求多项式乘法的FFT、NTT算法，并大致了解过生成函数、多项式相关的理论，同时又对数学分析有着浓厚的兴趣，于是就花了一些时间仔细学习了一下傅里叶分析，初步了解了它在信号处理中的应用。之后，我决定将我的笔记和我看到的一些资料整理成这篇随笔。前言音频信号是什么？如果你用过Cool Edit，Fruity
2020-12-12 15:54:40
620
4
原创 为了求正切的麦克劳林展开式，我复习了伯努利数
这是一篇随笔。前段时间数分课讲到了Taylor公式，做题的时候常常会用到sinx,cosx\sin x,\cos xsinx,cosx等函数的Taylor展开式。我们容易写出sinx\sin xsinx和cosx\cos xcosx的nnn阶麦克劳林展开式，但是tanx\tan xtanx的麦克劳林展开式比较复杂，于是我翻开《具体数学》重新学习了一下跟伯努利数有关的内容，并做一些简单的整理。
2020-11-19 22:06:06
2366
原创 关于C字符串的一个陷阱
关于C字符串的一个陷阱今天有小伙伴来问了我一个挺有趣的问题，正好最近在读的《C++ 沉思录》在开头谈到“为什么用C++”的时候也提到了这一点，于是决定写一篇笔记。注：笔者水平有限，如有错误欢迎指出，不胜感激。众所周知，C语言中是没有真正的“字符串”的，我们不能像在Python或者C++中那样很方便地使用str或者std::string来处理字符串，而只能用以空字符'\0'结尾的字符数组来假装一个字符串。这种字符串最大的问题在于，它将拷贝控制和内存管理这两件棘手的工作完全交给了用户。不妨考虑一个“切片
2020-11-03 16:13:26
236
1
原创 [JSOI2018]潜入行动（洛谷p4516）题解
传送门一道树上背包简单题状态很好推。设dp[x][i][0/1][0/1]dp[x][i][0/1][0/1]dp[x][i][0/1][0/1]表示以xxx为根的子树中共放了iii个监听装置，其中xxx点放没放装置，xxx点有没有被监听到的方案数（在以xxx为根的子树中除xxx外的其它结点都被监听到了）不难看出这是一个树上背包，树上背包的转移套路是dp[x][i+j]=combine(d...
2019-10-19 22:15:16
221
原创 CF923E Perpetual Subtraction 题解
洛谷传送门设f(τ,i)f(\tau,i)f(τ,i)表示第τ\tauτ次操作进行之前，也就是第(τ−1)(\tau-1)(τ−1)次操作进行之后得到的数是iii的概率。那么f(1,i)=pif(1,i)=p_if(1,i)=pi，我们需要对于每个iii求出f(m+1,i)f(m+1,i)f(m+1,i)。不要问我为什么用τ\tauτ这个奇怪的字母考虑一次操作带来的影响：显然有f(τ+1...
2019-08-21 13:28:11
402
原创 [HAOI2018]奇怪的背包 题解
传送门题意有nnn件物品，第iii件物品的体积是viv_ivi，数量不限，现在有qqq次询问，每次询问一个www，要选出若干件物品使得它们的体积之和对PPP取模的结果等于www，问方案数。注意，两个方案不同，当且仅当放入物品的种类不同，与物品的数量无关。题解相当于是要解这个方程v1x1+v2x2+⋯+vnxn≡w(modP)v_1x_1+v_2x_2+\cdots+v_nx_n\eq...
2019-08-20 15:28:25
179
原创 [TJOI2019]唱、跳、rap和篮球 题解
传送门老年退役选手来写题解了题意有aaa个人喜欢唱，bbb个人喜欢跳，ccc个人喜欢rap，ddd个人喜欢篮球，现在要从中选出nnn个人排成一队，使得不存在位置kkk满足第kkk，k+1k+1k+1，k+2k+2k+2，k+3k+3k+3个人依次喜欢唱、跳、rap、篮球，求方案数。两种方案不同，当且仅当有一个位置上的同学的喜好不同。题解为了方便，我们将连续的唱跳rap篮球四个人称为“i...
2019-07-30 11:36:46
411
原创 [国家集训队作业]城市规划 题解
传送门：洛谷P4841题意：求nnn个点简单无向连通图数量。首先我们设g(n)g(n)g(n)表示nnn个点的简单无向图（不要求连通）数量，对于每一对点都可以连或者不连边，所以g(n)=2Cn2g(n)=2^{C_n^2}g(n)=2Cn2设f(n)f(n)f(n)表示nnn个点简单无向连通图数量，那么枚举111号点所在的连通块至少是多大，可得g(n)=∑i=1nCn−1i−1f(i)g...
2019-07-02 17:34:38
240
原创 [JSOI2015]染色问题 题解
传送门容斥原理把三个容斥套一起我们枚举至少有iii行没有染色，至少jjj列没有染色，至少kkk种颜色没有用到，那么剩下(n−i)(m−j)(n-i)(m-j)(n−i)(m−j)个格子每个都有c+1−kc+1-kc+1−k种选择（可以在剩下c−kc-kc−k种颜色中挑一种，也可以不染色），因此答案就是∑i=0n∑j=0m∑k=0c(−1)i+j+kCniCmjCck(c+1−k)(n−i)...
2019-07-02 09:57:37
619
原创 [SCOI2014]方伯伯的OJ 题解
传送门我佛了，我这么大常数的写法竟然跑得还不算特别慢。。。首先想到用一个splay按排名维护队列，那么操作都挺sb的，随便写写就行了吧。然后就发现有问题，n≤108n\leq10^8n≤108，这意味着好像不能把整棵树建出来（可以吗？我也不清楚==）。于是我们考虑一种结点分裂的做法，就是把一段区间合成一个结点，用到的时候再分裂。那么既然这样我们还需要一个map来知道编号x对应的结点是哪一个...
2019-06-28 23:23:19
158
原创 [国家集训队]Crash的文明世界 题解
传送门题意给一棵树，设S(x)=∑i=1ndist(x,i)kS(x)=\sum\limits_{i=1}^n\mathrm{dist}(x,i)^kS(x)=i=1∑ndist(x,i)k，对每个点求出S(x)S(x)S(x)。n≤5×104,k≤150n\leq 5\times10^4,k\leq150n≤5×104,k≤150。题解不会点分树首先我们知道第二类斯特林数SijS_...
2019-06-27 12:23:10
150
原创 分部求和法简介
分部求和法首先我们知道ddx(u(x)v(x))=u′(x)v(x)+u(x)v′(x)\cfrac{\mathrm{d}}{\mathrm{d}x}(u(x)v(x))=u'(x)v(x)+u(x)v'(x)dxd(u(x)v(x))=u′(x)v(x)+u(x)v′(x)d(u(x)v(x))=u′(x)v(x)dx+u(x)v′(x)dx\m...
2019-06-27 08:26:23
2891
原创 [NOI2012]骑行川藏 题解
传送门题意：给出u1,u2,⋯ ,un,k1,k2,⋯ ,kn,s1,s2,⋯ ,snu_1,u_2,\cdots,u_n,k_1,k_2,\cdots,k_n,s_1,s_2,\cdots,s_nu1,u2,⋯,un,k1,k2,⋯,kn,s1,s2,⋯,sn，最小化函数T=∑i=1nsi...
2019-06-16 14:02:25
263
原创 牛客练习赛47 题解
比赛传送门正好跟cf时间撞上了，然而我太菜了cf的题做不出来，就来看了看牛客的题真的好简单啊…A DongDong破密码题意：将一个01串aaa（长度为nnn）向右移动mmm次，最后求出这n+m−1n+m-1n+m−1位每一位的异或值，得到一个新串bbb。（这个描述不太清楚，建议看原题有张图）现在给出串bbb，请你求出原串aaa。题解：b[i]b[i]b[i]的值其实就代表了a[i−m+...
2019-06-07 23:53:26
311
原创 [CEOI2017]Building Bridges 题解
传送门设sis_isi为wiw_iwi的前缀和，fif_ifi表示将第111根柱子与第iii根柱子连接的最小代价。考虑最后一座桥从第jjj根柱子架到第iii根柱子，于是枚举jjj，有转移fi=min{fj+si−1−sj+(hi−hj)2}f_i=\min\{f_j+s_{i-1}-s_j+(h_i-h_j)^2\}fi=min{fj+si−1−sj+(hi−hj)2}把...
2019-05-03 23:04:48
286
原创 [HAOI2016]找相同字符 题解
传送门开始对后缀数组上瘾了。。。题意：给两个字符串，求公共子串数量。把两个串拼在一起并且在中间加一个分隔符，然后统计出这个长串有多少对位置不同的相等子串。这些子串要么同时来自S1S_1S1，要么同时来自S2S_2S2，要么一个来自S1S_1S1一个来自S2S_2S2；而我们需要的答案是最后一类。所以我们只要对S1S_1S1和S2S_2S2分别求一次，用总数减去它们的答案即可。现...
2019-05-03 17:15:04
231
原创 [十二省联考2019]字符串问题 题解
传送门写篇题解记录一下我第一道sa大题。我再也不是不会sa的sb了其实自从去年12月份决定放弃冲省队开始就一直没有按原计划继续学下去（废话），所以各种后缀数据结构一片空白，结果在考场上遇到了这个题。当时我就知道这题肯定是用后缀数据结构优化匹配，然后用线段树优化建图，但是我并不能写得出任何一个可用的后缀数据结构…其实不是什么很难的东西啦…只是代码有点长。首先考虑一个40分暴力：对于每一组支配...
2019-05-03 13:30:06
262
原创 [SDOI2018]旧试题 题解
传送门简单反演+神仙优化题。首先我们知道σ0(xy)=∑i∣x∑j∣y[(i,j)=1]\sigma_0(xy)=\sum\limits_{i|x}\sum\limits_{j|y}[(i,j)=1]σ0(xy)=i∣x∑j∣y∑[(i,j)=1]σ0(xyz)=∑i∣x∑j∣y∑k∣z[(i,j)=1][(i,k)=1][(j,k)=1]\sigma_0(xyz)=\sum\lim...
2019-05-01 18:06:55
582
原创 [APIO/CTSC2007]数据备份 题解
传送门首先把数组差分，那么就是要在差分数组中找kkk个不相邻的数，使它们的和最小。首先有一个暴力的DP做法：f(i,j,0/1)f(i,j,0/1)f(i,j,0/1)表示前iii个数，选了jjj个，第iii个数不选/选，和最小是多少。f(i,j,0)=min(f(i−1,j,0),f(i−1,j,1)),f(i,j,1)=f(i−1,j−1,0)+dif(i,j,0)=\min(f(i-1...
2019-04-28 07:10:13
211
原创 [GXOI/GZOI2019]逼死强迫症 题解
传送门题意：用n−1n-1n−1块大小为1×21\times21×2的砖和两块大小为1×11\times11×1的砖铺满2×n2\times n2×n的路，要求两块小砖不能有边相邻，求方案数。这题简直是弟中弟。首先设fif_ifi表示用1×21\times21×2的砖铺满2×n2\times n2×n的路的方案数，显然fif_ifi是斐波那契数列。并注意到斐波那契数列的一个重要性质：∑...
2019-04-28 00:25:56
200
原创 [GXOI/GZOI2019]与或和 题解
传送门题意：给出一个n×nn\times nn×n的矩阵，求所有子矩阵的and\text{and}and值之和和or\text{or}or值之和。显然可以把每一位分开来求，那么对于某一位而言矩阵中的元素不是000就是111。一个仅由000和111构成的子矩阵的and\text{and}and值是111当且仅当这个子矩阵中全是111，否则是000；类似地，or\text{or}or值是000当且...
2019-04-28 00:00:38
270
原创 [北京省选集训2019]图的难题 题解
传送门题意：给一张无向图，将其中的边染成黑色或白色，使得不存在同色环。问是否存在可行的染色方案。观察可知一个结论：图G=(V,E)G=(V,E)G=(V,E)的可行的染色方案存在，当且仅当对于任意子图G′=(V′,E′)G'=(V',E')G′=(V′,E′)都有∣E′∣≤2∣V′∣−2|E'|\leq2|V&#x...
2019-04-27 22:29:07
234
原创 [GXOI/GZOI2019]旧词 题解
传送门题意：给一棵树，qqq次询问，每次询问给出x,yx,yx,y，求∑i=1xdepk(lca(i,y))\sum\limits_{i=1}^x\mathrm{dep}^k(\mathrm{lca}(i,y))i=1∑xdepk(lca(i,y))当k=1k=1k=1的时候它几乎就是[LNOI2014]LCA。k=1k=1k=1的做法：lca(i,y)\mathrm{lca}(i,y)...
2019-04-27 20:34:17
162
原创 [GXOI/GZOI2019]旅行者 题解
传送门题意：给一张图以及kkk个关键点，求关键点两两最短路最小值。这题难道不是寒假里正睿讲过的原题？？？官方正解比较厉害，感觉有点难想。我们考虑将关键点分为两个集合AAA和BBB，建立源点sss和汇点ttt，从sss向AAA中所有点连权值为000的边，从BBB中所有点向ttt连权值为000的边，然后求sss到ttt的最短路。我们知道答案一定由某一对点产生，关键是你如何恰好让这一对点分属A...
2019-04-21 16:09:14
191
原创 Codeforces1111E Tree 题解
传送门比赛的时候满脑子虚树 就死掉了看来真的不能先入为主这种询问点集的，首先考虑建虚树，然后按套路设dp(x,i)dp(x,i)dp(x,i)表示将以xxx为根的子树中的关键点分成iii组的方案数，那么你很快就会发现这玩意根本不能转移，因为它不是正常的背包。换一个思路，如果我们考虑将关键点按dfs\text{dfs}dfs序排序，那么对于一个点nodei\text{node}_inodei...
2019-04-21 14:48:03
133
原创 卡特兰数（Catalan）相关应用
关于卡特兰数这玩意，其实最早是为了准备NOIP初赛而学的（包括斯特林数），不过那时候也没意识到它这么好玩。这几天好像经常看到关于卡特兰数的一些应用，尤其是文化课数学正好在学计数，所以就决定写一篇总结一下。为了给非竞赛生更好的阅读体验不至于一上来就被大量的公式劝退，我先介绍卡特兰数的应用，再推导公式。当你看到这些时，它对应了卡特兰数我们用CnC_nCn表示第nnn个卡特兰数，其中n∈Nn\...
2019-04-20 08:42:35
335
原创 [IOI2018]werewolf狼人 题解
传送门由于LOJ真的很慢（不知道是LOJ的问题还是我电脑的问题），这里提供洛谷的传送门，代码是完整代码而不是交互代码从SSS出发，只经过编号大于等于LLL的点，能够到达的所有点构成的集合记为AAA；从EEE出发，只经过编号小于等于RRR的点，能够到达的所有点构成的集合记为BBB，那么就是要求A∩BA\cap BA∩B是否为空集。自然想到kruskal重构树，先对每条边以两个端点的编号较小...
2019-04-14 12:39:06
291
原创 [十二省联考2019]异或粽子 题解
传送门好吧，其实是个套路题。这种选k大的，有一种套路就是用堆维护，连续取k个，一边取一边加入新的。跟那个给你几个数组求k大和的很像。考虑暴力：首先sis_isi为异或前缀和这大家肯定都会，O(n2)O(n^2)O(n2)枚举区间，加进堆里或者放数组里最后排序，取前kkk大即可。我们考虑一个优化：我们在枚举区间[l,r][l,r][l,r]这一步，可以只枚举一个右端点rrr，然后在[0,r...
2019-04-14 12:36:05
304
原创 [HAOI2018]染色 题解
传送门题目大意：一个长度为nnn的颜色序列，至多mmm种颜色，如果有kkk种颜色恰好出现了SSS次，愉悦度增加wkw_kwk（k=0,1,2,⋯ ,mk=0,1,2,\cdots,mk=0,1,2,⋯,m）。求所有方案愉悦度之和。首先颜色数量至多L=min(m,⌊nS⌋)L=\min\left(m,\lfloor\frac{n}{S}\rfloor\right)...
2019-04-14 10:51:07
176
原创 [十二省联考2019]春节十二响 题解
传送门做完之后真的有一种 艹这么简单的题为什么我考场上没想出来 的感觉当时在考场上已经被两个计数题的dp洗脑了，于是对着这道题推了半天的dp，最后写了个奇怪的记忆化搜索+一条链。然而写一条链的时候可能也只有我这种菜逼没看见题目里说1不一定是链的端点了。。。最后就只拿了45分我要是能花时间好好想想一条链怎么做，这题就切了。因为一条链的情况实在是离正解很近很近。一条链的做法：1号点至多两个分支...
2019-04-13 18:36:18
405
原创 [ZJOI2014]力 题解
传送门题意：给出nnn个数qiq_iqi，定义Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2F_j=\sum\limits_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum\limits_{i>j}\frac{q_iq_j}{(i-j)^2}Fj=i<j∑(i−j)2qiqj−i>j...
2019-04-13 17:14:06
86
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人