- 博客(326)
- 收藏
- 关注
RSS订阅原创 如何在低版本Ubuntu上安装Clang等
从 https://apt.llvm.org/ 找到对应的源，例如deb http://apt.llvm.org/xenial/ llvm-toolchain-xenial maindeb-src http://apt.llvm.org/xenial/ llvm-toolchain-xenial main# 11deb http://apt.llvm.org/xenial/ llvm-toolchain-xenial-11 maindeb-src http://apt.llvm.org/xenia
2021-03-23 18:00:48
790
原创 Ubuntu & wsl 黑科技
试过很多源，都不靠谱。这个阿里云靠谱。deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiversedeb-src http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiversedeb http://mi...
2019-11-10 13:46:04
356
原创 CodeChef February Challenge 2019 Division 1
文章目录Chef and Secret IngredientsArt of BalanceManhattan RectangleGuess It RightXor DecompositionMaximize the TaxChef and Secret Ingredients水题，直接安排。T = int(input())while T: T -= 1 n = int(input())...
2019-02-14 15:02:46
443
2
原创 手写数字识别-KNN算法
最近学了一下Python，找个东西练练手。Python写东西是真的简洁！真的简洁！真的简洁！要做到手写数字识别基本得靠机器学习，这里用了监督学习里的KNN算法。我参考了这一篇。KNN算法的思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。对于识别数字，可以把数字图片先转化成一个n*n的数字矩阵，矩阵中的数字为1个字...
2019-02-06 23:26:08
554
原创 拦截网页广告
一些网站（比如本站）都是很不错的分享知识的平台，然而广告太多啦…这就引出了一个一般性的问题：怎么拦截网页广告，至少让它从视野里消失？找到了一个方法，写下来备忘。Chrome里面有一个插件叫AdBlock可以实现这个功能。在Chrome Extension Downloader里面搜它的ID：gighmmpiobklfepjocnamgkkbiglidom，就能下了。使用方法就是点击Chro...
2019-01-30 00:21:25
1006
原创 “灯笼高高挂”助手
再次献丑。之前写过一个“穿越福城”助手(戳我)，感觉是个大失败…参数很难调，稳定性也非常差，不想改进了。然而第二个小游戏好白痴…不打算给它写助手了，就写第三个的吧。这个“灯笼高高挂”就比较好做了，参数用对了之后，只要不手动停下来，它就永远都不会输。跑到六百多就不想跑了。主要思想：先写一个能算周期的程序跑一会儿，能够发现，在最好的情况下（掉下来的房子大小不变），前7个房子的周期都是3s，随后...
2019-01-29 17:44:59
2122
10
原创 “穿越福城”助手
献丑。只能跑到223，提高分数的瓶颈在于我实在摸不透这款游戏中距离和尺寸之间的函数…主要思想：先用RGB匹配出企鹅脚（它可能没有脚，那就企鹅屁股吧）的位置和目标点中央的菱形的位置。算出它们之间的欧几里得距离。计算菱形的尺寸（可以以对角线长，边长等菱形的属性作为标准）。用以上参数计算出企鹅前的白板需要延长到多长。控制鼠标按下，这时候企鹅前面的白板在不断延长。在这个过程中用RGB方法一直匹配白板...
2019-01-28 17:18:13
8279
33
原创 Java快速输入输出
Java的输出和输出真实太慢了！！！如果需要输入105数量级的数据并输出同样数量级的数据，使用Scanner和System.out耗时将很可能超过1s。为了避免这种输入输出过慢的情况，这里引入Java中比较快的一种输入输出方式。 /* 这种输入输出会抛出异常IOException，所以要么写一个捕获异常，要么写一个throws IOException之类的东西 */ StreamTok.........
2019-01-21 13:26:51
3895
原创 BZOJ 4971 [Lydsy1708月赛]记忆中的背包
构造我觉得这是一道神题，官方题解戳我主要的想法是先构造出 kkk 个 111，再构造出若干个不小于 ⌈w2⌉⌈w2⌉\lceil \frac {w}{2} \rceil 的数，显然后者最多只能取一个，且取了这一个方案数就会多 (kw−vi)(kw−vi)k \choose w-v_i。那么只需考虑k=1到k=20的所有情况就能过了。我不知道为什么k=20是足够的，但它就是够的，感觉...
2018-08-24 23:36:02
342
2
原创 BZOJ 4974 [Lydsy1708月赛]字符串大师
KMP这题的解法直接揭示了一个结论。定义：称一个串 TTT 是 SSS 的循环节，当且仅当存在正整数 kkk ，使得 SSS 是 TTT 重复 kkk 次拼接形成的串的前缀。性质：若一个字符串 SSS 的最小循环节长度为 aaa，那么 SSS 的最大的border（当然要除了 SSS 本身）是 |S|−a|S|−a|S|-a。证明显然。知道完这个，模拟一遍KMP就好了。#inc...
2018-08-22 00:02:01
340
原创 BZOJ 5109 [CodePlus 2017]大吉大利，晚上吃鸡！
最短路+bitset+DP个人觉得这题的思路非常高妙。首先肯定是要建出最短路DAG，这个图上任意一条路径都对应一条原图的最短路。如果一个点a在S到T的必经之路上，那就会有S到a的方案数 * a到T的方案数 = S到T的方案数这个东西显然是充要的，这是一个巧妙的转化。套用这个想法，这题要求选出两个点，那就只需S到a的方案数 * a到T的方案数 + S到b的方案数 * b到T的...
2018-08-19 00:22:49
299
原创 BZOJ 4346: [POI2016]Nadajniki
树形DP好久没写正常的题解了，于是写一发。记f[i][j=0/1/2/3/4][k=0/1/2]表示以i为根的子树，j=0表示i和i子树中与i相邻的点都没有放，j=1和j=2分别表示i这个点放了1或2个，j=3和j=4分别表示i这个点没放但i子树中与i相邻的点放了1或2个，k表示与i相邻的点中还缺了几个，即至少还要放几个。最麻烦的地方就是状态之间的转移，手推清楚即可。#includ...
2018-08-16 22:56:55
218
原创 POJ 2024 Know When to Hold 'em
模拟刚开始题目看错了，原来后面两个 hole cards 是不能用的……英语不太好。然后我就没有在训练规定时间内干掉这个题了。做法就是暴力选牌，找到最大的手牌，如果有多种答案就枚举每一张牌，如果在每一种方案里它都出现那它就一定在答案里，否则把它的花色改成*就好了。#include<cstdio>#include<cstring>#include<alg...
2018-07-26 12:26:20
237
原创 CS Academy 题目泛做
一个神犇同学向我推荐了这个OJ。这个OJ上的题目都是挺经典的。数据、标程、题解都有，已经是很方便了。出于强迫症，下面的题目按照字典序排列。太简单的题大家应该都能一看就会，就直接略了。这个网经常崩，做起来好麻烦，所以这个坑先停了吧…Addition：略。A-Game：显然如果当前还有B就不会去选A。也就是说游戏的过程一定是先把B拿完，最后两人一个一个地拿A。若A是偶数则不论怎样一定平...
2018-07-22 21:48:47
1580
原创 BZOJ 4345 [POI2016]Korale
模拟搜索+线段树我觉得这题挺妙的啊。注意到当n=1000000很大的时候会有2^1000000种取法，但题目只要求选到k=1000000个，也就是我们不能爆搜，但要保证每一次都能取到一个前k大的。也就是要进行一个优秀的搜索。考虑朴素的垃圾搜索，是每次枚举i选或者不选，然后搜索i+1。注意到搜索的下一层的和总大于上一层。因此把其中有用的节点拿出来，是一个树形结构，若当前在第i层，有两种决...
2018-07-18 23:27:17
266
原创 Codeforces Round #493 (Div. 1)
A : 模拟 B : 打表 C : 容斥+反演+推式子 D : Unfinished E : Unfinished 这些题是赛后刷的，因为当时并不知道有这场比赛，就算知道可能也因为网络或者时间问题打不了吧… D和E看起来没什么人过，估计很难，先丢了。A. Convert to Ones考虑一个串，连续的0有多少段，显然一次取反操作最多使段数减一，一次翻转也至多使段数减一...
2018-07-03 22:57:00
218
原创 AtCoder Regular Contest 100
C : 排序 D : 贪心 E : 二进制+前缀和 F : Unfinished我晚上只是想来填一下高考志愿的，突然发现AtCoder有比赛，马上点进去就开始了…… 因为刚校选完不太想再打，于是养生地做完了C，离开比赛玩了一会儿，再打开准备做D和E，发现时间可能不太够就选分大的E做完就继续去玩了…C - Linear Approximation显然把 AiAiA_i .........
2018-07-01 21:52:08
495
原创 圆的反演 学习笔记
我还像还没有正经地写过学习笔记啊…… 学一学圆的反演性质(0) 除反演中心外，平面上的每一个点都只有唯一的反演点，且这种关系是对称的，位于反演圆上的点，保持在原处，位于反演圆外部的点，变为圆内部的点，位于反演圆内部的点，变为圆外部的点，这是一一对应的。(1) 过反演中心的圆，反形为不过反演中心的直线。 (2) 不过反演中心的直线，反形为过反演中心的圆。(3) 不过反...
2018-06-26 20:16:19
922
原创 CF 285D & 285E
大家好，时隔一年，我复活了！这两题并没有什么关系，只是一起A掉了就顺便一起写个题解吧……CF 285D 打表看了好久没有什么想法，猜测答案不会太大就直接打表。 发现n为偶数答案就是0。 n为13可以秒出，n为15大概等一会儿就好了，恩然后就过了。 打表代码不小心删了，反正不难写吧。CF 285E计数DP第一反应记f[i][j][k][0/1][0/1]表示...
2018-06-13 21:09:44
2289
原创 NOI2017 退役记
也许以后这个博客就再也没有更新了……也许有？这也说不定呢。希望以后不要再有人因为写挂题，特别是模板写挂而退役呀……然而这又怎么可能一直不发生呢？就当自己运气差吧。其实到现在还是无法释怀，因为确实只差了那么一点点。除了这篇游记，退役文可能还会写，但也不知道什么时候写。20170717 Day1报道日，来到绍一新校区。感受就是浙江真TM热住宿条件比冬令营的时候好，但是wifi实在是太慢了啊……食堂依旧是
2017-07-26 12:05:50
4318
5
原创 福建省队集训游记
作为FJ省队里最弱的一个，很荣幸能够参加这次省队面基大会省队集训。谨以此篇纪念我的被虐日常。20170706 Day0省队集训开始的前一天，高二生活的最后一天（话说其他同学好像还在准备下周的期末考呀……停课了大半年早已感觉自己没救了）。CY说，现在是什么水平，到NOI就是什么水平了。确实，一周之内基本很难有特别大的进步了。我现在这么弱，到NOI考场上也还是这么弱。CY又说，这次省队集训主要干的一件事
2017-07-22 20:21:54
931
原创 LOJ 6032 「雅礼集训 2017 Day2」水箱
线段树合并+树状数组把0设成-1，问题就变成求最大前缀和。考虑一个DP，记f[i]表示i隔板隔住了水，i之前最多满足多少条件。转移的时候枚举j表示[j,i]能是一个以j，i为左右端点的装水区间。这样的问题是每次从新的i扫到一个j都要合并一遍区间里的所有标记，也就是一个区间会被合并多次。然而能够证明，不同的装水区间不超过O(n)个，且它们之间不会有交（端点可能相同）。因此先找出这些区间，线段树维护一个
2017-06-28 07:54:54
921
原创 LOJ 6100 「2017 山东二轮集训 Day1」第一题
可持久化线段树+二分注意到如果[l,r]不降，[l,r-1]就肯定也不降，因此如果能对于每一个位置l，找到最远的r满足不降。这样套上主席树问题就搞定了。会降当且仅当此时异或上的a[i]的最高位恰好把当前的这一位从1变成0。因此记f[i][j][0/1]f[i][j][0/1]表示从a[1]开始异或到a[i]，以j为最高位的时候，j从1变成0（或0变成1）有多少次。这样二分以后每一位都判一下即可。O(
2017-06-25 15:04:56
1156
原创 LOJ 6043 「雅礼集训 2017 Day7」蛐蛐国的修墙方案
搜索+贪心因为要有解，所以把给出的置换连边形成的图一定是若干简单偶环。然后想了半天贪心，发现什么策略都找不到……考虑爆搜，直接搜索是O(2n2n)O(2^{n\over2}n)的，注意到如果环大小为2则一定前一个是左括号，因此只要枚举长度至少4的环，这样O(2n4n)O(2^{n\over4}n)，就能过了。#include<cstdio>#include<cstdlib>#define N 1
2017-06-24 21:50:47
679
原创 LOJ 6041 「雅礼集训 2017 Day7」事情的相似度
LCT+SAM+线段树问一个区间里的前缀之间的最长公共后缀，考虑SAM一发，建出反串后缀树，然后求最长公共后缀就变成求最深的LCA。直接维护区间的答案不好做，因此考虑一些离线的算法。莫队不知道能不能做，这里考虑把询问按照右端点排序，然后从左到右扫一遍。扫到i，则维护所有左端点在1～i-1，右端点在i的区间的答案。i新贡献的答案就是i和1～i-1的最公共后缀，也就是后缀树上一个点和其它一些点的最深LC
2017-06-24 17:34:53
1532
原创 BZOJ 4540 [Hnoi2016]序列
线段树+矩阵我来发一篇博客证明我还活着题目要求的区间所有子区间的最小值之和不太容易合并，因此直接上数据结构不好做。考虑离线做法。把所有询问右端点排序。从左到右扫描整个序列，扫描到ii时维护所有1≤j≤i1\le j\le i的区间[j,i][j,i]的答案。那每做完一个ii只要抓出当前询问的区间查询即可。如何随着ii右移，动态地维护前缀所有区间的答案？新加一个ii进来的时候，只会增加右端点在ii的子
2017-06-20 13:55:39
336
原创 UOJ 112 & BZOJ 4071 [Apio2015]巴邻旁之桥
线段树同侧的显然不用管他。k=1。枚举啊三分啊什么的应该都能过。进一步地，桥的位置一定是中位数。k=2。发现没有什么二分三分之类的性质。假设两座桥已经定下来，那么一个居民会选择离(A+B)/2近的桥来走。也就是按(A+B)/2排序后，居民会被分成左右两波走不同的桥。那就枚举分界点，对于走同一座桥的，类似k=1的找出中位数，用线段数维护中位数。#include<cstdio>#include<alg
2017-05-04 13:14:48
413
原创 UOJ 111 & BZOJ 4070 [Apio2015]雅加达的摩天楼
分块+最短路我们把一个(有doge的)点连向所有它能到达的所有点，这样就是一个最短路问题。考虑优化建图，用分块。如果pp大于n‾√\sqrt n就直接连。小于n‾√\sqrt n的情况？其实有一个性质，对于一系列有相同pp的点i<j<ki<j<k，如果ii能到达kk，jj能到达kk，那只要连上(i,j)(i,j)和(j,k)(j,k) 而不连(i,k)(i,k)即可。也就是说在pp相同的情况下，一个
2017-05-03 22:33:00
445
原创 UOJ 206 [APIO2016]Gap
构造第一个子任务就从外往内两个两个地确定即可。第二个子任务，发现如果我们类似上面地把每一个数都确定下来，至少也要N/2级别的询问，而询问代价还有一个k，因此不能直接确定所有数字。那就是要忽略一些数字，发现答案的下界是⌈an−a1n⌉\lceil \frac {a_n-a_1}{n} \rceil，因此把a1a_1至a−na-n分成下界个块数，块内就不用管了。只有块之间有贡献。#include "ga
2017-05-01 22:05:26
387
原创 BZOJ 4827 [Hnoi2017]礼物
FFT把式子展开完发现c和顺序无关，可以直接算，最小化这个式子就是最小化一个乘积的东西，也就是一个裸的FFT……涨姿势，C++有一个四舍五入的函数叫round()#include<cmath>#include<cstdio>#include<algorithm>#define N 400005using namespace std;namespace runzhe2000{ ty
2017-05-01 16:04:09
375
原创 BZOJ 4825 [Hnoi2017]单旋
splay 或 线段树观察这种spaly的性质。插入一个点，这个点的深度就是它的前驱后继中深度较大的那个+1。单旋最小值，则最小值的右子树里的点深度不变，自己深度变为1，其他点深度+1，单旋最大值同理。删除则在这个基础上让全部深度-1。这个是在平衡树上的子树维护，也就是一个区间维护，离线上线段树即可。然而我还是带着敬意地写了一个splay……#include<set>#include<cstdio
2017-05-01 13:43:29
406
原创 UOJ 109 [APIO2013]TASKSAUTHOR
提交答案题感觉这道提答是我见过的最善良的提答了……tasksauthor 1卡floyd，上一个101个点的无边图就行了。tasksauthor 2注意到代码里是只要能松弛就把边集for一遍，那就用一条链把松弛卡到V-1次，再把边加到满即可。tasksauthor 3同1tasksauthor 4dijkstra是一个看起来没有什么问题的算法，然而有一个致命弱点在于负权。建出一系列负权边让它的松弛次
2017-05-01 10:14:30
540
原创 51Nod 算法马拉松24
A : 构造 B : 状压DP C : 构造 D : 线段树或平衡树 E : 树链剖分+线段树 F : UnfinishedA 1804 小C的多边形强行猜了一个结论，试了一下小数据发现没问题，那就假装没问题吧……就是外面一圈1~n-1，里面把1插在n-2和n-1之间，其他的顺次递推。本题考察输出优化的使用。#include<cstdio>using namespace std;nam
2017-05-01 01:04:30
1362
1
原创 BZOJ 4813 [Cqoi2017]小Q的棋盘
树形DP记f[i][j]f[i][j]表示在i的子树里走j步最多能走多少个点。实际上的决策一定是先进一个i的儿子节点的子树，然后出来，再进一个子树，再出来……最后进一颗子树，也许还会出来。枚举在外面走多少步，转移到最后进去的子树即可。#include<cstdio>#include<algorithm>#define N 105using namespace std;namespace ru
2017-04-28 20:54:35
656
原创 BZOJ 3992 [SDOI2015]序列统计
NTT+矩阵快速幂懒得写了，orz链接：http://blog.csdn.net/ied98/article/details/46852805#include<cstdio>#include<cstring>#include<algorithm>#define N 17005#define MOD 1004535809using namespace std;namespace runzh
2017-04-27 23:47:01
325
原创 BZOJ 3489 A simple rmq problem
可持久化树套树发现这是一个多维偏序，可持久化树套树即可。#include<cstdio>#include<algorithm> #define N 100005using namespace std;namespace runzhe2000{ int read() { int r = 0; char c = getchar(); for(;
2017-04-27 23:42:08
339
原创 AtCoder agc007_f Shik and Copying String
贪心+队列画出折线图，每一列表示一个位置，每一行表示一次copy，折线段表示覆盖。一个过程就相当于从第一行开始不断向下画折线来覆盖最后一行。根据贪心，显然折线应贴着上面来画，且转移一定是从最近的转移过来。瞎JB感受一下就会发现折线每次至多增加一格，因此只要维护这些折线的拐点，也就是差分点就可以了，用一个队列维护即可。以上口胡，目测讲不清楚。详情还是去看题解吧。#include<cstdio>#in
2017-04-27 23:37:19
668
1
原创 洛谷 2480 [SDOI2010]古代猪文
中国剩余定理+Lucas定理题目就是要求G∑i|nCinmodpG^{\sum_{i|n}C_n^i} \mod p 然后费马小定理一下，变成求指数modp−1\mod p-1模数是合数，拆开来对每一个小质因数做一遍，最后CRT合并一下即可。注意费马小定理ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p成立，当且仅当pp是质数，且a,pa,p互质，然而GG=模数虽然不满足定理
2017-04-27 23:36:27
400
原创 BZOJ 4161 Shlw loves matrixI
特征多项式优化常系数线性递推详细内容请见《线性递推关系与矩阵乘法 》—叉姐常见的矩阵乘法可以在O(k3logn)O(k^3\log n)的时间复杂度内算出k k 阶常系数线性递推数列第 nn 项的精确值。我们来研究一下矩阵的特征多项式怎么优化这个东西。设这个矩阵是MM，把这个矩阵的特征多项式搞出来，根据Cayley-hamilton定理以及一些推导，可以得到：∀i\forall i，MiM^i 都可
2017-04-27 23:35:33
452
原创 BZOJ 3682 Phorni
后缀平衡树考虑如果可以离线，只需构出后缀数组套上线段树。在线的话我们需要一个在线的后缀数组，结合题意中后缀的含义，用后缀平衡树即可。#include<set>#include<cstdio>#include<algorithm>#define N 800005using namespace std;namespace runzhe2000{ typedef double db;
2017-04-27 23:34:32
500
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人