爱悠闲 > 分类 >

BZOJ 第24页

BZOJ 1297 SCOI2009 迷路 矩阵乘法
题目大意:给定一个邻接矩阵,求1~n的边权恰好为T的路径条数 考虑当所有边权都是1的时候 那么显然邻接矩阵自乘T次之后a[1][n]就是答案 因为当边权为1的时候a[i][j]可以表示从第i个点转移到第j个点的方案数 显然这个符合矩乘的定义 现在边权最大为9 那么将一个点拆成9个 第i个点拆成的第j+1个点向第j个点连一条边权为1的边 那么i->j有一条边权为k的边等价于i向j拆成的第k个点连边
BZOJ 3531 SDOI2014 旅行 树链剖分
题目大意:给定一棵树,每个点有一个权值和一个颜色,多次改变一些点的权值和颜色,多次求一条路径上与起点和终点颜色相同的点的权值和以及权值最大值 每种颜色开一个线段树 动态开节点 每个点只建一条链 这样空间复杂度是O(nlogn)的 然后就正常树链剖分就行了 #include <queue> #include <cstdio> #include <cstring> #include <iostream
BZOJ 2321 BeiJing2011集训 星器
题目大意:给定一个矩阵,定义一个操作: 选择两个同一行或同一列不相邻的点,将这两个点上各一个星向中间移动一位,产生魔力为两点间距离-1,求始态到终态的产生魔力 定义一个星的势能为这个点到原点的欧几里得距离的平方 即一个在(i,j)位置上的星的势能为i*i+j*j 假如一次操作之前两个星的位置为(i,j)和(i,k),其中j+2<=k 那么操作之前两个星的势能和为i*i+j*j+i*i+k*k 操作
BZOJ 2326 HNOI2011 数学作业 矩阵乘法
题目大意:求1234567891011121314...n mod m 的值 设F(n)=1234567891011121314...n 那么显然有F(n)=F(n-1)*(floor(lgn)+1)+n 于是我们可以矩乘 将数字按照floor(lgn)+1分类 构造状态矩阵F(n) n+1 1 初值为0 1 1 1~9的转移矩阵为 10 0 0 1 1 0 0 1 1 10~99的转移矩阵为 1
BZOJ 1433 ZJOI2009 假期的宿舍 最大流
题目大意:给定一些人,有些人是在校学生,有些去学校探访,在校学生有些回家,一个人只能睡认识的人的床,求能不能睡下 二分图的模型,左侧是所有需要睡觉的人,右侧是所有能用的床铺,二分图最大匹配即可 嫌建图麻烦可以考虑最大流 一个点拆成两个 如果这个人需要睡床,从原点出发向这个人的第一个点连边 如果这个人是在校学生,从这个人的第二个点向汇点连边 如果i==j或者i和j认识,从i的第一个点出发向j的第二个
BZOJ 2440 中山市选2011 完全平方数 二分答案+容斥原理+莫比乌斯反演
题目大意:求第k个无平方因子数是多少(无视原题干,1也是完全平方数那岂不是一个数也送不出去了? 无平方因子数(square-free number),即质因数分解之后所有质因数的次数都为1的数 首先二分答案 问题转化为求x以内有多少个无平方因子数 根据容斥原理可知 对于√x以内的所有质数 x以内的无平方因子数=无需是任何质数的倍数的数的数量(即x)-是至少一个质数平方倍数的数的数量+是至少两个质数
BZOJ 3529 SDOI2014 数表 莫比乌斯反演+树状数组
题目大意:令F(i)为i的约数和,多次询问对于1<=x<=n,1<=y<=m,F(gcd(x,y))<=a的所有数对(x,y),求ΣF(gcd(x,y))%(2^31) n,m<=10^5,a<=10^9 首先如果不考虑a的限制 令g(i)为1<=x<=n,1<=y<=m,gcd(x,y)=i的数的个数 那么显然有 利用线性筛处理出F(i) 那么答案显然是 治好了我多年的公式恐惧症。。。 现在我们
BZOJ 2154 Crash的数字表格 莫比乌斯反演
题目大意:求Σ[1<=i<=n]Σ[1<=j<=m]LCM(i,j) mod 20101009 题解见 http://www.cnblogs.com/jianglangcaijin/archive/2013/11/27/3446169.html 我到底写错什么了这么慢。。。。 #include <cstdio> #include <cstring> #include <iostream> #inc
BZOJ 2693 jzptab 莫比乌斯反演
题目大意:同2154 多组数据 后面那坨东西 由于积性函数的约数和仍是积性函数 因此只需要线性筛一下就行 i%prime[j]==0那部分由于多出来的因数都不是无平方因子数因此μ值都为0 增加的只有原先的D/i #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100010
BZOJ 3809 Gty的二逼妹子序列 莫队算法+分块
题目大意:给定一个序列,多次询问[l,r]区间内[a,b]范围内的数有多少 内存28MB,树套树可以歇菜了 首先普通的莫队+树状数组应该都能想到 这样做每次增加/删除一个点是O(logn)的 查询也是O(logn) 时间复杂度O(m√nlogn) 过(bu)不(hao)去(ka) 考虑将树状数组 改成分块 这样虽然查询变成了O(√n) 但是修改变成了O(1)的 这样就把时间复杂度降到了O(m√n)