- 博客(159)
- 收藏
- 关注
RSS订阅原创 用moviepy将视频剪掉一段
from moviepy.editor import VideoFileClip, concatenate_videoclipsclipOri = VideoFileClip("E:/2020-03-29 19-31-39.mkv")#截取两个subclip再拼接#time_length = int(clipOri.duration) 这句可以获取片子的时#超过时长会报错，时长默认用...
2020-03-31 23:29:27
1178
1
原创 2020 CCPC Wannafly Winter Camp Day2 K.破忒头的匿名信（AC自动机）
题目：https://ac.nowcoder.com/acm/contest/4010一看到题面，很容易就往dp上想，而dp式也很容易想到，当前dp[i]可以从dp[i - （当前前缀i所有在字典中出现的后缀长度）]位置转移过来，所有转移加上该匹配后缀的cost取个min就是当前dp[i]的值。直觉上，dp的转移位置好像很多，似乎是n方级别的，这就不可做了。一眼看上去确实如此，于是我往许多方向...
2020-01-20 23:38:58
588
原创 lpoj5576 hongrock的柠檬树
题目：https://lpoj.cn/problemdetail?problemID=5576输入一棵树，求树上所有两点之间路径或之和。权神设计出来使用并查集做的。然而第一反应就是向上合并维护二进制位。写了一发维护1的个数愉快的wa了，之后就忘了有这题了。最近这题被大师兄，被教育了一手可以先当成整棵树全是1来做，然后再合并0的个数，减掉0的情况。瞬间好写了很多。。。。我们把子树0的个数向...
2019-11-23 21:17:35
278
原创 Comet OJ #contest14 D.转转的数据结构题（珂朵莉树）
题目：https://cometoj.com/contest/73/problem/D?problem_id=4120由于有“将一段区间全部变成v”这一操作，考虑使用珂朵莉树维护。将所有查询离线按右端点排序，在每个查询询问前，将1到R的操作全部做完，然后使用线段树/树状数组查询大于当前询问的L的操作产生的贡献。在珂朵莉树的节点中记录一下当前节点是由第几次操作产生，assigan时消除上次的贡...
2019-11-13 16:13:49
304
原创 2019哈尔滨CCPC L.LRU Algorithm（模拟+字典树）
给出一个LRU算法的操作序列，q个查询，询问在内存池大小为m时，LRU操作过程中会不会出现查询给出的内存池状态。我们发现内存池大小的限制因为LRU算法的特殊性质，仅仅只是把当前状态限制成了无限内存池大小的一个前缀。这题就变成了一个前缀匹配问题。由于n比较小，可以考虑n方的算法，模拟LRU算法的过程，不加内存限制，对于每一个中间状态，都去跑一遍查询建立的字典树，在字典树上经过的前缀显然就是答案Y...
2019-11-04 14:44:05
936
原创 [网络流24题]飞行员配对方案问题（最大流）
二分图匹配。使用最大流求解。博客中终于有网络流分类了…建反向边，开两倍空间。#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> pii;const int maxn = 1e5 + 15;int n, m;struct edge...
2019-11-02 22:19:00
331
原创 Tarjan求强连通分量模板
int dfn[maxn], low[maxn], scc[maxn], tot, scc_cnt;stack<int> st;void tarjan(int x) { dfn[x] = low[x] = ++tot; st.push(x); for (auto v:G[x]) { if (!dfn[v]) { ta...
2019-10-28 14:40:13
202
原创 HDU 5934 Bomb（强连通分量缩点）
题目:https://vjudge.net/contest/338569#problem/P显然可以想到引爆花费最小需要选择能引爆尽量多的，如果A能引爆B，B能引爆C，一定是引爆A最优。如果有一些点可以相互引爆，那么就引爆这些点里花费最小的。“能互相引爆”这显然是一个强连通分量，因此用tarjan求强连通分量之后，对于每个拓扑序最开头（入度为0）的连通分量，选择花费最小的进行引爆，即可求出答...
2019-10-28 14:38:10
155
原创 CF-932G Palindrome Partition（回文树等差优化）
给定一个串，把串分为偶数段假设分为了s1,s2,s3…sk求，满足s1=sk,s2=sk−1… 的方案数。当你把原串S变成S′=S[1]S[n]S[2]S[n−2]… 后，这题的问题就变成了有多少种切分S’的方法使得每一段都是回文串。（这个转化已经很神仙了，这道题就出到这里我都觉得已经很nb了）回文切分方法这个东西是一个经典的n方dp，dp[i]表示当前前缀i有多少种切分方法，dp[i]...
2019-10-15 20:28:35
396
原创 P4287 [SHOI2011]双倍回文（回文树建trans）
题目：https://www.luogu.org/problem/P4287求最长双倍回文。容易发现双倍回文的前半部分一定与整个回文在同一条fail链上，因此可以想出一种跳fail链统计答案的解法。对于每个点，往上跳fail，直到跳到一个点，这个点的长度*2刚好是起始点的两倍，再判断一下起始点长度能否被4整除，都满足即可统计答案。该解法如同各种自动机的连续跳fail做法一样，在fail树是...
2019-10-05 20:31:29
179
原创 2019 沈阳网络赛 F.Honk's pool（二分）
每次挑出最大的，令其减一，然后挑出最小的，令其加一。共操作K 次，求最大值和最小值的差。可以显然预见到如果操作次数无限，那么所有池子的水量就会在平均值附近徘徊。但是k不是无限的，有可能到不了平均，因此可以讲平均值作为上下界，对最大最小值分别进行二分。#include <bits/stdc++.h>using namespace std;typedef long long l...
2019-09-17 19:00:09
307
原创 [LOJ6198] 谢特（sam+字典树合并）
题目：https://loj.ac/problem/6198学习了学习了。在sam上跑一个合并，将儿子节点的可用数字合并到parent树父亲节点，在01字典树上找异或最大值，再加上当前父亲节点表示的长度来更新答案。很简单明了的一个思路，但是有一个疑问，题目要求的是最长公共前缀，众所周知倒着建sam后树上两个节点的lcp就是其lca，那么这么一路向上合并，有很多时候我们走到的不是lca了，这种...
2019-08-30 15:58:19
391
原创 Educational Codeforces Round 71 G.Indie Album（ac自动机+dfs序线段树维护fail树）
输入一颗字典树，之后m个查询，每个查询给出一个串，问这个串在字典树某一个节点代表的串中出现了多少次。一个串在另一个串中出现了多少次是sam的基操，但是这里输入了一颗字典树，4e5个节点，于是后缀自动机维护的难度和复杂度就变得巨大，分析了一下，似乎是不可做的。久违的用了一次ac自动机来解决一个串在另一个串里出现了多少次的问题，只需要建出fail树，这个问题就变成了一个串的链有多少个节点在另一个串...
2019-08-28 22:13:22
220
原创 2019CCPC网络赛 1003.K-th occurrence（Sam线段树合并+倍增优化）
一句话题解：用线段树合并维护right集，对于每个串记录在sam里的位置，倍增跳到合适的节点之后在那个节点的线段树里查询kth。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 5;int _, n, q, l, r, k;char s[maxn]...
2019-08-23 22:05:51
352
原创 2019牛客多校E.All men are brothers（并查集+排列组合）
给出一个并查集连边的过程，问每次连边之前，选出四个都不在同一集合内的选法。垃圾文科生又被组合数上了一课。首先这题直接算根本算不动，容易得知一条边都没有的时候选法是Cn4，所以可以考虑去算每次连边的损失。那么每次连边损失的选法就是这两个集合同时选出人的情形。怎么算呢？首先，这两个集合（k1，k2）各选一人，选法是集合大小相乘。之后要从剩下的集合里选出2人，如果不考虑不能从同一集合内选，选法是...
2019-08-16 20:32:42
199
原创 2019HDU多校第8场1005.Acesrc and String Theory（为什么要写SAM？）
给一个串，求问有多少子串是由k个循环节组成的。似乎是一种经典的搞循环节的做法…对字符串进行枚举分块（从1到len/k枚举块的个数），然后判断有多少个连续的块是相同的。得到了一片相同的块之后，我们再把这一段向左右扩展，对这几块前面的前缀部分，与这几块的任意一部分求个lcs（最长公共后缀），lcs的长度即为可向前拓展的部分。同理，对这几块后面的后缀与任意一块求一个lcp（最长公共前缀），lcp长...
2019-08-16 17:09:14
301
原创 2019HDU多校第6场 1005.Snowy Smile（线段树维护子段和）
给出若干个带权点，问丢一个任意大小的矩形下去框柱一些点，最多能得到多少权值。补题。n总和小于1e4，给了4秒，大致是一个n方log的算法。枚举矩阵的上下（或左右）两条边界，剩下两条边并不一定要枚举出来，可以用一个线段树维护最大子段和直接搞定。板子+1？#include<bits/stdc++.h>using namespace std;typedef long lon...
2019-08-09 21:27:39
271
原创 2019牛客多校第七场 C.Governing sand（贪心）
很多棵树，砍掉一些树使得最高的树的个数是总数的两倍，问砍树的最小花费。wa了很多发，写篇博客纪念一下（并不值得纪念）。每棵树都有成为最高的树的潜力，只要你把比它高的都砍掉。那么把树按高度排序，首先计算把比它高的树都砍掉的花费以及砍了多少树，这部分用两个前缀和O(1)求出。如果砍完比它高的树就已经满足条件了，那么更新答案，如果还不行，就还要砍掉一些比它矮的，这时候贪心的砍花费小的，由于花费最...
2019-08-08 23:04:04
225
原创 2019HDU多校第五场 1002.three arrays（01字典树）
输入两个数组，可以将这两个数组顺序任意变化，问相同位置异或能生成的字典序最小序列。一上来奇奇哥就告诉我这多半是01字典树，于是开始思考01字典树。这题麻烦在于两个数组都能随意排列，一开始想到一个序列建01字典树，另一个序列在上面跑，仔细想了想发现这样要枚举一个数组的排列，铁超时。自闭了一会儿想到干脆俩数组都建成01字典树然后用字典树跑字典树吧，敲的挺顺的一下就过了样例，3点提交了第一发，之后...
2019-08-06 00:23:44
587
2
原创 强力输入挂
namespace IO { const int maxn = 150960; char buf[maxn], t[50]; int bn = maxn, bi = maxn; int read(char *s) { while (bn) { for (; bi < bn && buf[bi] <...
2019-08-06 00:08:07
180
原创 2019牛客多校第六场 C.Palindrome Mouse（回文树）
给一个串，问这个串里所有本质不同的回文子串，有多少对满足一个串是另一个的子串。这题现场过的人很少啊，题解也给了个蛮复杂我还没看懂的带log的做法，其实了解回文树的话特别好想，我们现场写了一个O(n)的做法（在牛客跑了72ms）。回文树还算是个新东西，还没有被玩坏，我以前刷的回文树套题基本都算是板子题，最近多校有几道回文树就进入了灵活运用的范畴了，出题人开始准备玩坏这个算法了，以后这都是基操。见...
2019-08-04 00:57:17
587
3
原创 2019牛客多校第三场 F.Planting Trees（单调队列）
题目明确表示要用n3的的算法做。因此枚举矩阵的上下边界和右边界，再用两个单调队列维护左边界。#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 505;int t, n, m, num[maxn][maxn];int maxx[maxn], minn[m...
2019-07-29 00:53:32
304
原创 2019牛客多校第四场 k.number（3的性质）
全世界就我不知道一个数各位数之和是3，这个数就是3的倍数。#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 5;char s[maxn];ll cnt[3], now;int main() { scanf("%s", s + 1);...
2019-07-28 01:03:45
316
原创 牛客多校第四场 I.string（后缀自动机+回文树）
问一个串内，能选出多大的一个子串集合，满足两两子串直接互不相同而且不存在一个子串是另一个子串的反串。首先显然，重复出现的子串只能选一个，也就是只能选本质不同的子串。于是考虑将原串和其反串建立广义sam，此时原反串相同的部分全部压缩在了一起，对这个sam统计本质不同的子串个数，此时的统计结果中，符合题目条件（反串不同）的子串统计了两次（正串一次反串一次），不符合题目条件的串统计了一次。但是显然回...
2019-07-27 19:29:40
227
原创 2019HDU多校第二场 1009.I Love Palindrome String（回文树）
问所有长度的回文子串满足其一半（向上取整）也是回文串的个数。对原串建出回文树，并且建立fail树，一个节点在fail树上的父亲是其回文后缀，因此从根节点向下dfs，某个长度的一半如果曾经出现过，那么就找到了长度的一半也是回文的回文子串。统计其出现次数，即可求出答案。#include <bits/stdc++.h>using namespace std;typedef lon...
2019-07-26 16:01:13
237
原创 2019HDU多校第一场 1006.Typewriter（后缀自动机+dp）
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 2e5 + 5;int p, q;char s[maxn];struct Sam { int next[maxn << 1][26]; int link[maxn <<...
2019-07-24 11:59:31
364
原创 2019hdu多校第一场 1009.String（序列自动机贪心）
mark，明天补题解，现在打cf去了。#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 5;/*abcdabcda 42 1001 10 1001 1000 00 00 00 00 00 00 00 00 00 00...
2019-07-22 22:27:40
312
原创 牛客多校第二场 D.Kth Minimum Clique（bitmask优化跑团）
小团拓展出的新团一定比大团拓展出的新团要小，因此可以使用优先队列搜索。在寻找可拓展点的时候，可以使用位运算来优化，如果当前团的点集是找到点出边的子集，就可以拓展团。每个团找拓展点的时候只找比最后入团的点编号大的，不回头找（回头找会拓展出重复的团）。#include <bits/stdc++.h>using namespace std;typedef long long ll...
2019-07-21 21:52:47
203
原创 牛客多校第二场 H.Second Large Rectangle（次大全1子矩阵）
给出一个01矩阵，求次大的全1子矩阵。求最大是经典的单调栈O(m*n)做法，但是求次大的时候就会出现各种麻烦。算是成功签到了。比起求最大，同时维护一个次大，但是这样会wa，还需要记录最大子矩阵宽高里最小的那一个，然后用最大子矩阵减去min(宽，高)，这是为了考虑次大在最大内部的情况。#include <bits/stdc++.h>using namespace std;t...
2019-07-20 22:58:08
302
原创 叉积三角形面积
struct point { ll x, y; point operator-(const point &a) const { return {x - a.x, y - a.y}; }} a, b, c;ll s(point a, point b) { return abs(a.x * b.y - a.y * b.x) / 2;}...
2019-07-18 18:20:26
526
原创 HDU - 6096 String（这个ac自动机有、骚）
题意：给出n个串作为字典，和q个查询，每个查询包含一个前缀和一个后缀，问字典中有多少串与查询给出的前后缀匹配。绝了这个做法。ac自动机在失配的时候，会自动跳转到当前在ac自动机上跑的串能够匹配的最长后缀位置，这一条性质竟然能搞出这么骚的操作。将查询的前后缀以后缀 + “{” + 前缀的形式拼在一起（之所以用大右括号是因为它是小写字母z的ascii码下一个），全部建立ac自动机，然后将字典串变...
2019-07-05 07:54:26
289
1
原创 Codeforces1817-D. Subarray Sorting（关于排序的结论）
题面：https://codeforc.es/contest/1187/problem/D给出a、b两个数组，问对a进行部分区间排序操作（可无限次进行），能否得到b数组。这题被hack炸了，愣是搞出173个测试样例。题解给出了一个有趣的结论：一个数可以往前移动的个数是前面所有数都比他大的区间有多长。有了这个结论之后我们就可以对b数组每次都贪心的取a数组最左边的ai = bj的位置，然后检查a...
2019-07-03 13:46:23
330
原创 aes加密
#include<bits/stdc++.h>using namespace std;//al4f3dfe78e803fc10d5a8df4c632923//acc1d6b8efb55a7b1323cfdf457311b5string s = "2017040147055a7b1323cfdf457311b5";//string state[4][4];unsigned ...
2019-06-10 21:27:02
208
原创 关于没那么启发式的启发式合并写法
mark#include<bits/stdc++.h>using namespace std;const long long mod = 1e9 + 7;typedef long long ll;const int maxn = 1e5 + 5;int n, u, v, cor[maxn];ll ans[maxn];int id[maxn], tot;unord...
2019-06-03 13:47:03
167
原创 bytecamp
#include<bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; const int maxn = 20005; struct node { int v; char w; }; vecto...
2019-06-01 21:27:24
542
原创 Codeforces Round #562 (Div. 2) 题解
A.Circle Metro按题意模拟。#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;typedef long long ll;const int maxn = 1e3 + 5;int main() { int n, a, b, x, y; ios:...
2019-05-28 16:14:03
228
原创 在36mh看漫画更爽的脚本。
function del(){ var element, pElements = document.getElementsByTagName('p'); while (pElements.length>0) { element = pElements[0]; element.parentElement....
2019-05-19 20:33:30
106643
1
原创 牛客网暑期ACM多校训练营（第九场）F.Typing practice（ac自动机）
题解后补。#include<bits/stdc++.h>typedef long long ll;using namespace std;typedef long long ll;const int maxn = 1e5 + 5;int n, minn = maxn;string s, p;struct AC_Automaton { int next[m...
2019-05-17 19:36:14
212
原创 做两道sam+线段树合并的题
mark。进度1/2#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;typedef long long ll;const int maxn = 6e5 + 5;int n, q;string s, pp;pii cmp(pii a, pii b) { ...
2019-05-06 15:02:07
379
2
原创 华南理工大学“三七互娱杯” I.HRY and repeaters（sam+线段树合并）
题面：https://ac.nowcoder.com/acm/contest/874/I博客明天补，准备打cf，先贴代码。sam：听说你强制在线？好巧哦我就是在线的。ac代码：#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 3e5 + 5;int n,...
2019-04-29 21:29:35
240
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人