爱悠闲 > 分类 >

BZOJ 第5页

BZOJ 3209 花神的数论题 数位DP+数论
题目大意:令Sum(i)为i在二进制下1的个数 求∏(1<=i<=n)Sum(i) 一道很简单的数位DP 首先我们打表打出组合数 然后利用数位DP统计出二进制下1的个数为x的数的数量 最后输出∏(1<=x<=logn)x^ans[x]即可 此题的坑在于这题的组合数和数位DP的结果都是指数 对指数取模不能直接取 要取Phi(p) 于是我们对10000006取模 然后这题就WA了 因为10000007
BZOJ 3362 Navigation Nightmare 带权并查集
题目大意:给定一些点之间的位置关系,求两个点之间的曼哈顿距离 此题土豪题,不过POJ也有一道同样的题,可以刷一下 别被题目坑到了,这题不强制在线,把询问离线处理即可 然后就是带权并查集的问题了。。。将权值设为方向向量,重载+和-,按照正常权值并查集做就行了 #include<cstdio> #include<cstring> #include<iostream> #include<algorith
BZOJ 2186 SDOI2008 沙拉公主的困惑 数论
题目大意:给定询问组数T和取模数P,每次询问给定两个整数n和m,求1~(n!)的数中与m!互质的数个个数模P (m<=n) 首先T<=1W,暴力肯定过不去,我们需要预处理一些东西 首先我们知道,若x与y互质,则x+y与y也互质,x+2y与y也互质。。。 换到这道题上来说,若一个数x与m!互质,那么x+(m!)也一定与m!互质,(x+m!*2)也一定与m!互质。。。 由于n!一定是m!的倍数,于是我
BZOJ 1260 CQOI2007 涂色paint 动态规划
题目大意:给定一块木板,上面每个位置有一个颜色,问最少刷几次能达到这个颜色序列 动态规划,可以先去重处理(其实没必要),令f[i][j]代表将i开始的j个位置刷成相应颜色序列的最小次数,然后状态转移如下: 若s[i]==s[j] 则f[i][j]=min(f[i-1][j],f[i][j-1]) 即将i与右半部分并成一刷子,或者将j与左半部分并成一刷子 若s[i]!=s[j] 则f[i][j]=m
BZOJ 1264 AHOI2006 基因匹配Match 动态规划+树状数组
题目大意:给定n个数和两个长度为n*5的序列,每个数恰好出现5次,求两个序列的LCS n<=20000,序列长度就是10W,朴素的O(n^2)一定会超时 所以我们考虑LCS的一些性质 LCS的决策+1的条件是a[i]==b[j] 于是我们记录a序列中每个数的5个位置 扫一下b[i] 对于每个b[i]找到b[i]在a中的5个位置 这5个位置的每个f[pos]值都可以被b[i]更新 于是找到f[1]到
BZOJ 3365 Distance Statistics 树的点分治
题目大意:同POJ1741 链接:http://blog.csdn.net/popoqqq/article/details/39959803 和POJ1741一样的题,土豪题,POJ有道一样的题,做完1741可以水水 我会告诉你我直接改了下上题的代码么0.0 数据范围4W 距离最大1000 不会爆INT 放心写吧 #include<cstdio> #include<cstring> #includ
BZOJ 3211 花神游历各国 树状数组+并查集
题目大意:给定一个序列,提供下列操作: 1.将[l.r]区间内每个数a[i]变为sqrt(a[i]) 2.查询[l,r]区间的和 根号是不支持区间修改的,于是我们选择单点修改区间查询的树状数组,但是这样是O(n^2)的,怎么办? 我们发现一个数x最多开loglogx次根号就会变为1 也就是一个int范围内的数只要开6次根号就会变为1 于是修改的总时间复杂度为O(nloglogn) 但是单次修改怎么
BZOJ 2435 NOI2011 道路修建 BFS/DFS
题目大意:给定一棵树(直接给树,不是给图求生成树!),求每条边权值*两边点数之差的和 BFS水过即可 其实DFS也能过。。。系统栈可能有些不充裕,我们可以利用内嵌汇编手动开大系统栈 详见代码 这题读入优化可以优化掉4s左右 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define stack_
BZOJ 3037 创世纪 树形DP
题目大意:给定一张有向图,每个点有且仅有一条出边,要求若一个点x扔下去,至少存在一个保留的点y,y的出边指向x,求最多扔下去多少个点 首先原题的意思就是支配关系 我们反向考虑 求最少保留的点 要求一个点若扔出去 则必须存在一个保留的点指向它 于是这就是最小支配集 不过由于是有向图 所以一个点要么选择 要么被子节点支配 所以就只剩下2个状态了 设f[x]为以x为根的子树选择x的最小支配集 g[x]为
BZOJ 3689 异或之 Trie树+堆
题目大意:给定n个数,求这n个数两两异或的值中的前k小 首先我们对所有数字建立二进制Trie树,可以利用Trie树上的size域查询出一个数与其它数异或值的第k小 然后我们维护一个堆,将所有数与其它异或值的第2小加入堆(第一小是自己异或自己,不在题目要求范围内),当取出一个数异或值的第k小后,将第k+1小加入堆 一个异或值会被两个数分别取出一次,所以取出奇数次时输出,取2*k次即可 时间复杂度O(