使用LaTeX写作的快感

快感 我们终于不用不用看到.ppt,.doc等一系列的后缀名,也不用安装office,WPS等一系列的文本编辑器了。 所有的文件将会变成.pdf。查看只需要浏览器。也不需要担心各种不兼容的问题。能够轻松排版,还能完美支持数学公式的插入。 原因是使用了一种名叫$\LaTeX$的格式。只需要知道怎么写.tex的源文件,就能将它编译成.pdf。 缺陷 使用$\LaTeX$的缺点就是会有一定的台阶。要学习源代码的结构,要安装$\TeX$的引擎(占用空间很大),得到的文件也不直观,需要不断地编译。 编写 编写.tex源文件只需要使用记事本或gedit,或使用一些IDE ......

NOIP2009道路游戏

题目描述 小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段 马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n 个机器人工厂编号为 1~n,因为马路是环形的,所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在 一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n,并规定第 i 段马路连接第 i 个 机器人工厂和第 i+1 个机器人工厂(1 ≤ i ≤ n-1),第 n 段马路连接第 n 个机器人工厂和第 1 个机器人工厂。 游戏过程中,每个单位时间内,每段马路上 ......

[WC2018]即时战略

题目大意 这是一道非常有趣的题,也是我第一次在现场遇到的交互题。 给定一棵树(选手并不知道),一开始只有1号点是已知的。交互库中提供了一个函数explore(x,y),给这个函数一个已知节点x和(未知)节点y(x!=y),它会返回x到y的链上的第二个点,如果返回的点未知,可以让它变为已知。 要求调用<=T次explore函数,使得树上所有点都变为已知节点。 具体看题目链接 Windows的同学建议看LOJ的题面 Solution 赛场上,我只会写暴力,好像连一条链的都写挂了,然后成功拿到25分的好成绩(大众分70),然后离Ag线差了一分(此处应 ......

弦图染色问题

关于弦图和弦图的各类应用,陈丹琦的论文中已经介绍的非常清楚。 弦图与区间图 接下来我将用自己的语言解释一下弦图的染色问题 先来说几个概念 子图: 图$G=(V,E),G’=(V’,E’),V’\subseteq V,E’\subseteq E$,则认为G’是G的一个子图 诱导子图:图$G=(V,E),G’=(V’,E’),V’\subseteq V E={ (u,v)|u,v\in V,(u,v)\in E } $,则认为G’是G的一个诱导子图 团: 图G的一个子图$G’=(V’,E’)$,G’是关于V’的完全图 极 ......

bzoj 3238 差异

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3238 后缀数组+单调队列 这是一道后缀数组的模板题。 简单来说,就是先用后缀数组求出h数组。 然后利用单调队列在o(n)的时间复杂度下求出任意两个后缀的最大公共前缀长度的和。 大家看代码理解吧。 #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cstring&gt; using namespace std; long long ans; char st[510000]; int sum[510000],c[510000],h[510000],sa[2][510000],rk[2][510000]; in ......

证明伸展树与动态树的时间复杂度

Splay时间复杂度证明 定理0 若x=y+z+1,那么$2\lg(x)-\lg(y)-\lg(z)\geq 2$ 证明. $2\lg(x)-\lg(y)-\lg(z)$ $=\lg((y+z+1)^2)-\lg(y)-\lg(z)$ $=\lg(\frac{(y+z+1)^2}{yz})$ $=\lg(\frac{2yz}{yz}+\frac{y^2+z^2+1+2y+2z}{yz})$ $\geq \lg(2+\frac{y}{z}+\frac{z}{y})$ $\geq \lg(2+2)$ $=2$ 定理1 在一棵n个节点的Splay中,对一个节点进行splay操作的时间复杂度为均摊复杂度为$O(\log n)$ 证明. 设size(x)表示节点x的子树大小。势能分析,设节点的势能$r(x)=\lg(size(x))$。 对于Zig-Zig或Zag-Zag的情况,势能的增量为 $r'(x)+r ......

[BZOJ4811]由乃的OJ

题目大意 给你一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。 有修改和询问两种共m次操作。 每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你,最后到y时,希望得到的值尽可能大,求最大值?给定的初始值v必须是在[0,z]之间。 每次修改包含三个数x,y,z,意思是把x点的操作修改为y,数值改为z。 $k<=64$ $x,y,z<2^k$ Solution 其实就是在树上的带修的多次询问的起床困难综合症。 那道题的方法 ......

浅谈快速傅里叶变换

本人太菜了,不是很懂这个东西,只是有点懂了快速傅里叶变换的一种方法,本文没有代码,只是证明了这种快速傅里叶变换的方法是正确的。 本文大量使用复数,i表示$\sqrt{-1}$。 多项式乘法 快速傅里叶变换用于快速解决多项式乘法的问题。即 设$A(x)=\displaystyle\sum_{j=0}^{n-1}a_jx^j$ $B(x)=\displaystyle\sum_{j=0}^{m-1}b_jx^j$ 令$C(x)=A(x)\times B(x)$ 则C(x)可表示为: $\displaystyle\sum_{j=0}^{n+m-2}c_jx^j$ 我们要解决的问题是已知a数组和b数组,求c数组。 举个例子:有多项式$A(x)=6x^3+7x^2-10x+9,B(x)=-2x^3+4x-5 ......

剑与魔法-解题报告

剑与魔法-解题报告 标签(空格分隔): 编程 解题报告 1.题面 剑与魔法 时间限制: 1 Sec 内存限制: 128 MB 题目描述 万老师听说某大国很流行穿越,于是他就想写一个关于穿越的剧本。 闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般,所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类:战役事件(CASE)、穿越回去事件(END)。战役事件可以选择是否参加,参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是,END事件如果满足要求 ......

【入门难度】时间复杂度符号的辨析

符号的辨析 Ο,读音:big-oh;表示渐进上界,小于等于。 ο,读音:small-oh;表示上界,小于。 Ω,读音:big omega、欧米伽;表示渐进下界,大于等于。 ω,读音:small omega;表示下界,大于。 Θ,读音:theta、西塔;既是上界也是下界,称为确界,等于。 Ο是渐进上界,Ω是渐进下界。Θ需同时满足大Ο和Ω,故称为确界。Ο极其有用,因为它表示了最差性能。 对于一个算法来说,我们常常需要计算其复杂度来决定我们是否选择使用该算法。 对于一个算法,假设其问题的输入大小为n,那么我们可以用 O(n) 来表示其算法复杂度(time comple ......