题目描述 喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。 例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？ 输入格式 输...

题目描述 Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he can’t predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality. To perform a rigorous study,...

AC 自动机是 以 Trie 的结构为基础 ，结合 KMP 的思想 建立的。   文章目录    解决：多模式匹配问题 字典树： Fail指针 求fail[u]指针   代码：  多模式匹配   代码：  总代码：    解决：多模式匹配问题 匹配问题： 有多个不同的模式串s[1…N] 给定长度=M的目标串t，求每个模式串s[i]总共在t中出现了多少次 跑N遍kmp 字典树： 对所有的模式串s[1…N]构建trie 字典树的根到字典树上任意节点构成的路径都对应某个模式串s[i]的前缀 概念： 状态：对字典树的任何一个结点都看做状态，对应某个模式串s[i]的前缀 转移：任意一个状态添加一个字符得...

牛客网链接   文章目录    Easy Chess 题意： 题解： Easy Problemset 题意 题解： Shuffle Cards 题解： Diff-prime Pairs 题意 题解： 代码：    Easy Chess 题意： 通过n步从左下角走到右上角，每次移动都是直线，每个格子只能停留一下，输出停留过的格子 题解： 队友做的 #include<bits/stdc++.h> using namespace std; int n; bool vis[10][10]; int main(){  scanf("%d",&n); printf(...

rope是一种可持久化数组，可持久化平衡树，采用块状链表实现 #include<ext/rope>  using namespace __gnu_cxx; rope<int>a;  rope就是一个用可持久化平衡树实现的“重型”string 库中模板计算基本和string一样简单 各种操作的复杂度都是O(log n) rope的基本操作有： x.length()/x.size() 返回x的大小 x.push_back(s) 在末尾添加s x.push_front(n) 在开头添加s x.insert(pos,s) 在pos位置插入s x.erase(pos,x) 从po...

Musical Theme(后缀数组) 题意： n个数，选取一段子序列，满足以下条件： 1.长度至少为5 2.在数列中其他位置出现过(允许转置) 3.与其他位置出现的不重叠 转置：将恒定的正或负值添加到子序列上 例如： n个数为1，2,3，4,5，6,7，8,9，10 12345是一段子序列，那6,7，8,9，10也是，因为前者加5等于后者，且两者没有重叠 题解： 人是傻的，完全不会。。。 虽然两段序列不相等，但是也是有关系的，他们的差分区间相同，也就是其两两之间的差值一样，这样题目就转化成不重叠的最长公共子串问题 可以用二分+后缀数组 我们将原数组前后相减得到的新数据做后缀数组 二分的che...

参考博客 可持久化数据结构：可以保留每一个历史版本，若所有版本都既可以访问又可以修改，成为完全可持久化（可以回滚到某个历史版本） 时间线：  可持久化线段树 可持久化下标线段树 题目： 模板 可持久化数组 你需要维护一个长度为N的数组，支持如下几种操作： 1.在某个历史版本上修改某一个位置上的值 2.访问某个历史版本的某一位置的值 做法： 用下标线段树维护一个数组，对于每个版本建一棵线段树->空间O(QN) 用可持久化的思想进行优化 当a[id]的值发生改变时，会影响从根[1,N]–>叶子[id,id]这条链上的所有点，其他点不会被影响，受影响的点只有logN个，所有我们没必要单独...

L2-005 集合相似度 (25分) 给定两个整数集合，它们的相似度定义为：N​c/N​t​​ ×100%。其中N​c 是两个集合都有的不相等整数的个数，N​t是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。 输入格式： 输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104​​ ），是集合中元素的个数；然后跟M个[0,109​​ ]区间内的整数。 之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。 输出格式： 对每一对需要...

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式： 输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。 输出格式： 在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。 输入样例： 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7  输出样例： 4 1 6 3 5 7 2  题解： 我发现pta就喜欢考前序后序这种题。。。 给出后序+中序，求层次遍历 先序，后序遍历可以确定根节点。 中序遍历可以确定左子树和右子树。 不断递...

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。  输入格式： 输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105​​ ，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1 来表示。 随后 N 行，每行按以下格式描述一个结点： 地址 键值 下一个结点 其中地址是该结点的地址，键值是绝对值不超过10 ​4 ...

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点， 其左子树中所有结点的键值小于该结点的键值； 其右子树中所有结点的键值大于等于该结点的键值； 其左右子树都是二叉搜索树。 所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。 给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。 输入格式： 输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。 输出格式： 如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间...

文章目录    介绍： 题目： 做法： 模板题 [P3806 【模板】点分治1](https://www.luogu.com.cn/problem/P3806)   代码：     介绍： 将原问题分解成若干相同形式，相互独立的子问题，各个击破 一般用来解决有关树上路径的统计和询问 题目： P4178 Tree 给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。  做法： 暴力做法；(O(n2)) 点分治做法： 选择一个点作为分治中心，令其为rt做dfs。对于一条路径path(u,v)，其要么经过rt(即lca(u,v) = = rt)，要么在某个子树sub(s...

模板题 P3806 【模板】点分治1 题目描述 给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。 详讲 关于点分治具体内容可以看这个 这里主要是详细讲讲代码： getrt是用来求重心，我们利用树型dp的思维来做，即找到该节点所有的子树，找到最大的哪一颗即可 void getrt(int u,int pa)//求重心  {  size[u]=1; maxp[u]=0; for(int i=head[u];i;i=E[i].nxt) {  int v=E[i].v; if(v==pa||vis[v]) continue; getrt(v,u); size[u]+=size[v]; m...

POJ2155 - Matrix   文章目录    题目 题解： 代码    题目 给你一个二维矩阵，初始化为0，然后可以进行两次操作： C:x,y,x1,y2 对该小矩阵内的数进行取反 Q:查询某个点是0还是1 题解： C是区间修改，Q是单点查询， 我们将二维矩阵先简化成一维矩阵的情况，C是对一段区域[l,r]取反，我们没有必要对这段区域全部操作，我们只需要对点l和点（r+1）分别加1即可，然后查询k时，我们只需要求出k的前缀和，然后mod2即可 为什么？  如果，当k1在区间[l,r]里，k的前缀和比之前就了一个1，mod2之后就说明k1被改变了一次；当k2在[l,r]之前，没有影响；在...