题意：给你n个字符串，求出，f(si,sj)的意思是字符串 si 的前缀和字符串 sj 后缀最长相等部分。 题解：先对所有的字符串后缀hash，用map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字符串倒过来求，每次乘以base^ i ，这和字符串正着求每次 t=t *base + s 是一样的，可以想象一下，前后缀相同位置乘base的次数是一样的。然后遍历所有的前缀的hash，在map里找当前 hash 值出现的次数的记录下来，最后把符合条件的长度平方乘以个数加起来，即ans+=mp[hash]* i * i。但是这样会...

题意：给出矩阵的行数n和列数m，矩阵 Aij = lcm( i , j ) ,求每个大小为k*k的子矩阵的最大值的和。 题解：如果暴力求解肯定会t，所以要智取。前几天刷蓝书的时候看到这种求区间最值的可以用单调队列，这个题就是用单调队列求解。先横着算一下每个长度为k的区间的最大值记录下来，然后再把记录下来的数组竖着同样算一下，最后求和。求最小公倍数的时候，不能用__gcd()，会 t 的。这个题的矩阵不会超long long ，所以用 int 就好了，不然会超内存。（血泪史 至于单调队列是什么，可以看看这个，在acwing写题的时候看到的。https://www.acwing.com/blog...

传送门：https://www.acwing.com/problem/content/162/（acwing有视频讲解，题解，数据之类的） 题意：给你两个字符串a和b，有q次询问，每次询问输出a的所有后缀和b恰好匹配长度为x的后缀个数。 题解：这个题好微妙啊，我换了两种思路都不太对。然后看了一下大雪菜老师的视频和（传送门）这个题解，豁然开朗。 先求出 b 串的 next 数组，然后a和b串进行匹配。a 串遍历用 i，b串用 j，j 正好是b串能匹配以 i 为结尾的a串的长度，所以就是以 i-j+1 为头的串。根据 kmp 中 next 数组的性质以 i-next[j]+1 的串和 b 恰...

题意：给出n个点的权值，m次操作，操作为1时为询问，每次询问给出 l 和 r ，求 f(l,r)。操作为0时为修改权值。f(l,r)=f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)F(l,r)=f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)。 题解：首先多写算几个 l 到 r，可以发现当 r - l 时奇数的时候，f(l,r)为0；当 r - l 为偶数时，就是 l⊕l+2⊕⋯⊕r；区间异或可以用两个树状数组来完成，一个记录奇数位的前缀异或，一个记录偶数为的前缀异或。修...

昨天搞了一下午+一晚上，终于捣鼓出了一些奇奇怪怪的操作，成功发送了消息。 应实验要求，博主有幸在家里搞到了两台win7，其他的系统是不是这么操作就不太清楚了。 一开始实验指导书上是用net send发消息，然后查了一下发现win7已经没有这个功能了，可以用msg发送。 命令是  msg /server:对方IP地址 * "消息" （*的前后都要有空格） 然后你就会惊奇的发现 “ 获取会话名称时的错误 1722 ” 或者是 “ 获取会话名称时的错误 5 ”。 然后要怎么操作呢，我研究了好久博客，百度的知道啥的，还差点把电脑弄废了orz。大概步骤是这样的：   1、...

感觉指针容易错，可以用数组模拟。数组开两倍（因为如果一直从前插入从0开始下标就是负数了，数组会越界），然后双指针，l记录头的位置，r记录尾的位置，因为排序不超过十次，所以sort（nlogn）不会超时的。最开始l在2e5的位置（只要数组够大，l再往后一些也是可以的），r=l; 模拟以下操作 a从前面插入元素（就是a[--l]=x,如果r=l+1的话，就可以用a[l--]=x）； 从前面删除一个元素（++l就相当于删掉最前面的元素）； a从后面插入一个元素（就是a[r++]=x）； 从后面删除一个元素（r--就相当于删掉最后面的元素）； 将整个容器头尾翻转 ，reverse（a+l,a+r）；...

传送门：E - Restorer Distance  题意：给出四个数 N, A, R, M ，然后给出一个长度为N的序列。让一个数+1花费A，-1花费R，从一个大的数向一个小的数移动1花费M。问让所有数一样大的最小花费。 题解：三分，每次找到可以移动的最大数量*M，再加上剩下比当前数小的*A，比当前数大的*R。 1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll p[100100]; 6 ll q[100100]; 7 ll n,a,b,c; 8...

传送门：E - Restorer Distance  题意：给出四个数 N, A, R, M ，然后给出一个长度为N的序列。让一个数+1花费A，-1花费R，从一个大的数向一个小的数移动1花费M。问让所有数一样大的最小花费。 题解：三分，每次找到可以移动的最大数量*M，再加上剩下比当前数小的*A，比当前数大的*R。 1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll p[100100]; 6 ll q[100100]; 7 ll n,a,b,c; 8...

传送门：E - Restorer Distance  题意：给出四个数 N, A, R, M ，然后给出一个长度为N的序列。让一个数+1花费A，-1花费R，从一个大的数向一个小的数移动1花费M。问让所有数一样大的最小花费。 题解：三分，每次找到可以移动的最大数量*M，再加上剩下比当前数小的*A，比当前数大的*R。 1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll p[100100]; 6 ll q[100100]; 7 ll n,a,b,c; 8...

传送门：D - Game With Array 题意：让你构造一个长度为n的序列，并且n个数的和为S，问能不能找到一个1~n的数k，使得数组里找不出一个子序列的和为k或者n-k； 题解：最简单的想法肯定是让k=1，然后数组只要不出现1和n-1就好了，只要 s /n >= 2，也就是由n-1个2和一个 s-(n-1)*2 != 1 构成就可以。 1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 int main() 6 { 7 ios::sy...

传送门：D - Game With Array 题意：让你构造一个长度为n的序列，并且n个数的和为S，问能不能找到一个1~n的数k，使得数组里找不出一个子序列的和为k或者n-k； 题解：最简单的想法肯定是让k=1，然后数组只要不出现1和n-1就好了，只要 s /n >= 2，也就是由n-1个2和一个 s-(n-1)*2 != 1 构成就可以。 1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 int main() 6 { 7 ios::sy...

传送门：D - Game With Array 题意：让你构造一个长度为n的序列，并且n个数的和为S，问能不能找到一个1~n的数k，使得数组里找不出一个子序列的和为k或者n-k； 题解：最简单的想法肯定是让k=1，然后数组只要不出现1和n-1就好了，只要 s /n >= 2，也就是由n-1个2和一个 s-(n-1)*2 != 1 构成就可以。 1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 int main() 6 { 7 ios::sy...

传送门：C - Count Triangles  题意：给你四个数A，B，C，D，求有多少个三边为x，y，z （A ≤ x ≤ B ≤ y ≤ C ≤ z ≤ D）的三角形。 题解：枚举 x=A~B，然后计算当z的值大于等于C时，y为最小值B可以有多少个三角形，y为最大值C有多少个三角形。想想就可以发现 y=B~C时 其实就是一个差值为1的等差数列。然后要算出 y=B 和 y=C 时 z 比最大值D大了多少，这也是个等差数列，然后两个等差数列做差就好了。这么说可能有点乱，代码看了就明白了。 1 #include<bits/stdc++.h> 2 #define ll...

传送门：C - Count Triangles  题意：给你四个数A，B，C，D，求有多少个三边为x，y，z （A ≤ x ≤ B ≤ y ≤ C ≤ z ≤ D）的三角形。 题解：枚举 x=A~B，然后计算当z的值大于等于C时，y为最小值B可以有多少个三角形，y为最大值C有多少个三角形。想想就可以发现 y=B~C时 其实就是一个差值为1的等差数列。然后要算出 y=B 和 y=C 时 z 比最大值D大了多少，这也是个等差数列，然后两个等差数列做差就好了。这么说可能有点乱，代码看了就明白了。 1 #include<bits/stdc++.h> 2 #define ll...