BzhH

这道题其实就是一道裸的AC自动机板子题，只需要在建tire图的时候稍微处理一下，因为它求的是子串的最长前缀，那么我们可以将子串再划分为许多长度不同的前缀就行了，然后再记录一下划分出来的前缀分别属于哪一个子串。 代码 #include<iostream>#include<cstdio>#include<vector>#include<queue>using namespace std;const int N = 1e7 + 5;char str[N], s[N];int tr[N][4], cnt[N], net[N], idx, mp[200], ans[N];bool vis[N];queue<int> q;vector<int> v, bel[N];void insert(int x){ int p = 0; for (int i = 0; str[i]; i++) { int t = mp[(int)str[i]]; if (!tr[p][t] ...

P2444 [POI2000]病毒 这道题直接输出都可以得60分,如果再写个随机算法,那么就可以用O(1)的时间复杂度解决这道题 首先看到这到题,不难想到暴力去枚举每一位,然后再用AC自动机,因为每个点最多只会被访问一次,所以时间复杂度可以道玄学的O(n) 代码 #include<iostream>#include<cstdio>#include<cstdlib>#include<queue>using namespace std;const int N = 1e5 + 5;char str[N];int tr[N][2], cnt[N], net[N], idx;bool vis[N];queue<int> q;void insert(){ int p = 0; for (int i = 0; str[i]; i++) { int t = str[i] - '0'; if (!tr[p][t]) tr[p][t] = ...

P3121 [USACO15FEB]Censoring G 这道题很明显是一道AC自动机的题目。 可以先将AC自动机板子打出来，打出来后该如何做这到题？可以考虑暴力做法，一个while循环一直扫描，每次扫描到了直接删除，但很明显，这样是会超时的。 通过标签观察我们发现，重新出现的单词是跟前面的部分没有关系的，那么我们就可以用栈来维护，一个栈来维护没有被删除的字符，另一个栈来维护AC自动机的下标 代码 #include<iostream>#include<cstdio>#include<queue>#include<cstring>using namespace std;const int N = 1e6 + 5, INF = 0x3f3f3f3f;char str[N], s[N];int tr[N][26], idx, cnt[N], net[N], len[N];int stk1[N], stk2[N], top;queue<int> q;void insert(){ int p = 0; for ( ...

为了方便统一,本文中下标均从0开始 KMP P3375 【模板】KMP字符串匹配 对于两个字符串S1,S2(S1>S2),求S2在S1中的出现位置 例如S1=ababa,S2=aba 在这个样例中答案就是0 2 首先考虑暴力做法,对于S1的每一个字符,我们都一该字符开始往后与S2对比.时间复杂度为O(n2)O(n^2)O(n2) 很明显这并不是我们想要的,所以考虑优化,仔细观察一下,其实我们不用每个字符都去枚举一遍 如图 我们假设图中绿色区域的字符串相等,那么当第i个字符匹配完时,对于第i+1个字符,我们不需要去枚举所有字符,因为我们可以知道, 图中绿色区域时已经匹配好了的,所以我们就只需要从绿色区域以后开始匹配就行了. 那么我们就可以设一个next数组,表示以第i个字符终点,相同的前缀和后缀的最大长度为多少 如上面的aba 那么next[0]=1,next[1]=1,next[2]=1 注意不能包括自己本身,因为这样的话存的东西就没有了意义,一直都是它本身的长度 那么在匹配的时候对于第i个字符,如果相等,那么已经匹配好的长度就加1,如果不等,就开始往回跳 我们每次就往会跳, ...

例题P3369 【模板】普通平衡树 概念： 平衡树是二叉搜索树和堆合并构成的数据结构，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 性质：对于每一个节点，满足它大于左儿子里的每一个节点，小于右儿子的每一个节点,即树的中序遍历为有序序列 对于一个平衡树，它可以支持的操作有 1:插入一个值 2:删除一个值 3:查询一个 xxx 的排名 4:查询排名为 xxx 的值 5:查询严格小于 xxx 的最大值 6:查询严格大于 xxx 的最小值 时间复杂度:不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素， 那么平均每次操作需要 O(logn)O(logn)O(logn) 的时间,所以我们要尽量让这棵树随机. 那么对于每一个节点,我们可以这样定义 struct tr{ int l, r; int siz, cnt, val, key;} tree[N]; l,rl,rl,r 为树的左右儿子的编号,sizsizsiz 为这棵子树的节点个数,valvalval 为一个随机值,keykeykey ...

读完题,很容易想到这是一道背包问题 ,但就是做不来,可以看到,方案既与差值有关,又跟和有关,那么可以考虑根据差值或和来考虑状态,可以考虑f[i][j][k]f[i][j][k]f[i][j][k]表示前iii个人选了jjj个人并且差值为kkk的和最大的方案 那么状态该如何转移呢? 考虑第iii个人选或不选 若不选第iii个人 很明显f[i][j][k]=f[i−1][j][k])f[i][j][k]=f[i-1][j][k])f[i][j][k]=f[i−1][j][k]) 若选第iii个人 第iii个人的差值已经定了,那么前iii个人的差值就是k−(p[i]−d[i])k-(p[i]-d[i])k−(p[i]−d[i]) 可以得出f[i][j][k]=max(f[i][j][k],f[i−1][j−1[k−(p[i]−d[i])])f[i][j][k]=max(f[i][j][k],f[i-1][j-1[k-(p[i]-d[i])])f[i][j][k]=max(f[i][j][k],f[i−1][j−1[k−(p[i]−d[i])]) 从题目中可以看出,差值的范围[−400,400 ...

这道题其实和SP703 SERVICE - Mobile Service一样 看到这到题,很容易想到一种定义状态的方式f[i][x][y][z]f[i][x][y][z]f[i][x][y][z]表示完成前iii个请求,三个人的位置分别在x,y,zx,y,zx,y,z,但很明显如果这么定义会超空间,所以想办法减掉一位,因为完成请求必须要有一个人在请求发生的位置,那么,我们就可以用当前完成的第iii个请求来推出其中一个人的位置,所一这个状态就可变成f[i][x][y]f[i][x][y]f[i][x][y],b表示完成前iii个请求时,其中两个人分别在x,yx,yx,y,接下来考虑怎么转移状态,如果我们从前面的状态来推当前的状态,需要考虑许多种情况,所以我们就用当前状态来更新下一个状态 然后是状态转移方程，因为有三个员工,那么我们可以考虑,下面三种情况 在当前请求的位置的人去 f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[p[i]][p[i+1]])f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + ...

看到这到题,很容易想到一种定义状态的方式f[i][x][y][z]f[i][x][y][z]f[i][x][y][z]表示完成前iii个请求,三个人的位置分别在x,y,zx,y,zx,y,z,但很明显如果这么定义会超空间,所以想办法减掉一位,因为完成请求必须要有一个人在请求发生的位置,那么,我们就可以用当前完成的第iii个请求来推出其中一个人的位置,所一这个状态就可变成f[i][x][y]f[i][x][y]f[i][x][y],b表示完成前iii个请求时,其中两个人分别在x,yx,yx,y,接下来考虑怎么转移状态,如果我们从前面的状态来推当前的状态,需要考虑许多种情况,所以我们就用当前状态来更新下一个状态 然后是状态转移方程，因为有三个员工,那么我们可以考虑, 在当前请求的位置的人去 f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[p[i]][p[i+1]])f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + c[p[i]][p[i+1]])f[i+1][x][y]=min(f[i+1][x][y ...

看到这道题，很容易想到是一道树型DP，那么该如何做？ 首先我们可以先这样定义状态，fi,jf_{i,j}fi,j​表示以iii为根节点,向下走jjj步最多能经过多少点,但很明显,只是这样是不行的,所以我们再加一维,第三维为0表示不会到根节点,第三维为1表示需要回到根节点,那么就可以得出状态转移方程 {fi,j,0=max(fi,j−t,0+fv,t−2,1,fi,j−t,1+fv,t−1,0)fi,j,1=max(fi,j−t,1+fv,t−2,1)\begin{cases}f_{i,j,0}=max(f_{i,j-t,0}+f_{v,t-2,1},f_{i,j-t,1}+f_{v,t-1,0})\\f_{i,j,1}=max(f_{i,j-t,1}+f_{v,t-2,1})\end{cases}{fi,j,0​=max(fi,j−t,0​+fv,t−2,1​,fi,j−t,1​+fv,t−1,0​)fi,j,1​=max(fi,j−t,1​+fv,t−2,1​)​ (其中iii表示父节点,jjj表示一共走了多少步,vvv表示儿子节点,ttt表示儿子节点向下走多少步) 注意到这里面为什 ...

看完这到题，很容易想到用背包做，即设状态fi,jf_{i,j}fi,j​表示前iii个商店一共带了jjj吨货的最小花费,只需要先把商店的位置排个序,就可以直接枚举了,那么就可以得到状态转移方程 {fi,j=fi−1,j+j∗j∗(Xi−Xi−1),u=0fi,j=min0≤j≤k,1≤u≤Fi(fi,j−u+u∗Ci)\begin{cases} f_{i,j}=f_{i-1,j}+j*j*(X_i-X_{i-1}),u=0\\ f_{i,j}= \underset{0\le j\le k,1\le u\le F_i}{min}(f_{i,j-u}+u*C_i) \end{cases}⎩⎨⎧​fi,j​=fi−1,j​+j∗j∗(Xi​−Xi−1​),u=0fi,j​=0≤j≤k,1≤u≤Fi​min​(fi,j−u​+u∗Ci​)​ 第一层循环枚举当前走到第iii商店，第二层循环枚举当前一共运了jjj吨货物,第三层循环枚举在当前商店购买u吨货物u吨货物u吨货物,那么我们就可以O(n3)O(n^3)O(n3)实现这个算法,很明显是会超时的,所以想办法优化,(通过查看标签),很明显可以看到 ...