- 博客(198)
- 收藏
- 关注
RSS订阅转载 2018年小记
去年写了一次总结，今年看来感觉颇有趣味，于是今年闲着无聊又来“如法炮制”一番。----------------------------------------------正文的分界线---------------------------------------------- 感觉今年于我而言是黯淡却又传奇的一年：黯淡在于一年除了互娱短暂的实习以外，其余时间似乎大多处于“摸鱼...
2019-02-04 12:14:00
200
转载 利用python爬虫爬取图片并且制作马赛克拼图
想在妹子生日送妹子一张用零食（或者食物类好看的图片）拼成的马赛克拼图，因此探索了一番= =。 首先需要一个软件来制作马赛克拼图，这里使用Foto-Mosaik-Edda（网上也有在线制作的网站，但是我觉得这个比较方便，而且也找到了一个汉化过的版本，地址为http://witmax.cn/foto-mosaik-edda.html）。要制作马赛克拼图，需要一个图片的数据库，至少需...
2018-07-29 13:18:00
671
转载 2017年小记
只感觉刚刚还只是高中毕业，现在已经跨上实习的道路了，时间真的走的很快。今年感觉变化了很多，也成长了许多，于是想今年稍微总结下今年的小结。 回想起今年的ACM之路来，感觉相比上一年来说似乎并没有过大的进展，在大腿队友的带领下又摸了一年的鱼，感觉水平没有过大的提高，可能只是算法熟练度上有所进展吧。 看了看去年一年的博客，大多数的博客都是密集在去年的上半年，可能的确只有那段时间...
2018-02-15 12:06:00
219
转载 CodeForeces 842d Vitya and Strange Lesson ——（带lazy标记的01字典树）
给一个序列，每次操作对这个序列中的所有数异或一个x，问每次操作完以后整个序列的mex值。 做法是去重后构建01字典树，异或x就是对root加一个x的lazy标志，每次pushDown时如果lazy的这一位是1，则交换左右儿子。找mex的话只要每次往左走，如果左子树是满的，则往右走，并且加上左边相应造成的贡献。具体见代码： 1 #include <bits/st...
2017-11-11 17:14:00
147
转载 Codeforces 876E National Property ——（2-SAT）
在这题上不是标准的“a或b”这样的语句，因此需要进行一些转化来进行建边。同时在这题上点数较多，用lrj大白书上的做法会T，因此采用求强连通分量的方法来求解（对一个点，如果其拓扑序大于其为真的那个点，则这个语句为真，都相同则无解，否则为假）。AC代码如下： 1 #include <bits/stdc++.h> 2 using namespace std;...
2017-11-02 12:21:00
513
转载 POJ1635 Subway tree systems ——（判断树的同构，树的最小表示法）
给两棵有根树，判断是否同构。因为同构的树的最小表示法唯一，那么用最小表示法表示这两棵树，即可判断同构。顺便如果是无根树的话可以通过选出重心以后套用之前的方法。 AC代码如下： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #inclu...
2017-10-12 17:25:00
135
转载 HDU 6208 The Dominator of Strings ——（青岛网络赛，AC自动机）
最长的才可能成为答案，那么除了最长的以外全部insert到自动机里，再拿最长的去match，如果match完以后cnt全被清空了，那么这个最长串就是答案。事实上方便起见这个最长串一起丢进去也无妨，而且更好写（时间也没有慢特别多）。 另外需要注意的一点是init()里头的memset只需要清空之前用过的节点而不是所有节点，这是经常被卡的一点。 代码如下： 1 #i...
2017-09-21 18:25:00
105
转载 HDU 6194 string string string ——（2017沈阳网络赛，后缀数组）
思路见：http://blog.csdn.net/aozil_yang/article/details/77929216。 代码如下： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std;...
2017-09-11 20:56:00
75
转载 HDU 6086 Rikka with String ——（AC自动机 + DP）
这是一个AC自动机+dp的问题，在中间的串的处理可以枚举中断点来插入自动机内来实现，具体参见代码。 在这题上不止为何一直MLE，一直找不到结果（lyf相同写法的代码消耗内存较少），还好考虑到这题节点应该不会过多，可以少开一点节点数。 代码如下： 1 #include <bits/stdc++.h> 2 using namespace std;...
2017-08-21 15:57:00
211
转载 HDU 6129 Just do it ——（找规律）
思路见：http://blog.csdn.net/qq_32506797/article/details/77206167。 利用二进制讲m次转化成log次然后进行转移。 代码如下： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4...
2017-08-21 14:44:00
86
转载 HDU 6041 I Curse Myself ——（仙人掌图，tarjan，转化）
题解见这个博客：http://blog.csdn.net/ME495/article/details/76165039。 复杂度不太会算。。这个经典问题的解法需要注意，维护队列里面只有k个元素即可。另外，tarjan对无向图仙人掌图缩点（即只把所有环变成一个点）得注意一下（栈得手写才能实现要求，这是因为在这里割边不能被算进环内，而在有向图中，一个点也算是强连通分量的）。 ...
2017-08-21 14:38:00
96
转载 HDU 1402 A * B Problem Plus ——（大数乘法，FFT）
因为刚学fft，想拿这题练练手，结果WA了个爽= =。 总结几点犯的错误： 1.要注意处理前导零的问题。 2.一定要注意数组大小的问题。（前一个fft的题因为没用到b数组，所以b就没管，这里使用了b数组，结果忘记给其大小乘以4倍了） 代码如下： 1 #include<bits/stdc++.h> 2 using namespace st...
2017-08-06 15:41:00
115
转载 HDU 4609 3-idiots ——（FFT）
这是我接触的第一个关于FFT的题目，留个模板。 这题的题解见：http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html。 FFT的模板如下： 1 #include<bits/stdc++.h> 2 using namespace std; 3 const double p...
2017-08-06 12:27:00
108
转载 Codeforces Round #426 (Div. 2)
AB都是水题。 C，设A和B是输入的最终分数，A和B一定具有这样的形式：A=a*b*b， B=a*a*b。那么A*B开三次方得到a*b，从而得到a和b，只要a和b存在答案便存在。开三次方使用二分即可。 D题，题意是使序列刚好分成k段，每段的贡献值为这段不同数字的个数，问一种分法使得分数最大，求最大的分数。在扫描的过程中，假设当前出现的数字是now，last[now]表示的...
2017-07-31 11:14:00
94
转载 CodeForces 787 题解
A题，因为数据范围很小，所以只要暴力即可，如果能相遇一定范围不大，如果范围很大还没相遇一定是不会相遇的了。正解应当是用扩展欧几里得计算这个方程的整数解，再想办法看看有没有正整数解才是。 B题，只要看懂了题意，用map维护一下即可。真不知道题目给的n是干嘛用的。。 C题，如果不存在loop的情况就用np态判断一下即可。现在存在loop正向dfs是不可以的，因为dfs的顺序会...
2017-07-25 10:37:00
158
转载 2017杭电ACM集训队单人排位赛 - 2 题解
1001，水题，直接模拟即可。比赛中开局连wa三发，因为把int写成了bool.. 1002，积分题，比赛中找到了下面这个积分公式， 但是并没什么用，，因为带入以后存在误差，估计是展开了以后出现了误差。然后用自适应simpson即可。大白书上的模板不怎么好用（虽然能过），优化版的模板如下（本题AC代码）： 1 #include<iostream>...
2017-07-06 13:36:00
145
转载 CodeForces 816E Karen and Supermarket ——（树形DP）
题意：有n件商品，每件商品都最多只能被买一次，且有一个原价和一个如果使用优惠券以后可以减少的价格，同时，除了第一件商品以外每件商品都有一个xi属性，表示买这个商品时如果要使用优惠券必须已经使用了xi的优惠券。现在有B的钱，问在不超过B的钱的情况下最多能买多少件商品。 做法：因为根据x属性，所有商品能够被连缀成一棵以1为根节点的树，因此考虑树形dp，因为n=5000，所以定义状态...
2017-07-04 09:29:00
142
转载 Codeforces Round #420 (Div. 2)
A题，水题，只要暴力即可，要注意的是题意要理解清楚。 B题，枚举每一个x作为矩形的右边，那么其中的贡献是可以用等差数列累和公式计算的，最后对所有可能的答案取一个max即可。该题很友好，使用floor没有被卡精度= =。 C题，由于题目是保证了一定能够使得满足要求，那么如果remove的时候这个栈不是递减的只需要给它排序一下即可。实际上并不需要对其这样模拟（也不可以这样模拟...
2017-07-02 16:49:00
105
转载 计蒜客 UCloud 的安全秘钥 ——（hash）
题目链接：https://nanti.jisuanke.com/t/15769。 题意是求可以变换位置以后相同的子串有多少个，那么做法是只要每个数字的平方和，立方和以及四次方和都相同就可以了。 代码如下： 1 #include <cstdio> 2 #include <cstring> 3 #include <algorith...
2017-06-04 21:02:00
164
转载 Codeforces 812E Sagheer and Apple Tree ——（阶梯博弈）
之前在bc上做过一道类似的阶梯博弈的题目，那题是移动到根，这题是移动到叶子。换汤不换药，只要和终态不同奇偶的那些位置做nim即可。因此这题给出了一个条件：所有叶子深度的奇偶性相同。同时需要注意的是，上次bc中，根节点是不能移动的，因此根节点是终态节点，而这里叶子上面还可以进行操作（可以吃掉），那么就相当于叶子节点都还可以继续向下移动，因此他们不是终态节点，也就是说这题只要和叶子节点同...
2017-06-03 22:39:00
211
转载 2017年浙江省赛总结
最终是5题银。其实感觉再给点时间能7题的，主要是最后机子不够用了，没时间调试了，当然代码能力弱也是很大的一个问题。 E题，队友当时卡了很久，最终是A了。赛后发现就是一个很水的数位DP。。代码如下： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h&g...
2017-04-26 09:04:00
443
转载 UVALive 3716 DNA Regions ——（扫描法）
乍一看这个问题似乎是很复杂，但其实很好解决。 先处理出每个点到原点的距离和到x正半轴的角度（从x正半轴逆时针旋转的角度）。然后以后者进行排序。 枚举每一个点到圆心的距离，作为半径，并找出其他到圆心距离不超过这个值的点，由于他们的角度是有序的，因此线性的找出角度差最小的满足题意的两个点即可（相当于拿一个长度为k的尺子不断地移动过去）。 那么总的复杂度为O(n^2)。...
2017-04-18 22:44:00
117
转载 UVALive 3716 DNA Regions ——（式子变形）
一开始直接想到了二分，写了一发然后过了全部样例就交了，果断WA。因为这个问题显然是不满足单调性的。 然后想之前刚做的斜率优化DP，但是那个是求斜率最大值，不是求满足斜率大于一定值的最大长度的。也构造不出好的方法。 最后的方法是列个式子：i+1~j位置可以成立仅当 (pre[j] - pre[i]) / (j - i) >= (100-p) / 100。不妨把p变成1...
2017-04-18 22:29:00
114
转载 2016-2017 ACM-ICPC Northwestern European Regional Programming Contest (NWERC 2016)
只A出了其中的5题。。这场题意好晦涩啊，而且其他题目也有一定的难度。又是tarjan又是dinic的。。暂时先给写出来的5题做个题解吧。 题目链接：https://vjudge.net/contest/158990#overview。 C题，还是一个比较水的题目，只要看懂了题意就能A出来了。 E题，也是一个水题，不过要对题目的意思有一定的想象力。。从一个...
2017-04-16 21:52:00
248
转载 Egyptian Collegiate Programming Contest (ECPC 2015) C题 Connecting Graph
这题上次用的是线性求LCA过的，数据比较水，当时没有被T掉（不过线性的做法是在线的）。现在重新的分析一下这个问题。在所有的操作都进行完毕以后，这个图形肯定会变成一棵树，而我们的要求是在这棵树上的一条链上求出边权值t的最大值，那么很显然的可以使用树链剖分来解决这个问题（在做这题之前我还不知道LCA也可以获得一条链上的最值）。然后再看这个问题，因为不论是LCA还是树链剖分，都不能够动态的...
2017-04-16 09:52:00
167
转载 UVALive 4726 Average ——（斜率优化DP）
这是第一次写斜率优化DP= =。具体的做法参照周源论文《浅谈数形结合思想在信息学竞赛中的应用》。这里仅提供一下AC的代码。 有两点值得注意：1.我这个队列的front和back都是闭区间的；2.在while(...) front++; 这个循环里面，<=写成<就会WA，不知道是为何（讲道理是肯定没问题的，至多多判断几个点而已，我猜想可能是存在了精度误差导致的）。。...
2017-04-14 14:00:00
111
转载 CodeForces 494B Obsessive String ——（字符串DP+KMP）
这题的题意就很晦涩。题意是：问有多少种方法，把字符串s划分成不重叠的子串（可以不使用完s的所有字符，但是这些子串必须不重叠），使得t串是所有这些新串的子串。譬如第一个样例，"ababa"和"aba"，共有5种方法：{aba}（前3个），{aba}（后3个），{abab}，{baba}，{ababa}。 先设s的长度为lena，t的长度为lenb。 做法是：用dp[i]表示...
2017-04-13 23:04:00
137
转载 UVALive 5052 Genome Evolution ——（xjbg）
本以为这题n=3000，随便n方一下就能过。于是我先枚举长度len再枚举起点，不断增加新的点并删除原来的点，判断在b中的r-l+1是不是等于len即可，这个过程显然要用set维护比较方便，但是貌似卡了这个log，T了= =。 然后修改了一下思路，先枚举左端点，再不断的向有扩张，并用两个变量l和r来标记在b中的最左和最右的位置，然后如上做法即可。这样的好处在于不需要删除点的信息，...
2017-04-13 12:57:00
115
转载 UVA 11525 Permutation ——（线段树，脑筋急转弯）
只要注意到对于譬如：S1*(k-1)! 因为后面k-1个数字的全排列个数刚好是(k-1)!，那么第一个数字就是没有取过的数字的第(S1+1)个即可。取走这个数字以后这个数字就不能再用了，依次类推即可得到整个排列了。 那么随便用线段树维护一下即可。 代码如下： 1 #include <stdio.h> 2 #include <algorithm...
2017-04-04 11:39:00
95
转载 UVALive 4976 Defense Lines ——（LIS变形）
题意：给出序列，能够从这序列中删去连续的一段，问剩下的序列中的最长的严格上升子串的长度是多少。 这题颇有点LIS的味道。因为具体做法就是维护一个单调的集合，然后xjbg一下即可。具体的见代码吧： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h>...
2017-04-03 11:08:00
103
转载 UVA 11605 Lights inside a 3d Grid —— （概率和期望）
题意：见大白书P181。 分析：一个一个点的进行分析，取其期望然后求和即可。假设当前点在第一次中被选到的概率为p，f[i]表示进行k次以后该点亮的概率（在这里也可以理解为期望），g[i]表示k次后该点不亮的概率，那么联立： 1.f[1] = p; 2.f[i] + g[i] = 1.0; 3.f[i] = f[i-1] * (1-p) + g[i-...
2017-04-01 17:49:00
111
转载 ZOJ 2592 Think Positive ——（xjbg）
做法是，先求出前缀和pre。然后枚举端点i，[i+1,n]中pre最小的找出来，减去pre[i-1]大于0，这是第一个条件；第二个条件是，从i开始的后缀和和i之前的最小的一个pre相加大于0。只要满足这两个条件那么这个端点就是可行的。显然找这两个区间的最值都是可以用数组线性维护的，因此总体复杂度是O(n)的。 代码如下： 1 #include <stdio.h&g...
2017-03-28 21:51:00
122
转载 POJ 3342 Party at Hali-Bula ——（树型DP）
一开始用pii保存dp类型，写的很长，还是WA了= =。。 然后参考了一下别人的博客，重新写了一发（似乎是岐哥的博客233）。 代码如下： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream...
2017-03-27 22:55:00
109
转载 POJ 2486 Apple Tree ——（树型DP）
题意是给出一棵树，每个点都有一个权值，从1开始，最多走k步，问能够经过的所有的点的权值和最大是多少（每个点的权值只能被累加一次）。 考虑到一个点可以经过多次，设dp状态为dp[i][j][k]，i表示当前从i出发，j表示最多走j步，k=0的话表示最后回到i点，否则不回到i点的子问题的答案。 转移见代码。 值得注意的是dfs中j循环的方向必须从大到小，因为如果从小到大...
2017-03-27 20:08:00
108
转载 Egyptian Collegiate Programming Contest (ECPC 2015)
题目链接：https://vjudge.net/contest/155219#overview。 A题，用全排列来找出比当前这个数字字典序还大的排列有几个，然后前缀和dp即可。据说可以康拓展开来快速找出前面需要实现的要求。 B题，水题。 C题，感觉数据比较水。做法是dsu+lca，但是为了实现lca树的结构不被破坏，dsu::find()不能压缩路径。然后线性找lc...
2017-03-26 11:33:00
176
转载 2015 ACM Arabella Collegiate Programming Contest
题目链接：https://vjudge.net/contest/154238#overview。 ABCDE都是水题。 F题，一开始分类讨论，结果似乎写挫了，WA了一发。果断换并查集上，A了。 G题，状态压缩DP，不难写，但是时限有点紧，读入也比较恶心。。值得注意的是计算一个数二进制下有几个1可以用__builtin_popcount(mask)；判断a和b在二进制...
2017-03-17 18:02:00
185
转载 UVALive 4394 String painter ——（区间DP）
其实这个dp过程有点似懂非懂。。。代码如下： 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 100 + 5; 6 7 char a[N],b[N];...
2017-03-17 17:38:00
107
转载 2015-2016 ACM ICPC Baltic Selection Contest
这是上礼拜三的训练赛，以前做过一次，这次仅剩B题没补。题目链接：https://vjudge.net/contest/153192#overview。 A题，水题。 C题，树形DP，其实是一个贪心问题，比如要取max的话，从根往下的肯定是要依次放max门，因此取一条能够获得最大值的一路放下max门即可。min同理。 D题，BFS即可。 E题，从小点到大点建边，...
2017-03-13 17:56:00
168
转载 UVALive 4254 Processor ——（二分+优先队列处理）
题目是求最小化最大值，很显然是二分，但是二分以后怎么判断mid是否可行并不容易。 代码参考了网上一个博客的代码。巧妙之处在于一秒一秒的考虑，这样可以把处理速度mid直接转化成1秒内实际的量来解决（避免小数问题），然后贪心考虑每次处理最早结束的工作即可。注意我这里的代码t表示的是一整秒，譬如[1,2]即t=1。 具体见代码： 1 #include <stdio...
2017-03-13 17:42:00
88
转载 HDU 2243 考研路茫茫――单词情结 ——（AC自动机+矩阵快速幂）
和前几天做的AC自动机类似。 思路简单但是代码200余行。。 假设solve_sub(i)表示长度为i的不含危险单词的总数。 最终答案为用总数（26^1+26^2+...+26^n）减去（solve_sub(1)+solve_sub(2)+...+solve_sub(n)）。前者构造f[i]=f[i-1]*26+26然后矩阵快速幂即可（当然也可以分治的方法）。后者即...
2017-03-06 22:53:00
129
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人