权限题。 题意： 求一个字符串中出现超过k次的最长子串，可重叠 （n<=20000） Solution： 先用后缀数组跑出height 然后我们知道一个性质：任意两个后缀的最长公共前缀就是它们之间所有height取min 那么这个问题就相当于枚举每个长为k-1的区间，在区间内部求min，每个区间求max，倍增解决即可 代码： #include<cstdio> #include<iostream> using namespace std; const int N=20010; int m,n,kk,a[N],p; int tax[1000000],SA[N],tp[...

传送门 题意： 给出一张n个点，m条边的无向图，每个点有点权，求一条从1到n的路径，使得经过的点中点权大的个数尽量少 n<=100000 Solution： 相当于求一条将这条路径中的所有点权排序后，字典序最小的路径 用主席树维护当前路径经过不同点权的次数，再运用hash可以在logn的时间内判断两个字符串的大小 再加上堆优化的dij，复杂度为 O((n+m)lognlogn)  O ( ( n + m ) log ⁡ n log ⁡ n )  代码： #include<cstdio> #include<iostream> #include<queue&gt...

传送门 题意： 给出一个N的排列，问是否存在一个长度至少为3的等差子序列 n<=10000 Solution： 注意到我们给出的是一个排列，而且我们只需要找长度为3的子序列即可 那么我们可以枚举中间项x，用01串S和T来表示x前面的数中[1,x-1]和[x+1,x+x-1]是否出现，每次判断串S和T的反串是否相等即可，如果不相等说明会出现等差子序列 判断两个串是否相等，我们很容易就可以想到哈希，再用线段树维护哈希值即可 代码： #include<cstdio> #include<iostream> #define ull unsigned long long us...

传送门 题意： 定义 f[0]=0,f[1]=1,f[n]=f[n−1]+f[n−2],n≥2  f [ 0 ] = 0 , f [ 1 ] = 1 , f [ n ] = f [ n − 1 ] + f [ n − 2 ] , n ≥ 2  给出n,m，求 Πni=1Πmj=1f[gcd(i,j)]%1e9+7  Π i = 1 n Π j = 1 m f [ g c d ( i , j ) ] % 1 e 9 + 7  多组数据，n,m<=1e6 Solution： 做多了就会发现莫比乌斯反演都是套路题 然而就算知道是套路题自己也推不出来QAQ 首先改变式子为枚举gcd 原式  =∏...

传送门 题意： 给出一个序列a，两种操作 1.将[l,r]这段区间所有的数 ai  a i 换为 cai  c a i  2.求[l,r]这段区间的和，对p取模  1≤n≤50000; 1≤m≤50000; 1≤p≤100000000; 0<c<p; 0≤ai<p  1 ≤ n ≤ 50000 ;   1 ≤ m ≤ 50000 ;   1 ≤ p ≤ 100000000 ;   0 < c < p ;   0 ≤ a i < p  Solution： 这道题有些类似于BZOJ3884和Codeforces906D 对一个位置执行多次1操作后，φ的值就变成了...

传送门 题意： B 君在玩一个游戏，这个游戏由 n 个灯和 n 个开关组成，给定这 n 个灯的初始状态，下标为从 1 到 n 的正整数。 每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。 但是当操作第 i 个开关时，所有编号为 i 的约数（包括 1 和 i）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。 B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。 这个策略需要的操作次数很多， B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 k 个开关使所有灯都灭掉，那么他将...

传送门 题意： 求 ∑n−1i=0∑m−1j=0max((i xor j)−k,0)  ∑ i = 0 n − 1 ∑ j = 0 m − 1 m a x ( ( i   x o r   j ) − k , 0 ) ,多组数据  ，，，，T=5000，n≤1018，m≤1018，k≤1018，p≤109  ， ， ， ， T = 5000 ， n ≤ 10 18 ， m ≤ 10 18 ， k ≤ 10 18 ， p ≤ 10 9  Solution： 看到两个求和符号下意识想到莫反… 等等 为什么莫反会有异或操作？？？ … 最终发现是一道二进制下的数位dp：  f[i][0/1][0/1][...

传送门 题意： 给出n个数 ai  a i ，求 ∑ni=1∑nj=1lcm(ai,aj)  ∑ i = 1 n ∑ j = 1 n l c m ( a i , a j )   1≤N≤50000;1≤ai≤50000  1 ≤ N ≤ 50000 ; 1 ≤ a i ≤ 50000  Solution： 再次被数论题制裁 太弱推不出式子来… 然后就去看了题解 我们把h[i]设为是i的倍数的a的两两数的积的总和，g[i]设为gcd为i的两两数的积的总和 那么有一个显然的结论： h(i)=∑i|jg(j)  h ( i ) = ∑ i | j g ( j )  根据莫比乌斯反演公式我们可以知道 ...

两道都是权限题… 题意： 给出一张n个点，m条边的图，同一条边不能走两次，每条边正着走与反着走所需要的时间可能不同，求一个从1开始的大于一个点的最短环  N<=10000,M<=200000,1<=W,V<=10000  N <= 10000 , M <= 200000 , 1 <= W , V <= 10000  Solution: 网上的题解都是构造…然而并不是很理解 听学长讲了一种神奇的解法，感觉非常妙： 我们可以发现，我们走出一步后，就会变成一个裸的最短路问题，所以最暴力的解法就是枚举从1开始能到达的点，然后从这个点开始走最短路（不经过来...

传送门 题意： 给出一个字符串，分别求出前1~n位所含的不同的字符串个数  n<=100000  n <= 100000  Solution： 看这道题的时候感觉到有后缀排序的那么点意思，然而只是感觉到而已… 正解太TM神了 考虑对于一个字符串，他所产生的本质不同的字符串个数为所有后缀的长度和减去height数组的和 那么我们如何动态的求呢？我们每次是在字符串后面增加一个字符，这样所有的后缀都会改变，非常不好维护，所以我们就翻转整个字符串，每次在字符串前面加字符，这样旧的后缀就不会改变，只会增加一个新的后缀 那么我们的问题就变成了：增加一个字符串，求他与前面的所有字符串中最长的LC...

传送门 题意： 棋盘上的一个棋子，给出他的两种移动方式： 1. (u,v)−>(u+Ax,v+Ay)  ( u , v ) − > ( u + A x , v + A y )  2. (u,v)−>(u+Bx,v+By)  ( u , v ) − > ( u + B x , v + B y )  现给出一些不能走的障碍点n个，求(0,0)到(Ex,Ey)的方案数  |Ax|,|Ay|,|Bx|,|By|<=500,0<=n,Ex,Ey<=500;Ax∗By−Ay∗Bx≠0  | A x | , | A y | , | B x | , | B y | &...

第一次参加省选 好紧张QWQ 简单的记录一下都发生了什么 DAY-1 学不进去PWP 晚上开包出了张橙 很慌 DAY0 正逢假期 所以就顺路回了趟老家_(:з」∠)_ _(:з」∠)_  在车上补完了京紫 并且得知了京紫要出续集的消息 激动得不行PWP violet天下第一 下午到酒店 给房间的门锁坏了 给换了两个大单间hhh这波血赚 晚上去试机的时候按照惯例写了个sort和优先队列开始对拍 看旁边一个在写树剖另一个在写LCT 感到很方 于是又写了一个后缀数组接着就开始颓扫雷 回来后复习了一下各大板子，在群里奶人，最后颓了一会崩崩崩，在深渊搞了一波事情 总算是又回到了苦痛 睡觉时睡不着觉 左滚...

传送门 题意： 你需要给给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n首曲目，每首曲目都会有一个难度d，游戏内第i首曲目会在玩家Pass第 ⌊ik⌋  ⌊ i k ⌋ 首曲目后解锁。 安排这些曲目的顺序，使得每次解锁出的子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个i满足 di≥d⌊ik⌋  d i ≥ d ⌊ i k ⌋ 。 输出字典序最小的方案。  1≤n≤500000  1 ≤ n ≤ 500000  Solution： 考场上一眼了一个做法：将权值从大到小排序，对于每个点贪心的放最大的符合条件的数，然后递归下去 但是这样的做法只适...

传送门 题意： 有n位选手和m位导师，每位导师战队有容量限制 bi  b i 。 每位选手有一张志愿表。对于每位选手，导师之间允许并列（最多允许C位导师并列）。所有选手有一个排名，选手之间不允许并列。 导师录取的规则可以简单概括为：对每位选手，在优先满足更高位选手的前提下，尽可能满足该选手最高位志愿。 每位选手有一个理想的志愿s_i（梦想），表示他希望被s_i或更高位的志愿录取。 求： 1.每位选手的最终录取情况。 2.每位选手至少要上升几名，才能被理想的志愿录取（实现梦想）。  n,m≤200 C≤10  n , m ≤ 200   C ≤ 10  Solution： 考场上只想到了费用流，...