最大MOD值 题意：有一个长度为n的数列a,求数列中      a   i    %    a   j    (    a   i    >    a   j    )    a_i\%a_j(a_i>a_j)   ai​%aj​(ai​>aj​)的最大值。n<=2e5       a   i    <   =   1   e   6    a_i<=1e6   ai​<=1e6  例: n=3 a: 3 4 5      m   a   x   (    a   i    %    a   j    )   =   2...

题目描述 给出一个     n   ∗   m    n*m   n∗m的矩形，然后用     1   ∗   2    1*2   1∗2大小的多米若骨牌去填充     n   ∗   m    n*m   n∗m的这个矩形，问有多少种填充方法。     n   ∗   m   <   =   100    n*m<=100   n∗m<=100 题外话：从刘汝佳的算法竞赛入门经典学习来的,这里自己总结一下 轮廓线动态规划 轮廓线动态规划是状态压缩动态规划的一种，只不过不是一行一行的压，而是一条一条地像轮廓线一样的压。 这种题目可看做多段图的问题，可以根据一...

prufer 数列学习笔记 今天学习了     p   r   u   f   e   r    prufer   prufer数列(编码),可以解决无根树计数的问题(带标号的无根树) 主要参考了这篇学习笔记和Matrix67的证明。 更好的体验请点这里  正文 prufer数列是无根树的编码表示，对于任意一颗n个节点的带编号的无根树，有唯一一串长度为n-2的prufer编码。 求法 对于一颗带标号的无根树，我们规定无根树中度数为1的节点是叶子节点，接着我们每次找出编号最小的叶子节点，写下与它相邻的节点的编号，然后删掉这个节点，如此反复知道这颗树只剩下两个节点为止。 例如： 对于如下的一颗节点...

ncurses库是一个Linux系统下的图形支持的函数库,使用方法可以阅读官方的手册，这里列出了里面许多有用的函数。 “ncurses.h” 包含 “stdio.h” 使用手册 安装 $ sudo apt install libncurses5-dev  编译时添加链接: 编译命令 g++ a.cpp -o a -l ncurses  函数列表 1.初始化函数 raw()和cbreak() 这两个函数用来关闭行缓冲,即读入后不会等待回车(好像也不会回显字符)。raw()模式读入字符不带信号，cbreak()会带信号,所以raw()可以读入’CTRL-C’,‘CTRL-Z’ echo()和noe...

K-Dimension-Tree (KDT) 宣传一波个人博客 顾名思义，kd树其实就是多维二叉树（空间二叉树的一种特殊情况）， 里面储存着k维的点的信息，是对k维空间进行划分的一种数据结构。 在竞赛中一般用来解决二维空间和三维空间的信息检索 KD树可以解决以下几个任务:   KNN问题。即查询离某个点第k邻近的点  查询最近最远（就是 KNN问题）  查询矩阵和  图像处理（与竞赛无关）  对于KD树,我们可以把它分为两部分   KD树的构建  对于KNN问题的最邻近查找算法  KD树的构建 KD树是一种平衡二叉树，它的各种操作都与我们学过的数据结构方法相似，对于我们一点也不陌生，很好理解。...

                                结构体运算符的简单重载 在算法竞赛中我们经常会使用结构体来保存我们需要的变量,但在我们需要进行排序或使用一些需要运算符的STL容器时,我们往往会定义一个函数cmp来保存,但这不是一个万全的方法. 假如现在需要保存每个人的名字,身高,年龄等信息 我们很容易想到要用结构体 来进行保存  const int maxn=1e6; struct people{ std::string name; unsigned int age; unsigned int height; }pp[maxn]; 设我们现在需要按照name来进行排序 一般我们...

                                       ST表  ST表是用来解决RMQ（Range Maximum Query 区间查询最值)问题的一种方法。  基本流程： 对于一个数组a( 范围为 1   ---  n  )查询区间 [ l , r ] 中的最值（这里以最大值为例），我们可以分为以下几步。   分治思想：把问题分为两部分                              1        先求出 [l, (l+r)/2] 和 [ (l+r)/2+1,r]的最大值                             2            ...

NOIP 2017 小凯的疑惑  思路  a,b 互质 求最大不能表示出来的数k 则k与 a,b 互质  这里有一个结论：（网上有证明）不过我是打表找的规律 若 x,y(设x<y) 互质 则 :      n   x   ≡    nx\equiv   nx≡a (mod y)若将x依次加倍则可以得    nx mod y ans     x a   2x 2a mod y   3x 3a mod y   4x 4a mod y   … …   y*x y*a mod y    这时a的值刚好把 0 ~ y-1内的所有数字都遍历了一遍。 设 k>x*y ,如果我们要用x,y来拼出k...

完全平方数 题目描述 题目描述 小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。 这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。 然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？ 输入输出格式 输入格式： 包含多组测试数据。文件第一行有一个整数 T，表示测试数据的组数。 第2 至第T+1 行每行有一个整数Ki​，描述一组数据，含义如题目中所描述。...

BZOJ3207 花神的嘲讽计划Ⅰ 背景 花神是神，一大癖好就是嘲讽大J，举例如下： “哎你傻不傻的！【hqz：大笨J】” “这道题又被J屎过了！！” “J这程序怎么跑这么快！J要逆袭了！” …… 描述 这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录：   “J你在讲什么！” “我在讲XXX！” “哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！” “……”   “J你XXX讲过了没？” “……” “那个都不讲你就讲这个了？哎你傻不傻的！” “……” DJ对这种情景表示非常无语，每每出现这种情况，DJ都是非常尴尬的。 经过众蒟蒻研究，DJ在讲...

n  <mtext>   </mtext>  d   a   y    n ~ day   n day前学习了     F   W   T    FWT   FWT，一直没有打，最近打了板子，来总结一下      F   W   T    FWT   FWT是利用分治的方法来求解多项式诸如       C   k    =  <munder>  ∑    i   +   j   =   k   </munder>   A   i    ⊕    B   j   <mtext>   </mtext>  (   ⊕   =  ...

换根dp 树形     d   p    dp   dp的一个内容，对于有根树的     d   p    dp   dp值可以     O   (   n   )    O(n)   O(n)求的题目，而要求考虑无根树的方法。 方法比较简单，下面来看一道例题POJ3585 题目描述 有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。 我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。 每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。 河道中单位时间流过的水量不能超过河道的容量。 有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之...

邻接链表的使用 我们知道，如果一个图比较小的话，可以使用邻接矩阵来存图，但当图比较大的话，再使用邻接矩阵，那么空间就会爆炸,所以我们采用邻接链表来优化空间。 构建方法 顾名思义，邻接链表也是一种链表，包括表头，指向的边和下一个链表的位置,若为带权图，还能保存权值。 int head[maxn];//表头索引 struct edge{ int to,next,w;//to表示指向的点，next表示链表的下一个位置，w表示边权 }e[maxn<<1];//无向图为两倍空间  添加元素的方法也十分简单,就跟链表的构建方法一样。 int cnt;//新建链表的位置 void add(int...

洛谷     P   1654    P1654   P1654 题解 数学期望这一块不太好，每次考试都想不出期望的题，打几道练习题练练手。 题目简述 给一个长度为     n    n   n的     01    01   01串的每一位为     1    1   1的概率,一个串的分数为其中每一个长度为     x    x   x的全     1    1   1串的长度的立方和,即      x   3     x^3   x3,求期望分数。（每一个     1    1   1只会作为一个全     1    1   1串的一部分而只被算一次) 解题方法 考虑先从分数为     ...