luoOJ1898 运动会(Race)题解

[题目传送门][1] 我看到题一脸懵逼,感觉一点思路都没有,然后想了6个小时,搞出来了一个很复杂的一堆前缀和的做法,然后错了。最后我发现其实不需要这么复杂,这题其实是一道水题,我们可以进行一些简单的分析来A了它。 由于每天各个人的分数是异或产生的,很容易想到搞一棵字典树。我又发现对于每一个人,它既要取模又要异或,肯定不会一起来算,因此可以把每一个人的得分分开来考虑。 然后我发现,在字典树中对于每一条通向某人A得分的路径上每一层的另外一棵子树中的人总是一起出现在A排名的前面或者后面,而且前 ......

傻逼的世界题目+题解

一道我自己出的水题,题目描述: 要求支持两种操作:对一个三维区间上的数都加上一个数,或者询问一个三维区间上所有数的和,三维区间的三个坐标都是整数且范围在[1,100],询问10000个。 写个三维树状数组就AC了,是不是很简单。数据: sbworld 标程: var c1,c2,c3,c4,c5,c6,c7,c8:array[1..105,1..105,1..105]of int64; num,x1,y1,z1,x2,y2,z2,n,m,p:longint; v,s1,s2:int64; function lowbit(x:longint):longint; begin exit(x and(-x)); end; procedure add(x,y,z:longint;v:i ......

HNOI2008GT考试题解

我们先简化一下问题,比如我们把字符集变成3,可以先来看下长度为3,字符串为10的答案。我们可以想到构一棵决策树,叶节点就是所有的方案,如果一个树上一个节点到根的路径上构成的字符串中有一个子串匹配就把这个点涂黑。如图是这个例子的决策树: 我们用一个补集思想,考虑对于每一个子树中叶节点被染黑的个数,我们发现其只跟前面至多有多少个字符连成的字符串是原串前缀以及树的高度有关,因此我们可以定义动态规划的状态f[i][j]表示高度为i,前面至多有j个字符连成的字符串是原串前缀的子树中被染黑的叶节点的个数。然后我们 ......

BZOJ3670(NOI2014)动物园题解

题目传送门 一道水题,据说有O(n)做法,我竟然没想到也没看懂。我的做法是KMP后用next数组搞棵树,然后在树上找一个节点前面最后一个符合条件的节点,一种方法是发现这玩意有单调性,然后用一个point数组记录下其父亲的决策点,再拿个ST表倍增或者Tarjan+二分,也可以利用轻重链搞一搞就可以了。这里用了轻重链。这种方法我只能证明有O(n^2lgn)的上界,但平均效率很高。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; ......

莫队算法入门:小Z的袜子

先说一句:这是我的第一个算法,太菜勿喷,可在评论区答疑. Description 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他 ......

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个点权值大于根。 有个 ......

浅谈平行四边形优化(包含正确性证明)

1.概述 平行四边形优化是一个神奇的东西,可以将时间复杂度为$\Theta(n^3)$的常规区间动态规划问题优化成$O(n^2)$。我们先抛出一个常规的区间DP转移方程: $$m(i,j) =\begin{cases} \displaystyle\min_{i<k\le j}{m(i,k-1)+m(k,j)+w(i,j)} &\text{if } i<j \ 0 &\text{if } i=j \ \infty &\text{if } i>j \end{cases}$$ 如果要可以进行平行四边形优化,该式还要满足:对于所有的$i\le i'<j \le j’$,有: $w(i’,j’)\le w(i,j’)$ (1.1) $w(i,j)+w(i’,j ......

BZOJ5248[2018多省省队联测]一双木棋

题目传送门 方法一 看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[1]>=A[2]>=A[3]>=…>=A[n-2]>=A[n-1]>=A[n]>=0,可以算出状态A[1~n]只有${n+m+1}\choose{m+1}$个,也就最多只有352716,可以放心的DP。 code: #include&lt;bits/stdc++.h&g ......

回文自动机

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么? 对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。 现在来看回文自动机是如何构建的。 定义变量: cnt表示pam中的节点数,pam的每一个节点分别表示一个本质不同的回文串子串 trans[u][c]表示在节点u所对应的回文子串两边加入字符c时变成的回文串对应的节点(可能不存在) len[u]表示节点u表示的回文子串的长度 fail[u]表示结尾与u表示的回文子串相同,长度小 ......

浅谈C++指针

1.指针基础 1.引用 C++有一个东西叫引用,引用相当于给对象(如:变量)起了另一个名字,引用必须用对象初始化,一旦初始化,引用就会和初始化其的对象绑定在一起,就是说引用的值就是被引用的对象的值,引用的值被修改时被引用的对象也会被修改,但不能定义引用的引用,因为引用不是对象,引用定义方式: 类型  &引用名1=对象名1 比如: int i=0; int &amp;x=i,y=i,z=i; 123 int i=0;int &amp;x=i,y=i,z=i;  ......