彩灯 线性基基础题（     1   l   l   <   <   i    1ll<<i   1ll<<i一定要写     l   l    ll   ll !） 单纯地想在线性基专题中水一篇博客，hhh 题意：没啥讲的 思路：太简单了（求线性空间的秩） 题面描述 #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) using ...

装备购买 哈哈，这才是真正的线性基呀！跟线性代数里面学的一模一样！ 题意： 求给定矩阵的秩，并且所选的基底尽可能小（“小”的定义在题面中） 思路：  像平时做的二进制线性基一样插入即可 插入前按照     c    c   c的值先排个序，就当做贪心了吧 （补充：如果所有条件全部换成整数，而不是实数，则不能当做线性基处理。比如将此处的     m    m   m维换成     1    1   1维，那么这个问题就变成背包问题了，比如货币系统）  题面描述 #include "bits/stdc++.h" #define hhh printf("hhh\n&qu...

小Z的袜子 我的莫队之旅开始啦！ 题意：求区间[l,r]中相同数字的数量关系（具体见题） 思路：（莫队思路）  将所有询问按照左端点     l    l   l所在块进行排序，若左端点属于同一块，则按照右端点排序（不用按照左端点具体大小排序啦！） 排序的一点优化，为后面求解过程加速：对于左端点属于第奇数块的询问，将它们按照右端点从小到大排序；对于左端点属于第偶数块的询问，将它们按照右端点，从大到小排序。这样相反的排序可以让     r    r   r指针不用每次都从最右边跑到最左边。 莫队的四个     w   h   i   l   e    while   while循环，暴力的模拟 ...

小B的询问 刚写完小Z的袜子，然后删了些代码，反手把这题A了。。。 题意、思路：见小Z的袜子 #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) using namespace std; typedef long long ll; typedef pair<int,int> pr; inline int read() {int x=0;char c=get...

数颜色/维护队列 写完这题差不多直接1A？（第一次没吸氧，T了） 题意：  询问：求区间     [   l   ,   r   ]    [l,r]   [l,r]之间有多少种不同的数字 修改：修改某个位置的数字 不强制在线  思路：（带修莫队板子）  基本与普通莫队一样，仅仅额外加上了时间这个维度（其实看代码更好懂），甚至按奇偶排序的小技巧也很好用！ 分块的大小也有讲究（当然也可以采用其他玄学分块）： 设分块大小为     a    a   a，莫队算法时间复杂度主要为     t    t   t轴移动，同     r    r   r块     l   ,   r    l,r   l...

有向图 题意：  意思是当Bobo位于     n   +   1   ,   n   +   2   ,   .   .   .   ,   n   +   m    n+1,n+2,...,n+m   n+1,n+2,...,n+m节点后就不会移动了，求Bobo从节点     1    1   1开始经过无穷时间后Bobo停在这     m    m   m个点的概率分别是多少 思路：  这个问题告诉要我们求Bobo开始在节点     1    1   1处的答案，我们可以先求解一个子问题的答案，就是Bobo最终停在     n   +   1    n+1   n+1处的概率 对于这个子...

Distinct Substrings 写完这题发现自己曾经的扩展KMP板子（     Z    Z   Z函数）太laji了！现在的板子简洁又漂亮，并且这题很妙！ 题意： 给定一个长为     n    n   n的数字串，问在尾部独立的添加     1    1   1~     m    m   m这些数字分别会使原串增加多少本质不同的子串 思路：  看到本质不同，首先想到了后缀自动机，每次在结尾插入元素后只需要知道插入元素的父节点是谁，然后利用     l   e   n   [   n   p   ]   −   l   e   n   [   f   a   [   n   p  ...

重新记录一个板子  字符串下标从     0    0   0开始（也可以很容易得改成从     1    1   1开始）      Z    Z   Z数组的     Z   [   0   ]    Z[0]   Z[0]不是良定义的，默认为     0    0   0；如果有必要，可以在     g   e   t   Z   (   )    getZ()   getZ()的最后进行     Z   [   0   ]   =   n    Z[0]=n   Z[0]=n的修改      S   [   j   ,   j   +   z   [   j   ]   −   1  ...

糖果公园 由于国庆节比赛过多，因此这题断断续续写了好几天。。。 题意： 给定一棵树，每个点的颜色，每种颜色的价值（由遍历次数和颜色种类决定）。然后有一种操作和一种询问： 操作0：修改某个点的颜***r> 询问1：询问     x   ,   y    x,y   x,y两点之间总价值（价值定义具体见题意） 思路：树上莫队+带修莫队   （关键词：括号序）树上莫队核心：处理出树的括号序（括号序：在     d   f   s    dfs   dfs过程中进入和离开某个点时都要打上标记），在括号序上进行普通莫队（还是有点不普通）。  （关键词：遍历次数的奇偶）括号序上的莫队算法：关键在于知...

喵星球上的点名 一道据传言有多种解法的题（不过大多是因为数据太弱过的）。先用AC自动机搞了一上午，无果；看了题解，后缀自动机+莫队？正好是我最喜欢的算法之一+正在学习的算法，就这个了！然后由于广义自动机的     l   a   s   t    last   last标记有个地方忘了初始化。。。然后在大物课上调了三节课，洛谷一页都是我，hhh 题意： 有     N    N   N个同学，名字包含姓和名；然后老师要点     M    M   M次名，某次点名若是某个同学的姓或者名的子串，则这位同学要答到。求：  每次点名会有多少同学答到      M    M   M次点名后每位同学分别...

大爷的字符串题 莫队板子题。。。因为离散化的     n   n    nn   nn不小心写成了     n    n   n，卡了两小时。。。 题意：贪心后正确的题意： 求区间众数的数量。 思路：没啥思路，就想水一篇博客，hhh！  莫队正常的统计每个数字的出现次数（整体加一个常数，不然过程中可能是负数） 另开一个数组统计某种出现次数有几种数 记录众数即可  代码 #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'...

小清新人渣的本愿 这两天写了些     b   i   t   s   e   t    bitset   bitset的题，但都不想写题解。。。正巧这道题还结合了莫队，也是正在学习的，就记录一下吧。 题意： 给定一个     a    a   a数组，有三种询问：  询问     [   l   ,   r   ]    [l,r]   [l,r]区间中是否有差为     x    x   x的数对； 询问     [   l   ,   r   ]    [l,r]   [l,r]区间中是否有和为     x    x   x的数对； 询问     [   l   ,   r   ]   ...

The Kouga Ninja Scrolls 这题可真暴力呀！曼哈顿距离转成切比雪夫距离后大力线段树搞即可！第一次把线段树封装一下，为了     x   ,   y    x,y   x,y两个坐标不用写两棵线段树，也是第一次把     p   u   s   h    push   push_     u   p    up   up写成结构体     m   e   r   g   e    merge   merge形式，为了方便query时的区间合并。而且写好后(赛后)1A，刺激！！！ 题意： 给定二维平面上     n    n   n个点（编号     1    1   1~  ...

最短不公共子串 题意： 问最短的满足：是A的子串（子序列），且不是B的子串（子序列，子序列（子串））。（共四个问题） 思路：  子串问题，考虑后缀自动机；子序列问题，考虑序列自动机；这不就成板子题了？ 然后本题要求属于前者，而不属于后者的子结构，可以考虑暴力的在两种DAG上同时跑；若前者可以跑，后者却不能跑，说明此子结构仅属于前者，好像问题就解决了？ 但仔细一想，长度为     2000    2000   2000的串子序列似乎太多了，好像不能跑完？这里我们考虑     b   f   s    bfs   bfs，记录哪些状态（二维）已经遍历；对于已经遍历过的状态，虽然此前在遍历时当前状态...