爱悠闲 > 分类 >

BZOJ 第15页

BZOJ 3175 Tjoi2013 攻击装置 二分图最大匹配
题目大意:给定一个n*n的网格图,要在0的位置上放置一些攻击装置,其中一个攻击装置的攻击范围是周围8个“日”字形区域,要求不能互相攻击,求最多放置多少个攻击装置 每两个能互相攻击且能放置的点连一条双向边,然后跑二分图最大点独立集即可 4W个点n^2居然没TLE 是数据太弱还是匈牙利算法太强了? #include<cstdio> #include<cstring> #include<iostream
BZOJ 1984 月下“毛景树” 树链剖分
题目大意:给定一棵树,边上有边权,提供一堆乱七八糟的操作(0.0),多次询问两点之间边权最大值 将每条边的边权放在边下面的点上,然后按照点权处理就行了。注意两个点的LCA的点权不能被算进路径中去 尼玛UBUNTU奇葩系统……我不写返回值居然直接把re给我返回回去了 然后咋拍都过…… 交上去就WA…… 我跪了 再也不敢不写-Wall了…… #include<cstdio> #include<cstr
BZOJ 1415 NOI2005 聪聪和可可 期望DP+记忆化搜索 BZOJ200题达成&&NOI2005全AC达成
题目大意:给定一个无向图,聪聪在起点,可可在终点,每个时刻聪聪会沿最短路走向可可两步(如果有多条最短路走编号最小的点),然后可可会等概率向周围走或不动,求平均多少个时刻后聪聪和可可相遇 今天早上起床发现194了然后就各种刷……当我发现199的时候我决定把第200题交给05年NOI仅剩的一道题……结果尼玛调了能有一个小时……我居然没看到编号最小这个限制0.0 首先我们知道,由于聪聪走两步而可可走一步
BZOJ 1567 JSOI2008 Blue Mary的战役地图 Hash+二分
题目大意:给定两个矩阵,求最大公共子正方形边长 首先二分答案 然后Check的时候先把A矩阵的所有边长为x的子正方形存在哈希表里 然后枚举B矩阵的每个子正方形查找 注意二维哈希的时候横竖用的两个BASE不能一样 否则当两个矩阵关于对角线对称的时候会判断为相等 尼玛我的哈希表居然比map慢……不活了 #include<map> #include<cstdio> #include<cstring> #
BZOJ 1414 ZJOI2009 对称的正方形 Hash+二分
题目大意:求正方形回文子矩阵数量(即左右对称、上下对称的正方形子矩阵) 正解是Manacher……但是Hash+二分是能卡过去的0.0 我太丧病了0.0 首先为了避免边长奇偶性带来的WT要把矩阵扩大二倍 然后样例就变成了这样: 00000000000 04020404040 00000000000 03010404030 00000000000 03050303030 00000000000 03
BZOJ 1031 JSOI2007 字符加密Cipher 后缀数组
题目大意:给定一个字符串,求将这个字符串首尾相接后以每个字符开头的字符串排序后最后一列的字符串 传说中的后缀数组0.0 昨晚看了一晚上DC3没看懂,于是写了倍增0.0 罗先生的25行代码实在是抽象QAQ 蒟蒻表示理解不能QAQ 于是自己写了个比较清晰的版本QAQ 首先这题是环 于是我们把字符串的前n-1个字符添加到这个字符串的尾端 然后就是后缀数组的事情了 求完这个之后按照后缀数组的顺序枚举每个开
BZOJ 1861 ZJOI2006 Book 书架 Splay
题目大意:……自己看懒得打了 很裸的Splay 首先开一个指针数组记录每个值代表的节点 然后就能找到某本书在序列中的什么位置了 总感觉这题可以不用Splay的说……一定是我的错觉 样例中居然尼玛有中文字符……坑爆了 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 8080
BZOJ 3172 Tjoi2013 单词 后缀数组
题目大意:给定一个n个单词的文章,求每个单词在文章中的出现次数 文章长度<=10^6(不是单词长度<=10^6,不然读入直接超时) 首先将所有单词用空格连接成一个字符串,记录每个单词的起始位置和长度 然后求后缀数组,对于每个单词后缀数组中一定有连续一段后缀以这个单词开头,我们通过一开始记录的起始位置找到这个单词的后缀,然后左右端点二分答案,满足左右端点之间的后缀与原单词的LCP都当与等于原单词长度
BZOJ 1692 队列变换 贪心+后缀数组
题目大意:给定一个字符串,每次取头或者尾放在新字符串里,求字典序最小的新字符串 首先如果两边的字符不一样 那么肯定要选择小的放在新字符串里 但如果两边一样 比如CCBACC 肯定从尾取比较优 原因是CCA比CCB要小 于是我们把原串反写接在后面变成CCBACC@CCABCC 然后跑一遍后缀数组 每次就能O(1)比较两个子串的大小了 时间复杂度O(nlogn) #include<cstdio> #i
BZOJ 2351 BeiJing2011 Matrix Hash
题目大意:给定一个m*n的01矩阵,问Q个a*b的子矩阵中有多少在原矩阵中出现过 首先将原矩阵哈希 将所有a*b的子矩阵的哈希值插入哈希表 然后对于每个矩阵哈希之后去哈希表中查找即可 注意不要因为是01矩阵就把进制数弄得太小……一开始用了3和5,结果狂WA不止,无奈改成了999911657和999911659才过…… 此外就是我的哈希表终于比map快了……好鸡冻…… #include<cstdio