爱悠闲 > 分类 >

BZOJ 第7页

BZOJ 3261 最大异或和 可持久化Trie树
题目大意:给定一个序列,提供下列操作: 1.在数组结尾插入一个数 2.给定l,r,x,求一个l<=p<=r,使x^a[p]^a[p+1]^...^a[n]最大 首先我们可以维护前缀和 然后就是使x^sum[n]^sum[p-1]最大 x^sum[n]为定值,于是用Trie树贪心即可 考虑到l-1<=p-1<=r-1,我们不能对于每个询问都建一棵Trie树,但是我们可以对于Trie数维护前缀和,建立
BZOJ 1499 NOI2005 瑰丽华尔兹 单调队列
题目大意:给定一个m*n的地图,一些点有障碍物,钢琴初始在一个点,每个时间段可以选择向给定的方向移动一段距离,求最长路径长 朴素DP的话,我们有T个时间段,每个时间段有m*n个点,n个时间,一定会超时 考虑到一个时间段所有的更新操作都是相同的,我们可以考虑单调队列优化 设队尾为(x,y),新插入的点为(x',y'),那么当Distance( (x,y) , (x',y') ) <= f[x'][y
BZOJ 1026 SCOI2009 windy数 数位DP
题目大意:求[a,b]区间内有多少个数满足任意相邻两个位置上的数>=2 首先将[a,b]分解为[1,b]-[1,a-1] 然后令f[i][j]为以i开头的j位windy数有多少个 然后十进制拆分即可 此题有些要讨论的地方: 1.小心爆int 2.最后一位要单独讨论 3.已经确定的数字是否不满足windy数的条件 4.一开始的[0,99...99]的区间需要单独计算 #include<cstdio>
BZOJ 1833 ZJOI2010 count 数字计数 数位DP
题目大意:求[a,b]间所有的整数中0~9每个数字出现了几次 令f[i]为i位数(算前导零)中每个数出现的次数(一定是相同的,所以只记录一个就行了) 有f[i]=f[i-1]*10+10^(i-1) 然后照例十进制拆分 其中计算[0,999...9]的时候要从1~9枚举最高位,然后其余位调用f[i-1]即可 剩余部分已知位直接乘,未知位调用f[i] #include<cstdio> #includ
BZOJ 2728 HNOI2012 与非 高斯消元
题目大意:给定k位二进制下的n个数,求[l,r]区间内有多少个数能通过这几个数与非得到 首先观察真值表 我们有A nand A = not A 然后就有not ( A nand B ) = A and B 与和非都弄到了,我们就可以做出一切逻辑运算了,比如说或和异或 A or B = not ( ( not A ) and ( not B ) ) A xor B = ( A or B ) and
BZOJ 2783 JLOI2012 树 DFS
题目大意:给定一棵有根树,每个节点有权值,求有多少链上的权值和为S,要求链上节点的深度必须单调(即这条链由某个节点出发指向根) DFS一遍,当深搜到一个点时将这个点加入队列,同时队头向后调整,使队列中元素之和<=s,记录ans 当一个点出栈时将队尾删除,同时队头向前调整,使队列中元素之和刚好<=s 这题1s略卡时间。。。不过我旁边的哥们用nlogn的算法超时700ms过去的0.0 这怎么过去的0.
BZOJ 1901 Dynamic Rankings 主席树
题目大意:可修改的区间第k小 这个主席树卡了我两天。。。切掉Count On A Tree 之后我就一直认为带修改的主席树是树状数组套可持久化线段树。。。其实我被误导了。。。 尼玛带修改的主席树和可持久化线段树毛关系都木有啊!!! 那就是动态的权值线段树啊啊啊啊啊啊啊!!! 好吧这里给不明白主席树的孩纸一些简介: 1.外层树状数组 2.里层线段树 3.线段树动态开节点。仅此而已。和可持久化完全没关
BZOJ 2734 HNOI2012 集合选数 状压DP
题目大意:给定n,求集合S={1,2,3,...,n}有多少子集满足对于任意集合中任意两个数x和y,x≠2y并且x≠3y 原题解见 http://www.cnblogs.com/Randolph87/p/3677786.html 对于n以内任意与6互质的整数x,我们列出一个矩阵 x 3x 9x 27x ... 2x 6x 18x 54x ... 4x 12x 36x 108x ... ... 向下
BZOJ 1072 SCOI2007 排列perm 状压DP
题目大意:给定n个数字,求这些数字的全排列中有多少数能被d整除 令f[i][j]为状态为i,余数为j的方案数 枚举最高位转移 小心爆int #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,d,ans,f[1<<10][1<<10],digit[1
BZOJ 1867 NOI1999 钉子和小球 动态规划
题目大意:给定一个钉子阵,小球从最上方的钉子释放,求到达最底端某个位置的概率 只需要DP就好了 f[i][j]表示小球落在第i行第j个钉子上的概率 如果一个点有钉子 f[i+1][j]和f[i+1][j+1]平分这个点的概率 如果一个点没有钉子 f[i+2][j+1]得到这个点的全部概率 最后输出f[n+1][m+1]即可 注意不能输出回车 否则PE 无视这凶残的结构体操作符重载吧0.0 #inc