典题。题目不难，注意细节就行。#include<iostream>#include<iomanip>#include<cstdio>#include<vector>#include<stack>#include<queue>#include<bitset>#include<map>#include<set>#include<unordered_map&

您的名字。做法好像和其他题解不太一样。空间少个\(\log\)，而且常数小。description给定长度为\(n\)的字符串\(S\)。\(Q\)次询问，第\(t\)次给定字符串\(T_t\)以及正整数\(l,r\in[1,n]\)。每次询问回答\(T_t\)有几个本质不同子串在\(S_{l\dotsr}\)中没有出现过

我永远喜欢数据结构题目传送门给出字符串\(s\)以及\(q\)个询问，第\(i\)个询问给出一个串\(t_i\)以及一个区间\([l_i,r_i]\)。记\(s[l,r]\)为字符串\(s\)第\(l\)位到第\(r\)位字符顺次拼接而成的子串。形式化地，\(s[l,r]=\overline{s_ls_{l+1}\dotss_r}\)

链接：P4768[NOI2018]归程观察一下题目，如果没有车，求一个单源最短路就行了（但不要使用一种广为人知的最短路算法）现在考虑有车的情况，显然最优策略是坐车到离\(1\)号节点最近的车能去的点下车。于是我们还是可以预处理每个点到\(1\)号节点的最短路，每次从节点\(v\)开始广搜它能去的所

题目描述小A被选为了ION2018的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。由于ION已经举办了很多届，所以在题目命名上也是有规定的，ION命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字

题意求解下列同余方程组，\[\begin{cases}b_1x\equiva_1\pmod{m_1}\\b_2x\equiva_2\pmod{m_2}\\\dots\\b_nx\equiva_n\pmod{m_n}\\\end{cases}\]其中，\(n\leqslant10^5,m_i\leqslant10^8,lcm(m_i)\leqslant10^{12},a_i\leqslant

T1BS5463【NOI2018模拟7】xiz考场A了，猜的结论。求出每个位置上一个和他相同的数的距离，进行KMP。但是每个数在\(B\)中第一次出现的位置不好处理，就猜了个结论——KMP的两个循环中相等的判断方式相同就可以了（至今不知道是否一定是这样），改动一下两个数相等的判断就完了。详解T

给定串\(S,T_{1,\cdots,q}\)，每次询问是\(S[l_i,r_i]\)的子串但不是\(T_i\)的子串的本质不同子串个数。\(|S|\le5e5,q\le1e5,\sum|T|\le1e6\)。我们先考虑\(l=1,r=|S|\)怎么做。显然我们使用SAM可以简单计算出\(T_i\)的本质不同子串数，那么我们肯定想算出来\(S\)

题面步行的最小距离很容易求，dij随便求一下每个点的最短路，然后找到与\(v\)能相互坐车到达的点，对这些点的最短路都有可能是答案，取个\(\min\)即可。所以本题最大的问题是怎么找到在水位线为\(p\)时，与\(v\)能相互坐车到达的点。可以想到只保留海拔大于\(p\)的边，因为只要考

【NOI2018】冒泡排序Description最近，小S对冒泡排序产生了浓厚的兴趣。为了问题简单，小S只研究对\(1\)到\(n\)的排列的冒泡排序。下面是对冒泡排序的算法描述。

这是一个悲伤的题目，自这道题后，\(\text{Noi}\)再无\(\text{SPFA}\)。首先讲一下重构树是啥。重构树是基于\(\text{kurskal生成树}\)算法的一棵树，对于每一次合并一条

题目描述[NOI2018]归程思路题目说，所有海拔\(\leqp\)的边都会有积水，因此所有的边分为了两个集合\(S_车,S_步\)，其中\(S_车\)所有的边的海拔都\(>p\)，\(S_步\)反

题面传送门牛逼题，第一步转化都想不到。首先题目要求的是选出两条路径\((x_1,y_1),(x_2,y_2)\)满足有交，并且并的部分减去\(w_1+w_2\)最大。不妨假设\(p_1\)是\(x_1\)与\(