来自 [Junqi Huang] 的全部文章

使用LaTeX写作的快感

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

[WC2018]即时战略

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

[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 其实就是在树上的带修的多次询问的起床困难综合症。 那道题的方法 ......

BZOJ5250: [2018多省省队联测]秘密袭击

原题链接 Solution 先看一份官方题解:秘密袭击simple 然而作为一个连FFT都不会的蒟蒻,又怎么可能在只有五小时,写完前两题的情况下做出这题呢? 所以是时候用暴力吊标算了。 考虑枚举每个点,算出这个点作为第k大时对答案的贡献。如果直接算,可能会算重。 我们可以定义:u的权值大于v当且仅当d[u]>d[v]||(d[u]==d[v]&&u>v),记为$u\rhd v$,即d相同时比较两点的编号。 如果枚举一个点u作为第k大点,那么可以从u开始进行树形DP。 设f[u][k]表示以u为根的子树,选了点u,并且选出的联通块中有k个点权值大于根。 有个 ......

[BZOJ2006]超级钢琴

题目大意 从一个序列中,找出k段连续的子序列,且每个子序列的长度不小于L,不大于R。 一个序列的权值定义为序列中所有数的和,求k个子序列和的最大值。具体看原题。 Solution 这道题应该用主席树来做,但是太麻烦。相比起来,ST表+堆的算法显然比较方便(可能我代码写得太丑)。 考虑每次取出一段最大的合法的子序列,这样取k次。第一次取的时候,如果枚举了一个右端点r,那么r-R+1<=l<=r-L+1。 如果用前缀和sum数组表示这个区间的和,就是sum[r]-sum[l-1]。当r固定时,l也在一个固定的区间内变化,只要sum[l]取这个区间中的 ......

BZOJ3123 森林

题目大意 给一个森林,森林有n个节点m条边。 现在有两种操作: Q x y k 表示询问x-y这条链上点权的第k小。保证x,y在同一个连通块里。 L x y 表示链接x,y两点。保证x,y在不同的连通块里。 总共有T次操作,要求强制在线,last表示上一次的答案,每次x,y,k都要异或last.last初始为0. 对于所有的数据,n,m,T<=8*10^4 . Solution 因为有连接两个点的操作,所以xqj大神一眼就报出了题解:LCT。 可是我这个菜鸡怎么都想不出LCT的做法。因为还要询问点权的第k小,还要在splay上套一棵线段树。用树套树维护LCT,反正我是不会。但我相 ......

BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一条1到n的路径。 我们可以事先选出一条1到n的路径(任意),记为“主路径”。假设我们沿着这条路径由1走到n,并得到了这条路径的权值,记为ans。 再将所有环的异或和求出来。最后的答案就是在选取一些环的异或和和ans的异或和的最 ......

BZOJ2743 采花

题目大意 有n个数,每个数一种颜色。m次询问,每次询问l,r区间内除去只有一个数的颜色的不同颜色的种数。 n,m<=1000,000 Solution 刚看到题目,就想到了一种非常方便的莫队做法。看了一眼数据范围,发现要$10^9$的复杂度,卡一卡就过去了。 我会函数式线段树,于是有口胡了一个可持久化线段树的做法,就是维护出所有1~r的线段树,且1~i+1的线段树是从1~i的线段树修改几个点后继承过来的。花了10分钟写完,开数组时发现要开三个2e7的数组,空间240MB,而内存限制只有128MB,不得已,砍掉一半,数组大小定了1e7。交上去后,喜闻乐 ......

BZOJ2242 计算器

题目大意 你被要求设计一个计算器完成以下三项任务: 给定y,z,p,计算Y^Z Mod P 的值; 给定y,z,p,计算满足xy≡ z ( mod P )的最小非负整数; 给定y,z,p,计算满足y^x ≡ z ( mod P)的最小非负整数。 对于100%的数据,1<=y,z,p<=10^9,为质数,1<=T<=10。 Solution 典型的NOIP三合一题,硬是把三道题合在了一起…… 前两问就不说了(一个快速幂,一个exgcd)…… 而要怎么解决第三问呢? 要用到BSGS(Baby-Step-Giant-Step)算法。用某方姓大佬的话: 就是枚举到根号的暴力 设x=im-j $ y^x=y^{im-j}\equiv z(mod p)$即$ y^{i ......

对后缀自动机的一点认识

一个蒟蒻,在字符串方面只会Hash不会KMP,还有一点点AC自动机,竟然看起了SAM,真的很累。幸好有许多dalao的帮助(包括NBC),还有hihocoder上图文并茂的介绍,当然也有其他论文和博客,我竟然有一点点理(bei)解(xia)了SAM的代码。 对于一个字符串S,它对应的后缀自动机是一个最小的确定有限状态自动机(DFA),它接受且只接受S的后缀。 其实也能接受S的所有子串。 一些定义 endpos(s)即right(s):对于S中的一个字串s,endpos(s)是s在S中所有出现的结束位置的集合。且endpos()相同的字串属于同一种状态。 将子串重编号后: substr ......