爱悠闲 > 分类 >

BZOJ 第4页

BZOJ 1055 HAOI2008 玩具取名 动态规划
题目大意:给定一个由‘W','I','N','G'构成的字符串,给定一些规则,这些规则可以将两个字符合成为一个,例如"II"可以合成为'W',"WW"可以合成为'I'或者'N' 求这个字符串可以最终合成为哪几种字符 看到这题我想到了广搜。。。其实没必要,动归完全可以解决 令f[i][j][k]为从i开始的j个字符是否可以合成为字符[k] 然后j从外层循环,剩下的全部预处理,怎么暴力怎么转移,我写了
BZOJ 1089 SCOI2003 严格n元树 动态规划+高精度
题目大意:定义一棵深度为d的严格n元树为根的深度为0,最深的节点深度为d,且每个非叶节点都有恰好n个子节点的树 给定n和d,求深度为d的严格n元树一共有多少种 此题的递推部分并不难 首先我们设深度为i的严格n元树一共有f[i]种 令S[i]为f[i]的前缀和 我们不难发现一棵深度为i以下的严格n元树由两部分组成:一个根节点,n棵子树,其中每棵子树的深度不超过i-1 每棵子树有S[i-1]种 一共n
BZOJ 2115 Wc2011 Xor DFS+高斯消元
题目大意:给定一个无向图,每条边上有边权,求一条1到n的路径,使路径上权值异或和最大 首先一条路径的异或和可以化为一条1到n的简单路径和一些简单环的异或和 我们首先DFS求出任意一条1到n的简单路径以及图中所有最简单的简单环(环上不存在两个点可以通过环外边直连) 然后在一些数中选出一个子集,使它们与一个给定的数的异或和最大,这就是高斯消元的问题了 利用高斯消元使每一位只存在于最多一个数上 然后贪心
BZOJ 2844 albus就是要第一个出场 高斯消元
题目大意:给定一个n个数的集合S和一个数x,求x在S的2^n个子集从大到小的异或和序列中最早出现的位置 有学长真好不用自己打题目大意了233 首先我们求出线性基 我们会得到一些从大到小排列的数和一堆0 记录0的个数 不考虑0,看前面的数,由于线性基的性质,我们直接贪心从大到小枚举 若当前异或和异或这个值小于Q则取这个数 (注意^不要写成+或者| 本蒟蒻已经因为这个WA了两道题了 然后我们通过每个数
BZOJ 2142 礼物 组合数学+数论
题目大意:给定n个物品,分给m个人,每个人拿到wi个礼物,问方案数mod P P不一定为质数 首先我们把剩下的礼物也分给一个人 答案明显不变 w[++m]=n-w1-w2-...-wm 然后就会很方便地得到公式: ans=C(n,w1)*C(n-w1,w2)*C(n-w1-w2,w3)*...*C(n-w1-w2-...-w_(m-1),wm) mod P        =n!/w1!/w2!/.
BZOJ 1041 HAOI2008 圆上的整点 数论
题目大意:给定一个半径为为r的圆x^2+y^2=r^2,求圆上多少个点的坐标为整数 卡了很久的一道题。。。我之前用了两个公式,理论上可以O(√n)出解,可惜这两个公式并不能涵盖所有勾股数。。。 于是去找了下题解,发现这样一种方法:(原帖地址: http://www.cppblog.com/zxb/archive/2010/10/18/130330.html ) x^2+y^2=r^2 化简为 y^
BZOJ 2005 NOI2010 能量采集 数论
题目大意:给定n和m,求Σ(1<=i<=n)Σ(1<=j<=m)GCD(i,j)*2-1 i和j的限制不同,传统的线性筛法失效了,这里我们考虑容斥原理 令f[x]为GCD(i,j)=x的数对(i,j)的个数,这个不是很好求 我们令g[x]为存在公因数=x的数对(i,j)的个数(注意不是最大公因数!),显然有g[x]=(n/x)*(m/x) 但是这些数对中有一些的最大公因数为2d,3d,4d,我们要
BZOJ 3732 Network Link-Cut-Tree (我是认真的!!
题目大意:给定一个n个点m条边的无向连通图,k次询问两点之间所有路径中最长边的最小值 LCT的裸题!首先维护一个动态的最小生成树,然后每次加入边时删除两点间路径上权值最大的边!最后询问时直接求x到y链上的最大权值即可!水爆了!! 。。。好吧开玩笑的 真正的题解见http://blog.csdn.net/popoqqq/article/details/39755703 我只是闲得无聊水一发LCT罢了
BZOJ 1355 Baltic2009 Radio Transmission KMP算法
题目大意:给定一个字符串,求最小循环节(可以不整除) 样例的Hint是错的无视掉就好 循环节应该是cab 这题利用了KMP中next数组的性质,也就是n-next[n]表示循环节 POJ的题都要求整除,这题不用整除,直接输出n-next[n]即可 注意next数组不要开成char~ #include<cstdio> #include<cstring> #include<iostream> #inc
BZOJ 1411 ZJOI2009 硬币游戏 递推
题目大意:给定一圈硬币,T次操作,每次操作在每个硬币中间各放一枚硬币,硬币的正反面由它旁边两个决定,两边相同则为正面,两边不相同则为反面,然后将之前的硬币全部撤掉,问T次操作后的硬币序列 T<=2^60,不是260!!!不然这题就成模拟了!!! 首先原题的题目描述压根就是错的,无视就好 然后下面T的数据范围简直坑爹。。。一开始还以为这是模拟题,写了半天发现各种WA,后来看了数据才发现尼玛。。。 最