FFT 学习笔记

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

20160916测试

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

T1

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

20160910测试

T1

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

OI 模板总结

OI模板总结

数学模板

快速幂

「SCOI 2016」「BZOJ 4571」美味

分析

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

SPFA-SLF优化

SPFA【SLF优化】

SLF

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

pb_ds优先队列学习笔记

pb_ds库

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

「SuperOJ 729」迷宫花园

题目描述

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

「APIO 2012」派遣-PairingHeap

题目描述

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

「SuperOJ 773」集合的运算

题目描述

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

「SuperOJ 516」加边

加边

题目描述

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

输入格式

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

输出格式

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

为hexo首页随机生成配图

为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代码的替换

「SuperOJ 381」最佳路线

最佳路线

题目描述

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.”(有句号);
如果这条观光路线存在就输出经过的最小长度。

「SuperOJ 225」计算数字

计算数字

题目描述

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

输入格式

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

输出格式

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

「SuperOJ 224」查找

查找

题目描述

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

输入格式

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

输出格式

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

「SuperOJ 222」破译密码

破译密码

题目描述

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×