快感 我们终于不用不用看到.ppt,.doc等一系列的后缀名,也不用安装office,WPS等一系列的文本编辑器了。 所有的文件将会变成.pdf。查看只需要浏览器。也不需要担心各种不兼容的问题。能够轻松排版,还能完美支持数学公式的插入。 原因是使用了一种名叫$\LaTeX$的格式。只需要知道怎么写. …

题目大意 这是一道非常有趣的题,也是我第一次在现场遇到的交互题。 给定一棵树(选手并不知道),一开始只有1号点是已知的。交互库中提供了一个函数explore(x,y),给这个函数一个已知节点x和(未知)节点y(x!=y),它会返回x到y的链上的第二个点,如果返回的点未知,可以让它变为已知。 要求调用 …

题目大意 给你一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。 有修改和询问两种共m次操作。 每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你, …
BZOJ5250: [2018多省省队联测]秘密袭击

原题链接 Solution 先看一份官方题解:秘密袭击simple 然而作为一个连FFT都不会的蒟蒻,又怎么可能在只有五小时,写完前两题的情况下做出这题呢? 所以是时候用暴力吊标算了。 考虑枚举每个点,算出这个点作为第k大时对答案的贡献。如果直接算,可能会算重。 我们可以定义:u的权值大于v当且仅当 …

题目大意 从一个序列中,找出k段连续的子序列,且每个子序列的长度不小于L,不大于R。 一个序列的权值定义为序列中所有数的和,求k个子序列和的最大值。具体看原题。 Solution 这道题应该用主席树来做,但是太麻烦。相比起来,ST表+堆的算法显然比较方便(可能我代码写得太丑)。 考虑每次取出一段最大 …

题目大意 给一个森林,森林有n个节点m条边。 现在有两种操作: Q x y k 表示询问x-y这条链上点权的第k小。保证x,y在同一个连通块里。 L x y 表示链接x,y两点。保证x,y在不同的连通块里。 总共有T次操作,要求强制在线,last表示上一次的答案,每次x,y,k都要异或last.la …
BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一 …

题目大意 有n个数,每个数一种颜色。m次询问,每次询问l,r区间内除去只有一个数的颜色的不同颜色的种数。 n,m<=1000,000 Solution 刚看到题目,就想到了一种非常方便的莫队做法。看了一眼数据范围,发现要$10^9$的复杂度,卡一卡就过去了。 我会函数式线段树,于是有口胡了一个 …

题目大意 你被要求设计一个计算器完成以下三项任务: 给定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<=1 …

一个蒟蒻,在字符串方面只会Hash不会KMP,还有一点点AC自动机,竟然看起了SAM,真的很累。幸好有许多dalao的帮助(包括NBC),还有hihocoder上图文并茂的介绍,当然也有其他论文和博客,我竟然有一点点理(bei)解(xia)了SAM的代码。 对于一个字符串S,它对应的后缀自动机是一个 …