两个n次多项式相加最直接的方法所需时间为O(n)，但是相乘最直接的方法所需时间为O(n²)。
快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 O(n log n)时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法，在 OI 中的主要应用之一是加速多项式乘法的计算。

这一次 3 道题都与 gcd 有关的测试,也是醉了……

T1

此题 5 分钟以内想出标算,然后 zz 地写挂,而且还能 TLE 掉…只拿了50…… 然而据 lcr 所说,此题最难!!!
思路与 gcd 相同,只是每次取 $\lfloor \frac m n \rfloor * n$ 个 $n$,然后令 $n_1 = m % n, m_1 = n$ 递归获迭代下去即可…

T1

这本来是一道水题,八个方向暴力枚举,判断一下边界就行(其实不判断边界也行),谨以此题爆 $0$ 警示自己不能再把 $n,m$ 看反……
另外此题有许多同学在 linux 下 WA,*注意 windows 下的换行符为 \r\n *,不要只 getchar() 一次,注意单独处理…

OI模板总结

数学模板

快速幂

分析

如果没有加法就是普通的可持久化trie了,加法真是烦!此题可以按位进行贪心,肯定从高位开始,每次判断这一位异或完能不能是1,即查询一段区间是否有某个范围的数,可以用主席树…

SPFA【SLF优化】

SLF

Small Label First 策略，设要加入的节点是j，队首元素为i，若dis[j] < dis[i]，则将j插入队首，否则插入队尾，可能会被卡到指数级复杂度。

pb_ds库

pb_ds??
平板电视??
pb_ds是G++编译器默认附带的一个扩展库,全称是Policy-Based Data Structures(官方传送门)…
pb_ds库里含有许多数据结构,如HashTable,trie,rb_tree,priority_queue…

题目描述

给定一个一定存在从起点到终点的路径的四联通迷宫。已知 Tar 左右方向移动的时间为 1 ，上下移动的时间为未知实数 v 。求当 Tar 从起点到终点的最短移动时间为已知实数 L 时，未知实数 v 是多少。

题目描述

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。
在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

题目描述

在计算机科学应用中，我们经常要用到集合的运算，集合的运算操作有很多，下面是我们给出的集合基本运算定义：
（1）“∪”运算：设 S，T 是 2 个集合，那么 S∪T 是由 S 和 T 的元素组成的集合。
（2）“-”运算：设 S，T 是 2 个集合，那么 S-T 是由 S 中非 T 中的元素组成的集合。
（3）“∩”运算：设 S，T 是 2 个集合，那么 S∩T 是由既是 S 又是 T 的元素组成的集合。

加边

题目描述

给出一个 N×M 的矩阵，在这个矩阵上的每一个点都有一个高度值 h 。矩阵中相邻两点是连通的，而且只能从高度高的点到达高度低的点，高度相同的点之间可以相互到达。
现在要求在图中连若干双向边，使图中任意一点 u 出发都可以到达任意的其它点 v ，问至少需要连接多少条双向边？

输入格式

第一行是两个整数：（1 \leq N,M \leq 300），其中, N，M分别表示矩阵的行数和列数。
从第二行开始，描述的是一个 N 行 M 列的矩阵，矩阵每个位置上的数字表示该位置的高度 h（1 \leq h \leq 1,000,000）。

输出格式

输出一个整数，即至少需要连接的边的数量。

为hexo首页随机生成配图

美化边框模板

1
2
3

<img src="" style="float:left;margin-right:10px;margin-top:10px;margin-bottom:10px;-webkit-box-shadow:0 0 10px rgba(0, 204, 204, .5);  
  -moz-box-shadow:0 0 10px rgba(0, 204, 204, .5);  
  box-shadow:0 0 10px rgba(0, 204, 204, .5);width:240px;height:180px;">

Java实现对html代码的替换

最佳路线

题目描述

N 个景区，任意两个景区之间有一条或多条双向的路来连接，现在 Mr.Zeng 想找一条旅游路线，这个路线从 A 点出发并且最后回到 A 点，假设经过的路线为 V1，V2，….VK，V1，那么必须满足 K>2，就是说至除了出发点以外至少要经过 2 个其他不同的景区，而且不能重复经过同一个景区。不存在这样的景区 X：从 X 出发不到达其他景区马上回到 X。现在 Mr.Zeng 需要你帮他找一条这样的路线，并且长度越小越好。

输入格式

第一行包含两个正整数：景区个数 N（N<=100），另一个是道路的数目 M（M<10000）。
接下来 M 行每行描述一条路，每一行有三个正整数 A，B，C，其中 A 和 B 分别表示这条路连接的两个景区的编号，C 表示这条路的长度（不超过500的正整数）。

输出格式

如果这条观光路线是不存在的话就显示“No solution.”(有句号)；
如果这条观光路线存在就输出经过的最小长度。

计算数字

题目描述

当连续写下从十进制整数 1 开始到某个整数 N 之间的所有整数时，能得到如下的数字序列：
12345678910111213141516171819202122 \cdots \cdots
编写一个程序，计算这个序列中的数字个数。

输入格式

输入的第一行且是唯一的一行包含：一个整数 N，1 \leq N \leq 100,000,000。

输出格式

输出的第一行且是唯一的一行应包含：由给定的整数所产生的序列的数字个数。

查找

题目描述

中考成绩出来了，许多考生想知道自己成绩排名情况，于是考试委员会找到了你，让你帮助完成一个成绩查找程序，考生只要输入成绩，即可知道其排名及同名次的人有多少。

输入格式

第一行一个正整数 n（1<=n<=1500），表示一共有 n 个考生；
第二行一个正整数 k（1<=k<=n），表示一共有 k 个待查分数；
第三行 n 个数是以空格隔开的从大到小排列的 n 个学生成绩；
第四行 k 个数是待查的成绩。

输出格式

共输出 k 行，每行三个数，分别用一个空格隔开：第一个数为待查成绩所对应的名次；第二个数为同名次的人数；第三个数为分数高于该成绩的人数。
若查找不到，本行只输出一个单词“fail!”（fail后面加一个惊叹号，引号不输出）。

破译密码

题目描述

抗日战争中，中方截获日方的信息由 n（n \leq 30000）个非负整数组成，其中每个数字都在 int 范围内。因为是日军的高端秘密，所以一时不能破获。最原始的想法就是对这 n 个数进行从小到大排序，对排序后的数按顺序依次从 1～n 进行编号，然后请你输出编号为 i 的数。