爱悠闲 > 分类 >

BZOJ 第17页

BZOJ 3727 PA2014 Final Zadanie 树形DP
题目大意:给定一棵树,令一个点到所有点的距离与点权的乘积之和为b[i],求每个点的权值a[i] 首先如果给定a[i]我们可以很轻松的求出b[i] 但是反过来怎么搞?高斯消元?30W? 考虑已知a[i]求b[i]的情况 令这棵树的根为1 点i到根节点的距离为dis[i] 以i为根的子树的a值之和为size[i] 那么有递推式 b[1]=Σa[i]*dis[i] b[x]=b[fa[x]]-2*siz
BZOJ 1801 AHOI2009 中国象棋 递推
题目大意:给定一个棋盘,放置一些炮,要求任意两个炮不能互相攻击,求方案数对p取模的值 首先任意两个炮不互相攻击等价于一条线上最多只能有两个炮 直接状压DP的话是50分 考虑到每一列都是等价的 那么我们可以直接递推 令f[i][j][k]为前i行有j列有一个炮 k列有两个炮 那么讨论 这行不放炮 方案数为f[i-1][j][k] 在原先没有炮的列放炮 方案数为f[i-1][j-1][k]*(n-j-
BZOJ 1212 HNOI2004 L语言 AC自动机(Trie树)+动态规划
题目大意:给定一个单词表和m个字符串 问每个字符串的最长的前缀,满足这个前缀可以拆分成一些字符串 使这些字符串都在单词表中出现过 再也不敢看错数据范围了……一道明明用Trie树能解决的问题居然被我写了AC自动机…… 将单词表中的单词全都插入AC自动机 每个单词所在的节点记录这个单词的长度 然后对于每个字符串 用f[i]表示长度为i的前缀是否能拆分成单词表中的单词 跑AC自动机 对于每个匹配的节点
BZOJ 1834 ZJOI2010 network 网络扩容 Dinic+EK费用流
题目大意:给定一个n个点m条边的无向图,每条边有一个扩容费用c,代表每扩容1流量的花费,求最大流及将最大流扩大k的最小费用 第一问直接跑最大流 第二问将每条边的起始点向终点连接一条流量为正无穷、费用为c的边 然后将n向汇点连一条流量为ans+k 费用为0的边 跑最小费用最大流即可 #include<cstdio> #include<cstring> #include<iostream> #incl
BZOJ 1878 SDOI2009 HH的项链 树状数组/莫队算法
题目大意:给定一个序列,求一个区间内有多少个不同的数 正解是树状数组 将所有区间按照左端点排序 然后每次只统计左端点开始的每种颜色的第一个数就行了 用树状数组维护 我写的是莫队算法 莫队明显能搞 m√m明显慢了点但是还是能接受的一个复杂度 一开始离散化数组开小了各种秒RE…… 跪了 #include<cmath> #include<cstdio> #include<cstring> #includ
BZOJ 2007 NOI2010 海拔 平面图最小割
题目大意:YT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×n个区域。简单起见,可以将YT市看作一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路(简称道路),每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2),城市被划分为2×2个区域,包括3×3个交叉路口和12条双向道路。 小Z
BZOJ 1305 CQOI2009 dance跳舞 二分答案+最大流
题目大意:给定n个男生和n个女生,一些互相喜欢而一些不,举行几次舞会,每次舞会要配成n对,不能有相同的组合出现,每个人只能与不喜欢的人跳k次舞,求最多举行几次舞会 将一个人拆成两个点,点1向点2连一条流量为k的边,两个人若互相喜欢则点1之间连边,不喜欢则点2之间连边 对于每一个要验证的x值 将每个人的点1向源或汇连一条流量为x的边 然后二分答案跑最大流即可 #include<cstdio> #in
BZOJ 1324 Exca王者之剑 最小割
题目大意:给定一个n*m的矩阵,每个格子有宝石,人任选位置出发,取走当前位置的宝石之后四周的宝石消失,然后可以走两步,重复上述过程 容易发现一个格子取了那么四周的格子都不能取 于是方格取数问题 黑白染色 黑色点连源 白色点连汇 流量为格子的权值 黑白之间连边 流量为正无穷 用总和减去最大流就是答案 以前写的EK 跑了4000+ms我也是醉了 #include<stdio.h> #include<s
BZOJ 1975 SDOI2010 魔法猪学院 A*k短路
题目大意:给定一个值E 求起点到终点的最多条路径 使长度之和不超过E k短路的A*算法……每个点有一个估价函数=g[x]+h[x] 其中g[x]是从源点出发已经走了的长度 h[x]是从这个点到汇点的最短路 首先先在反图上跑一遍SPFA求出每个点的h[x],然后将源点的g[x]+h[x]加入堆 每次取出堆顶时将堆顶的g[x]向所连接的边扩展 第k次取出汇点即是答案 其中有一个剪枝就是当第k+1次取出
BZOJ 2743 HEOI2012 采花 树状数组
题目大意:给定一个序列,多次询问区间内出现两次以上的数的数量 n<=100W 莫队不用想了 考虑对于每个区间的左端点 对这个区间有贡献的数是从这个端点开始所有第二次出现的数 于是我们将区间按照左端点排序  然后从左向右扫 令next[i]为i位置上的数下一次出现的位置 初始将所有第二次出现的数加入树状数组 然后每删除一个点i 将next[i]从树状数组中删除 然后将next[next[i]]加入树