题意 给你n个点的有向图，有m条边， q次查询，每次查询第k大的路径的长度 思路 对于每个点所出去的边先排个序，预处理一下，我没可以知道最开始最短的边肯定只有一条，所以我们把每个点出去的最短的边先放到优先队列里面, 然后最短的边肯定就是当前最短的路径，那要如何扩展路径了，我们每次求出当前最短的路径那么放到队列里的肯定是由这条路径扩展出来的，因为其他路径暂时不用扩，因为有更短的在队列里面，但我们放出(u,v)这条边e的时候， 扩展v最小的出边，和以u为始点的e的下一条边即可 AC_code: /* Algorithm: Author: anthony1314 Creat Time: Time C...

题意 给你一个长度为n的字符串，q次查询，每次查询给你三个数字, l, r, k 查询 查询从左往右 第k个 与子串 s[l…r] 相同的子串的左端点的位置 查询不到输出-1      1   ≤   n   ≤   1   e   5   ,   1   ≤   q   ≤   1   e   5    1 \le n \le 1e5, 1 \le q \le 1e5   1≤n≤1e5,1≤q≤1e5 思路 对字符串后缀数组，根据sa数组建主席树，然后rmq预处理height数组 每一次查询，根据height数组二分找到一个最左的合法的左端点ansL，和最右的右端点ansR 然后在主席树上...

A. XORinacci 题意： f(0) = a, f(1) = b, f(n) = f(n-1)^f(n-2), 求f(n) 思路： 每三个数字一个循环 /* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */ #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #inc...

题意 给你n个数字 找至少出现t次的最长可重复子串 保证一定有答案 思路 继续刷后缀数组模板题 先二分答案，然后将后缀分成若干组。判断的是有没有一个组的后缀个数不小于t height数组真好 AC_code: #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define maxn 20005 int ss[maxn]; int sa[maxn],c[maxn]; int rank[maxn],height...

题意 有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1…88范围内的整数，现在要找一个重复的主题。 “主题”是整个音符序列的一个子串，它需要满足如下条件： 1.长度至少为5个音符 2.在乐曲中重复出现(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。) 3.重复出现的同一主题不能有公共部分。 思路 后缀数组入门题目 先转化成相邻两项的差值，然后就是找不可重叠重复子串。 来自论文的思路 先二分答案，把题目变成判定性问题：判断是否存在两个长度为k的子串是相同的，且不重叠。解决这个问题的关键还是利用height数组。把排序后的后...

后缀数组 定义 字符串s 子串：在字符串s中，取任意i<=j，那么在s中截取从i到j的这一段就叫做s的一个子串 后缀suff(i)：从字符串的某个位置i到字符串末尾的子串 后缀数组sa[i] ：表示排名为i的后缀的起始位置的下标 数组rk[i] ：表示起始位置的下标为i的后缀的排名 suff(sa[i])：表示排名为i的后缀 LCP(i, j) ： 排名为i的后缀 和 排名为j的后缀 的最长公共前缀 height[i] ： LCP(i, i-1) 排名为i 和排名为i-1的后缀 的 最长公共前缀 height[1]=0 可以解决的问题 Problem1 求一个字符串s的子串中至少出现过两...

昨天 2018的acm网络赛就告辞一段落了 听着罗老师的建议，要赛后进行总结，昨天那一场北京场还有点记忆，就来写写感受，顺便写写这一个星期遇到的难题 昨天打的是训练赛，和hhr和zcy组队，一开始zcy就死怼e，说找出了规律，叫他不要开，他还开，然后他就浪费了一个小时，一开始我就开了第一道签到题，d，看了一下题意，一开始理解错了题意，因为那个next以为下一步是可以随机挑选的，不用按着顺序，等我xjb敲完了发现过的人才20多个，就觉得是不是我理解错题意了，问了一下hhr，于是就交了一发，然后wa了，才知道要按顺序，仔细一想觉得会超时，但是想不出其他解法了，于是就敲了一发暴力，不敢交，在hhr和...

2018.08.24 .晚上还在打cf，那天晚上状态不是很好，因为在jxb他们宿舍打的cf，那天刚好是jxb的生日，去他们宿舍蹭了蹭空调,大家为xb准备了一个惊喜的蛋糕， 庆祝了一下，吃完就差不多9点多了，10点半开始的cf，吃完之后xb他们宿舍都说今晚不是很想打cf，xm说div3对于他这种手速慢的很不利，wd看了两个宿舍都不打也不打了，所以整个宿舍就我一个人孤军奋战，cy一直在说靠我了，我受宠若惊，吃完蛋糕准备看会dp专题就去打cf了,突然一个老友发给我，很久没聊天，就聊到10点多了，聊到比赛开始了，想了想已经开始了就没想打了，没想到等一会聊完了居然延迟时间了，我以为这是上天对我的安排，注...

初识ACM： 大学刚进来就抱着想要学好计算机这一门专业的目的， 但是进来刚开始的专业是数字媒体技术，也是我们学校的信息技术学院的一个专业，开学进来一片迷茫，第一次听见acm的就是在大一第一学期刚开学的国家奖学金评选上，评选奖学金的每一个都很优秀， 有各个专业的，每个人的经历都很丰富，有出国游学，参加国际建模大赛，完成一些看起来很厉害的项目，总之看起来每个人都是全能的，绩点高，又是各种学生干部，然而最终有一个看起来好像没什么竞争力的人上台了，比起别人丰富的学生干部生活和出国经历， 他的ppt上全都是他参与acm比赛拿的所有奖项，一页ppt都是奖项，后来我才知道他是14级的zdw学长，那一届我们院...

题意： 给你n个数字，求有多少个子区间满足 1.区间最大值 - 区间长度      ≤    \le   ≤ k 2.区间内各元素不相同 题解： 今天学了启发式分治，这道题就可以用这个算法 1.每次找到该区间的最大值的位置，以此作为分割点，枚举区间短的部分作为端点，统计答案，然后两个区间再分治，再统计两个区间的答案 2.找区间最大值，我们可以直接用ST表，然后还要预处理出以每个点作前缀和后缀不同元素区间最长长度 具体看代码实现 AC_code: #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; ...

题意: 如果一个序列的任意连续子序列都至少有一个元素唯一，则称这个序列“不无聊”，否则称这个序列“无聊”。给定T个序列，求是否“无聊”。 国内vjudge链接 思路: 先做一次预处理把每一个元素前一次出现的相同元素的值的位置和后一次出现的相同元素的值的位置记录下来 每次找到一个只出现了一次的点，其位置的pos，那么继续分治[L,pos-1]，[pos1+1,R] 为了保证时间复杂度，每一次找pos要从两边往中间找 AC_code: #include<bits/stdc++.h> using namespace std; const int maxn = 2e5; int a[max...

题意: N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色. 操作1 表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y. 操作2 表示要进行询问当前有多少段颜色      1   ≤   N   ≤   1   e   5   ,   1   ≤   X   ,   Y   ≤   1   e   6    1 \le N \le 1e5, 1 \le X,Y \le 1e6   1≤N≤1e5,1≤X,Y≤1e6 思路: 我们可以把每一种颜色的位置用链...

题意： 给你n个任务区间     [    a   i    ,    b   i    ]    [a_{i}, b_{i}]   [ai​,bi​]，      1   ≤    a   i    ≤    b   i    ≤   1000000    1\le a_{i} \le b_{i} \le 1000000   1≤ai​≤bi​≤1000000 你可以选择起点，每次你可以 向左 走一步或者两步，或者向右走两步或一步 请你依次到达所有的区间，最少需要多少次 思路： 比赛的时候看错两次题，第一次没有看到依次，比赛过程中看到了，把排序贪心改掉了，但是还是看错了题，我一直以为是只能向...

题意: 在一个封闭的n*m的矩形内，有k条射线，有四个方向，上下左右，射线，射线的端点不重合，该矩形内有多少个封闭的区域      1   ≤   n   ,   m   ≤   1   e   9   ,   1   ≤   k   ≤   1   e   5    1\le n,m \le 1e9 ,1\le k \le 1e5   1≤n,m≤1e9,1≤k≤1e5 没有任意两个个端点的x坐标 或 y坐标相同 题解： 看图不难观察到 当横向的线与纵向的线产生一个交点的时候,封闭的区域就会增加1 于是我们只需要求交点有多少 我的做法是 先离散化x坐标和y坐标 将所有点按y坐标从小到大排序 ...